Expectation-Maximization

Imagine you measure the heights of a crowd, but nobody recorded who is a child and who is an adult. You strongly suspect there are two groups mixed together, each roughly bell-shaped. You want to find the average height of each group — but to do that you'd need to know who belongs to which group, and that is exactly the information you don't have.

This is a chicken-and-egg problem. If you knew the group labels, fitting each bell curve would be easy. If you knew the curves, guessing the labels would be easy. You have neither.

Expectation-Maximization (EM) breaks the deadlock with a wonderfully simple idea: make up an answer, then let it improve itself. Start with a rough guess for the two curves. Use it to assign each point a soft guess of which group it came from (the E-step). Then pretend those guesses are true and re-fit the curves (the M-step). Repeat. Each round fits the data at least as well as the last, and the picture sharpens until it locks into place.

EM was given its general form and name by Dempster, Laird and Rubin in 1977, and it is one of the workhorses behind clustering, topic models, and missing-data statistics today.

Below are points scattered along a line — they secretly came from two overlapping clusters, but the labels are hidden. Two curves (orange and blue) start in a deliberately bad guess. Press Step to run one round of EM, or Run to let it iterate.

<p class="hint">{{hint_p}}</p>
<div class="ll">{{lbl_ll}} <span id="ll">—</span> &nbsp;·&nbsp; {{lbl_iter}} <span id="it">0</span></div>
<canvas id="cv" width="520" height="220"></canvas>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.ll { font: 700 14px ui-monospace, monospace; color: #1d3557; margin: .2rem 0 .5rem; }
canvas { width: 100%; max-width: 520px; height: auto; background: #f5f7fa;
         border: 1px solid #cdd9e3; border-radius: 8px; display: block; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Each Step does two things. First the E-step: every point is shaded by how likely each curve is to have produced it. Then the M-step: each curve's center and width are recomputed as a weighted average over the points it "owns." Watch the log-likelihood number at the top — it never goes down. The two curves drift apart, settle over the two real clusters, and stop moving. That stopping point is a local optimum: change the starting guess and EM may land somewhere slightly different.

EM has an unusually clean guarantee for an iterative method, and an unusually honest limitation.

• It never gets worse. Dempster, Laird and Rubin (1977) proved that each E-step / M-step pair can only increase (or hold) the data's likelihood. The numbers in the demo climb monotonically — that is not a coincidence, it is a theorem.
• It converges — but only locally. Because the likelihood keeps rising and is bounded, EM settles down. The catch: it settles on a local optimum, not necessarily the global best. A poor starting guess can trap it on a mediocre fit, which is why practitioners restart from several random seeds.
• One step is cheap. Each iteration is roughly linear in (points × clusters), so EM scales gracefully to large datasets — the cost is the number of iterations, not any single one.
• The global problem is hard. Finding the single best mixture that maximizes likelihood is NP-hard in general. EM is the practical compromise: fast, reliable improvement with no promise of perfection.

So EM is not a magic solver. It is a hill-climber for a landscape that is genuinely rugged — closely related to the hardness of clustering itself, the same wall you meet in k-means.

"I have data, but part of it is hidden" describes an enormous slice of real statistics, and EM is the default tool for it:

• Clustering and segmentation: Gaussian mixture models group customers, pixels or sensor readings without any labels — the soft cousin of k-means.
• Speech and language: training the hidden Markov models behind classic speech recognition uses EM (the Baum-Welch algorithm) to infer the unseen state sequence.
• Genetics and biology: EM untangles overlapping signals in gene-expression and population-genetics data where the underlying groups are unknown.
• Topic models and recommendations: latent factors behind documents or ratings are exactly the "hidden variables" EM was built to estimate, close in spirit to Bayesian inference.

Whenever the thing you most want to know is the thing you can't observe, EM gives you a principled way to bootstrap it from the data you can see.

Expectation-Maximization is a small idea with a long reach: when you can't see the labels, invent them, refit the model, and let the two halves pull each other into focus. Each round provably improves the fit, and the procedure stops at a stable, sensible answer.

The honest fine print is that the answer is only locally best — the global optimum stays NP-hard, so a bad start can mislead it. But for countless problems where half the data is missing, EM is the dependable, elegant workhorse that turns a paradox into a picture. The next time a model seems impossible to fit because the key information is hidden, remember: guess, refit, repeat.