Home / MLF / Week 12

Week 12 · Estimating parameters, and EM

Official syllabus line: Parameter estimation. Expectation Maximization

About 90 minEnd Term material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Week 2 (derivatives, set to zero), week 10 (distributions), week 11 (helpful but not required).

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

Imagine a detective finding clues at a scene. Many stories could explain them, but only one story makes those clues seem least surprising. The best detective chooses that most likely story. This is like Maximum Likelihood Estimation. We pick the model that makes the data we actually saw most probable.
Now, imagine jars of sweets, but their labels are hidden. You get handfuls, but don't know which jar they came from! You first guess which jar each handful probably came from. Then, you use those guesses to re-estimate the jar contents. Repeating this loop is the EM algorithm.
Let's try an example. A coin is tossed 12 times, and it lands on heads 9 times. To find the most likely probability of getting heads, we simply divide the number of heads by total tosses. So, 9 heads out of 12 tosses gives us 0.75, or 75%.
For exams, remember: the normal variance MLE divides by 'n', but the unbiased version divides by 'n minus 1'. It's important to know which one to use! So, we learned to find the most likely story using MLE, and how EM helps with hidden information. You've got this!

The one-minute story

Think of it like this

A detective arrives at a scene and finds clues. Many different stories could explain them, but one story makes the clues the least surprising. A good detective picks that story. That is maximum likelihood estimation (MLE): among all possible settings of the model, pick the one under which the data you actually saw was most likely.

Now make the detective's job harder. Two jars of sweets are on a table, and a friend, with eyes closed, picks a jar each time and hands you a handful, but never tells you which jar. You want each jar's colour mix, but the labels are hidden. What do you do?

You guess which jar each handful probably came from (using your current idea of the jars), then re-estimate the jars using those guesses, and repeat. Each round your guesses and your jar recipes improve together. That loop is the EM algorithm (Expectation-Maximisation), and it lets us fit models with hidden pieces.

By the end of this week you can:

write down a likelihood and find the MLE for common models by calculus;
explain the bias of the Gaussian variance MLE;
state the idea of MAP estimation;
explain latent variables and run one step of EM by hand on the two-coin problem.

Words you need

Likelihood $L(\theta)$ - the probability (or density) of the observed data, viewed as a function of the parameter $\theta$ .
Log-likelihood $\ell(\theta)=\ln L(\theta)$ - easier to work with; its peak is in the same place.
MLE $\hat\theta$ - the parameter value that maximises the likelihood.
Estimator - a recipe that turns data into a guess for a parameter. It is unbiased if its guesses average to the truth.
Latent (hidden) variable - something the model needs but we never observe, like "which jar".
Responsibility - the current probability that a data point came from a given hidden cause.
Prior and posterior - what you believe about $\theta$ before and after seeing data.

Idea 1: Maximum likelihood estimation

Say $x_1,\dots,x_n$ are independent draws from a distribution with density or mass $p(x\mid\theta)$ . The probability of the whole data set is the product:

L(\theta)=\prod_{i=1}^np(x_i\mid\theta)\qquad\ell(\theta)=\sum_{i=1}^n\ln p(x_i\mid\theta)

The idea

The MLE recipe

Write the likelihood $L(\theta)$ .
Take the log (products become sums, and the maximiser does not move because $\ln$ is increasing).
Differentiate with respect to $\theta$ and set it to zero.
Solve, and check it is a maximum.

Likelihood is not the probability that $\theta$ is true. It is how probable the data is if $\theta$ were true. We vary $\theta$ and keep the data fixed.

The MLEs worth knowing

Model	MLE
Bernoulli( $p$ )	$\hat p=\bar x$ (fraction of successes)
Poisson( $\lambda$ )	$\hat\lambda=\bar x$
Exponential( $\lambda$ )	$\hat\lambda=1/\bar x$
Normal, known variance	$\hat\mu=\bar x$
Normal, both unknown	$\hat\mu=\bar x$ , $\;\hat\sigma^2=\frac1n\sum(x_i-\bar x)^2$
Uniform $(0,\theta)$	$\hat\theta=\max_ix_i$

Two cautions. The Normal variance MLE divides by $n$ , and it is biased (it underestimates on average); dividing by $n-1$ gives the unbiased version. And for the uniform, the derivative method fails (the likelihood $\theta^{-n}$ keeps falling as $\theta$ grows, but $\theta$ cannot go below the biggest observation), so you argue directly: the smallest $\theta$ allowed is the max.

