30
$\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$
22
$\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$
  • 10
    $\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
  • 3
    $\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
  • 1
    $\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
  • 1
    $\begingroup$ @Elvis I added another answer beneath which you might find interesting based on your comment $\endgroup$ – Lucas Roberts May 16 '20 at 18:47
3
$\begingroup$

I wanted to follow up (even though this is some years later) on the OP's second question:

Is there any condition under which they are equivalent?

In fact there is a condition under which they're equivalent.

The first order EM algorithm is gradient descent on the marginal likelihood function.

To parse the implications of this statement you need the precise definitions and the derivation, which is pretty straightforward so I'll sketch it here:

The statement above is literally, $\nabla_\theta Q_n(\theta | \theta^t)|_{\theta =\theta^t} = \nabla_{\theta}l(\theta^t).$ Define, $$ Q_n(\theta | \theta^t) = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)logf_\theta(y_i, z)dz \right\}. $$ Here $z$ is the unobserved or 'latent' variable, and $y_i$ are observed data, and $\theta^t$ is the parameter value at iteration $t$, $\theta$ is the parameter you are optimizing for in the EM algorithm.
And $$ l(\theta) = \frac{1}{n}\sum_{i=1}^nlog\left(\int_z f(y_i, z)dz\right) $$

Now consider,

$$ \nabla_\theta Q_n(\theta | \theta^t) = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\nabla_\theta logf_\theta(y_i, z)dz \right\}. $$ The r.h.s. of the equation is: $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\nabla_\theta logf_\theta(y_i, z)dz \right\} = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}. $$ Next write out the definition of the conditional distribution, $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}= \frac{1}{n}\sum_{i=1}^n \left\{\int_z \frac{f_\theta(y_i, z)}{f_\theta(y_i)}\frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i, z)}\right\}. $$ Now you cancel the $f_\theta(y_i, z)$ terms $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z \frac{\nabla_\theta f_\theta(y_i, z)dz }{f_\theta(y_i)}\right\}. $$ Now bring in the integral to get $$ \frac{1}{n}\sum_{i=1}^n \left\{ \frac{\nabla_\theta f_\theta(y_i)dz }{f_\theta(y_i)}\right\} = \frac{1}{n}\sum_{i=1}^n \left\{\nabla_\theta logf_\theta(y_i)\right\}, $$ and it is easy to see that this is the same as

$$ \nabla_\theta l(\theta), $$

which shows the claim:

The first order EM algorithm is gradient descent on the marginal likelihood function.

Of course this makes the usual assumptions about interchange of derivative and integral, so if those assumptions are not valid, then the claim will not be valid. Those types of cases occur most frequently when a parameter is on the boundary of the support of the distribution and the derivative w.r.t. the parameter becomes a Dirac delta function which does not allow interchange of derivative and integral.

The claim is made at the bottom of page 82 of the paper:

STATISTICAL GUARANTEES FOR THE EM ALGORITHM:FROM POPULATION TO SAMPLE-BASED ANALYSIS

by Balankrishnan, Wainwright, and Yu, but the claim is not proven, as you can see it's only a couple of lines.

$\endgroup$

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.