Expectation–maximisation Explained with Worked Examples

The EM algorithm fits models with hidden variables by repeating two steps: the E-step computes , and the M-step maximises over . The likelihood never decreases.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

What Expectation–maximisation means

A standard case is a mixture of normal distributions: each data point comes from one of two components, but we do not know which. The E-step computes responsibilities, the probability that each point belongs to each component given the current parameters, using Bayes' theorem with the normal density. The M-step recomputes each mean as a responsibility-weighted average, a weighted average.

Example: equal weights, unit variances, current means 1 and 3, data and . For : , , so the responsibility of component 1 is . By symmetry for it is . The M-step gives and : the means move to the data.

EM is a maximum likelihood method (maximum likelihood estimation) when direct maximisation is hard, and its convergence is a fixed-point iteration (fixed-point iteration). Applications include clustering, missing data and hidden Markov models. A cousin from linear algebra is principal component analysis.

What is it used for?

EM fits models when some information is hidden, by alternately guessing the hidden labels and re-fitting the parameters.

How to use expectation–maximisation

  1. Choose initial parameters .
  2. E-step: compute the responsibilities for each data point.
  3. M-step: update the parameters using the responsibilities as weights.
  4. Repeat until the parameters or likelihood stop changing.

Graph

Components N(1, 1) and N(3, 1); the point x = 0 fits the firstx = 0: 98% component 1-3-2-10123456700.10.20.30.4Components N(1, 1) and N(3, 1); the point x = 0 fits the firstxdensitycomponent 1component 2Graph with x from -3 to 7 and y from 0 to 0.45. Shows the curve component 1; the curve component 2; point x = 0: 98% component 1 at (0, 0.242).

At x = 0 the first density is far higher, so its responsibility is 0.982.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: E-step at x = 0

Two components and , equal weights. Find the responsibility of component 1 for .

Worked example
Answer
0.98200.9820
  1. Densities
  2. Responsibility

Example 2: M-step for μ₁

With data and , responsibilities of component 1 of 0.9820 and 0.0180, find the new .

Worked example
Answer
0.07200.0720
  1. Weighted mean

Example 3: M-step for μ₂

With responsibilities of component 2 of 0.0180 and 0.9820, find the new .

Worked example
Answer
3.9283.928
  1. Weighted mean

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

π = 0.5, densities 0.2 and 0.1

responsibility r₁

0.6667.

r = 0.9, 0.6, 0.3

new π

0.6.

x = 1, 2, 3

new μ

1.6667.

Σr

effective count

1.8.

Word problems

E-step: compute responsibilities (posterior of the hidden variable). M-step: maximise the expected complete-data log-likelihood. The likelihood never decreases.

Responsibility

π₁f₁ / (π₁f₁ + π₂f₂).

  1. 0.1/0.15
  2. Check: ✓0.6667

New weight

Average responsibility.

  1. 1.8/3
  2. Check: ✓0.6

New mean Higher

Weighted average of x.

  1. 3.0/1.8
  2. Check: ✓1.6667

Effective count Higher

Σr.

  1. 0.9 + 0.6 + 0.3
  2. Check: ✓1.8

Common mistakes

Hard assignments

0 or 1 ✗

soft responsibilities ✓

Posterior.

Guaranteed global maximum

global ✗

local maximum ✓

Initialisation matters.

Skipping normalisation

unnormalised ✗

divide by sum ✓

Responsibilities sum to 1.

Likelihood can decrease

decrease ✗

never decreases ✓

EM property.

Exam tips

  1. E: responsibilities.
  2. M: weighted updates.
  3. Repeat until convergence.
  4. Try several starts.
  5. Likelihood increases.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. r₁: π = 0.5, densities 0.4, 0.1 Foundation

0.8

2. New π: r = 0.5, 0.5, 1 Foundation

0.6667

3. New μ: r = 1, 1, x = 2, 4 Foundation

3

4. r₁: π₁ = 0.3, densities 0.2, 0.2 (π₂ = 0.7) Higher

0.3

5. Σr for r = 0.2, 0.3, 0.5 Higher

1

6. New μ: r = 0.5, 0.5, x = 0, 10 Higher

5

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

EM algorithm
Fits latent-variable models.
E-step
Compute expected hidden variables.
M-step
Maximise Q.
Responsibility
P(Z
Latent variable
Hidden Z.
Mixture model
Weighted components.

Frequently asked questions

What is the EM algorithm?

An iterative method for maximum likelihood with hidden variables.

What does the E-step do?

Computes the expected complete-data log-likelihood, i.e. responsibilities.

What does the M-step do?

Maximises it over the parameters.

Does it find the global maximum?

Not always.

Which page covers MLE?

maximum likelihood estimation.

Which page covers Bayes’ theorem?

Bayes’ theorem.

More in Advanced statistics and stochastic processes and the formula sheets.