Solved example: 1. A density with a parameter

Question. A variable on $(0,1)$ has density $f(x;\theta)=\theta x^{\theta-1}$ , $\theta>0$ . Two observations are $x_1=0.5$ and $x_2=0.25$ . Find the MLE of $\theta$ .

Solution.

$\ell(\theta)=\sum\ln(\theta x_i^{\theta-1})=n\ln\theta+(\theta-1)\sum\ln x_i$ .
$\ell'(\theta)=\frac n\theta+\sum\ln x_i=0\Rightarrow\hat\theta=-\dfrac n{\sum\ln x_i}$ .
$\sum\ln x_i=\ln0.5+\ln0.25=-0.693-1.386=-2.079$ , $n=2$ . So $\hat\theta=\frac{2}{2.079}\approx\mathbf{0.962}$ .

Solved example: 2. A discrete variable with an unknown constant

Question. $P(X=1)=\theta$ , $P(X=2)=2\theta$ , $P(X=3)=1-3\theta$ . The observations are $1,2,2,3,1,3$ . Find $\hat\theta$ .

Solution. Counts: two 1's, two 2's, two 3's. $L(\theta)=\theta^2(2\theta)^2(1-3\theta)^2\propto\theta^4(1-3\theta)^2$ . $\ell=4\ln\theta+2\ln(1-3\theta)+\text{const}$ . $\ell'=\frac4\theta-\frac{6}{1-3\theta}=0\Rightarrow4(1-3\theta)=6\theta\Rightarrow\theta=\dfrac{4}{18}=\mathbf{\dfrac29}$ . (Valid: $3\theta=\frac23<1$ .)

Solved example: 3. Normal with known variance, and the bias of the variance MLE

Question. (a) Five thickness measurements $2.1,\,2.3,\,2.2,\,2.4,\,2.0$ come from a normal distribution of known variance. Find the MLE of the mean. (b) For the data $2,4,6$ find the MLE of the variance and the unbiased estimate.

Solution. (a) $\hat\mu=\bar x=\frac{11.0}5=\mathbf{2.2}$ . (b) $\bar x=4$ . MLE: $\frac13(4+0+4)=\frac83\approx2.67$ . Unbiased: $\frac12(4+0+4)=4$ .

MLE and MAP

If you also have a prior belief $p(\theta)$ , the posterior is $p(\theta\mid\text{data})\propto p(\text{data}\mid\theta)\,p(\theta)$ , and the MAP (maximum a posteriori) estimate maximises it. MLE is MAP with a "flat" prior. With lots of data, the two agree. MAP gives you regularisation (ridge and LASSO in MLT week 6).

Link to least squares. If $y=\mathbf w^T\mathbf x+\text{noise}$ with Gaussian noise, the log-likelihood is $-\frac1{2\sigma^2}\sum(y_i-\mathbf w^T\mathbf x_i)^2+\text{const}$ . Maximising it means minimising the squared error: so least squares is MLE under Gaussian noise (week 3 and MLT week 5).

Idea 2: When something is hidden

Fitting a mixture of distributions: a data point comes from one of $K$ components, but we do not see which. The density is

p(x\mid\theta)=\sum_{k=1}^K\pi_k\,p_k(x\mid\theta_k)

Now $\ell(\theta)=\sum_i\ln\Big(\sum_k\pi_kp_k(x_i\mid\theta_k)\Big)$ has a log of a sum, which does not simplify, and setting the derivative to zero gives no tidy formula. If we knew which component produced each point, MLE would be easy (just estimate each component from its own points). The EM algorithm exploits exactly this.

Idea 3: The EM algorithm

Start with a guess for the parameters, then repeat two steps:

The idea

E-step (Expectation): with the current parameters, compute for every data point the responsibility: the probability that it came from each hidden cause. These are soft, fractional guesses.

M-step (Maximisation): pretend those fractional guesses are real. Re-estimate every parameter by ordinary MLE, weighting each data point by its responsibility.

Facts to remember:

Each full round never decreases the likelihood, so EM climbs steadily.
It converges to a local maximum, not necessarily the global one, so the starting guess matters.
It is k-means' soft cousin: k-means assigns each point to one cluster (a hard guess); EM gives each point a fractional membership.

