pythondemos/em.py.Dictionary of Applied Machine Learning
Updated on 2026-09-06
Typeset PDF version — the authoritative form of this entry
Python demo — a script that recomputes what this entry states and prints one line per check
The expectation–maximization (EM) algorithm is an iterative optimization method for approximately solving maximum likelihood optimization problems that are difficult to solve directly, such as fitting a Gaussian mixture model (GMM). Each iteration alternates an E-step, which computes the posterior distribution of an unobserved auxiliary attribute under the current model parameters, and an M-step, which minimizes a surrogate objective function derived from this posterior distribution. The surrogate upper-bounds the negative log-likelihood and is tight at the current iterate, so each iteration never increases the negative log-likelihood: EM is a majorize–minimize (MM) method. The method is a fixed-point iteration whose fixed points are model parameters that minimize their own surrogate.
B-fetchThe nightly minimum temperatures recorded over one year at the weather station of Krems an der Donau (Austria) scatter around two regimes — cold-season and warm-season nights. A Gaussian mixture model (GMM) with two components captures such a two-regime distribution, but maximizing its likelihood has no closed-form solution. The standard method for fitting it is the EM algorithm (Dempster et al., 1977): an iterative optimization method for approximately solving certain maximum likelihood optimization problems that are difficult to solve directly (Bishop, 2006, Sec. 9.4; Murphy, 2012, Sec. 11.4.7). To motivate the EM algorithm and explain its construction, consider a machine learning (ML) application involving a single observed data point with feature $\feature \in \featurespace$, where $\featurespace$ is a finite feature space. The data generation is modeled via a probabilistic model that consists of a random variable (RV) $\feature'$ with a probability mass function (pmf) $\pmf{\feature'}{\cdot;\weights}$. Here, the actual model parameters $\weights \in \paramspace$—used for the data generation via sampling from $\pmf{\feature'}{\cdot;\weights}$—are unknown. A widely used approach for estimating these model parameters is via the solutions of the following maximum likelihood problem: \begin{equation} \label{equ_def_ML_EM_dict} \min_{\weights \in \paramspace} - \log \pmf{\feature'}{\feature;\weights}. \end{equation} For some probabilistic models, such as a GMM, this optimization problem can be difficult to solve directly. As a work-around, one can often introduce an auxiliary attribute $\truelabel \in \labelspace$, generated via some RV $\truelabel'$. For a suitable choice of this attribute, the corresponding probabilistic model $\pmf{\feature',\truelabel'}{\cdot,\cdot;\weights}$ yields the following, much easier maximum likelihood problem: \begin{equation} \label{equ_def_complete_EM_dict} \min_{\weights \in \paramspace} - \log \pmf{\feature',\truelabel'}{\feature,\truelabel;\weights}. \end{equation} The attribute $\truelabel$ is introduced solely to simplify \(\eqref{equ_def_complete_EM_dict}\), but it is not observed in practice—only the feature $\feature$ is available. Thus, \(\eqref{equ_def_complete_EM_dict}\) cannot be solved directly, as the value of $\truelabel$ to plug into the pmf is unknown $ \pmf{\feature',\truelabel'}{\feature,\truelabel;\weights}$. The EM method resolves this dilemma by alternating between two steps. The E-step computes a “soft’’ estimate of the auxiliary attribute $\truelabel$: the posterior distribution $\pmf{\truelabel'|\feature'}{\cdot;\widehat{\weights}}$, i.e., the probability of each value of $\truelabel$ given the observed feature, under the current choice $\widehat{\weights}$ for the model parameters. The M-step minimizes a surrogate objective function derived from this posterior distribution. Together, one E-step and one M-step constitute one full iteration of the EM method. In more detail, the E-step produces the following function: \[ Q(\weights \mid \widehat{\weights}) \defeq - \sum_{\truelabel \in \labelspace} \pmf{\truelabel'|\feature'}{\truelabel;\widehat{\weights}} \log\!\Big( \pmf{\feature',\truelabel'}{\feature,\truelabel;\weights} /\pmf{\truelabel'|\feature'}{\truelabel;\widehat{\weights}} \Big), \] and the M-step minimizes $Q(\weights \mid \widehat{\weights})$ over $\weights \in \paramspace$. This function satisfies the following two key properties (Bishop, 2006, Sec. 9.4; Murphy, 2012, Sec. 11.4.7): 1) upper bound $Q(\weights\mid \widehat{\weights}) \geq - \log \pmf{\feature'}{\feature;\weights}$ for all $\weights \in \paramspace$; and 2) tightness $Q(\widehat{\weights}\mid \widehat{\weights}) =- \log \pmf{\feature'}{\feature;\widehat{\weights}}.$ To summarize, during each iteration, EM minimizes an upper-bounding surrogate objective function that is tight at the current iterate $\widehat{\weights}$. Thus, EM is a majorize–minimize (MM) method for approximately solving \(\eqref{equ_def_ML_EM_dict}\).
B-emThe EM method is also a fixed-point iteration $\widehat{\weights}^{(\iteridx+1)} = \fixedpointop\big(\widehat{\weights}^{(\iteridx)}\big)$ with the operator \[\fixedpointop(\widehat{\weights}) \defeq \argmin_{\weights \in \paramspace} Q(\weights \mid \widehat{\weights})\text{.}\] By the upper-bound and tightness properties above, each application of $\fixedpointop$ never increases the objective function of \(\eqref{equ_def_ML_EM_dict}\) — the negative log-likelihood — so monotone descent, rather than a contractive operator property, justifies convergence. The fixed points of $\fixedpointop$ are model parameters that minimize their own surrogate: there, the surrogate touches the negative log-likelihood from above, so no further descent step is available to the method. The above construction and analysis of EM can be extended to more general settings involving multiple data points and infinite feature spaces such as $\reals^{\featuredim}$ (see (Murphy, 2012, Sec. 11.4.7) for further details).
B-fitFig. 1 shows EM at work on real data: a
GMM with two components, fitted to the $366$ nightly
minimum temperatures of 2024 at Krems, recovers the
cold-season and warm-season regimes, and the negative
log-likelihood descends monotonically to a fixed point.
pythondemos/em.py.
@misc{dictml_em,
author = {Jung, Alexander and Olioumtsevits, Konstantina and Schnoor, Ekkehard},
title = {expectation–maximization},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-09-11},
url = {https://dictionaryofml.org/terms/em.html}
}