Expectation Maximization EM Algorithm

The EM algorithm is used to find the (locally) maximum likelihood parameters of a statistical model in cases where the equations cannot be solved directly. Typically these models involve latent variables in addition to unknown parameters and known data observations. That is, either there are missing values among the data, or the model can be formulated more simply by assuming the existence of additional unobserved data points. 

For example, a mixture model can be described more simply by assuming that each observed data point has a corresponding the unobserved data point, or latent variable, specifying the mixture component that each data point belongs to. Finding a maximum likelihood solution typically requires

taking the derivatives of the likelihood function with respect to all the unknown values: the parameters and the latent variables, and simultaneously solving the resulting equations. In statistical models with latent variables, this usually is not possible. Instead, the result is typically a set of interlocking equations in which the solution to the parameters requires the values of the latent variables and vice versa, but substituting one set of equations into the other produces an unsolvable equation. 

One can simply pick arbitrary values for one of the two sets of unknowns, use them to estimate the second set, then use these new values to find a better estimate of the first set, and then keep alternating between the two until the resulting values both converge to fixed points. It’s not obvious that this will work at all, but in fact, it can be proven that in this particular context it does, and that the derivative of the likelihood is (arbitrarily close to) zero at that point, which in turn means that the point is either a maximum or a saddle point. In general, there may be multiple maxima, and there is no guarantee that the global maximum will be found.