25
$\begingroup$

I have read a couple of explanations of EM algorithm (e.g. from Bishop's Pattern Recognition and Machine Learning and from Roger and Gerolami First Course on Machine Learning). The derivation of EM is ok, I understand it. I also understand why the algorithm coverges to something: at each step we improve the result and the likelihood is bounded by 1.0, so by using a simple fact (if a function increases and is bounded then it converges) we know that the algorithm converges to some solution.

However, how do we know it is a local minimum? At each step we are considering only one coordinate (either latent variable or parameters), so we might miss something, like that the local minimum requires moving by both coordinates at once.

This I believe is a similar problem to that of general class of hill climbing algorithms, which EM is an instance of. So for a general hill climbing algorithm we have this problem for function f(x, y) = x*y. If we start from (0, 0) point, then only by considering both directions at once we are able to move upwards from 0 value.

$\endgroup$
  • 3
    $\begingroup$ The likelihood is bounded only for fixed variances. That is, in the binomial situation, the variance is $p(1-p)$; or in the Gaussian situation, if the variance is assumed known. If the variance is unknown, and has to be estimated, the likelihood is not bounded. Also, in the EM algorithm, there is a generic separation of the missing and parameters, at least for the frequentist statisticians, but the surfaces may indeed have saddles. $\endgroup$ – StasK Mar 4 '14 at 16:45
  • $\begingroup$ @Stask I am not sure that likelihood is generally bounded even with fixed variances. Are you restricting to some particular family? $\endgroup$ – Glen_b -Reinstate Monica Dec 11 '15 at 0:54
28
$\begingroup$

EM is not guaranteed to converge to a local minimum. It is only guaranteed to converge to a point with zero gradient with respect to the parameters. So it can indeed get stuck at saddle points.

$\endgroup$
13
$\begingroup$

First of all, it is possible that EM converges to a local min, a local max, or a saddle point of the likelihood function. More precisely, as Tom Minka pointed out, EM is guaranteed to converge to a point with zero gradient.

I can think of two ways to see this; the first view is pure intuition, and the second view is the sketch of a formal proof. First, I shall, very briefly, explain how EM works:

Expectation Maximization (EM) is a sequential bound optimization technique where in iteration $t$, we first construct a (lower) bound $b_t(\theta)$ on the likelihood function $L(\theta)$ and then maximize the bound to obtain the new solution $\theta_t = \arg\max_\theta b_t(\theta)$, and keep doing this until the new solution does not change.

Expectation Maximization as gradient ascent

In each iteration $t$, EM requires that the bound $b_t$ touches the likelihood function $L$ at the solution of the previous iteration i.e. $\theta_{t-1}$ which implies their gradients are the same too; that is $g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$. So, EM is at least as good as gradient ascent because $\theta_t$ is at least as good as $\theta_{t-1} + \eta g$. In other words:

if EM converges to $\theta^*$ then $\theta^*$ is a convergent point for gradient ascent too and EM satisfies any property shared among gradient ascent solutions (including zero gradient value).

Sketch of a formal proof

One can show that the gap between the bounds and the likelihood function converges to zero; that is $$ \lim_{t \rightarrow \infty} L(\theta_t) - b_t(\theta_t) = 0. \tag{1} $$ One can prove that the gradient of the bound also converges to the gradient of the likelihood function; that is: $$ \lim_{t \rightarrow \infty} \nabla L(\theta_t) = \nabla b_t(\theta_t). \tag{2} $$ Because of $(1)$ and $(2)$ and that the bounds used in EM are differentiable, and that $\theta_t = \arg\max_\theta b_t(\theta)$, we have that $\nabla b_t(\theta_t)=0$ and, therefore, $\lim_{t \rightarrow \infty} \nabla L(\theta_t) = 0$.

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