Expectation–maximization algorithm

• 1. Introduction

  ›

  The expectation-maximization algorithm sits at the heart of modern statistics, quietly solving problems that would otherwise be mathematically impossible. Statisticians call it EM for short, and its central trick is as elegant as it is counterintuitive: when you cannot solve two sets of equations at once, alternate between them until both converge. The algorithm handles situations where data is incomplete, observations are censored, or the model depends on variables that no one ever directly measured. What makes EM remarkable is not just that it works, but that it was being rediscovered again and again, in different fields, by researchers who had no idea others had arrived at the same idea. The question that runs through its history is how one method, rooted in a single deceptively simple alternation, came to touch fields as different as genetics, medical imaging, natural language processing, and financial risk management.

• 2. Convergence and Credit

  ›

  Arthur Dempster, Nan Laird, and Donald Rubin published the paper that named and formalized the EM algorithm in 1977, and they were candid about what they found when they looked back at the literature. The method had been proposed many times in special circumstances by earlier authors who did not recognize the general principle at work. Among the earliest was a gene-counting method for estimating allele frequencies, developed by Cedric Smith. H.O. Hartley had proposed a version in 1958, and a later paper by Hartley and Hocking in 1977 supplied many of the ideas that Dempster, Laird, and Rubin would build upon. S.K. Ng, Thriyambakam Krishnan, and G.J. McLachlan also published a version in 1977. Rolf Sundberg worked out an especially detailed treatment for exponential families in his thesis and in several papers, drawing on unpublished results from Per Martin-Löf and Anders Martin-Löf. The 1977 Dempster-Laird-Rubin paper generalized all of this and sketched a convergence argument for a wider class of problems, establishing EM as a standard tool of statistical analysis. That convergence argument, however, turned out to have a flaw. C.F. Jeff Wu published a correct convergence proof in 1983, extending the guarantee to models outside the exponential family, as Dempster, Laird, and Rubin had originally claimed.

• 3. The Hidden Variable Problem

  ›

  To understand why EM exists, consider what statisticians face when a model involves variables that are never directly observed. These are called latent variables, and their presence creates a mathematical deadlock. Finding the maximum likelihood solution normally requires taking derivatives of a likelihood function and solving for all unknown quantities simultaneously. With latent variables in the picture, that simultaneous solution is usually impossible. The equations interlock: the right values for the parameters depend on knowing the latent variables, and the right values for the latent variables depend on knowing the parameters. Substituting one set of equations into the other produces an expression that cannot be solved analytically. A mixture model is one of the clearest illustrations of this problem. Each observed data point is assumed to come from one of several underlying distributions, but the assignment is unrecorded. The mixture component each point belongs to is the latent variable, and without knowing those assignments, estimating the distribution parameters is blocked. EM breaks the deadlock by starting with arbitrary parameter guesses and then alternating between two steps: computing the probability that each data point belongs to each component given current estimates, and then updating the parameter estimates given those probabilities, repeating until the values stabilize.

• 4. Two Steps, Infinite Uses

  ›

  Each cycle of the EM algorithm consists of an E step and an M step, and the names describe exactly what each does. The expectation step constructs a function for the expected log-likelihood of the complete data, treating the latent variables as if they had been observed, weighted by their current probability estimates. The maximization step then finds the parameter values that make that expected log-likelihood as large as possible, and those new parameters feed into the next E step. Viewed from another angle, the E and M steps can each be interpreted as maximization operations over different parts of a single function, making EM a special case of coordinate descent. In information geometry, these same steps correspond to projections under dual affine connections known as the e-connection and the m-connection, and the Kullback-Leibler divergence that appears in those projections connects EM to a broader family of geometric ideas about probability distributions. When the model belongs to the exponential family, the E step reduces to computing expected sufficient statistics, and the M step reduces to maximizing a linear function. In that setting, Rolf Sundberg's formula, proved using unpublished results from Per Martin-Löf and Anders Martin-Löf, makes it possible to derive closed-form update equations for each step.

• 5. Guarantees and Their Limits

  ›

  EM is guaranteed to increase the observed data likelihood at each iteration, but that guarantee stops short of promising the best possible answer. The algorithm converges to a local maximum, not necessarily the global one. For multimodal distributions, the final answer depends on where the algorithm started. Practitioners deal with this by running the algorithm from several different random starting points, a technique called random-restart hill climbing, and comparing where each run ends up. Simulated annealing methods offer another route out of local optima. In high dimensions the situation is more serious. The algorithm can converge arbitrarily slowly, and the number of local optima can grow exponentially. This has motivated a separate line of research into moment-based and spectral methods, which carry stronger theoretical guarantees including global convergence under certain conditions, with no spurious local optima. Gibbs' inequality is the key mathematical fact that makes EM's correctness provable at all: it ensures that improving the auxiliary Q function by choice of parameters cannot decrease the marginal likelihood of the observed data, so each M step is guaranteed to move in the right direction. One subtlety worth noting is that some likelihood functions contain singularities, spurious maxima where one component of a mixture is assigned zero variance and its mean is set equal to a single data point, giving a technically infinite density that is statistically meaningless.

• 6. Where EM Shows Up

  ›

  Positron emission tomography, single-photon emission computed tomography, and x-ray computed tomography all rely on EM and its faster variants for reconstructing medical images. In quantitative genetics, EM is a standard method for estimating parameters in mixed models. Psychometricians use it to estimate item parameters and latent abilities in item response theory. Financial analysts have adopted it for pricing and risk management of portfolios, particularly because of its ability to handle missing data and unidentified variables. Natural language processing has two prominent EM-derived algorithms: the Baum-Welch algorithm for training hidden Markov models, and the inside-outside algorithm for unsupervised induction of probabilistic context-free grammars. The structural engineering community developed a variant called the Structural Identification using Expectation Maximization algorithm, or STRIDE, which uses sensor data to identify the natural vibration properties of structures without needing to know the input forces. Filtering and smoothing problems in control theory offer yet another application, where EM combines with Kalman filters and minimum-variance smoothers to simultaneously estimate both the state of a system and the parameters of the model governing that system. Yasuo Matsuyama extended the framework further with the alpha-EM algorithm, which generalizes the standard log-likelihood approach using alpha-log likelihood ratios and alpha-divergence, and which produces a faster version of the Hidden Markov model estimation algorithm known as alpha-HMM.