EM, Step by Step

← text notes · Foundations › Probability. Three widgets for the Expectation–Maximization algorithm: watch it cluster, watch it climb, and see where the soft assignments come from.

1. EM on 2-D clusters, one step at a time

Each point is coloured by its responsibilities: a point that's surely in one blob takes that blob's colour, and a point that's split between blobs gets a blend. Ellipses show each Gaussian at 1 and 2 standard deviations, with thickness proportional to its weight π_k.

Press E-step and only the colours change: the blobs stay put and the points re-vote. Press M-step and only the ellipses change: each blob moves to the weighted average of the points that voted for it. The button that comes next is outlined. Click the canvas to add points.

Things to try. Two long stripes with K=2: EM usually finds the two thin ellipses (press ↻ if a start lands badly). Flip to Hard (k-means) and it can only think in round clusters, so it chops the stripes into a left half and a right half instead. Start: all on top of each other shows the plateau from the notes (§6): nothing happens for many steps, then it suddenly splits. Try K=5 on three blobs a few times: sometimes a blob shrinks around a handful of points, the start of the collapse in §3 (a tiny ridge 10^-4 is added to every covariance to stop it at zero).

2. Climbing the likelihood with lower bounds

The red curve is the log-likelihood of 120 one-dimensional points as a function of one parameter, θ = μ₁ (the second blob's mean is fixed at 1.8, both variances at 1, both weights at ½). EM never looks at the red curve directly. E-step builds a bound ℒ(q, θ) that lies under it and touches it at the current θ. M-step jumps to the top of that bound. Drag the start slider and step.

Start at the far left and two or three big steps reach the top. Now start at the far right, where blob 1 begins on the wrong side of blob 2: the first bounds are nearly flat, the first few steps are short, and it needs about twice as many steps. A slow-looking EM run is usually this, a nearly flat stretch of the likelihood, not a bug. (A decreasing log-likelihood, on the other hand, is always a bug.)

3. Where responsibilities come from

Two weighted Gaussians on a line. At every x, the responsibility of the blue blob is its share of the total height: γ₁(x) = π₁N(x | μ₁, σ²) / p(x). With a shared σ, that share is exactly a logistic sigmoid in x, shown in the lower panel. Shrink σ and it sharpens into a step at the midpoint. That's the k-means limit: nearest centre takes all.

Set π₁ to 0.8 and the crossover point slides toward the orange blob: a more common blob claims ambiguous points. Unequal weights shift the curve sideways; they don't change how steep it is. That's the ln(π₁/π₂) term in the intercept.

Data are generated in the browser from a fixed seed, so they differ slightly from the figures in the text notes, which come from code/em.py.