expectation-maximization algorithm

In statistical computing, an expectation-maximization (EM) algorithm is an algorithm for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an expectation (E) step, which computes the expected value of the latent variables, and a maximization (M) step, which computes the maximum likelihood estimates of the parameters given the data and setting the latent variables to their expectation. Let the observed variables be known as

y

and the latent variables as

z

. Together,

y

and

z

form the complete data. Assume that

p

is a joint model of the complete data with parameters

\theta

p(y,x | \theta)

. An EM algorithm will then iteratively improve an initial estimate

\theta_0

and construct new estimates

\theta_1

through

\theta_N

. An individual re-estimation step that derives

\theta_{n+1}

from

\theta_n

takes the following form (shown for the discrete case; the continuous case is similar):

\theta_{n+1} = \arg\max_{\theta}

  \sum_z   p \left(z \,|\, y, \theta_n \right)   \log p \left(y, z \,|\, \theta \right)

In other words,

\theta_{n+1}

is the value that maximizes (M) the expectation (E) of the complete data log-likelihood with respect to the conditional distribution of the latent data under the previous parameter value. This expectation is usually denoted as

Q(\theta)

Q(\theta) = \sum_z

  p \left(z \,|\, y, \theta_n \right)  \log p \left(y, z \,|\, \theta \right)

Speaking of an expectation (E) step is a bit of a misnomer. What is calculated in the first step are the fixed, data-dependent parameters of the function

Q

. Once the parameters of

Q

are known, it is fully determined and is maximized in the second (M) step of an EM algorithm. It can be shown that an EM iteration does not decrease the observed data likelihood function, and that the only stationary points of the iteration are the stationary points of the observed data likelihood function. In practice, this means that an EM algorithm will converge to a local maximum of the observed data likelihood function. EM is particularly useful when maximum likelihood estimation of a complete data model is easy. If closed-form estimators exist, the M step is often trivial. A classic example is maximum likelihood estimation of a finite mixture of Gaussians, where each component of the mixture can be estimated trivially if the mixing distribution is known. "Expectation-maximization" is a description of a class of related algorithms, not a specific algorithm; EM is a recipe or meta-algorithm which is used to devise particular algorithms. The Baum-Welch algorithm is an example of an EM algorithm applied to hidden Markov models. Another example is the EM algorithm for fitting a mixture density model. An EM algorithm can also find maximum a posteriori (MAP) estimates, by performing MAP estimation in the M step, rather than maximum likelihood. There are other methods for finding maximum likelihood estimates, such as gradient descent, conjugate gradient or variations of the Gauss-Newton method.

References

Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977.
Radford Neal, Geoffrey Hinton. "A view of the EM algorithm that justifies incremental, sparse, and other variants". In Michael I. Jordan (editor), Learning in Graphical Models pp 355-368. Cambridge, MA: MIT Press, 1999.

Expectation-maximization Algorithm

References

See also