Lecture 26 · Fitting a GMM, part 3 · end of unsupervised learning

The EM Algorithm

Alternate the two easy steps from L25 until the parameters stop changing. That's the Expectation–Maximization (EM) algorithm. It's a soft, probabilistic version of K-means, it climbs the log-likelihood to a local maximum, and in practice it's usually started from K-means.

Source: this lecture on YouTube (≈17 min). Previous: L25 · the lower bound and its two easy steps.

1 · The algorithm

Initialise θ⁰ = (μ₁…μ_K, σ₁²…σ_K², π₁…π_K)
repeat until ‖θᵗ⁺¹ − θᵗ‖ ≤ ε (ε is a small tolerance, e.g. 10⁻³)
E-step: λᵗ⁺¹ = argmax_λ ℓ̃(θᵗ, λ) → λᵢₖ = πₖ𝒩(xᵢ; μₖ, σₖ²) / Σₗ πₗ𝒩(xᵢ; μₗ, σₗ²)
M-step: θᵗ⁺¹ = argmax_θ ℓ̃(θ, λᵗ⁺¹) → weighted means, weighted variances, πₖ = average λ

E-step (Expectation): with the parameters fixed, compute each point's soft membership λ. It's called "expectation" because the quantity being optimised can be written as an expected value; the course doesn't go into the general form.
M-step (Maximization): with the memberships fixed, refit every component's mean, variance and weight.
Both steps are the closed-form formulas from L25. EM was named and set out in its general form by Dempster, Laird and Rubin in 1977.

2 · EM is "soft K-means"

	Lloyd's / K-means (L14)	EM for a GMM
Assignment step	each point goes fully to its nearest mean (hard: $z_i$)	E-step: each point gets a probability for every cluster (soft: $\lambda_{ik}$)
Update step	recompute the means	M-step: recompute the means and variances and weights π
Cluster shape	Voronoi regions, all treated alike	each cluster has its own spread, so the regions need not be Voronoi
Output	a partition	parameters plus soft memberships; take argmax_k λᵢₖ for a hard clustering

Because EM learns each cluster's variance (in higher dimensions, its covariance and so its orientation), it handles overlapping clusters of different spreads much better than K-means. The demo below shows this in 1-D: a wide cluster next to narrow ones.

iteration

–

log-likelihood

–

‖θᵗ⁺¹ − θᵗ‖ (last change)

component 1component 2component 3

3 · What EM is really doing: climbing with lower bounds

The GMM log-likelihood, as a function of θ, is a bumpy landscape with several peaks. EM never tackles it directly. At the current θᵗ:

E-step: choose λ so the lower bound ℓ̃ (always ≤ log L, by Jensen) touches log L at θᵗ.
M-step: the bound is easy to maximise, so jump to its peak, θᵗ⁺¹. Since the bound sits under log L and touched it at θᵗ, log L at θᵗ⁺¹ is at least as high as before.
Repeat. log L never decreases, and EM converges, but only to a local maximum.

An illustration of the idea on a made-up bumpy function (not the actual GMM bound). The black curve is "log L"; each coloured curve is a lower bound that touches it at the current point. Change the starting point and see which peak EM climbs to.

start θ⁰ =

4 · Initialisation matters, so start from K-means

Since EM only reaches a local maximum, where you start decides which peak you end up on. Standard practice:

Run Lloyd's algorithm (K-means) to get a hard clustering.
For each cluster, use its sample mean, its sample variance, and its fraction of the points as μ⁰ₖ, σ²⁰ₖ and π⁰ₖ.
Run EM from there.

Try both starts in the demo in section 2. The random guess puts two components on the same cluster, and EM converges to a clearly worse local maximum (log L ≈ −351 instead of ≈ −310).

5 · The bigger picture

EM isn't specific to Gaussians. It works for any latent variable model whose log-likelihood splits nicely once the hidden variables are accounted for.
In practice it converges fast and gives good estimates.
This finishes the course's unsupervised learning part: representation learning (PCA, kernel PCA), clustering (K-means), and estimation (ML, Bayesian, GMM + EM). Next up: supervised learning.

Key takeaways

EM = initialise θ, then repeat the E-step (λ by Bayes) and the M-step (weighted μ, σ², π) until θ barely changes.
It's soft K-means: probabilities instead of hard labels, plus variances and weights. Clusters needn't be Voronoi, and argmax λ gives a hard clustering.
Each step pushes log L up (via the touching lower bound), but EM reaches only a local maximum.
So initialisation matters. Starting from K-means is the standard choice.

Self-check: why can a GMM cluster be split into two separate pieces of the line, while a K-means cluster can't?

A K-means cluster is a Voronoi cell, the set of points nearest one mean, which is always one interval in 1-D. In a GMM, a wide component's density falls off more slowly than a narrow one's, so far from both, the wide one wins again on both sides of the narrow one.

Self-check: what does EM guarantee, and what doesn't it guarantee?

It guarantees that log-likelihood never decreases and that it converges, to a local maximum. It doesn't guarantee the global maximum, which is why the starting point matters.