Gaussian mixture models and EM

A Gaussian mixture model describes data as a blend of several bell curves, and the EM algorithm fits it by alternating soft assignment of points (E-step) with refitting each curve (M-step).

Why it matters

Real data is often a mix of hidden groups: delivery times from two routes, heights of two populations, colours in an image. You don't know which group each point came from, and the groups overlap, so hard clustering is too crude.

A mixture model gives each point a probability of belonging to each group, and EM is the classic way to fit models with hidden variables like this.

The idea

A Gaussian mixture model says the data comes from several bell curves mixed together. The EM algorithm finds them by repeating two steps. E-step: work out how much each point belongs to each bell curve (its 'responsibilities'). M-step: refit each bell curve using those responsibilities as weights.

Sorting a pile of socks from two families by size. First guess which family each sock belongs to, then update your idea of each family's typical size, then guess again.

You would give each sock to exactly one family. EM gives soft answers, like 70% family A and 30% family B. That is exactly how it differs from k-means, which is the hard-assignment version of the same idea.

How it works

  1. Choose the number of components, and start each with a rough mean, spread and weight.
  2. E-step: for each point, compute how much each component explains it: rₖ = πₖ·N(x | μₖ, σₖ) / Σⱼ πⱼ·N(x | μⱼ, σⱼ). These shares are the responsibilities.
  3. M-step: refit each component as a weighted average, using the responsibilities as weights: new mean, new spread, and new weight πₖ = the average responsibility.
  4. Compute the log-likelihood. EM guarantees it never goes down.
  5. Repeat until it stops improving.
  6. Like k-means, the result depends on the start, so run it several times. k-means is EM with hard 0/1 assignments and equal round spreads.

Key points

Common mistakes

Not true: EM separates the components even when they all start in the same place.
In fact: Components that start identical get identical responsibilities and identical updates, so they stay identical. Start them in different places.

Not true: Responsibility 0.9: the point really did come from that component.
In fact: A responsibility is the model's guess, based on its current means and spreads. A different or better model would give a different number.

Go deeper: Why EM can never make the likelihood worse

  1. Call the hidden information z (which component made each point) and the parameters θ (the means, spreads and weights). For any guess q(z) about the hidden part, the log-likelihood splits in two: log p(x | θ) = F(q, θ) + KL(q ‖ p(z | x, θ)).
  2. Here F(q, θ) = E_q[log p(x, z | θ)] − E_q[log q(z)]. Because a KL divergence is never negative, F is a lower bound on the log-likelihood.
  3. E-step: set q to the responsibilities under the current parameters, q = p(z | x, θ_old). The KL term becomes 0, so the bound touches the likelihood: F(q, θ_old) = log p(x | θ_old).
  4. M-step: keep q fixed and choose the parameters that make F as large as possible. So F(q, θ_new) ≥ F(q, θ_old).
  5. Chain the three facts: log p(x | θ_new) ≥ F(q, θ_new) ≥ F(q, θ_old) = log p(x | θ_old).
  6. F is the same lower bound a VAE maximises, where it is called the ELBO (Unit 7).

Each E-step lifts the lower bound up to the likelihood, and each M-step pushes the bound higher, so the log-likelihood never goes down. It can still stop at a local optimum.

Part of Unit 2: Classical ML, built by you in the free ML Foundations course.