Applying Expectation Maximization to coin toss examples

I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:

From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and $p_2$ the respective probability for landing on Head when tossed. Toss $c_0$. If the result is Head, toss $c_1$ three times, else toss $c_2$ three times. The observed data produced by $c_1$ and $c_2$ is like this: HHH, TTT, HHH, TTT, HHH. The hidden data is the result of $c_0$. Estimate $p_0$, $p_1$ and $p_2$.

And from here: There are two coins $c_A$ and $c_B$ with $p_A$ and $p_B$ being the respective probability for landing on Head when tossed. Each round, select one coin at random and toss it ten times; record the results. The observed data is the toss results provided by these two coins. However, we don't know which coin was selected for a particular round. Estimate $p_A$ and $p_B$.

While I can get the calculations, I can't relate the ways they are solved to the original EM theory. Specifically, during the M-Step of both examples, I don't see how they're maximizing anything. It just seems they are recalculating the parameters and somehow, the new parameters are better than the old ones. Moreover, the two E-Steps don't even look similar to each other, not to mention the original theory's E-Step.

So how exactly do these examples work?

• In the first example, how many instances of the same experiment do we get? In the second example, what is law of "select one coin at random"? How many rounds do we observe? – Raphael Mar 20 '13 at 11:18
• The PDF files I linked already solve these two examples step-by-step. However, I don't really understand the EM algorithm used. – IcySnow Mar 20 '13 at 11:23
• @IcySnow, do you understand the concept of expectation and conditional expectation of a random variable? – Nicholas Mancuso Mar 20 '13 at 13:45
• I understand basic expectation of a random variable and conditional probability. However, I'm not familiar with conditional expectation, its derivative and sufficient statistic. – IcySnow Mar 20 '13 at 13:50

(This answer uses the second link you gave.)


We want to find maximum likelihood estimator $\hat{\theta}$. The Expectation-Maximization (EM) algorithm is one such method to find (at least local) $\hat{\theta}$. It works by finding the conditional expectation, which is then used to maximize $\theta$. The idea is that by continually finding a more likely (i.e. more probable) $\theta$ in each iteration we will continually increase $\Pr[X,Z|\theta]$ which in turn, increases the likelihood function. There are three things that need to be done before going forward designing an EM-based algorithm.

1. Construct the model
2. Compute Conditional Expectation under the model (E-Step)
3. Maximize our likelihood by updating our current estimate of $\theta$ (M-Step)

Construct the Model

Before we go further with EM we need to figure out what exactly it is we are computing. In the E-step we are computing exactly the expected value for $\log \Pr[X,Z|\theta]$. So what is this value, really? Observe that \begin{align*} \log \Pr[X,Z|\theta] &= \sum_{i=1}^5 \log\sum_{C\in \{A,B\}}\Pr[X_i, Z_i=C| \theta]\\ &=\sum_{i=1}^5 \log\sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}\\ &\geq \sum_{i=1}^5 \sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \log\frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}. \end{align*} The reason is that we have 5 experiments to account for, and we don't know what coin was used in each. The inequality is due to $\log$ being concave and applying Jensen's inequality. The reason we need that lower bound is that we cannot directly compute the arg max to the original equation. However we can compute it for the final lower bound.

Now what is $\Pr[Z_i=C|X_i,\theta]$? It is the probability that we see coin $C$ given experiment $X_i$ and $\theta$. Using conditional probabilities we have, $$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

While we've made some progress, we're not done with the model just yet. What is the probability that a given coin flipped the sequence $X_i$? Letting $h_i = \#\text{heads in } X_i$ $$\Pr[X_i, Z_i = C| \theta] = \frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$ Now $\Pr[X_i|\theta]$ is clearly just the probability under both possibilities of $Z_i=A$ or $Z_i=B$. Since $\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ we have, $$\Pr[X_i|\theta] = 1/2 \cdot (\Pr[X_i |Z_i = A, \theta] + \Pr[X_i |Z_i = B, \theta]).$$

E-Step

Okay... that wasn't so fun but we can start doing some EM work now. The EM algorithm begins by making some random guess for $\theta$. In this example we have $\theta^0 = (0.6,0.5)$. We compute $$\Pr[Z_1=A|X_1,\theta] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$ This value lines up with what is in the paper. Now we can compute the expected number of heads in $X_1 = (H,T,T,T,H,H,T,H,T,H)$ from coin $A$, $$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$ Doing the same thing for coin $B$ we get, $$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$ We can compute the same for the number of tails by substituting $h_1$ for $10 - h_1$. This continues for all other values of $X_i$ and $h_i$ $1 \leq i \leq 5$. Thanks to linearity of expectation we can figure out $$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

M-Step

With our expected values in hand, now comes the M step where we want to maximize $\theta$ given our expected values. This is done by simple normalization! $$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$ Likewise for $B$. This process begins again with the E-Step and $\theta^1$ and continues until the values for $\theta$ converge (or to some alloweable threshold). In this example we have 10 iterations and $\hat{\theta} = \theta^{10} = (0.8, 0.52)$. In each iteration the value of $\Pr[X,Z|\theta]$ increases, due to the better estimate of $\theta$.

Now in this case the model was fairly simplistic. Things can get much more complicated pretty quickly, however the EM algorithm will always converge, and will always produce a maxmimum likelihood estimator $\hat{\theta}$. It may be a local estimator, but to get around this we can just restart the EM process with a different initialization. We can do this a constant amount of times and retain the best results (i.e., those with the highest final likelihood).

• If any parts aren't clear I can try to expand them also. – Nicholas Mancuso Mar 20 '13 at 21:02
• It gets much clearer now. What I don't really get is why the expected number of heads for coin A was calculated as: E[#heads by coin A|X1,θ]=h1⋅Pr[Z1=A|X1,θ]=5⋅0.45≈2.2? The problem mentioned in the first PDF is more complicated. If you don't mind, can you do some illustrative calculations for it as well? Many thanks for your answer. – IcySnow Mar 21 '13 at 6:51
• @IcySnow, as far as the expectation calc goes: $E[\# \text{ heads by coin }A|X_1,\theta] = \sum_{\#\text{ heads in }X_1} \Pr[Z_1 = A| X_1, \theta] = 5 \cdot \Pr[Z_1 = A| X_1, \theta]$. The reason is you can think of there being another indicator random variable if A was used. Computing expectation over indicator variables is simple the probability of that event. – Nicholas Mancuso Mar 24 '13 at 21:07
• Sorry for the slow reply. Thanks to you, I can now really understand the logic behind the two coin examples, after going through your answer many times. There's one last thing I want to ask regarding this question: The example starting from page 8 in this slide cs.northwestern.edu/~ddowney/courses/395_Winter2010/em.ppt shows that in the M-Step, we have to first compute the derivative of the log-likelihood function and use it to maximize the expectation. Why isn't something like that in the coin toss examples' M-Steps? Because these M-Steps don't look like they're maximizing anything – IcySnow Mar 28 '13 at 14:23
• I'm confused by the first displayed equation after "Constructing the Model". Can you explain where that came from? It looks to me like $\Pr[Z_i=A|X_i,\theta]+\Pr[Z_i=B|X_i,\theta]=1$, so the inner sum is 1 for every $i$, so the entire right-hand side becomes zero. I'm sure I'm missing something -- can you spell out the reasoning about how you got to that equation? – D.W. Apr 19 '13 at 8:03