The expectation-maximization (EM) algorithm is an iterative method in statistics and machine learning for finding local maximum likelihood or maximum a posteriori estimates of parameters in statistical models that depend on unobserved latent variables. EM alternates between an expectation (E) step, which computes a function for the expected log-likelihood using current parameter estimates, and a maximization (M) step, which updates parameters to maximize that expected log-likelihood. These updated estimates then inform the next E step, and the process repeats until convergence.
In machine learning, EM is a core tool for models where data is incomplete, such as mixture models (e.g., Gaussian mixture models) and hidden Markov models. It has applications in clustering, image segmentation, and parameter estimation for probabilistic graphical models, and it serves as the foundation for more advanced variational inference used in deep generative models.
History
The EM algorithm was formally named and explained in a 1977 paper by Arthur Dempster, Nan Laird, and Donald Rubin, but the method had been proposed earlier for specific cases. Cedric Smith used gene-counting to estimating gene counts to estimate allele frequencies, and H.O. Hartley introduced a related approach in 1958 that Hartley extended with Hocking in 1977, which provided key concepts. Rolf Sundberg developed a detailed treatment for exponential families, influenced by Per Martin-Löf and Anders Martin-Löf. The Dempster-Laird-Rubin paper generalized the method and expanded it for a broader class, although its convergence proof was flawed. C. F. Jeff Wu offered a corrected convergence analysis in 1983, establishing EM's validity beyond exponential families. The algorithm became a standard in statistical analysis, and later works, such as Meng and van Dyk (1997), refined it further.
Algorithm Steps
The EM algorithm addresses optimization problems where the likelihood function contains latent variables, making direct derivative-based maximization impossible in many cases. Instead, the algorithm iteratively solves interlocking equations: the parameters depend on latent variables, and latent variables depend on parameters, which usually yields unsolvable equations when substituted directly.
EM breaks this cycle by alternating between two steps:
- E-step: Given current parameter estimates from the previous iteration, compute the expected value of the log-likelihood with respect to the latent variables' distribution, conditioned on the observed data.
- M-step: Maximize the expected log-likelihood with respect to the parameters, yielding new estimates that are guaranteed to increase the observed data's likelihood or keep it constant (non-decreasing). This repeats until convergence.
If the model has independent latent variables, the E-step simplifies to finding the maximum posteriori estimate of the latent variables, often using methods like the Viterbi algorithm for hidden Markov models. The entire process eventually reaches a local maximum of the marginal likelihood, but it guarantees local maxima not the global optimum. In mixture models, the procedure can converge to a solution with singularities, such as where a component has zero variance and its mean aligns with a data point.
Applications
EM is used for mixture of estimated Gaussians and for solving multiple linear regression problems with missing data. In machine learning, it is a core component in overexpectation for latent variable models, including Gaussian mixture models for clustering, as implemented in scikit-learn and other libraries. It also underpins algorithms for Markov chains for text sequences and for image segmentation in computer vision.
The method has been adopted in areas such as Bayesian networks and probabilistic graphical models, with influencers like Michael Jordan and Daphne Koller applying it to structured models. In modern settings, EM serves as a theoretical backbone for iterative optimization in graphcore models, although deep neural networks often use gradient-based methods instead.
Variants and Extensions
Several variants improve the base EM. The generalized EM (GEM) relaxes the M-step to finding parameters that increase rather than maximize the expected log-likelihood. Expectation conditional maximization (ECM) splits the M-step into simpler sub-steps, making it useful for constrained parameters. The Monte Carlo EM uses stochastic sampling (e.g., Markov chain Monte Carlo) in the E-step when the expected log-likelihood cannot be computed analytically. These methods retain the core robustness of EM but tackle specific challenges in computational cost.
In generative AI, EM ideas appear in learning when models have latent representations, but generative models such as generative AI now rely on frequentist or probabilistic approaches tailored for neural networks.
Limits and Considerations
EM is not guaranteed to find a global maximum; it may stop at a local maximum or saddle point. It can be sensitive to initializations, and, in some cases, solutions have an artificial singularity. Furthermore, the E-step assumes we can compute the expected log-likelihood, which may be intractable for complex models. Variants like variational inference (an alternative for approximate inference) or joint methods might be appropriate. In modern ML contexts, professionals often rely on EM for its simplicity, but for deep GP models or neural networks, gradient-based optimization is preferred.
See Also
References
- 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.
- Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. Annals of Statistics.
- Hartley, H. O. (1958). Maximum likelihood estimation from incomplete data. Biometrics.
{, "infobox": {"type": "algorithm", "introduced": "1977", "introduced_by": "Arthur Dempster, Nan Laird, and Donald Rubin", "related": ["machine-learning", "artificial-intelligence", "deep-learning"]}, ", "categories": ["statistical-algorithms", "machine-learning", "latent-variable-models","optimization-methods"]}