Expectation-maximization algorithms

What Are Expectation-Maximization Algorithms?

Expectation-maximization algorithms are a family of iterative optimization procedures for finding maximum likelihood or maximum a posteriori estimates of parameters in statistical models that involve unobserved latent variables or incomplete data. The core idea is to replace a single, difficult optimization problem over observed and hidden variables jointly with a sequence of simpler steps: an expectation step that computes the expected value of the complete-data log-likelihood given current parameter estimates, and a maximization step that updates the parameters by maximizing that expected log-likelihood. The procedure was formalized by Arthur Dempster, Nan Laird, and Donald Rubin in their 1977 paper in the Journal of the Royal Statistical Society, which established its convergence properties and unified a disparate collection of earlier techniques under a single framework.

Expectation-maximization is widely used in machine learning, signal processing, bioinformatics, and econometrics whenever data are naturally incomplete, measurements are censored, or a model posits underlying structure that cannot be directly observed.

The E-Step and M-Step

In the expectation step (E-step), the algorithm computes the conditional expectation of the complete-data log-likelihood function with respect to the latent variables, treating the current parameter estimate as fixed. For models where the latent variables take discrete values, this amounts to computing posterior probabilities, sometimes called responsibilities, that each data point was generated by each component of the model. For continuous latent variables, the E-step computes sufficient statistics under the posterior distribution.

In the maximization step (M-step), the algorithm maximizes the expected log-likelihood computed in the E-step with respect to the model parameters. Because the complete-data log-likelihood is typically chosen from an exponential family, the M-step often has a closed-form solution, which is one reason the framework is computationally tractable. After the M-step, the updated parameters feed back into the next E-step, and the process repeats until convergence. A rigorous tutorial on the algorithm's derivation and convergence behavior is available in the University of Washington technical report by Borman, which covers the Jensen's inequality argument that proves each iteration monotonically increases the observed-data log-likelihood.

Convergence Properties and Variants

The EM algorithm is guaranteed to increase, or at minimum not decrease, the observed-data log-likelihood at every iteration, so it converges to a stationary point. However, this stationary point may be a local maximum rather than the global maximum, meaning the outcome depends on initialization. Common mitigation strategies include running multiple random restarts and retaining the solution with the highest converged likelihood, or using deterministic annealing or variational inference to guide the search toward better solutions.

Several variants address EM's limitations in large-scale settings. Stochastic EM (SEM) and incremental EM update parameters using subsets of the data, reducing per-iteration cost. The variational EM approach replaces the exact posterior over latent variables with a tractable approximating distribution when the true posterior is intractable. The expectation-conditional maximization (ECM) algorithm decomposes the M-step into a sequence of simpler conditional maximizations, useful when the joint M-step has no closed form. Duke's computational statistics course notes on EM illustrate these variants with worked examples in Python.

Applications in Statistical Learning

The most prominent application of EM is fitting Gaussian mixture models for density estimation and clustering. Each component of the mixture has its own mean, covariance, and mixing weight; the E-step assigns each observation fractional membership in each component, and the M-step re-estimates each component's parameters using those soft assignments.

EM also underlies the Baum-Welch algorithm for training hidden Markov models, factor analysis parameter estimation, image segmentation via mixture models, and missing-data imputation in multivariate datasets. Columbia University's lecture notes on the EM algorithm present a formal derivation of both the standard and variational EM frameworks, with applications to Gaussian mixtures and hidden Markov models.

Applications

Expectation-maximization algorithms have applications in a range of fields, including: