Home / MLT / Week 4

Week 4 · MLE, Bayes, Gaussian mixtures and EM

Official syllabus line: Unsupervised Learning - Estimation - Recap of MLE + Bayesian estimation, Gaussian Mixture Model - EM algorithm

About 110 minQuiz 1 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 10 (probability), MLF week 12 (MLE and the idea of EM), MLT week 3 (k-means). This is the longest week of the first quiz: take it in two sittings.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

You find a coin and flip it 10 times: 7 heads. What is the chance of heads? A quick answer is '70%'. But what if it looked like a perfectly ordinary coin? You would probably say 'it is surely close to 50%'. The data and your prior feeling should both count.
Bayesian estimation is the maths of mixing these two: start with a belief, update it with data, and end with a better belief. With lots of data, evidence wins; with little data, the prior still has a voice. Another idea: GMM learns hidden groups by alternately guessing groups and refitting curves.
Imagine you start with a mild belief in a fair coin. Then you see 7 heads and 3 tails in ten flips. Your belief updates! Instead of just 70% heads, your new estimate might be closer to 64% or 67%. Your initial feeling still has a small say.
For exams, remember the Beta posterior update formula: add heads to alpha, tails to beta! Also, know that EM climbs to a local maximum, not always the best one. And always check if the question asks for the mean or the most likely value. You got this!

The one-minute story

Think of it like this

Part 1, one coin. You find a coin and flip it 10 times: 7 heads. What is the chance of heads? A quick answer is "70%". But what if it looked like a perfectly ordinary coin? You would probably say "it is surely close to 50%, 7 out of 10 is just luck". The data and your prior feeling should both count. Bayesian estimation is the maths of mixing the two: start with a belief, update it with data, and end with a better belief. With lots of data the evidence wins; with little data the prior still has a voice.

Part 2, mixed groups. Measure the heights of 1000 people at a school gathering, but forget to write down who is a child and who is an adult. The heights form two overlapping bumps. A Gaussian mixture model (GMM) says: "each person comes from one of two hidden groups, and each group has its own bell curve". EM (expectation-maximisation) learns the two bell curves without ever being told the groups, by alternately guessing the groups and refitting the curves.

By the end of this week you can:

compute MLE for common distributions and explain its bias;
do Bayesian estimation with a Beta prior and a Bernoulli likelihood, and tell MLE, MAP and posterior mean apart;
write the GMM model and compute its log-likelihood;
carry out the E-step and M-step by hand and count GMM parameters.

Words you need

Prior $p(\theta)$ - belief about the parameter before seeing data.
Likelihood $p(\text{data}\mid\theta)$ - how well each parameter value explains the data.
Posterior $p(\theta\mid\text{data})$ - updated belief after seeing data.
Conjugate prior - a prior chosen so that the posterior has the same family. Beta prior with Bernoulli data gives a Beta posterior.
MAP - the mode (peak) of the posterior.
Mixture component - one of the hidden groups, with weight $\pi_k$ , mean $\boldsymbol\mu_k$ and covariance $\Sigma_k$ .
Responsibility $r_{ik}$ - the probability that point $i$ came from component $k$ .

Idea 1: Recap of MLE

For data $x_1,\dots,x_n$ and a model $p(x\mid\theta)$ , MLE picks the $\theta$ that makes the data most probable: write the log-likelihood $\ell(\theta)=\sum\ln p(x_i\mid\theta)$ , differentiate, set to zero.

Model	MLE
Bernoulli( $p$ ) with $h$ heads in $n$ tosses	$\hat p=h/n$
Gaussian mean	$\hat\mu=\bar x$
Gaussian variance	$\hat\sigma^2=\frac1n\sum(x_i-\bar x)^2$ (biased low)
Exponential	$\hat\lambda=1/\bar x$
Poisson	$\hat\lambda=\bar x$
Uniform $(0,\theta)$	$\hat\theta=\max x_i$

MLE is the pure "let the data speak" answer. With 3 tosses and 3 heads it says $\hat p=1$ : "this coin never shows tails", which is silly. That is where a prior helps.

