# EM algorithm Practice Problem

This is a practice problem for a midterm exam. The problem is an EM algorithm example. I am having trouble with part (f). I list parts (a)-(e) for completion and in case I made a mistake earlier.

Let $X_1,\ldots,X_n$ be independent exponential random variables with rate $\theta$. Unfortunately, the actual $X$ values are not observed, and we only observe whether the $X$ values fall within certain intervals. Let $G_{1j} = \mathbb{1}\left\{X_j < 1\right\}$, $G_{2j} = \mathbb{1}\left\{1< X_j<2\right\}$, and $G_{3j} = \mathbb{1}\left\{X_j > 2\right\}$ for $j=1,\ldots,n$. THe observed data consist of $(G_{1j},G_{2j},G_{3j})$.

(a) Give the observed data likelihood:

\begin{align*} L(\theta | G) &= \prod_{j=1}^n \text{Pr}\left\{X_j < 1\right\}^{G_{1j}}\text{Pr}\left\{1<X_j<2 \right\}^{G_{2j}}\text{Pr}\left\{X_j >2\right\}^{G_{3j}}\\ &= \prod_{j=1}^n \left(1-e^{-\theta}\right)^{G_{1j}}\left(e^{-\theta}-e^{-2\theta}\right)^{G_{2j}}\left(e^{-2\theta}\right)^{G_{3j}} \end{align*}

(b) Give the complete data likelihood

\begin{align*} L(\theta | X,G) &= \prod_{j=1}^n \left(\theta e^{-\theta x_j}\right)^{G_{1j}}\left(\theta e^{-\theta x_j}\right)^{G_{2j}}\left(\theta e^{-\theta x_j}\right)^{G_{3j}} \end{align*}

(c) Derive the predictive density of the latent variable $f(x_j|G,\theta)$

\begin{align*} f(x_j|G,\theta) &= \dfrac{f_{X,G}(x_j, g)}{f_G(g)}\\ &= \dfrac{ \theta e^{-\theta x_j}\mathbb{1}\left\{x_j \in \text{region r s.t. } G_{rj}=1\right\}}{\left(1-e^{-\theta}\right)^{g_{1j}}\left(e^{-\theta}-e^{-2\theta}\right)^{g_{2j}}\left(e^{-2\theta}\right)^{g_{3j}}} \end{align*}

(d) E-step. Give the function $Q(\theta,\theta^i)$

\begin{align*} Q(\theta,\theta^i) &= \text{E}_{X|G,\theta^i}\left[ \log{f(\mathbf{x}|G,\theta)}\right]\\ &= n\log{\theta} - \theta\sum_{j=1}^n\text{E}\left[X_j|G,\theta^i\right] - N_1\log{(1-e^{-\theta})} - N_2\log{(e^{-\theta}-e^{-2\theta})} - N_3\log{e^{-2\theta}}\\ &= n\log{\theta} - \theta\sum_{j=1}^n\text{E}\left[X_j|G,\theta^i\right] - N_1\log{(1-e^{-\theta})} - N_2\log{(e^{-\theta}(1-e^{-\theta}))} + 2\theta N_3\\ &= n\log{\theta} - \theta\sum_{j=1}^n\text{E}\left[X_j|G,\theta^i\right] - N_1\log{(1-e^{-\theta})} + \theta N_2 -N_2\log{(1-e^{-\theta})} + 2\theta N_3 \end{align*}

where $N_1=\sum_{j=1}^n g_{1j}, N_2=\sum_{j=1}^n g_{2j}, N_3=\sum_{j=1}^n g_{3j}$

(e) Give expressions for $\text{E}\left[X_j|G_{rj}=1,\theta^i\right]$ for $r=1,2,3$.

I will list my results which I am pretty sure are right but the derivations would be a bit long for this already looong question:

\begin{align*} \text{E}\left[X_j|G_{1j}=1,\theta^i\right] &= \left(\dfrac{1}{1-e^{-\theta^i}}\right)\left(\dfrac{1}{\theta^i}-e^{-\theta^i}(1+1/\theta^i)\right)\\ \text{E}\left[X_j|G_{2j}=1,\theta^i\right] &= \left(\dfrac{1}{e^{-\theta^i}-e^{-2\theta^i}}\right)\left(e^{-\theta^i}(1+1/\theta^i)-e^{-2\theta^i}(2+1/\theta^i)\right)\\ \text{E}\left[X_j|G_{3j}=1,\theta^i\right] &= \left(\dfrac{1}{e^{-2\theta^i}}\right)\left(e^{-2\theta^i}(2+1/\theta^i)\right) \end{align*}

This is the part that I am stuck on, and it might be because of an earlier mistake:

