# expectation–maximization (EM)

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-08. [HTML](https://dictionaryofml.org/terms/em.html) · [typeset PDF](https://dictionaryofml.org/terms/em.pdf) · [LaTeX](https://dictionaryofml.org/terms/em.tex) · [Python demo](https://dictionaryofml.org/terms/em.py) · [notebook](https://dictionaryofml.org/terms/em.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

The expectation–maximization (EM) algorithm is an iterative optimization method for a particular class of maximum likelihood problems. In particular, EM is useful for probabilistic models that involve observed and unobserved (or latent) attributes of a data point. Each iteration of the EM algorithm alternates an E-step with an M-step. The E-step computes the posterior distribution of the unobserved attributes under the current model parameters. The M-step minimizes the negative log-likelihood of the complete data points averaged under this posterior distribution, which for many probabilistic models has a closed form. The EM algorithm is an instance of a majorize–minimize method. A canonical soft clustering method uses the EM algorithm to learn the model parameters of a Gaussian mixture model.

## Definition

The 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 probabilistic model for such data points has, besides the observed temperature, an unobserved attribute: the regime a night belongs to. Fig. 1 shows the histogram of the temperatures together with a Gaussian mixture model consisting of a separate normal distribution for each regime. The EM algorithm (Dempster et al., 1977) is an iterative optimization method for approximately solving maximum likelihood optimization problems for probabilistic models with an unobserved attribute (Bishop, 2006, Sect. 9.4; Hastie et al., 2009, Sect. 8.5; Murphy, 2012, Sect. 11.4.7).

![Figure 1 of the entry em](https://dictionaryofml.org/terms/fig/em-fig1.svg)

*Figure 1: Histogram of the $366$ nightly minimum temperatures of 2024 at the weather station Krems an der Donau, with the two-component Gaussian mixture model learned by EM (solid curve) and its two weighted components, the cold-season component (dashed curve) and the warm-season component (dotted curve). Each night belongs to one of the two regimes, but which one is not observed. Data generated by pythondemos/em.py*

Consider a dataset $\mathcal{D} = \{{\mathbf x}^{(1)}, \ldots,
{\mathbf x}^{(m)}\}$ whose data points are realizations of independent and identically distributed RVs. The underlying probability distribution is a probabilistic model $p^{({\mathbf x}',y')}\left({\mathbf x},y;{\mathbf w}\right)$ for the observed feature vector ${\mathbf x}$ and an unobserved attribute $y$ with values in a finite set $\mathcal{Y}$. This probabilistic model is a family of probability distributions parameterized by model parameters ${\mathbf w}$ in a parameter space $\mathcal{W}$. Maximum likelihood is an instance of empirical risk minimization: it minimizes the empirical risk

\begin{equation}
\tag{1}
\widehat{L}\big({\mathbf w}|\mathcal{D}\big) :=
- \frac{1}{m} \sum_{r=1}^{m}
\ln \sum_{y \in \mathcal{Y}}
p^{({\mathbf x}',y')}\left({\mathbf x}^{(r)},y;{\mathbf w}\right)\text{,}
\end{equation}

the average negative log-likelihood of the observed feature vectors. The sum inside the logarithm is what makes Eq. (1) hard to minimize directly: if the attributes $y^{(r)}$ were observed, the empirical risk would be an average of $-\ln p^{({\mathbf x}',y')}\left({\mathbf x}^{(r)},y^{(r)};{\mathbf w}\right)$, which for many probabilistic models, among them the Gaussian mixture model, has a closed-form minimizer (Bishop, 2006, Sect. 9.3.1).

The EM algorithm solves the maximum likelihood problem Eq. (1) by alternating two steps, which together form one iteration. The E-step computes, for every data point, the posterior distribution of the unobserved attribute under the current model parameters $\widehat{{\mathbf w}}$,

\begin{equation}
\tag{2}
p^{(y'|{\mathbf x}')}\left(y;\widehat{{\mathbf w}}\right)
= \frac{p^{({\mathbf x}',y')}\left({\mathbf x}^{(r)},y;\widehat{{\mathbf w}}\right)}
{\sum_{y'' \in \mathcal{Y}}
p^{({\mathbf x}',y')}\left({\mathbf x}^{(r)},y'';\widehat{{\mathbf w}}\right)}
\quad \text{for } y \in \mathcal{Y}
\text{ and } r = 1, \ldots, m\text{.}
\end{equation}

These posterior distributions fix the surrogate that the E-step of Algorithm 1 forms, the empirical risk of the complete data points averaged under them,

\begin{equation}
\tag{3}
Q({\mathbf w} \mid \widehat{{\mathbf w}}) :=
- \frac{1}{m} \sum_{r=1}^{m}
\sum_{y \in \mathcal{Y}}
p^{(y'|{\mathbf x}')}\left(y;\widehat{{\mathbf w}}\right)
\ln \frac{p^{({\mathbf x}',y')}\left({\mathbf x}^{(r)},y;{\mathbf w}\right)}
{p^{(y'|{\mathbf x}')}\left(y;\widehat{{\mathbf w}}\right)}\text{.}
\end{equation}

The M-step minimizes this surrogate over ${\mathbf w} \in
\mathcal{W}$. Algorithm 1 states the method in full.

![Algorithm 1 of the entry em](https://dictionaryofml.org/terms/fig/em-alg1.svg)

*Algorithm 1: Expectation-maximization*

The EM algorithm is a majorize–minimize method: each iteration minimizes a surrogate $Q({\mathbf w} \mid \widehat{{\mathbf w}})$ of the empirical risk Eq. (1). The surrogate Eq. (3) has three properties (Bishop, 2006, Sect. 9.4, whose lower bound on the log-likelihood is this surrogate written for the negative log-likelihood; Hunter and Lange, 2004, Sect. 2). First, it majorizes the empirical risk, $Q({\mathbf w} \mid \widehat{{\mathbf w}}) \geq
\widehat{L}\big({\mathbf w}|\mathcal{D}\big)$ for all ${\mathbf w} \in \mathcal{W}$, by Jensen's inequality applied to the concave logarithm. Second, it is tight at the current iterate, $Q(\widehat{{\mathbf w}} \mid \widehat{{\mathbf w}})
= \widehat{L}\big(\widehat{{\mathbf w}}|\mathcal{D}\big)$. Third, it is minimized exactly by the M-step.

Any model parameters ${\mathbf w}^{(t+1)}$ that minimize the surrogate built at ${\mathbf w}^{(t)}$ therefore satisfy $\widehat{L}\big({\mathbf w}^{(t+1)}|\mathcal{D}\big) \leq
Q({\mathbf w}^{(t+1)} \mid {\mathbf w}^{(t)}) \leq
Q({\mathbf w}^{(t)} \mid {\mathbf w}^{(t)}) =
\widehat{L}\big({\mathbf w}^{(t)}|\mathcal{D}\big)$: no iteration increases the empirical risk (Dempster et al., 1977, Thm. 1).

The monotone decrease of the empirical risk Eq. (1) along the EM iterates yields a stopping criterion: the iteration stops as soon as the decrease of the empirical risk achieved by the last iteration falls below a given threshold (Bishop, 2006, Sect. 9.2.2). The empirical risk Eq. (1) is in general a non-convex function of the model parameters, and EM might converge to a local minimum (Bishop, 2006, Sect. 9.2.2). It is therefore typically run several times with different initializations, keeping the run with the smallest empirical risk (Murphy, 2012, Sect. 11.3.2).

The EM algorithm is a fixed-point iteration $\widehat{{\mathbf w}}^{(t+1)} =
\mathcal{F}\big(\widehat{{\mathbf w}}^{(t)}\big)$. The operator $\mathcal{F}$ maps the current model parameters $\widehat{{\mathbf w}}$ to the result of one E-step followed by one M-step. The E-step Eq. (2) at $\widehat{{\mathbf w}}$ builds the surrogate $Q(\cdot \mid \widehat{{\mathbf w}})$, and the M-step Eq. (3) minimizes it,

$$
\mathcal{F}(\widehat{{\mathbf w}}) :=
\mathop{\mathrm{arg\,min}}_{{\mathbf w} \in \mathcal{W}}
Q({\mathbf w} \mid \widehat{{\mathbf w}})\text{.}
$$

The fixed points of $\mathcal{F}$ are model parameters that minimize their own surrogate: there, the surrogate touches the empirical risk from above, so no further descent step is available. If the empirical risk and the surrogate are differentiable and the fixed point $\widehat{{\mathbf w}}$ lies in the interior of $\mathcal{W}$, the gradient of the empirical risk vanishes at $\widehat{{\mathbf w}}$. Indeed, the difference $Q({\mathbf w} \mid \widehat{{\mathbf w}}) -
\widehat{L}\big({\mathbf w}|\mathcal{D}\big)$ is nonnegative for all ${\mathbf w}$ and zero at ${\mathbf w} = \widehat{{\mathbf w}}$, so its gradient vanishes there, and the gradient of $Q(\cdot \mid
\widehat{{\mathbf w}})$ vanishes at its interior minimum $\widehat{{\mathbf w}}$. Under the conditions of Wu (1983, Thm. 2), every limit point of the EM iterates is such a stationary point of the empirical risk.

EM is used to learn the model parameters of a Gaussian mixture model, where the unobserved attribute of a data point is its cluster index $I^{(r)} \in \{1, \ldots,
k\}$ and the model parameters are the cluster probabilities $p_{c}$, means ${\boldsymbol \mu}^{(c)}$, and covariance matrices $\mathbf{C}^{(c)}$ (Bishop, 2006, Sect. 9.2.2). The E-step Eq. (2) becomes the degree of belonging

\begin{equation}
\tag{4}
u_{c}^{(r)} :=
\mathbb{P}\left(I^{(r)} = c \mid {\mathbf x}^{(r)}\right) =
\frac{p_{c}\,
\mathcal{N}\left({\boldsymbol \mu}^{(c)},\mathbf{C}^{(c)}\right)({\mathbf x}^{(r)})}
{\sum_{c'=1}^{k} p_{c'}\,
\mathcal{N}\left({\boldsymbol \mu}^{(c')},\mathbf{C}^{(c')}\right)({\mathbf x}^{(r)})}\text{,}
\end{equation}

and minimizing the surrogate Eq. (3) yields the M-step in closed form. The cluster probability $p_{c}$ is the average of $u_{c}^{(r)}$ over the data points, while ${\boldsymbol \mu}^{(c)}$ and $\mathbf{C}^{(c)}$ are the mean and covariance matrix of the feature vectors weighted by $u_{c}^{(r)}$. The learned degrees of belonging Eq. (4) constitute a soft clustering. Fixing every cluster probability at $1/k$ and every covariance matrix at $\sigma^{2} \mathbf{I}$, a multiple of the identity matrix $\mathbf{I}$ with a common $\sigma^{2}$ that shrinks towards $0$ turns the degrees of belonging into $0$ or $1$, and EM reduces to Lloyd's algorithm for k-means (Bishop, 2006, Sect. 9.3.2).

Consider next, as an illustration of the EM algorithm, the Gaussian mixture model of Fig. 1 for the temperature dataset. The feature of a data point is the nightly minimum temperature $x \in \mathbb{R}$, and its unobserved attribute is the regime $y \in \{\mathrm{cold}, \mathrm{warm}\}$. The model parameters are the probabilities $p_{\mathrm{cold}}$, $p_{\mathrm{warm}} = 1 - p_{\mathrm{cold}}$ of the two regimes, the means $\mu_{\mathrm{cold}}$, $\mu_{\mathrm{warm}}$ and the variances $\sigma^{2}_{\mathrm{cold}}$, $\sigma^{2}_{\mathrm{warm}}$ of the two normal distributions, so ${\mathbf w} = (p_{\mathrm{cold}}, p_{\mathrm{warm}},
\mu_{\mathrm{cold}}, \mu_{\mathrm{warm}},
\sigma^{2}_{\mathrm{cold}}, \sigma^{2}_{\mathrm{warm}})^{\top}
\in \mathbb{R}^{6}$. The E-step Eq. (2) computes for every night the probability of the cold regime, and the M-step Eq. (3) recomputes ${\mathbf w}$ as averages weighted by these probabilities. On the $366$ nights of 2024, EM learns $p_{\mathrm{cold}} = 0.83$, $\mu_{\mathrm{cold}} = 5.1$, $\mu_{\mathrm{warm}} = 17.2$, $\sigma^{2}_{\mathrm{cold}} = 39.7$, and $\sigma^{2}_{\mathrm{warm}} = 3.3$.

Fig. 2 shows the majorize–minimize view for this Gaussian mixture model as the cold-season mean $\mu_{\mathrm{cold}}$ varies, while $p_{\mathrm{cold}}$, $\mu_{\mathrm{warm}}$ and $\sigma^{2}_{\mathrm{warm}}$ are fixed at their learned values and $\sigma^{2}_{\mathrm{cold}}$ is fixed at $16$. The empirical risk is then a function of $\mu_{\mathrm{cold}}$ alone, and so is each surrogate. Each surrogate lies above the empirical risk, touches it at its iterate, and its minimizer is the next iterate. Fig. 3 shows how the empirical risk decreases monotonically as the EM iterations proceed.

![Figure 2 of the entry em](https://dictionaryofml.org/terms/fig/em-fig2.svg)

*Figure 2: The majorize–minimize view of EM for the two-component Gaussian mixture model of Fig. 1 with a single free model parameter, the cold-season mean $\mu_{\mathrm{cold}}$. The other model parameters are fixed: $p_{\mathrm{cold}}$, $\mu_{\mathrm{warm}}$, and $\sigma^{2}_{\mathrm{warm}}$ at their learned values, and $\sigma^{2}_{\mathrm{cold}} = 16$, smaller than its learned value so that the surrogates differ visibly from the empirical risk. Solid: the empirical risk as a function of $\mu_{\mathrm{cold}}$. Dashed, dotted and dash-dotted: the surrogates built by the E-step at the first three iterates ${\mathbf w}^{(0)}, {\mathbf w}^{(1)}, {\mathbf w}^{(2)}$ of EM on $\mu_{\mathrm{cold}}$, starting from $\mu_{\mathrm{cold}} = -8$. Each surrogate lies above the empirical risk, touches it at its iterate, and is minimized at the next iterate. Data generated by pythondemos/em.py*

![Figure 3 of the entry em](https://dictionaryofml.org/terms/fig/em-fig3.svg)

*Figure 3: EM learning all six model parameters of the two-component Gaussian mixture model of Fig. 1 on the $366$ nightly minimum temperatures of 2024 at Krems: the negative log-likelihood decreases monotonically as the iterations proceed and settles at a fixed point of the EM operator $\mathcal{F}$. Data generated by pythondemos/em.py*

**See also:** maximum likelihood, probabilistic model, [empirical risk minimization](https://dictionaryofml.org/terms/erm.html), majorize–minimize, fixed-point iteration, fixed point, posterior distribution, [Gaussian mixture model](https://dictionaryofml.org/terms/gmm.html), soft clustering, degree of belonging, [$k$-means](https://dictionaryofml.org/terms/kmeans.html), Lloyd's algorithm, optimization problem.

## References

- Dempster et al. (1977). Maximum likelihood from incomplete data via the EM algorithm. *J. Roy. Statist. Soc.: Ser. B (Methodological)*. <https://doi.org/10.1111/j.2517-6161.1977.tb01600.x>
- Bishop (2006). Pattern Recognition and Machine Learning. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-45528-0>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Murphy (2012). Machine Learning: A Probabilistic Perspective. *MIT Press*.
- Hunter and Lange (2004). A Tutorial on MM Algorithms. *Amer. Statistician*. <https://doi.org/10.1198/0003130042836>
- Wu (1983). On the convergence properties of the EM algorithm. *Ann. Statist.*. <https://doi.org/10.1214/aos/1176346060>

## Cite this entry

```bibtex
@misc{dictml_em,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {expectation–maximization (EM)},
  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-11-11},
  url = {https://dictionaryofml.org/terms/em.html}
}
```