Expectation Maximization

Given a joint distribution \(P(X,Z|\theta)\) , Expectation-Maximization finds \(\theta\) that maximizes \(p(X|\theta)\) . EM is guaranteed to improve the likelihood monotonically (proof?) and converges to a local maxima of the likelihood. The method was introduced in Maximum Likelihood from Incomplete Data Via the EM Algorithm , my notes follow Bishop's PRML.

\(Z\) is the latent random variable, and \(\theta\) is the parameter vector of the model.

  1. Initialize parameters

    \[ \theta^{\text{old}} \leftarrow \{\text{initial value}\} \]

  2. E step

    Evaluate the posterior latent distribution given current parameter guess and observed samples \(\mathrm{X}\) .

    \[ p(Z | X, \theta^{\text{old}}) \]

  3. M step

    Find \(\theta^{\text{new}}\) that maximizes the expected likelihood \(\ln p(X,Z|\theta)\) under the posterior latent \( p(Z | X, \theta^{\text{old}}) \) .

    \[ \theta^{\text{new}} = \sum_z p(Z | X, \theta^{\text{old}}) \ln p(X,Z|\theta) \]

  4. Check for convergence, and repeat or exit

    Check if either the likelihood or \(\theta\) hasn't changed significantly in the last EM iteration. If not, set \( \theta^{\text{old}} \leftarrow \theta^{\text{new}}\) and go to step 2.