Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
    
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 at 2:32
1  
Yes Glen, sorry about that, it is indeed the $i$th iterate of the EM algorithm. –  Benjamin May 12 at 2:45
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
@Benjamin How's the problem coming along? Was I able to help you understand how to do it? –  jsk May 12 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 :) –  Benjamin May 12 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. –  Benjamin May 12 at 12:48
    
You're welcome. Hope your final goes well today! –  jsk May 12 at 18:26
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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