Release Date.  1st March 2024.

Due Date.  28th March 2024 at 23:59 AEDT.

Maximum credit.  100 Marks.

Bayes’ Rule, Generalisations, and Online Learning

Many diferent types of machine learning methods fall under the label of “Bayesian model”. Indeed, you might have noticed that in the irst half of the course (and much of the Bishop textbook), we introduce a non-Bayesian method which is then followed up by its Bayesian counterpart, e.g., from logistic regression to Bayesian logistic regression; or kernel regression to Gaussian process regression. Bayesian models are often justiied because of their ability to quantify uncertainties (you have a probability over outputs) and their abilities to incorporate “beliefs” into models (priors and likelihoods). Despite this there is a cost we pay in computability.

In the following question, we’ll be exploring the underlying mechanism which makes “Bayesian models” Bayesian – Bayes’ Rule. We’ll be exploring diferent perspectives of this deceptively simple equation. We will then explore diferent ways to alter Bayes’ Rule to decrease the computational cost and diferent generalisations of the rule. Finally, will look at an online learning showcase of how the previously explored ideas can be used to design an algorithm.

For submission Add an additional sol.pdf ile into the assignment folder, zip the entire folder as given, and then submit the zip ile on Wattle. Ensure that the coding solutions are in the designated iles (as speciied). Do not include additional iles such as your locally installed packages.

Installation To setup environment for coding, check  ./code/README.

Collaboration You are free to discuss the material in the assignment with your classmates. However, every proof and code submitted must be written by yourself without assistance. You should be able to explain your answers if requested.

Late submission policy Assignment submissions that are late from 1 minute to 24 hours attract a 5% penalty (of possible marks available). Submissions late by more than 24 hours will not be accepted.

Extension requests will be processed via the Extension online form available on the CECC website. Regrade requests will be processed via a Microsoft Form. This will be released in due course.

Other notes:

. When writing proofs, use the equation numbers when referring the equations in the assignment, i.e., “Through Equation (3.1) we can show ...” .

. You are not required to complete the assignment linearly, you may want to solve which-ever ques- tions you can regardless of order of appearance.

. If you have trouble with proving a statement, try reducing dimensionality of the problem irst.

.  Unless stated otherwise, code is only graded on correctness of functions implemented, not on per- formance or code quality. Our main requirement on performance/code quality is that we can run your code in reasonable time when marking it.

Assumption: Unless otherwise speciied, assume that Θ is discrete, i.e., |Θ| = d for some inite d > 0. Hence, all integrals can be computed over a sum：#2Θ. Furthermore, any distribution q ∈ P(Θ) can be written as a vector q ∈ [0, 1]d        Rd , where each subscript q#   corresponds to a single ϑ ∈ Θ (it is useful to think of Θ as the set {1, 2, . . . , d}).

For example, let Θ = {H, T} – heads and tails. Then qH  = q(H) ∈ [0, 1] is the probability of taking

heads. If we identify H = 1 and T = 2, then we have exactly q ∈ [0, 1]2  with appropriate indexing. This isn’t strictly needed, but it will simplify the problem for the purpose of this assignment.

We are going to study a modiied version of the maximum likelihood estimation (MLE). Recall that the MLE problem for p(D | ϑ) is the following optimisation problem:

ϑMLE(*)  ∈ arg max {p(D | ϑ)} .                                                      (1.5)

#2Θ

Of course, this typically only gives us a point estimate, we don’t get a distribution over ϑ. We can actually try and force MLE to give us a distribution by phrasing the problem slightly diferently, but it is only a “distribution” out of obligation.

Question 1.2: The distribution of MLE

Consider the following distribution optimisation problem:

qM(*)LE  ∈ arg min {Eq [__ log p(D | ϑ)]} .

q2P(Θ)

As a result of this  “collapse” in probability, we seek other optimisation problems to remedy MLE in

Eq. (1.6). We note that even in the case where there are multiple minima ϑMLE(*), a discrete set of collapsed

nodes in probability is still undesirable. For this assignment, let us consider the following objective function adjustment using KL-divergence and a positive λ > 0:

Eq [__ log p(D | ϑ)] + λ · KL(qkπ).                                                  (1.8)

Question 1.3: Convexity of objective                                                                         (10 Points)

Prove that the objective function in Eq. (1.8) is convex as a function of q .

Hint: For a recap on convexity, see “Mathematics for Machine Learning” Chapter 7.3 or Bishop’s “Pattern Recognition and Machine Learning” Chapter 1.6.1.

Now that we know that Eq. (1.8) can be minimised nicely, let do exactly that. More speciically let’s make the following identity.

Question 1.4: Bayes’ Rule as optimisation                                                           (15 Points)

Using KKT conditions, ind the optimal distribution in Eq. (1.8). Furthermore, show that qB(*)(#)

is the solution to the minimisation problem,

qB(*) = arg min fEq  [ — log p(D j #)] + λ · KL(qIπ)g ;                                (1.9)

q2P(Θ)

when λ = 1.

Hint:  For a refresher on KKT conditions, check Bishop’s  “Pattern  Recognition  and  Machine Learning” Appendix E. One may also want a refresher on Lagrange multipliers and optimisation, check “Mathematics for Machine Learning” Chapter 7.2a .

a See: https://mml-book.github.io

The equivalence in Eq. (1.9) gives us an interesting perspective of Bayes’ Rule.

Question 1.5: A regularised perspective of Bayes’ Rule                                      (4 Points) Given Eq. (1.9), write in a few sentences about what Bayes’ Rule does in terms of a  “regularised minimisation” problem (in an analogous way linear regression can be regularised by an L2  penalty on weights). What makes a good distribution according to Eq. (1.9)?

Further consider the general solution of Eq. (1.8) and write a few sentences about the behaviour of the solution as λ increases and decreases.

Of course, as computer scientists, we should also consider the costs of these diferent interpretations. Bayes’ Rule has some fundamental bottlenecks when trying to numerical compute it  (even when we estimate certain quantities).

Question 1.6: Cost of being Bayesian

Identity the cost of Bayes’ Rule when Θ is potentially high dimensional. Write a few sentences describing how Bayes’ Rule can be expensive:

1.  From the perspective of Eq. (1.3), argue what terms are expensive to calculate.

2.  From the perspective of Eq. (1.9), argue what might make the optimisation problem expen- sive to solve.