Expectation Maximization (EM) is an iterative method for finding the maximum likelihood estimates of the unknown parameters, , of a probabilistic model with latent variables, , given observed data, . The estimates are found by iteratively alternating between two steps: (1) the Expectation (E)-Step, in which the posterior distribution of the latent variables is calculated, using a conditional expectation given the data, and the current estimate of the model parameters, and (2) the Maximization (M)-Step, in which the model parameters are re-estimated using the distribution over .
An alternative explanation to EM gives the intuition behind alternating between variables in terms of lower bound maximization (Neal and Hinton, 1998, and Minka, 1998). In this formulation, the E-step is regarded as determining a lower bound for the posterior distribution, and the M-step as optimizing this bound, resulting in a better estimate for the model parameters.
EM has been shown to be a special case of Alternating Minimization.
Let be a set of observations resulting for a probabilistic model with unknown parameters, , and hidden variables . We wish to recover a set of parameters, that will maximize the likelihood function:
We assume that directly optimizing is difficult and that considering the full data is easier.
The algorithm will maximize the probability of the parameters given the data , marginalizing over the latent variables . This is done in two steps:
- E-Step: Determine the conditional expectation
- M-Step: Maximize this with respect to
EM can be seen as a process where the two steps increase the same function over alternating variables. Following the formulation of Neal and Hinton, 1998, the function being maximized is
where is the distribution over the latent variables, , and is the entropy of the distribution given by
Note that is defined for a fixed value of the observed data, .
The function can also be related to the Kullback-Lieber (KL) divergence between and as
Under this formulation, the two steps of the EM algorithm are defined as:
- E-Step: Find the distribution that maximizes
- M-Step: Find the values of that maximize
If you're curious to learn even more about the alternating minimization view of EM, check out the first several chapters of Wainwright and Jordan, http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf --Brendan 14:43, 11 October 2011 (UTC)