Expectation Maximization

Expectation Maximization (EM) is an iterative method for finding the maximum likelihood estimates of the unknown parameters, $\phi$, of a probabilistic model with latent variables, $Z$, given observed data, $X$. 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 $Z$.

Literature

Dempster et al., 1997 formalize the EM algorithm and provide a proof of convergence.

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 beter estimate for the model parameters.

Algorithm

Let $X$ be a set of observations resulting for a probabilistic model with unknown parameters, $\phi$, and hidden variables $Z$. We wish to recover a set of parameters, $\phi$ that will maximize the likelihood function:

$L(\phi )=p(X|\phi )=\sum _{Z}p(X,Z|\phi )$

We assume that directly optimizing $p(X|\phi )$ is difficult and that considering the full data $p(X,Z|\phi )$ is easier.

The algorithm will maximize the probability of the parameters $\phi$ given the data $X$, marginalizing over the latent variables $Z$. This is done in two steps:

1. E-Step: Determine the conditional expectation

   $\operatorname {E} _{Z|X,\phi _{(t)}}\left[\ln p(X,Z|\phi )\right]$

2. M-Step: Maximize this with respect to $\phi$

   $\phi _{(t+1)}={\underset {\phi }{\operatorname {arg\,max} }}\{\ \operatorname {E} _{Z|X,\phi _{(t)}}\left[\ln p(X,Z|\phi )\right]\ \}$