Maximum likelihood when part of the data is hidden. Two Gaussians are mixed and their labels erased; EM guesses the labels (E-step), then re-fits the Gaussians as if the guesses were true (M-step), and climbs the likelihood without ever seeing which point came from which bell. Rendered, not quoted.
source Dempster, Laird & Rubin, Maximum Likelihood from Incomplete Data via the EM Algorithm (1977), J. Roy. Stat. Soc. B, vol. 39, no. 1, pp. 1–38. Pre-arXiv classic — cited by journal & year.
The data are n real numbers drawn from a mixture of two Gaussians: p(x) = π₁·N(x;μ₁,σ₁²) + π₂·N(x;μ₂,σ₂²), with π₁+π₂=1. The latent label zᵢ∈{1,2} says which bell produced xᵢ — and it is never observed.
E-step. Given current θ, the responsibility γᵢₖ = πₖNₖ(xᵢ) / ΣₗπₗNₗ(xᵢ) is the posterior P(zᵢ=k | xᵢ,θ) — a soft label in [0,1].
M-step. Treat the γ as fractional counts and re-fit by weighted maximum likelihood: μₖ = Σγᵢₖxᵢ / Σγᵢₖ, σₖ² the weighted variance, πₖ = (Σᵢγᵢₖ)/n.
Parent: the-maximum-likelihood — EM is maximum likelihood, run when a latent variable makes the log-likelihood intractable. It does not maximize logΣₖπₖNₖ directly; it uses Jensen's inequality to build a tractable lower bound (the ELBO), maximizes the bound (M-step), tightens it (E-step), and repeats. Bound-and-maximize.
Descendants: the same E/M loop is the engine behind k-means (hard-label limit), hidden Markov models (Baum–Welch), and topic models — any model with data you can see and structure you cannot.
Re-runs selfcheck() against the engine on every load and after any tamper. It re-verifies the monotonicity theorem across the whole run, the responsibility simplex, convergence to truth, and the fixed-point = stationary-point identity.
200 points sampled (fixed seed) from the true mixture μ=(−4,+4), σ=(1,1), π=(.5,.5). The labels are thrown away. EM starts deliberately wrong at μ=(−1,+1), σ²=(2,2), π=(.5,.5).
The MLE recovered from unlabelled data. Proven at boot on the seeded run:
EM finds a local maximum, not the global one. On poorly separated or badly initialised data it converges to a saddle or a shallow ridge and reports it with full confidence. Monotonicity guarantees you climb — never that you reach the top.
It can also collapse: let one component chase a single point and σₖ²→0 sends the likelihood to +∞. Unbounded, degenerate, "correct." The wall is that likelihood alone does not fence these off.
"EM maximises the log-likelihood at each step."
→ It maximises a lower bound; the true log-likelihood can only be shown to not decrease.
"Monotone increase means it converges to the MLE."
→ It converges to a stationary point of the likelihood — local max, or saddle.
"Responsibilities are the true probabilities of the labels."
→ They are posteriors under the current, wrong θ; they are correct only at a fixed point.
Corrupt the M-step: instead of moving each mean to the weighted estimate, step past it (μ ← 2μ̂ − μold), overshooting the target. The likelihood must now dip on some iteration — the monotonicity theorem breaks and the Witness (7) turns red.
M-step intact.