2
$\begingroup$

I'm trying to solve a homework problem and I'm not getting the answer I expect.

The problem is from Pattern Classification by Duda,Hart,Stork (problem 3.47)

Consider $\mathcal{D} = \left\{\begin{pmatrix}1\\1\end{pmatrix},\begin{pmatrix}3\\3\end{pmatrix},\begin{pmatrix}2\\*\end{pmatrix} \right\}$, sampled from a two-dimensional (separable) distribution $p(x_1,x_2)=p_{1}(x_1)p_{2}(x_2)$, with \begin{equation} p_{1}(x) \sim \begin{cases} \frac{1}{\theta_1}e^{-x/\theta_1} & \text{if}~x \geq 0\\0 & \text{otherwise}\end{cases}. \end{equation} and \begin{equation} p_{2}(x) \sim \begin{cases} \frac{1}{\theta_2} & \text{if}~0 \leq x \leq \theta_2 \\ 0 & \text{otherwise}\end{cases} \end{equation} As usual, $*$ represents a missing feature value.

(a) Start with an initial estimate of $\theta^0=\begin{pmatrix}2\\4\end{pmatrix}$ and analytically calculate $Q(\theta; \theta^0)$ - The E step of the EM algorithm. Be sure to consider the normalization of your distribution.

(b) Find the $\theta$ that maximizes your $Q(\theta; \theta^0)$ - The M step.

$Q$ is defined as

\begin{equation} Q(\theta; \theta^i) = \mathbb{E}_{\mathcal{D}_b}\left[ \ln p(\mathcal{D}_g, \mathcal{D}_b ; \theta) | \mathcal{D}_g ; \theta^i \right] \end{equation}

where $\mathcal{D}_g$ is the "good" (observed) data and $\mathcal{D}_b$ is the "bad" (missing) data. Note that $\mathcal{D}=\mathcal{D}_g \cup \mathcal{D}_b$.

I'm assuming i.i.d. sampling and we are given that the features are independent. For this reason I would expect that EM converges to the maximum likelihood estimates which is $\theta=(2,3)^T$. So I expect my solution for part (b), $\theta^1$, to be closer to $(2,3)^T$ than $\theta^0$. However this doesn't seem to be the case.

Attempt

In this problem $\mathcal{D}_g$ contains 5 observations and $\mathcal{D}_b = \{ x_{32} \}$ is the missing data. I assume the domain of $Q$ is $\theta \in \mathbb{R}^2_{++}$. Also let $\theta = (\theta_1, \theta_2)^T$ and $\theta^0 = (\theta_0^1, \theta_0^2)^T$.

\begin{align} Q(\theta; \theta^i) &= \mathbb{E}_{\mathcal{D}_b}\left[ \ln p(\mathcal{D}_g, \mathcal{D}_b ; \theta) | \mathcal{D}_g ; \theta^0 \right] \\ &= \mathbb{E}_{x_{32}}\left[ \ln p(1,1;\theta) + \ln p(3,3;\theta) + \ln p_{1}(2;\theta_1) + \ln p_{2}(x_{32};\theta_2) | \mathcal{D}_g ; \theta^0 \right] \\ &= \ln p(1,1;\theta) + \ln p(3,3;\theta) + \ln p_{1}(2;\theta_1) + \mathbb{E}_{x_{32}} \left[ \ln p_{2}(x_{32};\theta_2) | \mathcal{D}_g ; \theta^0 \right] \\ \end{align}

Consider the expression in two parts $Q(\theta; \theta^0) = f(\theta) + g(\theta; \theta^0)$

where

\begin{align} f(\theta) &= \ln p(1,1;\theta) + \ln p(3,3;\theta) + \ln p_{1}(2;\theta_1) \\ &= \begin{cases} -3 \ln \theta_1 - \frac{6}{\theta_1} - 2 \ln \theta_2 & \text{if}~\theta_2 \geq 3 \\ -\infty & \text{otherwise} \end{cases}. \end{align}

