# Motivation of Expectation Maximization algorithm

In the EM algorithm approach we use Jensen's inequality to arrive at $$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$

and define $\theta^{(k+1)}$ by $$\theta^{(k+1)}=\arg \max_{\theta}\int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz$$

Everything I read EM just plops it down but I've always felt uneasy by not having an explanation of why the EM algorithm arises naturally. I understand that $\log$ likelihood is typically dealt with to deal with addition instead of multiplication but the appearance of $\log$ in the definition of $\theta^{(k+1)}$ feels unmotivated to me. Why should one consider $\log$ and not other monotonic functions? For various reasons I suspect that the "meaning" or "motivation" behind expectation maximization has some kind of explanation in terms of information theory and sufficient statistics. If there were such an explanation that would be much more satisifying than just an abstract algorithm.

-

## migrated from math.stackexchange.comJul 20 '13 at 15:49

This question came from our site for people studying math at any level and professionals in related fields.

What is the expectation maximization algorithm?, Nature Biotechnology 26:897–899 (2008) has a nice picture that illustrates how the algorithm works. – chl Jul 20 '13 at 20:58
@chl: I have seen that article. The point I'm asking is that notice that nowhere does it explain why a non-log approach can't work – user782220 Jul 21 '13 at 1:11

The EM algorithm has different interpretations and can arise in different forms in different applications.

It all starts with the likelihood function $p(x \vert \theta)$, or equivalently, the log-likelihood function $\log p(x \vert \theta)$ we would like to maximize. (We generally use logarithm as it simplifies the calculation: It is strictly monotone, concave, and $\log(ab) = \log a + \log b$.) In an ideal world, the value of $p$ depends only on the model parameter $\theta$, so we can search through the space of $\theta$ and find one that maximizes $p$.

However, in many interesting real-world applications things are more complicated, because not all the variables are observed. Yes, we might directly observe $x$, but some other variables $z$ are unobserved. Because of the missing variables $z$, we are in a kind of chicken-and-eggs situation: Without $z$ we cannot estimate the parameter $\theta$ and without $\theta$ we cannot infer what the value of $z$ may be.

It is where the EM algorithm comes into play. We start with an initial guess of the model parameters $\theta$ and derive the expected values of the missing variables $z$ (i.e., the E step). When we have the values of $z$, we can maximize the likelihood w.r.t. the parameters $\theta$ (i.e., the M step, corresponding to the $\arg \max$ equation in the problem statement). With this $\theta$ we can derive the new expected values of $z$ (another E step), so on and so forth. In another word, in each step we assume one of the both, $z$ and $\theta$, is known. We repeat this iterative process until the likelihood cannot be increased anymore.

This is the EM algorithm in a nutshell. It is well-known that the likelihood will never decrease during this iterative EM process. But keep in mind that EM algorithm doesn't guarantee global optimum. That is, it might end up with a local optimum of the likelihood function.

The appearance of $\log$ in the equation of $\theta^{(k+1)}$ is inevitable, because here the function you would like to maximize is written as a log-likelihood.

-
+1. Very good non-technical explanation of EM. – Zhubarb Oct 2 '13 at 15:23

As you said, I will not go into technical details. There are quite a few very nice tutorials. One of my favourites are Andrew Ng's lecture notes. Take a look also at the references here.

1. EM is naturally motivated in mixture models and models with hidden factors in general. Take for example the case of Gaussian mixture models (GMM). Here we model the density of the observations as a weighted sum of $K$ gaussians: $$p(x) = \sum_{i=1}^{K}\pi_{i} \mathcal{N}(x|\mu_{i}, \Sigma_{i})$$ where $\pi_{i}$ is the probability that the sample $x$ was caused/generated by the ith component, $\mu_{i}$ is the mean of the distribution, and $\Sigma_{i}$ is the covariance matrix. The way to understand this expression is the following: each data sample has been generated/caused by one component, but we do not know which one. The approach is then to express the uncertainty in terms of probability ($\pi_{i}$ represents the chances that the ith component can account for that sample), and take the weighted sum. As a concrete example, imagine you want to cluster text documents. The idea is to assume that each document belong to a topic (science, sports,...) which you do not know beforehand!. The possible topics are hidden variables. Then you are given a bunch of documents, and by counting n-grams or whatever features you extract, you want to then find those clusters and see to which cluster each document belongs to. EM is a procedure which attacks this problem step-wise: the expectation step attempts to improve the assignments of the samples it has achieved so far. The maximization step you improve the parameters of the mixture, in other words, the form of the clusters.

2. The point is not using monotonic functions but convex functions. And the reason is the Jensen's inequality which ensures that the estimates of the EM algorithm will improve at every step.

-

Likelihood vs. log-likelihood

As has already been said, the $\log$ is introduced in maximum likelihood simply because it is generally easier to optimize sums than products. The reason we don't consider other monotonic functions is that the logarithm is the unique function with the property of turning products into sums.

Another way to motivate the logarithm is the following: Instead of maximizing the probability of the data under our model, we could equivalently try to minimize the Kullback-Leibler divergence between the data distribution, $p_\text{data}(x)$, and the model distribution, $p(x \mid \theta)$,

