帮写COMP4670/8600: Statistical Machine Learning Semester 1, 2024 Assignment 1代做Python语言

日期：2024-03-21 04:25

COMP4670/8600: Statistical Machine Learning

Semester 1, 2024

Assignment 1

Weight: 25%

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.

Section 1: Bayes’ Rule and Optimisation                                       (50 Total Points)

Let’s begin with an all too familiar deinition of Bayes’ Rule. For any events A, B, we have that

 =  ∝ Pr(B | A) · Pr(A).                                     (1.1)

The  “∝” symbol denotes  “proportionate” where an increase on the left-hand side (LHS) will cause an increase on the right-hand side (RHS) (up to some multiplicative constant). In our case, ∝ is used as a shorthand to ignore Pr(B) and “absorb” the normalisation constant for the posterior. One should note that working with Bayes’ Rule, the normalisation Pr(B) can be exactly calculated as a function of the likelihood Pr(B | A) and prior Pr(A) terms (via the sum and product rules of probabilities). Hence, we aren’t loosing any information about the distribution by hiding Pr(B).

Eq. (1.1) considers Bayes’ Rule in term of general events. For machine learning, we often consider the rule in the context of training dataset D and model parameters ϑ ∈ Θ. In this case, we write Bayes’ Rule

w.r.t. a posterior distribution q(ϑ | D), a likelihood distribution p(D | ϑ), and a prior distribution π(ϑ),

q(ϑ | D) ∝ p(D | ϑ) · π(ϑ).                                                        (1.2)

To utilise Bayes’ Rule in Eq. (1.2), we have to deine the likelihood and prior distributions. For instance, in Bayesian linear regression we assign a Gaussian likelihood and prior on model parameters. For now, we won’t explicitly deine a speciic functional form for the likelihood and prior distributions – we leave them abstract.

For your irst question, let’s consider the simple task of rewriting Bayes’ Rule.

Question 1.1: A simple rewrite of Bayes’ Rule

Show that the posterior qB(*)

where Z = Eπ  [exp ( — ( — log p(D | ϑ)))].

Note: Yes! The double negative is intentional!

Let’s discuss a bit about the above’s seemingly inconsequential rewrite.

The double negative we explicitly write is to emphasise that the negative log-likelihood – which one minimises when itting a maximum likelihood estimation problem – plays a part in Bayes’ Rule.

Eq. (1.3)’s form actually resembles a lot of diferent ‘objects’ in many diferent ields. For instance, a statistically inclined person might interpret this as the ‘exponential tilt’ of a random variable distributed by the prior π(ϑ); a statistical physicist may interpret this as a Boltzmann or Gibbs distribution with a particular energy function; and so on ...

There is surprisingly deep connections we can arrive at by studying functions which are of the form of q(x) ∝ π(x) · exp( —V (x)), for some function V.

We  are  going to take  a  slight  departure  here  from  the  discussion  of Bayes’  Rule  and  look  at  some optimisation. Although, we will quickly return to Bayes’ Rule (foreshadowing).

Recall the following deinition of KL-divergence

 

where p,q are probability distributions over a set of parameters Θ, we write p, q ∈ P(Θ). (There is a technical requirement that the KL-divergence is only valid for p(ϑ) = 0  =⇒  q(ϑ) = 0).

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(Θ)

Show that the following is an optimal solution: qM(*)LE (ϑ) = {0(1)

if ϑ = ϑMLE(*) otherwise

.

(1.7)

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.

Section 2: Generalisations of Bayes’ Rule                                      (25 Total Points) 

In the following, we will look at two diferent variants of Bayes’ Rule. The irst of these variants can help remedy the computational cost of Bayes’ Rule (inference). The second generalises Bayes’ Rule to a non-log-likelihood setting.

One variant of Bayes’ Rule is  Variational Inference. In this variant, the idea is to replace the set of all valid probability distributions in Eq. (1.9) with a subset Q    P(Θ). As such, we deine this new optimal distribution

qV(*)I  = arg min {Eq  [ — log p(D | #)] + KL(qkπ)} :                                       (2.1)

q2Q

The main idea of Eq. (2.1) is to cheapen the cost by reducing what distribution we care about.

One may wonder how the solution to Eq. (2.1) relates to the original posterior obtained by Bayes’ Rule. The following gives a concrete example to this.

Question 2.1: Variational Inference as information projection                        (10 Points)

Show that the variational inference posterior qV(*)I (#) is equivalent to the KL-information projection,

qV(*)I  = arg min {KL(qkqB(*))} :                                                  (2.2)

q2Q

Another generalisation we can consider is switching the negative log-likelihood to a generic loss function (one may want to think about Question 1.5). This is particularly useful as a variety of diferent loss functions L( · ; D): Θ  → R  are  utilised  in machine learning. This gives us the following optimisation problem.

qL(*) = arg min {Eq [L(#; D)] + λ · KL(qkπ)} :                                         (2.3)

q2P(Θ)

Interestingly, the resulting “posterior” which we obtain is very similar to Question 1.1.

Question 2.2: Loss function based Bayes’ Rule                                                    (15 Points)

Given that,

˜(q)(#) ∝ π(#) · exp（ —  :                                                 (2.4)

Prove that for any q ∈ P(Θ)

 · Eq [L(#; D)] + KL(qkπ) — KL(qk˜(q)) = — logEπ   lexp（ —  :                (2.5)

With this, argue that qL(*)  = ˜(q).

Hint: For the second part, consider a proof by contradiction.

Of course, despite replacing the negative log-likelihood with a loss function, there is still an underlying “likelihood” distribution being used. One may want to think about the connection between the squared loss and Gaussian distributions, etc.