# Derivation of expectation-maximization in General - PRML

My question is:

1. Why the incomplete-data likelihood equal to formula 1?

2. Why it should not equal to formula 2?

I apologize for not being word-perfect in English.

I'm reading the book Pattern Recognition And Machine Learning. And I was confused at the derivation of EM algorithm in General at Page 467.

If we denote all of the observed variables by X and all of the hidden variables by Z. Our goal is to maximize the likelihood function: $p(X\mid\theta)$.

Why our goal is equal to $$\sum_Z p(X,Z \mid \theta) \qquad (1)$$

Where,

$$\sum_z p(X,Z \mid \theta) = \sum_z \prod_n \sum_k z_n^k p(x_n\mid \mu_k, \Sigma_k)\pi_k$$

from cos 513: mixture models and em algorithm page 4. As Gaussian mixture model, $p(x_n \mid \theta)= \sum_k \pi_k p(x_n \mid \mu_k, \Sigma_k)$ means instance $x_n$ with probability $\pi_k$ generated by kth Gaussian component.

And $z_n^k$ is a one of K variable, if instance $x_n$ was generated by kth Gaussian component, $z_n^k = 1$; otherwise, $z_n^k=0$.

In my mind,

$$p(X\mid\theta) = \prod_n \sum_z \sum_k z_n^k p(x_n\mid \mu_k, \Sigma_k)\pi_k \qquad (2)$$

So, I think this was the marginal likelihood. Cause, likelihood should be the product of probabilities of observations.

• OK, think I got the answer. $Z$ here is a vector, dimension equal the number of samples N as the COS513 described. So if $z_n$ has 2 possible values, $Z$ will be $2^N$ combinations. – roachsinai Jul 30 '16 at 10:11
• I think you're right :) – dontloo Jul 30 '16 at 10:26
• Thanks. But I think formula $2$ is correct, too. For $z$ has different meaning. – roachsinai Jul 30 '16 at 12:30

## 1 Answer

I think (1) and (2) are equal, with different interpretations of the $z$ that we are summing over.

For clarity I'll rewrite the formulas as $$p(X \mid \theta) = \sum_\mathbf{Z} p(X,Z \mid \theta) = \sum_\mathbf{Z} \prod_N a_n^k \qquad (1)$$ $$p(X \mid \theta) = \prod_N \sum_\mathbf{z} a_n^k \qquad (2)$$ $$a_n^k=\sum_K z_n^k p(x_n\mid\mu_k, \Sigma_k)\pi_k$$

As you well noted, in (1) there are $K^N$ different values in $\mathbf{Z}$, well in (2) there are $K$ different values in $\mathbf{z}$. Note that because $z$ is a one-hot vector, the number of possible values for $z$ is equal to the dimension of $z$ (which is the other $K$ that we are summing over in $a_n^k$).

Expanding (2) $$\prod_N \sum_\mathbf{z} a_n^k=\prod_N(a_n^1+a_n^2+...+a_n^K)=(a_1^1a_2^1...a_N^1)+(a_1^2a_2^1...a_N^1)+...+(a_1^Ka_2^K...a_N^K)=\sum_\mathbf{Z} \prod_N a_n^k$$

In fact as $z$ being one-hot, we have $$p(X \mid \theta) = \prod_N \sum_\mathbf{z} a_n^k=\prod_N \sum_\mathbf{z} \sum_K z_n^k p(x_n\mid\mu_k, \Sigma_k)\pi_k=\prod_N\sum_K\pi_kp(x_n\mid\mu_k, \Sigma_k)$$ which is the original definition. So the above just shows that integrating over the joint probability equals the marginal probability, $p(X \mid \theta) = \sum_\mathbf{Z} p(X,Z \mid \theta)$.

It feels like there should be one more subscript or superscript of the $z_n^k$ term in the original formula to denote which one-hot vector $z$ it is.

• Can't agree more! Thanks for your clarification. I have voted your answer, but stats.stackexchange.com will not display it for my reputations less than 15 :-(. – roachsinai Jul 31 '16 at 0:29
• @roachsinai you're welcome, yes the site requires a minimum reputation for that, also there's an "accept" button just below there, if you find this answer acceptable :P – dontloo Jul 31 '16 at 5:36
• Yes! Got it! :-) – roachsinai Jul 31 '16 at 9:00