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.
| Step | Input | Computation | Output |
|---|---|---|---|
| E-step | Data and current parameters | Posterior over latent variables | Responsibilities or expected sufficient statistics |
| M-step | Data and expected statistics | Maximize the expected complete-data log-likelihood | Updated parameters |
| Convergence check | Old and new log-likelihood | Compare improvement with a tolerance | Stop or continue iterating |
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.
| Model | Latent variable | What the M-step updates |
|---|---|---|
| Gaussian mixture model | Component that generated each point | Mixing weights, means, covariances |
| Hidden Markov model | Sequence of hidden states | Transition and emission probabilities |
| Naive Bayes with unlabeled data | Missing class labels | Class priors and feature likelihoods |
| Factor analysis | Low-dimensional latent factors | Loadings and noise variances |
| Missing-data imputation | Unobserved feature values | Distribution parameters of the full data |
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 compared with related methods
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.
| Method | Assignment type | Main difference from EM |
|---|---|---|
| k-means clustering | Hard, one cluster per point | Ignores uncertainty and covariance shape |
| Gradient ascent on likelihood | Not applicable | Needs step sizes; no automatic monotone guarantee |
| Variational inference | Approximate posterior | Replaces the exact E-step with an optimized approximation |
| Gibbs sampling | Sampled assignments | Returns a posterior sample, not a point estimate |
| Hard EM | Most probable assignment | Faster but biased parameter estimates |
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.
| Symptom | Likely cause | Typical fix |
|---|---|---|
| Likelihood grows without bound | Component collapses onto one point | Regularize covariances or set a variance floor |
| Very different results between runs | Poor local optima | More restarts and better initialization |
| Hundreds of iterations with tiny gains | Weakly identified parameters | Acceleration, looser tolerance or a simpler model |
| NaN values after a few iterations | Numerical underflow | Compute probabilities in log space |
| Components swap labels across runs | Label switching symmetry | Order components by a parameter before comparing |
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.