I found very helpful tutorial regarding EM algorithm.

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

enter image description here

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) $$

There is a hint in the footnotes about this where it says,

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.