Idea 2: Bayesian estimation

Treat the unknown parameter as a random variable with a distribution. Bayes' rule (MLF week 10) says

\underbrace{p(\theta\mid\text{data})}_{\text{posterior}}\;\propto\;\underbrace{p(\text{data}\mid\theta)}_{\text{likelihood}}\;\times\;\underbrace{p(\theta)}_{\text{prior}}

The Beta-Bernoulli model: the most-asked calculation of this quiz

The unknown is a coin's heads-probability $\theta\in[0,1]$ . A natural prior is the Beta distribution:

\theta\sim\text{Beta}(\alpha,\beta),\qquad p(\theta)\propto\theta^{\alpha-1}(1-\theta)^{\beta-1}

with mean $\dfrac\alpha{\alpha+\beta}$ . You see $h$ heads and $t$ tails ( $n=h+t$ ). The likelihood is $\theta^h(1-\theta)^t$ , so

p(\theta\mid\text{data})\propto\theta^{\alpha-1+h}(1-\theta)^{\beta-1+t}\quad\Longrightarrow\quad\boxed{\theta\mid\text{data}\sim\text{Beta}(\alpha+h,\;\beta+t)}

That is conjugacy: the posterior is the same kind of curve as the prior, with the counts simply added.

Think of it like this

Read $\alpha$ and $\beta$ as pretend flips you already saw: $\alpha$ pretend heads and $\beta$ pretend tails. Beta(2,2) means "I have a hunch from 2 heads and 2 tails". Then real data just adds real flips to the pile. After the update you have a pile of $\alpha+h$ heads and $\beta+t$ tails, and the Beta curve for that pile is your new belief.

For the posterior Beta $(A,B)$ with $A=\alpha+h$ and $B=\beta+t$ :

The idea

Summary	Formula
Posterior mean	$\dfrac{A}{A+B}=\dfrac{\alpha+h}{\alpha+\beta+n}$
MAP (posterior mode)	$\dfrac{A-1}{A+B-2}=\dfrac{\alpha+h-1}{\alpha+\beta+n-2}$ (when $A,B>1$ )
MLE (ignores the prior)	$\dfrac hn$
Posterior variance	$\dfrac{AB}{(A+B)^2(A+B+1)}$

Observations:

The posterior mean is a blend: $\frac{\alpha+h}{\alpha+\beta+n}$ lies between the prior mean and the MLE, and moves towards the MLE as $n$ grows.
A uniform prior is Beta $(1,1)$ : its posterior mean is $\frac{h+1}{n+2}$ , Laplace's rule of succession (never gives probability 0 or 1).
The probability that the next toss is heads equals the posterior mean.
As $n\to\infty$ the prior washes out: MAP, posterior mean and MLE all converge.

Solved example: 1. Beta posterior

Question. Prior Beta(2,2). You see 7 heads and 3 tails. Give the posterior, its mean, the MAP estimate and the MLE. What is the probability the next toss is heads?

Solution.

Posterior: Beta $(2+7,\,2+3)=$ Beta(9,5).
Posterior mean: $\frac9{14}\approx\mathbf{0.643}$ .
MAP (mode): $\frac{9-1}{9+5-2}=\frac8{12}\approx\mathbf{0.667}$ .
MLE: $\frac7{10}=\mathbf{0.70}$ .
The next toss is heads with probability the posterior mean, $\frac9{14}$ .

The prior (centred on $0.5$ ) has pulled the estimate from $0.70$ down towards $0.5$ : MLE $0.700>$ MAP $0.667>$ mean $0.643$ .

Watch out - real exam trap

Posterior mean and posterior mode (MAP) are different numbers: $\frac{\alpha+h}{\alpha+\beta+n}$ versus $\frac{\alpha+h-1}{\alpha+\beta+n-2}$ . Re-read whether the question asks for "expected value / mean" or "most likely value / MAP / mode".

Idea 3: Gaussian mixture models

