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. The conversion properties are discussed in McLachlan and Krishnan, 1997 in detail.

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.

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]\ \}$

Alternative Formulation

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

$F({\tilde {P}},\phi )=\operatorname {E} _{\tilde {P}}[p(X,Z|\phi )]+H({\tilde {P}})$

where ${\tilde {P}}$ is the distribution over the latent variables, $Z$, and $H({\tilde {P}})$ is the entropy of the distribution ${\tilde {P}}$ given by

$H({\tilde {P}})=-\operatorname {E} _{\tilde {P}}[\log {\tilde {P}}(Z)]$

Note that $F$ is defined for a fixed value of the observed data, $X$.

The function $F$ can also be related to the Kullback-Lieber (KL) divergence between ${\tilde {P}}(Z)$ and $p_{\phi }(Z)=p(Z|X,\phi )$ as

$F({\tilde {P}},\phi )=-D_{\text{KL}}({\tilde {P}}||p_{\phi })+\log L(\phi )$

Under this formulation, the two steps of the EM algorithm are defined as:

1. E-Step: Find the distribution ${\tilde {P}}$ that maximizes $F$

   ${\tilde {P}}_{(t)}={\underset {\tilde {P}}{\operatorname {arg\,max} }}\{\ F({\tilde {P}},\phi _{(t-1)})\ \}$

2. M-Step: Find the values of $\phi$ that maximize $F$

   $\phi _{(t)}={\underset {\phi }{\operatorname {arg\,max} }}\{\ F({\tilde {P}}_{(t)},\phi )\ \}$

Relevant Papers

Comments

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)