Search code examples
machine-learningstatisticsnlpexpectation-maximization

How to prove the convergence of EM?

Can you anybody explain how to prove the convergence of the Expectation Maximization algorithm?

For example EM for coins problems: https://math.stackexchange.com/questions/25111/how-does-expectation-maximization-work

Solution

  • EM algorithm does maximum likelihood estimation. If you look at the log likelihood, it's not true that both E and M steps always maximize it. However, if you look at the negative free energy function, both of them always maximizes it, with respect to different things though (so kind of like coordinate descent). So yes, EM algorithm always converges, even though it might converge to bad local extrema, which is a different issue.
    Take a look at the classical paper www.cs.toronto.edu/~radford/ftp/emk.pdf to learn more yourself.