assuming $\ln(0) = -\infty$, and

\begin{align} g(\theta; \theta^0) &= \mathbb{E}_{x_{32}} \left[ \ln p_{2}(x_{32};\theta_2) | \mathcal{D}_g ; \theta^0 \right] \\ &= \int_{-\infty}^{\infty} {\left( \ln p_{2}(x_{32};\theta_2)\right) p_{2}(x_{32} | \mathcal{D}_g ; \theta^0) dx_{32}} \end{align}

Note that $x_{32}$ is independent of $\mathcal{D}_g$ because i.i.d. and $p(x_1,x_2)=p_1(x_1)p_2(x_2)$. Therefore $p_{2}(x_{32} | \mathcal{D}_g ; \theta^0) = p_{2}(x_{32} ; \theta^0_2) = 1/4$ if $x_{32} \in [0,4]$, and $0$ otherwise so then

\begin{align} g(\theta; \theta^0) &= \frac{1}{4} \int_{0}^{4} \ln p_{2}(x_{32} ; \theta_2) dx_{32} \hspace{50pt} \text{(almost surely)} \\ &= \begin{cases} -\ln \theta_2 & \text{if}~\theta_2 \geq 4 \\ -\infty & \text{otherwise} \end{cases} \end{align}

Therefore \begin{equation} Q(\theta ; \theta^0) = \begin{cases} -3\ln\theta_1 - \frac{6}{\theta_1} - 3\ln\theta_2 & \text{if}~\theta_2 \geq 4 \\ -\infty & \text{otherwise} \end{cases} \end{equation}

Clearly $\theta^1 = \text{arg}\max_{\theta} Q(\theta ; \theta^0) = (2,4)^T$.

Again this solution disagrees with my belief that $\theta^1$ should be closer to $(2,3)$ than $\theta^0$. Is this belief wrong? Have I made a mistake somewhere? I really appreciate if someone could help me understand. I think there may be a mistake in the calculation of $g(\theta ; \theta^0)$ but I can't see it.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you please explain why it has to be $\theta_2 \geq 3$ in the calculation of $f(\theta)$? $\endgroup$ – fear Jan 20 '18 at 20:18
  • 1
    $\begingroup$ @fear Sure, it comes from the definition of $p_2$. We know that $p(3,3 ; \theta) = p_1(3; \theta_1) p_2(3; \theta_2)$. If $\theta_2 < 3$ then $p_2(3; \theta_2) = 0$, if $\theta_2 \geq 3$ then $p_2(3; \theta_2) = 1/\theta_2$. $\endgroup$ – jodag Jan 20 '18 at 21:05
  • $\begingroup$ Thank you! One more question. Duda, in the problem solutions says that $\int_{-\infty}^{\infty} p(x_1)dx_1=1$ and thus $\int_{-\infty}^{\infty} \frac{1}{\theta_1}e^{-\frac{x_1}{\theta_1}} dx_1 =1$ and thus $\theta_1=1$. This is different from your expectation (2, 3) and also $\theta_1$ will not change values. I don't understand why $p(x_1)=\frac{1}{\theta_1}e^{-\frac{x_1}{\theta_1}}$. To my understanding it should be $p(x_1)=p_1(x_1)p_2(x_1)=\frac{1}{\theta_1}e^{-\frac{x_1}{\theta_1}} \frac{1}{\theta_2}$ and then integrate from 0 to infinity. Is there something I am missing? $\endgroup$ – fear Jan 20 '18 at 23:12
  • $\begingroup$ @fear $\int_{-\infty}^{\infty} \frac{1}{\theta_1}e^{-\frac{x_1}{\theta_1}}dx_1 = 1$ is false. Remember that $p_1(x) = 0$ for $x < 0$ which means $1 = \int_{-\infty}^{\infty}{p_1(x_1)dx_1} = \int_{0}^{\infty}{\frac{1}{\theta_1}e^{-\frac{x_1}{\theta_1}}dx_1}$ for all $\theta_1 > 0$. $\endgroup$ – jodag Jan 21 '18 at 0:11
  • 1
    $\begingroup$ @fear I derived a closed expression for $Q(\theta ; \theta^0)$ which is $-\infty$ for all $\theta_2 < 4$. Obviously then $\theta_2 = 3 \Rightarrow Q = -\infty$ which doesn't maximize $Q$. To maximize for $\theta_1$ just solve $\frac{\partial Q}{\partial \theta_1} = 0$ assuming that $\theta_2 \geq 4$. To maximize over $\theta_2$ note that $-3 \ln \theta_1 - \frac{6}{\theta_1} -3 \ln{\theta_2}$ is monotonically decreasing for positive $\theta_2$ so it must be $\theta_2 = 4$. $\endgroup$ – jodag Jan 21 '18 at 0:42
