Expectation-Maximization
The expectation-maximization (EM) algorithm is an iterative method for finding maximum-likelihood or maximum a posteriori parameter estimates in models with latent (unobserved) variables or missing data, alternating between an expectation step that fills in the missing structure with its expected value under the current parameters and a maximization step that re-estimates the parameters as though that completed data were real. It was named and given a general proof by Arthur Dempster, Nan Laird and Donald Rubin in their 1977 paper "Maximum Likelihood from Incomplete Data via the EM Algorithm" in the Journal of the Royal Statistical Society, Series B, which also showed that many earlier special-purpose procedures were instances of one idea. The best known precursor is the Baum–Welch algorithm for hidden Markov models (Baum and colleagues, around 1970).
EM exists because the likelihood of incomplete data is a sum or integral over every possible value of the latent variables, which usually has no closed-form maximizer even though the complete-data problem would be easy. If it were known which mixture component generated each point, estimating each component would be a matter of ordinary averages; if the parameters were known, the probability of each assignment could be computed. EM bootstraps between the two. The E-step computes the posterior distribution of the latent variables given the data and the current parameters (the "responsibilities" in a mixture model), and the M-step maximizes the expected complete-data log-likelihood with those soft assignments as weights, which in many models has a closed form. Each cycle is guaranteed not to decrease the observed-data likelihood, so the sequence climbs monotonically.
The guarantee of monotone improvement comes from a lower-bound argument that later became central to modern probabilistic machine learning. The E-step builds a tight lower bound on the log-likelihood (the evidence lower bound) that touches it at the current parameters, and the M-step raises that bound; since the bound never exceeds the true log-likelihood, the true value rises too. Radford Neal and Geoffrey Hinton's 1998 paper recast EM as coordinate ascent on this free-energy function, which justified partial, incremental and sparse variants and opened the door to variational inference, where the E-step's exact posterior is replaced by a tractable approximation; the variational autoencoder's training objective is a descendant of the same bound. C. F. Jeff Wu's 1983 paper established the convergence conditions, showing that EM converges to a stationary point under regularity conditions, not necessarily the global maximum.
EM's applications are among the workhorses of classical machine learning and statistics: gaussian-mixture-model clustering, hidden Markov models in speech and bioinformatics, factor analysis, probabilistic PCA, topic models such as probabilistic latent semantic analysis, imputation of missing values, and estimation with censored data in survival analysis. In each, a missing piece (the cluster label, the hidden state, the unobserved value) is replaced by its expectation. Compared with direct gradient-based maximum-likelihood-estimation, EM needs no learning rate, keeps parameters valid automatically (covariance matrices stay positive definite, probabilities stay normalized) and has simple updates, which is why it remains attractive even in the age of automatic differentiation. Its drawbacks mirror those of the likelihood surface it climbs: convergence is linear and can be painfully slow when much information is missing, and it provides no standard errors without extra computation (such as the SEM algorithm or the observed information matrix).
The characteristic failure modes are local optima, degenerate solutions and a false sense of having found "the" answer. EM results depend strongly on initialization, so common practice is to run many random starts or to initialize from k-means; the likelihood of a Gaussian mixture is unbounded if one component collapses onto a single data point, so covariance regularization or a prior is needed; and a model with the wrong number of components will still converge happily, so model selection with information criteria or held-out likelihood must be done separately. A frequent misunderstanding is to describe EM as a model: it is an optimization procedure, and the same algorithm can fit mixtures, hidden Markov models or factor models, with the model supplied by the user.
Read expectation-maximization as the disciplined version of "guess the hidden labels, fit the parameters, and repeat," made rigorous by a likelihood bound that can only rise, and made fragile by the same fact, since it climbs to the nearest peak and does not look for a higher one.