13
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your link to notes seems to be dead. $\endgroup$ – G5W May 16 at 16:02
  • $\begingroup$ @G5W Thanks, updated. $\endgroup$ – Mike May 16 at 19:37
0
$\begingroup$

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:

enter image description here

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.

| cite | improve this answer | |
$\endgroup$

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.