Skip to content
Back to search results

EM Algorithm

Introduced by
Dempster, Laird & Rubin
Year
1977
Type
Iterative optimization algorithm
Family
Estimation
Font size

What does it do?

The Expectation-Maximization (EM) algorithm is an iterative optimization procedure for finding maximum likelihood or maximum a posteriori estimates of parameters in statistical models with latent variables or missing data.

Introduced by Dempster, Laird, and Rubin in their landmark 1977 paper, EM alternates between computing the expected complete-data log-likelihood (E-step) and maximizing it with respect to the parameters (M-step), guaranteeing monotone non-decreasing likelihood at each iteration.

The intuition behind the method

Imagine trying to learn the rules of a game by watching players whose cards you cannot see. In each round you guess what cards they likely hold given what you observe, then update your model of the rules assuming those guesses are correct. EM does exactly this: the E-step fills in the missing information probabilistically using current parameter estimates, and the M-step re-fits the model as if those filled-in values were real observations.

History

The algorithm was formally unified and named by Arthur Dempster, Nan Laird, and Donald Rubin in their 1977 JRSS-B paper, which remains one of the most cited statistics articles ever published. The paper generalized earlier special-case procedures developed independently for specific missing-data problems. Subsequent decades produced numerous extensions including the ECM, ECME, AECM, and SEM algorithms, broadening applicability and accelerating convergence in many practical settings.

When to use it

Use the EM algorithm when data contain missing values, hidden states, or latent variables and you need maximum likelihood estimates. It is well-suited to Gaussian mixture models, hidden Markov models, factor analysis, and missing-data imputation. Key assumptions include that missing data are missing at random (MAR) and that the complete-data model is tractable. Limitations include sensitivity to initialization, possible convergence to local maxima, and slow convergence near saddle points. Alternatives include gradient-based optimization with numerical integration, variational inference, or MCMC methods.

Limitations and considerations

  • Convergence to a local maximum rather than the global maximum when the likelihood surface is multimodal
  • Can exhibit very slow (linear) convergence when the fraction of missing information is large
  • Requires the analyst to specify the complete-data model and the distribution of latent variables
  • Standard EM does not directly provide the observed-data covariance matrix of the estimates; a supplementary step (e.g., Louis's method or the SEM algorithm) is needed for standard errors

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Guaranteed monotone increase in observed-data likelihood at every iteration, ensuring stable convergence
  • Converts a hard missing-data problem into a sequence of tractable complete-data optimizations
  • Broadly applicable across exponential-family models, mixture models, and latent-variable frameworks
  • Closed-form M-step updates are available for many standard models, making implementation efficient

Applications

  • Fitting Gaussian mixture models for clustering and density estimation
  • Training hidden Markov models for speech recognition and biological sequence analysis
  • Multiple imputation and missing-data analysis in clinical and social science research
  • Parameter estimation in factor analysis and latent class analysis
  • Image segmentation and reconstruction in medical imaging

How it works

How it works

1

Before iteration begins, the analyst selects starting values for the unknown parameters, denoted theta-0. These can be chosen randomly, from a simplified fit, or by domain knowledge. The quality of initialization can affect which local maximum the algorithm converges to, making multiple random restarts a common practice.

Formula
\text{Choose initial parameter estimates } \theta^{(0)}
2

Given the current parameter estimate theta-t, the E-step computes Q, the expected value of the complete-data log-likelihood over the distribution of the unobserved latent variables Z, conditioned on the observed data X. This expectation effectively replaces unknown quantities with their probabilistic estimates without committing to a single imputed value.

Formula
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

The M-step maximizes the Q function from the E-step with respect to theta, producing an updated estimate theta-(t+1). Because the complete-data log-likelihood is often simpler to maximize than the marginal observed-data likelihood, this step is frequently tractable even when direct maximum likelihood is not.

Formula
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

The E- and M-steps are repeated in alternation. After each full cycle, the observed-data log-likelihood is evaluated. Iteration stops when the change in log-likelihood (or in the parameter vector) falls below a user-defined tolerance epsilon. Dempster et al. proved that each cycle cannot decrease the observed-data likelihood, ensuring stable convergence.

Formula
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Common pitfalls

  • Using a single random initialization risks terminating at a poor local maximum; always run multiple restarts and select the solution with the highest final log-likelihood
  • Declaring convergence too early by monitoring only parameter change rather than the observed-data log-likelihood can yield inaccurate estimates
  • Applying EM when data are Missing Not At Random (MNAR) without model adjustment can introduce systematic bias in estimates
  • Ignoring the label-switching problem in mixture models leads to uninterpretable component assignments even after correct convergence

Frequently asked questions

Does the EM algorithm always converge to the global maximum?

No. EM is guaranteed only to find a local maximum (or saddle point) of the observed-data likelihood. When the likelihood surface has multiple modes, the final solution depends on initialization. Running the algorithm from several different starting points and retaining the solution with the highest log-likelihood is the standard practical remedy.

How is EM different from direct maximum likelihood optimization?

Direct MLE maximizes the observed-data log-likelihood, which may involve intractable integrals over latent variables. EM sidesteps this by iteratively maximizing the expected complete-data log-likelihood, which is often analytically tractable. The trade-off is that EM may converge slowly, whereas gradient-based methods can be faster when gradients of the marginal likelihood are available.

When should I prefer MICE imputation over the EM algorithm?

MICE (Multiple Imputation by Chained Equations) is preferable when the data include variables of mixed types, non-linear relationships, or complex interaction structures that are difficult to encode in a single parametric complete-data model. EM is more natural when a well-specified joint model for all variables exists and inference targets the model parameters rather than imputed datasets.

Related methods

Sources

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    Open DOI reference
    Copied.