# Expectation Maximization Clarification

I found very helpful tutorial regarding EM algorithm.

The example and the picture from the tutorial is simply brilliant.

Related question about calculating probabilities how does expectation maximization work?

I have another question regarding how to connect the theory described in tutorial to the example.

During the E-step, EM chooses a function $g_t$ that lower bounds $\log P(x;\Theta)$ everywhere, and for which $g_t( \hat{\Theta}^{(t)}) = \log P(x; \hat{\Theta}^{(t)})$.

So what the $g_t$ in our example, and it looks like it should be different for every iteration.

In addition, in example $\hat{\Theta}_A^{(0)} = 0.6$ and $\hat{\Theta}_B^{(0)} = 0.5$ then applying them to the data we get that $\hat{\Theta}_A^{(1)} = 0.71$ and $\hat{\Theta}_B^{(1)} = 0.58$. Which is for me looks counter intuitive. We had some prior assumptions, applied it to the data and get new assumptions, so the data somehow changed the assumptions. I don't understand why $\hat{\Theta}^{(0)}$ doesn't equal to $\hat{\Theta}^{(1)}$.

In addition, more questions emerge when you see Supplementary Note 1 to this tutorial. For example what is $Q(z)$ in our case. It's not clear to me why the inequality is tight when $Q(z)=P(z|x;\Theta)$

Thank you.

I found these notes very helpful in figuring out what was going on in the supplemental material.

I'll answer these questions a bit out of order for continuity.

First: why is it that

$$\theta^{(0)} \ne \theta^{(1)}$$

The reason is that the our function $$g_0$$ is chosen such that it is guaranteed to be less than or equal to $$\log(P(x;\theta))$$, with the 2 being incident at the point of our initial guess $$\theta^{(0)}$$. If our prior assumptions were perfect initial guesses then you would be correct and $$\theta^{(1)}$$ would be unchanged. But we can find higher values in the created function $$g_0$$, so our next iteration of the parameter for $$\theta$$ is guaranteed to be more likely than our original.

Second: why is the inequality tight when

$$Q(z) = P(z|x;\theta)$$

equality holds if and only if the random variable is constant with probability 1 (i.e., $$y=E[y]$$)

implying that our choice of $$Q$$ makes $$\frac{P(x, z; \theta)}{Q(z)}$$ constant. To see this, consider that:

$$P(x, z ; \theta) = P(z | x; \theta) P(x; \theta)$$

which makes our fraction

$$\frac{P(z | x; \theta) P(x; \theta)}{P(z|x;\theta)} = P(x; \theta)$$

So what is $$P(x; \theta)$$ and is it constant? Well, consider that we are calculating the sums over $$z$$ for which this term is independent (constant). Let's represent it as $$C$$ and that equation becomes:

$$\log{\big( \sum_z{Q(z)C} \big)} \ge \sum_z{Q(z)\log(C)}$$

from here we can see pretty quickly that the 2 sides are equal, as the expectation of a constant will be that constant no matter the weights (the $$Q(z)$$)

Lastly: what is $$g_t$$

The answer given in the notes I linked is slightly different from the one in the supplementary notes, but they differ only by a constant and we are maximizing it so it is not of consequence. The one in the notes (with derivation) is:

$$g_t(\theta) = \log(P(x|\theta^{(t)})) + \sum_z{P(z|x;\theta^{(t)})\log{\big( \frac{P(x|z;\theta)P(z|\theta)}{P(z|x;\theta^{(t)})P(x|\theta^{(t)})} \big)}}$$

This complex formula isn't talked about at length in the supplementary notes, probably because a lot of these terms will be constants that get thrown away when we maximize. If you are interested in how we arrive here in the first place, I recommend those notes I linked.

Using a similar argument to the one made in the answer to the second question, the term in the log is equal to 1 for $$g_t(\theta^{(t)})$$ so the sum term goes away and $$g_t(\theta^{(t)}) = \log P(x|\theta^{(t)})$$ as expected.

• @G5W Thanks, updated. – Mike May 16 at 19:37

