The Expectation Maximization (EM) algorithm is a fast
maximum likelihood parameter estimation algorithm for partially observed data.

Suppose that
D is some observed data, U is some unobserved data,
and T is a parameterisation for a joint probabilistic model for (D,U).
The goal is to choose T so as to maximize P(D|T)=sum(U) P(D,U|T).

Starting from an initial guess at T, 
EM obtains the next estimate, T', via a two-step procedure:

(1: "The E-step") Estimate the posterior probability distribution, P(U|D,T),
for the missing data given the current parameterisation.

(2: "The M-step") Maximize the following functional with respect to T'

Q(T'|D,T) = sum(U) P(U|D,T) log P(D,U|T')

(That is, maximize the expected log-likelihood of the observed and unobserved data,
using the posterior distribution over U computed during the E-step.)

Often the E-step reduces to the computation of certain expectation statistics
that characterise the unobserved data sufficiently to proceed with the M-step.

The K-means clustering algorithm can be viewed as an EM algorithm applied
to a mixture-of-Gaussians model.

The EM algorithm can also be viewed as a two-step optimization of
a single variational functional (see e.g. work of Radford Neal).
----
CategoryMath CategoryAlgorithm