28
$\begingroup$

What is the difference between the algorithms EM (Expectation Maximization) and Gradient Ascent (or descent)? Is there any condition under which they are equivalent?

$\endgroup$
21
$\begingroup$

From:

Xu L and Jordan MI (1996). On Convergence Properties of the EM Algorithm for Gaussian Mixtures. Neural Computation 2: 129-151.

Abstract:

We show that the EM step in parameter space is obtained from the gradient via a projection matrix P, and we provide an explicit expression for the matrix.

Page 2

In particular we show that the EM step can be obtained by pre-multiplying the gradient by a positive denite matrix. We provide an explicit expression for the matrix ...

Page 3

That is, the EM algorithm can be viewed as a variable metric gradient ascent algorithm ...

This is, the paper provides explicit transformations of the EM algorithm into gradient-ascent, Newton, quasi-Newton.

From wikipedia

There are other methods for finding maximum likelihood estimates, such as gradient descent, conjugate gradient or variations of the Gauss–Newton method. Unlike EM, such methods typically require the evaluation of first and/or second derivatives of the likelihood function.

$\endgroup$
  • 6
    $\begingroup$ This answer seems to hint that EM and gradient descent are basically the same algorithm, with transformations available to switch from one algorithm to the other. This is definitely not true in general, and strongly depends on the generative model taken into consideration. The paper cited only draws conclusions for Gaussian mixture models (which are relatively simple generative models), and rightly so. In my (admittedly limited) experience, when the model is highly non-linear and the role of the latent variables is important, EM is the only way to derive sensible update rules. $\endgroup$ – blue Sep 12 '16 at 21:47
10
$\begingroup$

No, they are not equivalent. In particular, EM convergence is much slower.

If you are interested in an optimization point-of-view on EM, in this paper you will see that EM algorithm is a special case of wider class of algorithms (proximal point algorithms).

$\endgroup$
  • 3
    $\begingroup$ Or for a similar sort of idea, Hinton and Neal (1998) $\endgroup$ – conjugateprior Dec 11 '12 at 23:33
  • 2
    $\begingroup$ "EM convergence is much slower"; this is not well defined, and certainly not generally true. EM algorithms are an entire class of algorithms. For many problems, a certain EM algorithm is the state of the art. $\endgroup$ – Cliff AB Jun 30 '16 at 23:15
  • $\begingroup$ @CliffAB please don‘t hesitate to elaborate on this, I would love to read your arguments — as I read this answer from 4 years, I realize that I wouldn’t answer this today. Since then I discovered that in many cases, the EM is a gradient ascent with a 'learning rate' parameter depending on the current point... (I may edit this answer in a while to point results of the sort) $\endgroup$ – Elvis Jul 1 '16 at 6:01
  • $\begingroup$ "Slower convergence" could be defined in term of convergence rate. The convergence rate of a gradient ascent will depend on the 'learning rate', which is not easy to chose, making gradient ascent difficult in many cases. However I still have a gut feeling that while EM can be in some cases the only feasible algorithm (the derivatives of the likelihood or the likelihood itself being hard to compute), its convergence rate is poor, as compared to a Newton like method. $\endgroup$ – Elvis Jul 1 '16 at 6:01
  • $\begingroup$ "The" EM algorithm is really an entire class of algorithms; one in which the original target function is difficult to optimize, but if some other variable was known, the solution would be much easier (typically in closed form). The basic outline is to fill in the expected variable conditional on current values of the other parameters, then update the parameters based on expected value of the variable. It has been shown that how quickly the algorithm converges is dependent on how informative the imputed data is; the more "informative" the missing data is, the slower the convergence. $\endgroup$ – Cliff AB Jul 4 '16 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.