The following questions extracted from your question once also challenged me:

So what the $$g_t$$ in our example, and it looks like it should be different for every iteration.

Firstly the $$\log P(X; \hat{\theta})=\log \sum_z p(z, X; \hat \theta)=\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)}$$ and the $$g_t$$ function is $$\sum_z Q(z) \log \frac{p(z, X; \hat \theta)}{Q(z)}$$, and the following inequality holds due to the concavity of $$\log$$ and the Jensen's inequality:

$$\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)} \geq \sum_z Q(z) \log \frac{p(z, X; \hat \theta)}{Q(z)}=g_t$$

Yes, $$g_t$$ is different for each iteration, and it is the green curves in the following figure from the Supplementary Note 1:

In addition, in example $$\hat{\Theta}_A^{(0)} = 0.6$$ and $$\hat{\Theta}_B^{(0)} = 0.5$$ then applying them to the data we get that $$\hat{\Theta}_A^{(1)} = 0.71$$ and $$\hat{\Theta}_B^{(1)} = 0.58$$. Which is for me looks counter intuitive.

If we treat $$\hat{\Theta}^{(0)}$$, representing $$\hat{\Theta}_A^{(0)}$$ and $$\hat{\Theta}_B^{(0)}$$, as $$\theta^{(t)}$$ in the above figure, $$\hat{\Theta}^{(1)}$$ can be treated as $$\theta^{(t+1)}$$ which more approximates the ground truth(the 0.8 and 0.45 we get in part (a) Maximum likelihood estimation with complete data).

I don't understand why $$\hat{\Theta}^{(0)}$$ doesn't equal to $$\hat{\Theta}^{(1)}$$.

Once we have fixed/hallucinated $$z$$ the lower bound function is also fixed as anyone of the green curves in the above figure(for instance $$g_t$$ in the above figure), and we can calculate the maximum likelihood like we do we have no missing data by choosing the $$\hat{\Theta}^{(1)}$$ or the $$\theta^{(t+1)}$$ in the figure(treating $$\hat{\Theta}^{(0)}$$ as $$\theta^{(t)}$$). They are not equal because $$\theta^{(t)}$$ is not the maximum of the lower bound $$g_t$$, but $$\theta^{(t+1)}$$ is.

Actually we optimize $$\theta$$ in each step to approximate the ground truth(0.8 and 0.45 in our case).

For example what is $$Q(z)$$ in our case. It's not clear to me why the inequality is tight when $$Q(z)=P(z|x;\Theta)$$

This is really a good question. $$z$$ stands for either coin A or coin B, and $$Q(z)$$ is for how confident the coin is A or B: $$Q_i(z^{(i)}=A)$$ for each observation i. $$Q(z)$$ is a distribution of $$z$$ and it sums up to 1: $$\sum_z Q_i(z^{(i)})=1$$.

Let's go back to the Jensen't inequality:

$$\log \sum_z Q(z) \frac{p(z, X; \hat \theta)}{Q(z)} \geq \sum_z Q(z) \log \frac{p(z, X; \hat \theta)}{Q(z)}$$

The equality only hold when $$\frac{p(z, X; \hat \theta)}{Q(z)}$$ is constant(please refer to this answer) since $$\log (x)$$ is not affine, then $$\frac{p(z, X; \hat \theta)}{Q(z)}=C$$ or $$Q(z)\propto p(z, X; \hat \theta)$$. To make $$Q(z)$$ a distribution, as we stated earlier, we can get the following:

\begin{align} Q(z) &\overset{\text{like normalization}}{=} \frac{p(z, X; \hat \theta)}{\sum_z p(z, X; \hat \theta)} \\ &= \frac{p(z, X; \hat \theta)}{p(X; \hat \theta)}\\ &= p(z|X,\hat \theta) \end{align}

This tutorial: The EM algorithm by Andrew Ng helped me a lot and so did this one: The expectation maximization algorithm: A short tutorial.

Hope that helps, and if you have any more questions please update me.