Why go through the trouble of expectation maximization and not use gradient descent?

Question

In expectation maximization first a lower bound of the likelihood is found and then a 2 step iterative algorithm kicks in where first we try to find the weights (the probability that a data point comes from a certain hypothesized distribution) and then, assuming the weights found are correct the distributions are updated to maximize the likelihood. This is repeated to find MLE

The step to find the lower bound is as follows (uses jensen's inequality since log is a concave function):

$$\sum_{i=1}^{M}\log\Sigma_{z_k\in z}(P(x_i, z_k;\theta)) \geqslant \sum_{i=1}^{M}E_{z_k\sim Q(z)}\left[\log\frac{P(x_i,z_k;\theta)}{Q(z_k)}\right]$$

Why can we not directly optimize the LHS using gradient descent? Why go through the entire create the evidence lower bound and then optimize using the EM algorithm?

Answer 1

There are several advantages of the EM algorithm over gradient descent:

1. Monotonic convergence. The EM algorithm never decreases the log-likelihood. This is not necessarily true for gradient descent.

2. Preserves contraints. Parameters like a vector of probabilities must sum up to 1, but there's no reason to believe they will after a step of gradient descent. They always will for an EM algorithm. There's tricks for getting around this in a gradient based method, but they can get quite complicated, especially if parameter values may be on the boundary (i.e. probabilities that equal 0).

3. More stable. Gradients can behave in an unstable manner which means you often need to do a lot of work to fix up or stabilize the parameters. Generally not an issue for EM algorithms.

4. No need to choose a learning rate. The success of gradient descent is highly dependent on choosing a good learning rate. No need for EM algorithm (although in many cases you can speed up the EM algorithm by being clever about what the missing data you are imputing is).

Another issue that may favor the EM algorithm is speed of convergence. Standard gradient descent is generally a very slow algorithm. In many cases the EM algorithm will be faster, but this is definitely problem specific. And methods like stochastic gradient descent may be much, much faster for large datasets.

On the other hand, gradient based methods are much more generic which is a big advantage. As such, there's been a lot of development of gradient based methods (i.e. LBFGS, Adam etc) that are more easily generalized to new problems, unlike EM-algorithms which need more specialization to their problem.

Answer 2

Expectation-Maximization can be seen as a form of gradient descent which has been specifically tailored for latent variables models.

In a latent variables model, you actually have 2 sets of unknowns:

1. The parameters $\theta$;
2. But also the latent variables $\{z_k\}_k$

Estimating $\theta$ knowing $\{z_k\}_k$ is usually easy (and may be performed using classical gradient descent). Estimating $\{z_k\}_k$ knowing $\theta$ might also be easy (this is called filtering, and different methods exist). But estimating $\theta$ without knowing $\{z_k\}_k$ can be intractable.

An example is the optimization of the likelihood of the observations when performing Factor Analysis. In Andrew Ng's lectures notes on Factor Analysis (part X), you can see that directly optimizing the likelihood $l(\mu,\Lambda,\Psi)$ is impossible (although for this specific problem an approximate direct likelihood optimization method can be derived, see 21.2.1 in Barber).

EM solves this issue by alternatively estimating $\{z_k\}_k$ knowing $\theta$ (E step) and estimating $\theta$ knowing $\{z_k\}_k$ (M step). It is thus a form of gradient descent, but which optimizes for $[\{z_k\}_k, \theta]$ instead of just $\theta$.