(f) M-Step. Find the $\theta$ that maximizes $Q(\theta,\theta^i)$

From law of total expectation we have \begin{align*} \text{E}\left[X_j|G,\theta^i\right] &= \left(\dfrac{1}{\theta^i}-e^{-\theta^i}(1+1/\theta^i)\right) + \left(e^{-\theta^i}(1+1/\theta^i)-e^{-2\theta^i}(2+1/\theta^i)\right) + \left(e^{-2\theta^i}(2+1/\theta^i)\right)\\ &= 1/\theta^i \end{align*} Therefor

\begin{align*} Q(\theta,\theta^i) &= n\log{\theta} - \theta\sum_{j=1}^n\text{E}\left[X_j|G,\theta^i\right] - N_1\log{(1-e^{-\theta})} + \theta N_2 -N_2\log{(1-e^{-\theta})} + 2\theta N_3\\ &= n\log{\theta} - \theta\dfrac{n}{\theta^i} - N_1\log{(1-e^{-\theta})} + \theta N_2 -N_2\log{(1-e^{-\theta})} + 2\theta N_3\\ \dfrac{\partial Q(\theta,\theta^i)}{\partial \theta} &= \dfrac{n}{\theta} - \dfrac{n}{\theta^i} - \dfrac{(N_1+N_2)e^{-\theta}}{1-e^{-\theta}} + N_2+2N_3 \end{align*}

Next I should set this equal to zero and solve for $\theta$, but I have tried this for a very long time and I cannot seem to solve for $\theta$!

-
I was interpreting $\theta^i$ as a power of $\theta$ for a minute. Most confusing. Usually the iteration number (step number) is put in brackets $[i]$ or parentheses $(i)$ so that $\theta^{(i)}$ isn't confused with the $i$-th power $\theta^{i}$. Probably best to at least say that's what it is in the question (assuming I now have it right). – Glen_b May 12 '14 at 2:32
Yes Glen, sorry about that, it is indeed the $i$th iterate of the EM algorithm. – bdeonovic May 12 '14 at 2:45

The complete data likelihood should not involve G! It should simply be the likelihood of $\theta$ when the $X$'s are exponential. Note that the complete data likelihood as you have it written simplifies to an exponential likelihood since only one of the $G_{rj}$'s can be 1. Leaving the $G$'s in the complete data likelihood, however, messes you up later on.

In part (d) should be taking the expectation of the complete data log likelihood, not the observed data log likelihood.

Also, you should not be using the law of total expectation! Recall that G is observed and is not random, so you should only be performing one of those conditional expectations for each $X_j$. Simply replace this conditional expectation by the term $X_j^{(i)}$ and then perform the M-step.

-
@Benjamin How's the problem coming along? Was I able to help you understand how to do it? – jsk May 12 '14 at 4:03
Thanks for the comments @jsk. I was tired last night so I went to bed, but I will tackle this again this morning after breakfast :) – bdeonovic May 12 '14 at 11:50
I think I've figured it out! Thank you again! This was actually in preparation for a final that I have today, so it really helped clarify some things about the EM. – bdeonovic May 12 '14 at 12:48
You're welcome. Hope your final goes well today! – jsk May 12 '14 at 18:26

Based off @jsk's comments I will try to remedy my mistakes:

\begin{align*} L(\theta|X,G) &= \prod_{j=1}^n \theta e^{-\theta x_j} \end{align*}

\begin{align*} Q(\theta,\theta^i) &= n\log{\theta} - \theta\sum_{j=1}^n \text{E}\left[X_j|G,\theta^i\right]\\ &= n\log{\theta} - \theta\left(\dfrac{\sum_{j=1}^n g_{1j}}{1-e^{-\theta^i}}\right)\left(\dfrac{1}{\theta^i} - e^{-\theta^i}(1+1/\theta^i)\right) - \theta\left(\dfrac{\sum_{j=1}^n g_{2j}}{e^{-\theta^i}(1-e^{-\theta^i})}\right)\left(e^{-\theta^i}(1+1/\theta^i)-e^{-2\theta^i}(2+1/\theta^i)\right) - \theta\left(\dfrac{\sum_{j=1}^n g_{3j}}{e^{-2\theta^i}}\right)\left(e^{-2\theta^i}(2+1/\theta^i)\right)\\ &= n\log{\theta} - \theta N_1 A - \theta N_2 B - \theta N_3 C\\ \dfrac{\partial Q(\theta,\theta^i)}{\partial \theta} &= \dfrac{n}{\theta} - N_1A-N_2B - N_3C \overset{set}{=}0 \end{align*}

solving for $\theta$ we get $\theta^{(i+1)} = \dfrac{n}{N_1A+N_2B+N_3C}$

-