2
$\begingroup$

I have been reading the following link about an example of the EM algorithm applied to the tossing of a coin. The link is:

http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf

In the example states that we have the record set of heads and tails from a couple of coins, given by a vector x, but that we do not count with information about which coin did we chose for tossing it 10 times inside a 5 iterations loop.

The problem that I have is with the following figure:

enter image description here

For what it says in the tutorial, it should converge to values of theta(A)=0.80 and theta(B)=0.45. At the beginning, it starts with two values of theta at random that are theta(A)=0.60 and theta(B)=0.50. The question that I have is from where does the values of 0.45x, 0.55x, 0.80x, 0.2x and so on appears? also how I can transform that to each of the values that appear on the table for Coin A and Coin B. In conclusion, I need details on how to obtain those values. Thanks

$\endgroup$
0

1 Answer 1

5
$\begingroup$

Let $\pi_A = \pi_B = \frac{1}{2}$ represent the probability of selecting coin A and B respectively.

Observed data: $\{\mathbf{X_1}, \mathbf{X_2}, \mathbf{X_3}, \mathbf{X_4}, \mathbf{X_5} \}$

Unobserved: $\{Z_1, Z_2, Z_3, Z_4, Z_5 \}$ where $Z_i=1$ if $i^{th}$ sequence used coin A.

Let $h_i$ represennt number of heads in $i^{th}$ sequence.

$$\begin{align*} P(X_i | h_i) &= P(X_i|Z_i=1,h_i)P(Z_i=1) + P(X_i|Z_i=0,h_i)P(Z_i=0) \\ P(X_i | h_i) &= \tbinom{10}{h_i} \theta_A^{h_i}(1-\theta_A)^{10-h_i} \pi_A + \tbinom{10}{h_i} \theta_B^{h_i}(1-\theta_B)^{10-h_i} \pi_B\\ P(\mathbf{X} | h_i) &= \prod_{i=1}^5 P(\mathbf{X_i}| h_i) \end{align*}$$

$$\begin{align*} P(X_i,Z_i | h_i) &= \big( \tbinom{10}{h_i} \theta_A^{h_i}(1-\theta_A)^{10-h_i} \pi_A \big)^{z_i}\big( \tbinom{10}{h_i} \theta_A^{h_i}(1-\theta_A)^{10-h_i} \pi_B \big)^{1-z_i} \\ \ln{P(X_i, Z_i|h_i)} &= z_i \big(\ln(\tbinom{10}{h_i}) + h_i \ln(\theta_A) + (10-h_i) \ln(1-\theta_A) \big) +\\ & (1-z_i) \big(\ln(\tbinom{10}{h_i}) + h_i \ln(\theta_B) + (10-h_i) \ln(1-\theta_B) \big)\\ \ln(P(X,Z|h)) &= \sum_{i=1}^n \ln(P(X_i, Z_i|h_i)\\ P(Z_i|X_i) &= \frac{P(X_i, Z_i | h_i)}{P(X_i|h_i)} \end{align*}$$

E step

(Integration carried w.r.t $P(Z_i|X_i)$)

$$\begin{align*} E_{Z|X}(\ln(P(X,Z))) &= E_{Z|X}[z_i] \big(\ln(\tbinom{10}{h_i}) + h_i \ln(\theta_A) + (10-h_i) \ln(1-\theta_A) \big) +\\ & (1-E_{Z|X}[z_i]) \big(\ln(\tbinom{10}{h_i}) + h_i \ln(\theta_B) + (10-h_i) \ln(1-\theta_B) \big)\\ E_{Z|X}[z_i] &= P(z_i=1|x_i)\\ &= \frac{\pi_A \big( \tbinom{10}{h_i} \theta_A^{h_i}(1-\theta_A)^{10-h_i} \big) }{\pi_A \big( \tbinom{10}{h_i} \theta_A^{h_i}(1-\theta_A)^{10-h_i} \big) + \pi_B \big( \tbinom{10}{h_i} \theta_B^{h_i}(1-\theta_B)^{10-h_i} \big) } \\ &= \frac{\big(\theta_A^{h_i}(1-\theta_A)^{10-h_i} \big) }{\big( \theta_A^{h_i}(1-\theta_A)^{10-h_i} \big) + \big( \theta_B^{h_i}(1-\theta_B)^{10-h_i} \big) } \cdots \ \ (1) \\ \end{align*}$$

M step

$E_{Z|X}(z_i^{(j)})$ is known at step $j$

$$ \begin{align*} \frac{\partial E_{Z|X}(z_i^{(j)})}{\partial \theta_A} &= \sum_{i=1}^n E_{Z|X}(z_i^{(j)}) \big( \frac{x_i}{\theta_A} + \frac{1-x_i}{1-\theta_A} \big) \\ \implies \theta_A^{(j+1)} &= \frac{\sum_{i=1}^n E_{Z|X}(z_i^{(j)}) x_i}{\sum_{i=1}^n E_{Z|X}(z_i)}\cdots \ \ (2) \\ \end{align*} $$

Walk through

1st sequence: H T T T H H T H T H

$\pi_A = \pi_B = \frac{1}{2}$

$\theta_A^{(0)} = 0.6, \theta_B^{(0)} = 0.5$

$h_i = 5$

$P(z_{i=1}^{(1)} =1 ) = \frac{\big( \theta_A^{5}(1-\theta_A)^{5} \big) }{\big( \theta_A^{5}(1-\theta_A)^{5} \big) + \big( \theta_B^{5}(1-\theta_B)^{5} \big) } = 0.4491$

$E_{Z|X}(z_i^{(1)})x_i = 0.45 *5 = 2.25 $

You can work out the other numbers similarly. Or simulate it

$\endgroup$

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