Expectation–Maximization

Learning a probability model from complete data is straightforward: the log likelihood decomposes into one term per parameter, each partial derivative can be set to zero independently, and every estimate turns out to be a ratio of counts. The difficulty arises when some of the variables that appear in those counts are never observed - which cluster a point came from, which topic generated a document, which state a process was in.

EM turns the missing counts into expected counts. In the E step, the current parameters are used to compute the posterior distribution over the hidden variables for each example; the fractional membership this assigns is called a responsibility. In the M step, the complete-data maximum-likelihood formulas are applied unchanged, with every count replaced by a sum of responsibilities. The two steps alternate until the log likelihood stops moving.

The guarantee that makes this work is that each iteration maximizes a lower bound on the log likelihood which touches it at the current parameters. Improving the bound therefore cannot make the likelihood worse. This is a genuinely useful invariant when implementing EM: if the log likelihood ever falls, the implementation is wrong rather than unlucky.

What is not guaranteed is the global maximum. Different initializations converge to different fixed points, and some of them are much worse than others; the usual remedy is a handful of random restarts, keeping the fit with the highest likelihood. Degenerate solutions are also possible - a mixture component can collapse onto a single point and drive its variance to zero, sending the likelihood to infinity - which is why implementations impose a floor on the variance.

The algorithm is far more general than clustering. Learning the parameters of a Bayesian network with hidden nodes, learning the transition and sensor models of a hidden Markov model from observations alone (where the E step is exactly forward–backward smoothing), and fitting latent-variable models throughout statistics are all instances of the same two steps.

Take twenty points on a line, eight drawn from a narrow group near zero and twelve from a broad group near five, with the labels withheld. Started from the crude guess that the means are 0 and 5 and both standard deviations are 1, EM converges in 82 iterations, raising the log likelihood monotonically from −56.616239 to −46.633131 and settling on weights 0.347288 and 0.652712, means 0.128189 and 4.581627, and standard deviations 0.731077 and 2.367312.

Those parameters recover the withheld labels exactly. The optimal k-means split of the same data does not: it places x = 1.7 in the narrow cluster, because 1.7 is 1.571811 from the narrow mean and 2.881627 from the broad one. EM compares densities rather than distances, and the broad component is 3.24 times wider and carries the larger weight, so it earns responsibility 0.736211 for that point.

Restarting matters. Of 400 random initializations on this data, 385 reached −46.633131 and the remaining 15 stopped at −48.277387 - a genuinely worse fit that no amount of further iteration escapes.