Expectation-Maximization Algorithm
EM iteratively fits models with latent variables by alternating a soft-assignment step with a maximum-likelihood update.
The problem EM solves
Many models contain latent (unobserved) variables: which cluster a point came from, which state a system occupied, which topic a word belongs to. If those variables were known, fitting the model by maximum likelihood would be easy. Expectation-Maximization (EM) breaks the chicken-and-egg deadlock by alternating between estimating the latent variables and re-fitting the parameters.
The two steps
The E-step computes the expected value of the complete-data log-likelihood using the current parameters, which in practice means computing the posterior probability (responsibility) of each latent value for each data point. The M-step then maximizes that expected log-likelihood over the parameters, treating the responsibilities as soft labels.
Formally, EM maximizes a lower bound Q(theta | theta_old) = E[ log p(x, z | theta) ] where the expectation is over p(z | x, theta_old). Because each M-step increases Q and Q lower-bounds the true log-likelihood, the observed-data likelihood never decreases across iterations.
Guarantees and limits
EM converges monotonically to a stationary point of the likelihood, but that point may be a local maximum or a saddle, so multiple random restarts are standard. Convergence can be slow near flat regions, and degenerate solutions (a cluster collapsing onto one point with zero variance) require regularization or variance floors.
- Guaranteed non-decreasing likelihood each iteration
- Sensitive to initialization; use several restarts
- Generalizes to any latent-variable model with a tractable posterior
- A generalized EM step that merely improves Q also converges
EM underlies Gaussian mixture models, hidden Markov models via Baum-Welch, and many missing-data problems where the missingness itself is treated as a latent variable.