11
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ "Why go through creating the lower bound...". In practice, implementing the EM algorithm does not require solving a new proof and in many cases the implementation is very easy to code up! However, in today's world with tools like JAX, coding up the gradients is no harder than coding up the log-likelihood so with that advancement, gradient methods are much more enticing relative to EM algorithms than they once were. $\endgroup$
    – Cliff AB
    Oct 15, 2023 at 0:10

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for helping me understand this. I think you make all very valid observations. However, for the point 2, I guess where you are talking about the multinomial prior for the latent variable, can we not define the multinomial to be [$p_1,p_2,..,1 - \Sigma{p_i}$] and this way they would always sum up to 1 even after the gradient updates? $\endgroup$ Oct 14, 2023 at 23:31
  • 2
    $\begingroup$ @figs_and_nuts yep what you are referring to is a reparameterization trick to remove constraints. In the reparameterization that you did, you removed one constraint, but still have several others (must be positive, sum of subset of probabilities <= 1). A more common constraint is to then take the logistic transform of what you have...but then you run into problems if any of those values are 0 at the optimal point. $\endgroup$
    – Cliff AB
    Oct 14, 2023 at 23:57
  • $\begingroup$ that said, reparameterization is often viable. Likewise, there are gradient based algorithms that allow for constraints (L-BFGS as one example, Quadratic Programming as another) so you may not even need to reparameterize in some cases. $\endgroup$
    – Cliff AB
    Oct 14, 2023 at 23:59
  • $\begingroup$ Awesomee!! Thank you $\endgroup$ Oct 15, 2023 at 4:27
  • $\begingroup$ Does gradient descent handle missing data natively? If not, perhaps that is another point in favor of the EM algorithm? $\endgroup$ Oct 16, 2023 at 11:08
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Estimating $\theta$ without knowing the latent variables leads to intractable computations. But, that would stop us from solving the problem analytically. Why can we not solve the maximization problem iteratively using gradient descent? If the function to be maximized is continuous then its partial derivatives exist. I am not sure if the derivatives could be intractable. And, if the partial derivatives exist we can use gradient descent. Can you give me an example that cannot be solved using gradient descent? I tried going through cs229 factor analysis and I think that can be solved with GD $\endgroup$ Oct 14, 2023 at 15:27
  • $\begingroup$ Why do you say "EM algorithm can be seen as gradient descent"? There's no gradients calculated in most EM implementations so I'm really struggling to see one could things this way. $\endgroup$
    – Cliff AB
    Oct 14, 2023 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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