Solved example: 4. One round of EM: the two-coins problem

Setup. Two coins A and B have unknown heads-probabilities $\theta_A$ and $\theta_B$ . In each of 5 sessions one coin was chosen at random (we do not know which) and tossed 10 times. Heads out of 10: $5,\,9,\,8,\,4,\,7$ . Start with $\theta_A=0.6$ , $\theta_B=0.5$ .

E-step. For a session with $h$ heads, coin A would produce that with likelihood $0.6^h\,0.4^{10-h}$ and coin B with $0.5^{10}$ . The responsibility of A is $r_A=\dfrac{L_A}{L_A+L_B}$ (the coins are equally likely a priori).

heads	$L_A$	$L_B$	$r_A$	$r_B=1-r_A$
5	$0.6^5 0.4^5$	$0.5^{10}$	0.45	0.55
9	$0.6^9 0.4^1$	$0.5^{10}$	0.80	0.20
8	$0.6^8 0.4^2$	$0.5^{10}$	0.73	0.27
4	$0.6^4 0.4^6$	$0.5^{10}$	0.35	0.65
7	$0.6^7 0.4^3$	$0.5^{10}$	0.65	0.35

M-step. Re-estimate each coin's bias as (expected heads) over (expected tosses), using the weights.

Coin A: expected heads $=0.45\cdot5+0.80\cdot9+0.73\cdot8+0.35\cdot4+0.65\cdot7\approx21.2$ ; expected tosses $=10\,(0.45+0.80+0.73+0.35+0.65)=29.8$ . So $\theta_A\approx\frac{21.2}{29.8}\approx\mathbf{0.71}$ .
Coin B: expected heads $\approx11.8$ ; expected tosses $=10\,(2.02)=20.2$ . So $\theta_B\approx\frac{11.8}{20.2}\approx\mathbf{0.58}$ .

From the guess $(0.60,\,0.50)$ the round moved to $(0.71,\,0.58)$ : coin A's probable heavy-heads sessions pulled it up. Repeating converges to roughly $(0.80,\,0.52)$ . (We verified these numbers by computer.)

For a Gaussian mixture the E-step responsibility is $r_{ik}=\dfrac{\pi_kN(x_i\mid\mu_k,\sigma_k^2)}{\sum_j\pi_jN(x_i\mid\mu_j,\sigma_j^2)}$ , and the M-step updates are $\pi_k=\frac{\sum_ir_{ik}}n$ , $\mu_k=\frac{\sum_ir_{ik}x_i}{\sum_ir_{ik}}$ and the weighted variance. MLT week 4 walks through that in detail with numbers.

Your turn

Your turn: 1. Bernoulli MLE

A coin is tossed 12 times and shows heads 9 times. What is $\hat p$ ? Write the log-likelihood and confirm.

Need a hint?

$L(p)=p^9(1-p)^3$ .

Show the full solution

$\ell=9\ln p+3\ln(1-p)$ . $\ell'=\frac9p-\frac3{1-p}=0\Rightarrow9(1-p)=3p\Rightarrow p=\frac{9}{12}=\mathbf{0.75}$ .

Your turn: 2. Exponential MLE

Waiting times $2,\,5,\,3$ minutes are modelled as exponential. Find the MLE of $\lambda$ and $P(X>4)$ .

Need a hint?

$\hat\lambda=1/\bar x$ .

Show the full solution

$\bar x=\frac{10}3$ , so $\hat\lambda=0.3$ . $P(X>4)=e^{-0.3\cdot4}=e^{-1.2}\approx0.301$ .

Your turn: 3. Unbiased or not?

Why do we sometimes divide by $n-1$ instead of $n$ when estimating a variance?

Need a hint?

The sample mean is itself estimated from the same data.

Show the full solution

Data points sit slightly closer to their own sample mean than to the true mean, so $\frac1n\sum(x_i-\bar x)^2$ underestimates the true variance on average. Multiplying by $\frac n{n-1}$ corrects that, giving the unbiased estimator. The MLE (with $n$ ) is biased but consistent: the bias vanishes as $n$ grows.

Your turn: 4. Uniform MLE

A uniform distribution on $[0,\theta]$ gives the sample $3,\,7,\,4,\,6$ . What is the MLE of $\theta$ ?