A GMM says each data point is generated in two stages:

Pick a component $k\in\{1,\dots,K\}$ with probability $\pi_k$ (the mixing weights, $\sum\pi_k=1$ ).
Draw $\mathbf x$ from $\mathcal N(\boldsymbol\mu_k,\Sigma_k)$ .

The density of a point is the weighted sum

p(\mathbf x)=\sum_{k=1}^K\pi_k\,\mathcal N(\mathbf x\mid\boldsymbol\mu_k,\Sigma_k)

and for $n$ independent points the log-likelihood is

\ell=\sum_{i=1}^n\ln\Big(\sum_{k=1}^K\pi_k\mathcal N(\mathbf x_i\mid\boldsymbol\mu_k,\Sigma_k)\Big)

The log of a sum blocks a neat formula for the best parameters, so we use EM.

The EM algorithm for a GMM

The idea

E-step. For every point and every component, the responsibility

r_{ik}=\frac{\pi_k\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_k,\Sigma_k)}{\sum_{j=1}^K\pi_j\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j)}

(Each point's responsibilities add to 1 across components.)

M-step. With $n_k=\sum_ir_{ik}$ (the "effective number of points" in component $k$ ):

\pi_k=\frac{n_k}n,\qquad\boldsymbol\mu_k=\frac1{n_k}\sum_ir_{ik}\mathbf x_i,\qquad\Sigma_k=\frac1{n_k}\sum_ir_{ik}(\mathbf x_i-\boldsymbol\mu_k)(\mathbf x_i-\boldsymbol\mu_k)^T

These are exactly the ordinary MLE formulas for a Gaussian, but every point is weighted by its responsibility.

Properties worth knowing:

Each EM iteration never decreases the log-likelihood; the algorithm climbs to a local maximum (it can depend on the start, which is often set by k-means).
If one component collapses onto a single point, its variance $\to0$ and the likelihood $\to\infty$ : a singularity that must be avoided (add a small floor to the variance).
k-means is the hard version: shrink every $\Sigma_k$ to $\sigma^2I$ and let $\sigma^2\to0$ ; the responsibilities become 0 or 1 and EM becomes Lloyd's algorithm.

Solved example: 2. One full EM step in one dimension

Question. Data: $x=1,\,4,\,6$ . A 2-component GMM in 1-D with both standard deviations fixed at 1, equal weights $\pi=(0.5,0.5)$ , initial means $\mu_1=3$ and $\mu_2=5$ . Do one E-step and one M-step.

Solution. Use $\mathcal N(x\mid\mu,1)\propto e^{-(x-\mu)^2/2}$ . The common factor $\frac1{\sqrt{2\pi}}$ and the equal weights cancel in the ratio.

E-step.

$x$	$e^{-(x-3)^2/2}$	$e^{-(x-5)^2/2}$	$r_{i1}$	$r_{i2}$
1	$e^{-2}=0.1353$	$e^{-8}=0.0003$	$0.9975$	$0.0025$
4	$e^{-0.5}=0.6065$	$e^{-0.5}=0.6065$	$0.5$	$0.5$
6	$e^{-4.5}=0.0111$	$e^{-0.5}=0.6065$	$0.0180$	$0.9820$

(For example $r_{11}=\frac{0.1353}{0.1353+0.0003}=0.9975$ .) The point $x=4$ sits exactly between the two means, so it is a coin flip.

M-step. Effective counts: $n_1=0.9975+0.5+0.0180=1.5155$ and $n_2=1.4845$ .

\pi_1=\frac{1.5155}3=\mathbf{0.505},\quad\pi_2=\mathbf{0.495}

\mu_1=\frac{0.9975(1)+0.5(4)+0.0180(6)}{1.5155}=\frac{3.1055}{1.5155}=\mathbf{2.05},\qquad\mu_2=\frac{0.0025(1)+0.5(4)+0.9820(6)}{1.4845}=\mathbf{5.32}

The means moved from $(3,5)$ to $(2.05,5.32)$ : the left component moved towards its point $x=1$ , the right one towards $x=6$ . The log-likelihood improved from $-7.12$ to $-6.19$ , as EM promises.

Counting GMM parameters

For $K$ components in $d$ dimensions:

Covariance type	Parameters per component	Total
Full	$d$ (mean) $+\frac{d(d+1)}2$ (covariance)	$K\big(d+\frac{d(d+1)}2\big)+(K-1)$
Diagonal	$d+d$	$2Kd+(K-1)$
Spherical ( $\sigma_k^2I$ )	$d+1$	$K(d+1)+(K-1)$

The final $K-1$ counts the mixing weights (the last weight is forced by $\sum\pi_k=1$ ).

Solved example: 3. How many parameters?

Question. A GMM with $K=3$ components in $d=2$ dimensions. Count the parameters for full, diagonal and spherical covariances.

Solution. Full: $3(2+3)+2=\mathbf{17}$ . Diagonal: $2\cdot3\cdot2+2=\mathbf{14}$ . Spherical: $3(2+1)+2=\mathbf{11}$ .

Your turn

Your turn: 1. Beta update

Prior Beta(1,1) (uniform). You see 4 heads and 1 tail. Give the posterior, posterior mean, MAP and MLE.

Need a hint?

Add the counts to $(1,1)$ .

Show the full solution

Beta(5,2). Mean $=\frac57\approx0.714$ . MAP $=\frac{5-1}{5+2-2}=\frac45=0.8$ . MLE $=\frac45=0.8$ (with a uniform prior the MAP equals the MLE).

Your turn: 2. Strong prior, little data

Prior Beta(20,20) (a strong belief the coin is fair). You see 3 heads in 3 tosses. What is the posterior mean? What would MLE say?

Need a hint?

$\frac{\alpha+h}{\alpha+\beta+n}$ .

Show the full solution

Beta(23,20), mean $=\frac{23}{43}\approx0.535$ . The MLE says $1.0$ . The strong prior barely moves: three tosses are tiny evidence against forty pretend ones.

Your turn: 3. Responsibilities

A two-component model gives a point likelihoods $\pi_1\mathcal N_1=0.06$ and $\pi_2\mathcal N_2=0.02$ . Find $r_1$ , $r_2$ .

Need a hint?

Normalise.

Show the full solution

Total $=0.08$ . $r_1=0.75$ , $r_2=0.25$ .

Your turn: 4. M-step weights

Three points have responsibilities for component 1 of $0.9,\,0.5,\,0.1$ , and values $x=2,\,4,\,10$ . Compute $n_1$ , $\pi_1$ and $\mu_1$ .

Need a hint?

$\mu_1=\sum r_ix_i/\sum r_i$ .

Show the full solution

$n_1=1.5$ . $\pi_1=\frac{1.5}3=0.5$ . $\mu_1=\frac{0.9\cdot2+0.5\cdot4+0.1\cdot10}{1.5}=\frac{1.8+2+1}{1.5}=\frac{4.8}{1.5}=\mathbf{3.2}$ .

Your turn: 5. Which are true?

(a) EM increases the log-likelihood each step. (b) EM always finds the global maximum. (c) A point's responsibilities across components add to 1. (d) The mixing weights are $\pi_k=n_k/n$ .

Need a hint?

Review the concept box.

Show the full solution

(a) True. (b) False, only a local maximum. (c) True. (d) True.

Exam radar

MLT Quiz 1 is where this week lives. Concept summaries mention EM / expectation-maximisation in 46 of 60 papers, Gaussian mixture models in 52, MLE in 39, Bayes in 32, Bernoulli in 28, Beta distribution in 16, Beta posterior mean in 15, GMM likelihood in 12, E-step in 11, M-step in 11, posterior mean in 11, Bernoulli distribution in 16.

The standard questions: Beta posterior mean after some heads and tails; MLE vs MAP vs posterior mean; compute a responsibility from given likelihoods; a mixing weight or mean after the M-step; "is the log-likelihood non-decreasing under EM?"; GMM parameter count.

Watch out - real exam trap

Mean vs mode of the posterior; the mode has the $-1$ and $-2$ .
Prior pseudo-counts are $\alpha$ and $\beta$ (not $\alpha-1$ ) when you compute the posterior mean.
The Beta prior is for the heads-probability, so adding data adds heads to $\alpha$ and tails to $\beta$ .
Responsibilities are per point, summing over components, not over points.
EM gives a local maximum. It does not guarantee the best fit.
The Gaussian-variance MLE divides by $n$ .

Quick quiz

Prior Beta(3,2), then 2 heads and 1 tail. The posterior is...

Beta(2,1)
Beta(5,3)
Beta(6,2)
Beta(3,2)

Add heads to the first parameter and tails to the second: Beta(3+2, 2+1) = Beta(5,3).

For Beta(5,3), the posterior mean is...

Mean = A/(A+B) = 5/8. (The mode would be 4/6.)

In the E-step of EM for a GMM, we compute...

new means
responsibilities
the learning rate
the number of clusters

The E-step gives the probability that each point belongs to each component.

Select all TRUE statements. (select all that apply)

MLE ignores the prior.
With a uniform Beta(1,1) prior, MAP equals MLE for Bernoulli data.
The posterior mean is always equal to the MLE.
EM can decrease the log-likelihood in some iteration.

EM never decreases the log-likelihood, and the posterior mean differs from the MLE whenever the prior has any pull.

Recap

Remember this

MLE: $\hat p=h/n$ for Bernoulli. Bayes: posterior $\propto$ likelihood $\times$ prior.
Beta( $\alpha,\beta$ ) prior + $h$ heads, $t$ tails $\Rightarrow$ Beta( $\alpha+h,\beta+t$ ); mean $\frac{\alpha+h}{\alpha+\beta+n}$ , mode $\frac{\alpha+h-1}{\alpha+\beta+n-2}$ .
GMM: $p(\mathbf x)=\sum\pi_k\mathcal N(\mathbf x\mid\boldsymbol\mu_k,\Sigma_k)$ ; log-likelihood has a log of a sum.
EM: E-step responsibilities $r_{ik}$ ; M-step weighted MLE ( $\pi_k=n_k/n$ , weighted means and covariances). Likelihood never decreases; local maximum; k-means is the hard limit.

Formulas to keep

Beta posterior: $\text{Beta}(\alpha+h,\beta+t)$ ; mean $\frac{\alpha+h}{\alpha+\beta+n}$ ; MAP $\frac{\alpha+h-1}{\alpha+\beta+n-2}$ ; MLE $\frac hn$
Beta mean $\frac\alpha{\alpha+\beta}$ ; variance $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$
GMM: $p(\mathbf x)=\sum_k\pi_k\mathcal N(\mathbf x\mid\boldsymbol\mu_k,\Sigma_k)$
$r_{ik}=\frac{\pi_k\mathcal N_k(\mathbf x_i)}{\sum_j\pi_j\mathcal N_j(\mathbf x_i)}$ ; $n_k=\sum_ir_{ik}$ ; $\pi_k=\frac{n_k}n$ ; $\boldsymbol\mu_k=\frac{\sum r_{ik}\mathbf x_i}{n_k}$ ; $\Sigma_k=\frac{\sum r_{ik}(\mathbf x_i-\boldsymbol\mu_k)(\cdot)^T}{n_k}$
Parameters: full $K(d+\frac{d(d+1)}2)+K-1$ ; diagonal $2Kd+K-1$ ; spherical $K(d+1)+K-1$

Connected weeks (learn them together)

MLF week 2 - Slopes, change and the steepest way up: Maximum likelihood means 'set the derivative to zero', which is MLF week 2 in action.
MLF week 12 - Estimating parameters, and EM: The EM algorithm for Gaussian mixtures is taught in both courses.
MLP week 12 - Unsupervised learning in sklearn: Gaussian mixtures in scikit-learn.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 33 real questions on this week All Quiz 1 papers