6
$\begingroup$

I wonder about the relationship between two methods called expectation-maximization (EM) and majorization-minimization. One of them, the EM algorithm can be used for finding the mode of the likelihood or posterior distribution by introducing the latent variables. In the book of Bishop, BRML, he claims that, the new distribution with latent variables are easy to optimize. Majorization minimization methods underlie the same idea, that is, one can introduce another cost function which iteratively converges to the original cost function which is hard to maximize.

Let us take following model: $$ y = x + \eta$$ where $\eta$ is a Gaussian random variable. Maximum likelihood estimation in this model corresponds to the optimization over a quadratic term $\|y -x \|_2^2$. This functional is easy to optimize, however we can find more complicated models which are not easy to optimize, hence introduce an alternative cost function which iteratively converges to the original one (Majorization minimisation). The EM algorithm achieve similar goals but introduce probabilistic notions such as latent variables.

I wonder if these two algorithms are equivalent for some special cases. Or if they are completely different, what is the relationship between them? Thanks!

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ "The EM algorithm is a special case of a more general algorithm called the MM algorithm", see. $\endgroup$
    – user10525
    Nov 27, 2012 at 14:11

1 Answer 1

Reset to default
2
$\begingroup$

The general idea of Minorant Maximization algorithms is: (a) Approximate target function with a dominated function. (b) Climb in approximating function. (c) Return to (a), approximating at new coordinate.

The "flavor" of the MM is given by the approximating method, and the climbing method. EM is a particular instance in which a convex combination of the target function at different points is used or approximation. This approximation is dominated by the target function via Jenessen's-Inequality (JI). Convexity alone still allows an endless amount of approximating functions. It turns out that (given regularity assumptions on the target function) there is a single convex combination of the target function, which is also tangent at the approximating point. This function, happens to have a nice probabilistic interpretation, and it know as the E step of the EM.

In conclusion, the EM is indeed a particular instance of the MM, although to the best of my knowledge, first came EM, then then generalization.

Improve this answer
$\endgroup$
3
  • $\begingroup$ JohnRos, I am particularly thankful to pointing out the clarify the expectation step. Now, I see the connection between convex combinations and taking expectations (since probabilities sum up to one), and now the connections to convex optimisation is much more clear. Thank you. $\endgroup$
    – user16776
    May 19, 2013 at 22:24
  • 1
    $\begingroup$ @JohnRos I found your comment "there is a single convex combination of the target function, which is also tangent at the approximating point" very useful, so I wrote out all of the details: blog.sigfpe.com/2016/10/expectation-maximization-with-less.html $\endgroup$
    – Dan Piponi
    Oct 18, 2016 at 14:02
  • 1
    $\begingroup$ @DanPiponi: definetly one the best explanations of EM I have read. Thank you for sharing. $\endgroup$
    – JohnRos
    Oct 19, 2016 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy