From "the name tags fell off" to soft clustering
Imagine a teacher who is handed a stack of test scores, but the name tags fell off the pages. Some scores came from the morning class, some from the afternoon class, and the two classes had different typical scores. Can you sort the scores back into two groups and work out each class's average, even though nobody tells you which page belongs to which class? Playing that guessing game carefully, over and over, is exactly the EM (Expectation–Maximization) algorithm.
Each class is a bell curve (a Gaussian) with its own center $\mu$ and spread $\sigma$. We also don't know how big each class is — call those fractions the mixing weights $\pi$. EM plays a two-move game. The "guess who" move (E-step): for every score, ask "how likely is it this came from class 1 versus class 2?" A score sitting right under class 1's peak might be 90% class 1 and 10% class 2. Those soft percentages are the responsibilities $r_{ik}$. The "update" move (M-step): now that every score has been softly handed to the classes, recompute each class's average and spread using those weights — a point that is 90% class 1 counts mostly toward class 1. One worked number: a point $x$ with responsibility $0.9$ for class 1 contributes $0.9\,x$ to that class's weighted mean and only $0.1\,x$ to the other.
Formally the responsibility is $r_{ik}=\dfrac{\pi_k\,f(x_i;\mu_k,\sigma_k^2)}{\sum_j\pi_j\,f(x_i;\mu_j,\sigma_j^2)}$, and the M-step maximizes the expected complete-data log-likelihood, giving the weighted mean, variance, and weight formulas in the next section. Each full E+M cycle provably never lowers the data's log-likelihood — it climbs a lower bound until it plateaus at a local maximum. The sliders map straight onto the story: K sets how many bell curves to fit, n the number of points, and Separation how far apart the true class centers sit.
(1) Push Separation to 5 and click Run to Conv — well-separated clusters lock in within a handful of steps. (2) Drop Separation to 0.5 so the curves overlap heavily, and watch convergence slow down and the fit grow ambiguous. (3) Set K=5 with low separation, hit New Data a few times, and notice the final log-likelihood differs from run to run — that is EM landing in different local optima, which is why practitioners use multiple random restarts.
EM Algorithm — Dempster, Laird, Rubin, 1977
E-step: $r_{ik}=\dfrac{\pi_k\,f(x_i;\mu_k,\sigma_k^2)}{\sum_j\pi_j\,f(x_i;\mu_j,\sigma_j^2)}$ (responsibilities)
$$\boxed{\text{M-step: }\mu_k=\frac{\sum_i r_{ik}x_i}{\sum_i r_{ik}},\quad\sigma_k^2=\frac{\sum_i r_{ik}(x_i-\mu_k)^2}{\sum_i r_{ik}},\quad\pi_k=\frac{\sum_i r_{ik}}{n}}$$
EM alternates between: (E) computing expected complete-data log-likelihood using current parameters → (M) maximizing to update parameters. Each iteration guarantees $\ell(\theta^{new})\ge\ell(\theta^{old})$ — log-likelihood never decreases.
EM converges to a local maximum of the likelihood. Not guaranteed to find the global maximum. Multiple random restarts help escape local optima. Convergence criterion: $|\ell^{(t)}-\ell^{(t-1)}|<\epsilon$.
EM converges to LOCAL maxima, not global maxima.
For GMMs with K>2, different initializations give different solutions. Always run EM multiple times from random starting points and keep the solution with highest log-likelihood. The Convergence tab shows the LL trajectory — a good solution increases monotonically and plateaus at a high value.
📖 Bishop — PRML Ch. 9
The component labeling is arbitrary — "cluster 1" and "cluster 2" are interchangeable.
The mixture model likelihood is invariant to permutation of component labels. This means MCMC for GMMs has K! equivalent modes. For EM, this is less problematic since we find one mode, but comparing across runs requires label alignment.
📖 Bishop — PRML Ch. 9