$$D_\text{KL}[p_\text{data}(x) \mid\mid p(x \mid \theta)] = \int p_\text{data}(x) \log \frac{p_\text{data}(x)}{p(x \mid \theta)} \, dx = const - \int p_\text{data}(x)\log p(x \mid \theta) \, dx.$$

The first term on the right-hand side is constant in the parameters. If we have $N$ samples from the data distribution (our data points), we can approximate the second term with the average log-likelihood of the data,

$$\int p_\text{data}(x)\log p(x \mid \theta) \, dx \approx \frac{1}{N} \sum_n \log p(x_n \mid \theta).$$

An alternative view of EM

I am not sure this is going to be the kind of explanation you are looking for, but I found the following view of expectation maximization much more enlightening than its motivation via Jensen's inequality (you can find a detailed description in Neal & Hinton (1998) or in Chris Bishop's PRML book, Chapter 9.3).

It is not difficult to show that

$$\log p(x \mid \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz + D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)]$$

for any $q(z \mid x)$. If we call the first term on the right-hand side $F(q, \theta)$, this implies that

$$F(q, \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz = \log p(x \mid \theta) - D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)].$$

Because the KL divergence is always positive, $F(q, \theta)$ is a lower bound on the log-likelihood for every fixed $q$. Now, EM can be viewed as alternately maximizing $F$ with respect to $q$ and $\theta$. In particular, by setting $q(z \mid x) = p(z \mid x, \theta)$ in the E-step, we minimize the KL divergence on the right-hand side and thus maximize $F$.

-
Thanks for the post! Though the given document doesn't say logarithm is the unique function turning products into sums. It says logarithm is the only function that fulfills all three listed properties at the same time. – Weiwei Jul 22 '13 at 3:47
@Weiwei: Right, but the first condition mainly requires that the function is invertible. Of course, f(x) = 0 also implies f(x + y) = f(x)f(y), but this is an uninteresting case. The third condition asks that the derivative at 1 is 1, which is only true for the logarithm to base $e$. Drop this constraint and you get logarithms to different bases, but still logarithms. – Lucas Jul 22 '13 at 7:49

The paper that I found clarifying with respect to expectation-maximization is Bayesian K-Means as a "Maximization-Expectation" Algorithm (pdf) by Welling and Kurihara.

Suppose we have a probabilistic model $p(x,z,\theta)$ with $x$ observations, $z$ hidden random variables, and a total of $\theta$ parameters. We are given a dataset $D$ and are forced (by higher powers) to establish $p(z,\theta|D)$.

1. Gibbs sampling

We can approximate $p(z,\theta|D)$ by sampling. Gibbs sampling gives $p(z,\theta|D)$ by alternating:

$$\theta \sim p(\theta|z,D) \\ z \sim p(z|\theta,D)$$

2. Variational Bayes

Instead, we can try to establish a distribution $q(\theta)$ and $q(z)$ and minimize the difference with the distribution we are after $p(\theta,z|D)$. The difference between distributions has a convenient fancy name, the KL-divergence. To minimize $KL[q(\theta)q(z)||p(\theta,z|D)]$ we update:

$$q(\theta) \propto \exp (E [\log p(\theta,z,D) ]_{q(z)} ) \\ q(z) \propto \exp (E [\log p(\theta,z,D) ]_{q(\theta)} )$$

3. Expectation-Maximization

To come up with full-fledged probability distributions for both $z$ and $\theta$ might be considered extreme. Why don't we instead consider a point estimate for one of these and keep the other nice and nuanced. In EM the parameter $\theta$ is established as the one being unworthy of a full distribution, and set to its MAP (Maximum A Posteriori) value, $\theta^*$.

$$\theta^* = \underset{\theta}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(z)} \\ q(z) = p(z|\theta^*,D)$$

Here $\theta^* \in \operatorname{argmax}$ would actually be a better notation: the argmax operator can return multiple values. But let's not nitpick. Compared to variational Bayes you see that correcting for the $\log$ by $\exp$ doesn't change the result, so that is not necessary anymore.

4. Maximization-Expectation

There is no reason to treat $z$ as a spoiled child. We can just as well use point estimates $z^*$ for our hidden variables and give the parameters $\theta$ the luxury of a full distribution.

$$z^* = \underset{z}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(\theta)} \\ q(\theta) = p(\theta|z^*,D)$$

If our hidden variables $z$ are indicator variables, we suddenly have a computationally cheap method to perform inference on the number of clusters. This is in other words: model selection (or automatic relevance detection or imagine another fancy name).

5. Iterated conditional modes

Of course, the poster child of approximate inference is to use point estimates for both the parameters $\theta$ as well as the observations $z$.

$$\theta^* = \underset{\theta}{\operatorname{argmax}} p(\theta,z^*,D) \\ z^* = \underset{z}{\operatorname{argmax}} p(\theta^*,z,D) \\$$

To see how Maximization-Expectation plays out I highly recommend the article. In my opinion, the strength of this article is however not the application to a $k$-means alternative, but this lucid and concise exposition of approximation.

-