34
$\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$
2

3 Answers 3

23
$\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$
1
  • 12
    $\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, 2016 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$
8
  • 3
    $\begingroup$ Or for a similar sort of idea, Hinton and Neal (1998) $\endgroup$ Dec 11, 2012 at 23:33
  • 4
    $\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, 2016 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, 2016 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, 2016 at 6:01
  • 1
    $\begingroup$ @Elvis I added another answer beneath which you might find interesting based on your comment $\endgroup$ May 16, 2020 at 18:47
6
$\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).$ Define, $$ Q_n(\theta | \theta^t) = \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\log f_\theta(y_i, z)dz \right\}. $$ Here $z$ is the unobserved or "latent" variable, $k_{\theta^t}(z|y_i)$ its conditional distribution, $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. Further $$ l(\theta) = \frac{1}{n}\sum_{i=1}^n\log\left(\int_z f_\theta(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 \log f_\theta(y_i, z)dz \right\}. $$ The right-hand side of the equation is: $$ \frac{1}{n}\sum_{i=1}^n \left\{\int_z k_{\theta^t}(z|y_i)\nabla_\theta \log f_\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 switch the order of the integral and derivative to obtain $$ \frac{1}{n}\sum_{i=1}^n \left\{ \frac{\nabla_\theta f_\theta(y_i) }{f_\theta(y_i)}\right\} = \frac{1}{n}\sum_{i=1}^n \left\{\nabla_\theta \log f_\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 following paper:

Statistical guarantees for the EM algorithm: From population to sample-based analysis Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu Ann. Statist. 45(1): 77-120 (February 2017). DOI: 10.1214/16-AOS1435.

$\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.