Expectation-maximization algorithm

Also known as: EM algorithm

On this page 7

The expectation-maximization algorithm (EM algorithm) is an iterative method for finding maximum likelihood or maximum a posteriori estimates of model parameters when the data depend on latent variables that are never observed. In machine learning, it is the standard way to fit Gaussian mixture models, hidden Markov models and many other probabilistic models with missing or hidden information.

Each iteration alternates two steps: an E-step that computes the expected values of the hidden variables under the current parameters, and an M-step that re-estimates the parameters as if those expectations were observed data. The procedure is guaranteed to never decrease the likelihood, which makes it stable and easy to monitor.

How the E-step and M-step work together

EM solves a problem that is hard directly but easy in pieces. Maximizing the marginal likelihood of observed data requires summing or integrating over every possible value of the hidden variables, which usually has no closed form. If the hidden values were known, however, the complete-data likelihood would often be simple to maximize.

The E-step bridges this gap by computing the posterior distribution of the latent variables given the data and the current parameters. From it, the algorithm builds the expected complete-data log-likelihood, usually written as the Q function. The M-step then chooses the parameters that maximize Q, and the two steps repeat until the change in log-likelihood falls below a tolerance such as 1e-4 or 1e-6.

StepInputComputationOutput
E-stepData and current parametersPosterior over latent variablesResponsibilities or expected sufficient statistics
M-stepData and expected statisticsMaximize the expected complete-data log-likelihoodUpdated parameters
Convergence checkOld and new log-likelihoodCompare improvement with a toleranceStop or continue iterating
The two steps of one EM iteration

The guarantee of monotone improvement follows from a lower bound on the log-likelihood. The E-step makes this bound touch the true log-likelihood at the current parameters, and the M-step pushes the bound upward, so the true likelihood can only rise or stay the same.

Models commonly fitted with EM

EM applies to any model whose likelihood becomes tractable once hidden variables are filled in. The latent variable differs from model to model, but the structure of the iteration stays the same.

ModelLatent variableWhat the M-step updates
Gaussian mixture modelComponent that generated each pointMixing weights, means, covariances
Hidden Markov modelSequence of hidden statesTransition and emission probabilities
Naive Bayes with unlabeled dataMissing class labelsClass priors and feature likelihoods
Factor analysisLow-dimensional latent factorsLoadings and noise variances
Missing-data imputationUnobserved feature valuesDistribution parameters of the full data
Typical applications of the EM algorithm

For hidden Markov models, the E-step is computed with the forward-backward algorithm, and the whole procedure is known as the Baum-Welch algorithm. For Gaussian mixtures, the E-step produces responsibilities, the probability that each component generated each data point.

EM is best understood next to the methods it generalizes or competes with. The comparison with k-means clustering is especially instructive, because k-means is a limiting case of EM for Gaussian mixtures with equal spherical covariances and hard assignments.

MethodAssignment typeMain difference from EM
k-means clusteringHard, one cluster per pointIgnores uncertainty and covariance shape
Gradient ascent on likelihoodNot applicableNeeds step sizes; no automatic monotone guarantee
Variational inferenceApproximate posteriorReplaces the exact E-step with an optimized approximation
Gibbs samplingSampled assignmentsReturns a posterior sample, not a point estimate
Hard EMMost probable assignmentFaster but biased parameter estimates
How EM differs from neighboring approaches

Variational EM and stochastic EM extend the classic algorithm when the exact posterior is intractable or the data set is too large for full passes. Online variants update sufficient statistics from mini-batches, which suits streaming data.

Initialization and convergence in practice

EM converges to a local maximum or saddle point, not necessarily the global maximum, so the starting parameters strongly influence the result. Practitioners therefore treat initialization as part of the model design rather than an afterthought.

  • Multiple random restarts, often 5 to 20, followed by choosing the run with the highest final log-likelihood.
  • k-means initialization for Gaussian mixtures, which places the starting means in dense regions.
  • Covariance regularization, adding a small constant such as 1e-6 to diagonal entries to avoid singular matrices.
  • Log-domain computation with the log-sum-exp trick to prevent numerical underflow in the E-step.

Convergence is linear and can be slow, particularly when the hidden variables carry a large share of the missing information. Accelerated schemes such as ECM, which splits the M-step into simpler conditional steps, or quasi-Newton acceleration reduce the iteration count.

Choosing the number of components or states is a separate problem that EM does not solve. Information criteria such as BIC and AIC, or cross-validated likelihood, compare fitted models with different sizes.

Limitations and common failure modes

Most problems with EM come from the shape of the likelihood surface rather than from the algorithm itself. The table below links frequent symptoms to their causes and standard remedies.

SymptomLikely causeTypical fix
Likelihood grows without boundComponent collapses onto one pointRegularize covariances or set a variance floor
Very different results between runsPoor local optimaMore restarts and better initialization
Hundreds of iterations with tiny gainsWeakly identified parametersAcceleration, looser tolerance or a simpler model
NaN values after a few iterationsNumerical underflowCompute probabilities in log space
Components swap labels across runsLabel switching symmetryOrder components by a parameter before comparing
Diagnosing problems in EM fitting

A frequent misconception is that a higher likelihood always means a better model. With more components, EM can always reach a higher training likelihood, so overfitting must be controlled with penalties, priors or held-out evaluation.

Put simply

The expectation-maximization algorithm is a way to learn from data when part of the story is hidden. Imagine a bag of mixed coins from two mints, without knowing which coin came from where. You first make a rough guess about each mint. Then you estimate which mint each coin probably came from.

Next, you update your description of each mint using those estimates. Repeating these two moves steadily improves the guess. The key idea is that guessing the hidden part and refining the model in turns solves a problem that is too hard to solve in one go.

In practice

A retail analytics team wants to segment 40,000 customers using two features: average basket value and visits per month. Instead of k-means, it fits a Gaussian mixture model with EM, because the segments are elongated and overlap, and the team wants a probability of membership for each customer rather than a hard label.

The analysts standardize both features, initialize with k-means, run ten restarts for each candidate size from two to eight components and add a covariance floor of 1e-6. BIC is lowest at four components. The fitted model converges in about 60 iterations and reveals a small segment of high-value but infrequent shoppers. Because about 15 percent of customers have responsibilities split between two segments, marketing targets those customers with mixed campaigns, and the soft assignments prevent wasted offers that a hard clustering would have produced.