Notes on Expectation maximization, Brown University CS

 
From reference 1:
EM can be thought of as a deterministic version of Gibbs sampling. EM operates on the means or modes of unknown variables using expected sufficient statistics instead of sampling unknown variables as does Gibbs sampling. Both EM and Gibbs sampling are used for approximation with incomplete data. [1]

Define Q(theta | theta') as follows:

        Q(theta | theta') = E[log p(x, y | theta) | theta', y] 

where x is the random variable and we are taking the expectation with respect to the probability density p(x | theta',y).
The EM algorithm works as follows

1. Set i to 0 and choose theta_i arbitrarily.

2. Compute Q(theta | theta_i)  The E-step. 

3. Choose theta_i+1 to maximize Q(theta | theta_i)  The M-step. 

4. If theta_i != theta_i+1, then set i to i+1 and return to Step 2. 

The generalized EM (GEM) algorithm is the same except that instead of requiring maximization in Step 3 it only requires that the estimate be improved.


Reference:
(1) http://cs.brown.edu/research/ai/dynamics/tutorial/Documents/ExpectationMaximization.html