Need a hint?

The likelihood is $\theta^{-n}$ for $\theta\ge\max x_i$ and $0$ otherwise.

Show the full solution

$\hat\theta=\max=\mathbf7$ . (It is biased low: $\theta$ is almost always slightly bigger than the biggest sample.)

Your turn: 5. Run EM mentally

Why is the E-step in the two-coin problem needed at all? What would be easy if the coin labels were known?

Need a hint?

Think about what MLE would do per coin.

Show the full solution

If the labels were known, each coin's bias would just be (heads with that coin) / (tosses with that coin). The E-step fills in the missing labels with probabilities (responsibilities), and the M-step does exactly that same ratio, but with weighted counts.

Exam radar

In the MLF End Term, MLE appears in 16 of the 42 summarised papers, typically as: "MLE of $\mu$ for a normal with known variance from 5 measurements", "MLE of $\lambda$ for exponential service times", "MLE of an unknown constant in a discrete distribution", or "a density with a parameter, find the estimate from a sample". The EM algorithm is not examined in MLF papers on the practice site.

EM matters in MLT: it appears in 46 of 60 MLT Quiz 1 papers (with Gaussian mixtures). Learn it here for the idea, then do the numbers in MLT week 4.

Watch out - real exam trap

Maximise the log-likelihood but report the parameter, not the maximum value, unless asked.
Normal variance MLE uses $\frac1n$ ; the unbiased version uses $\frac1{n-1}$ . Read which one the question asks for.
For an exponential the MLE of the rate is $1/\bar x$ , not $\bar x$ .
EM finds a local maximum and depends on the start.
Responsibilities across components must add to 1 for each data point.

Quick quiz

The MLE of p for a Bernoulli sample with 7 successes out of 10 is...

The MLE is the sample proportion: 7/10.

The MLE of the variance of a normal distribution (mean unknown) divides by...

n minus 1
n
n squared
2

The MLE uses 1/n and is slightly biased low; 1/(n-1) gives the unbiased estimator.

In the EM algorithm, the E-step computes...

the final parameters
the responsibilities (soft assignments to hidden causes)
the learning rate
the covariance of the data

The E-step fills in the hidden labels with probabilities; the M-step re-estimates parameters using them.

Select all TRUE statements about EM. (select all that apply)

Each iteration does not decrease the likelihood.
It can converge to a local maximum.
It always finds the global maximum.
It needs the hidden labels to be known.

EM climbs the likelihood but only guarantees a local maximum. Its whole purpose is to cope with hidden labels.

Recap

Remember this

MLE: write $L(\theta)$ , take $\ln$ , differentiate, set to zero. Bernoulli $\bar x$ ; Poisson $\bar x$ ; exponential $1/\bar x$ ; normal mean $\bar x$ , variance with $\frac1n$ (biased).
MAP adds a prior; least squares is MLE under Gaussian noise.
Latent variables make the likelihood a log of a sum.
EM: E-step (responsibilities) then M-step (weighted MLE). Likelihood never decreases; converges to a local maximum; soft version of k-means.

Formulas to keep

$L(\theta)=\prod p(x_i\mid\theta)$ , $\ell=\sum\ln p(x_i\mid\theta)$ , $\ell'(\hat\theta)=0$
Normal: $\hat\mu=\bar x$ , $\hat\sigma^2_{MLE}=\frac1n\sum(x_i-\bar x)^2$ ; unbiased $\frac1{n-1}\sum$
Uniform $(0,\theta)$ : $\hat\theta=\max x_i$ ; Exponential: $\hat\lambda=1/\bar x$
MAP: $\arg\max p(\text{data}\mid\theta)p(\theta)$
EM: $r_{ik}=\frac{\pi_kp_k(x_i)}{\sum_j\pi_jp_j(x_i)}$ ; $\pi_k=\frac{\sum_ir_{ik}}n$ ; $\mu_k=\frac{\sum r_{ik}x_i}{\sum r_{ik}}$

Connected weeks (learn them together)

MLT week 4 - MLE, Bayes, Gaussian mixtures and EM: The EM algorithm for Gaussian mixtures is taught in both courses.
MLT week 5 - Regression: least squares and its Bayesian view: MLE and MAP give the probabilistic view of least squares and ridge.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 6 real questions on this week All End Term papers