# 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.