3
$\begingroup$

I think $g(\theta;\theta^0)$ may have a mistake. If $0 < \theta_2 < 4$, then $$g(\theta;\theta^0)=\frac{1}{4} \int_0^{\theta_2} \ln \frac{1}{\theta_2} dx_{32} = -\frac{\theta_2}{4} \ln \theta_2.$$ Thus, $Q(\theta;\theta^0) = -3 \ln \theta_1-\frac{6}{\theta_1} -(2+\frac{\theta_2}{4}) \ln \theta_2$ if $3 \le \theta_2 < 4$.

EDIT

From paper "Exercises in EM":

"E-step does not simply involve replacing missing data by their conditional expectation (although this is true for many important applications of the algorithm). Rather, the E-step takes the expected value of the complete-data log-likelihood function, conditional on the observed data. If the likelihood function takes value zero in a subset of the parameter space, then the log-likelihood function does not exist, and the EM algorithm is not applicable."

I am just replacing the missing data by the conditional expectation above and this is not correct. I think we need to be very careful with non-exponential family distributions. In the book, it mentions that "If the support does depend on $\theta$, then the monotonicity of the EM algorithm might not hold."

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I can see that this gives me the expected solution. Can you explain why this is justified as opposed to assigning $-\infty$? $\endgroup$ – jodag Dec 11 '17 at 2:21
  • 1
    $\begingroup$ I do not see it is $-\infty$ . $g(\theta;\theta^0)=\frac{1}{4} \int_0^{4} \ln p_{2}(x_{32};\theta_2) dx_{32}$ is correct, but when $0 < \theta_2 <4$, $p_{2}(x_{32};\theta_2)$ is nonzero when $x_{32} \in (0,\theta_2)$. Thus, the integral is from 0 to $\theta_2$. $\endgroup$ – Statisfun Dec 11 '17 at 3:39
  • $\begingroup$ Maybe I'm thinking of it wrong. I'm considering $x_{32}$ as a r.v. with distribution $U(0,4)$ and $\ln p(x_{32} ; \theta_2)$ as a function of that random variable. Since $\ln p(x_{32} ; \theta_2) = -\infty$ for $x_{32} > \theta_2$ then if $\theta_2 < 4$ the function $\ln p(x_{32} ; \theta_2)$ takes on the value $-\infty$ with non-zero probability. Hense the expected value is $-\infty$ no? $\endgroup$ – jodag Dec 11 '17 at 3:43
  • $\begingroup$ Do we simply take the expected value over $\textbf{support} p(x ; \theta_2) \cap \textbf{support} p(x ; \theta_2^0)$ ? $\endgroup$ – jodag Dec 11 '17 at 3:46
  • $\begingroup$ I think you are right, sorry about my mistake. The algorithm simply got stuck at the initial values.After reading several materials, I realized that I fell into a trap. Please see my edits and thanks for asking this problem. $\endgroup$ – Statisfun Dec 11 '17 at 18:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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