11
$\begingroup$

Should the likelihood be increasing in every step of the EM algorithm?

I wrote an EM algorithm recently and the number it arrived does not seem to be the maximum.

I know this because I used the optim function on R on the same problem and it arrived parameters which gave a bigger log-likelihood value.

But even when I started at this maximum, I run my EM algorithm, it seem to converge to the other value I initially derived from my EM algorithm.

What is the most likely explanation for this?

$\endgroup$
2
  • $\begingroup$ Please rephrase your first sentence correctly: The likelihood function is increasing at every step of the EM algorithm, as proved by Dempster, Laird and Rubin (1977). $\endgroup$
    – Xi'an
    Dec 3, 2012 at 21:15
  • 1
    $\begingroup$ Can you provide a minimally reproducible example? IE, some data, & the algorithm? (You may have a coding error.) $\endgroup$ Dec 12, 2012 at 15:37

2 Answers 2

5
$\begingroup$

The estimator may increase or decrease during each iteration however the likelihood must increase.

You should make sure your likelihood is increasing at each step and see if you are converging to the same value.

$\endgroup$
3
  • $\begingroup$ Hi Glen, this is the question I posted the other day. I think I am almost done. Let the solution given by optim be called S1. Let the solution given by EM be called S2 S1 achieved better likelihood, but I fed S1 into the EM code, it converged to S2 again, this suggests there is something wrong with my algorithm? i.e. the log-likelihood was not increasing at every step? $\endgroup$
    – Lost1
    Dec 3, 2012 at 14:24
  • $\begingroup$ mathoverflow.net/questions/69690/… $\endgroup$
    – Lost1
    Dec 3, 2012 at 15:49
  • $\begingroup$ There is an issue of converging to local maxima. I'm not sure what you mean by I fed S1 and got S2. Probably I problem with your code. Print the likelihood at each step and make sure it continually increases. $\endgroup$
    – Glen
    Dec 3, 2012 at 17:31
4
$\begingroup$

Perhaps not relevant in this case but note that if the E-step is estimated, with Monte Carlo methods or another approximation, it is possible for the likelihood to decrease.

A thought that might be relevant is that the EM does not converge towards the global maxima but to a local.

For more details see section 3 of "On the Convergence Properties of the EM Algorithm" by Wu.

$\endgroup$

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.