Expectation Maximization clarification questions

Question

I know there are many questions related to EM, but I still could not find the answer I seek. I have learned Expectation Maximization from this turtorial: Andrew Ng. The lecture is easy to follow. To my understanding, Andrew's intuition is that when doing maximum likelihood for latent variable model, the log likelihood function can be difficult to maximize due to that the latent variable is unobserved. Therefore, we can find a tight lower bound of the log likelihood function by using Jensen's inequality, and maximize this lower bound function, which is easier to maximize than the original log likelihood function. Suppose ${\vec x}^{(i)}$ is the observed vector for sample i, ${\vec z}^{(i)}$ is the latent class, ${\vec \theta }$ is a vector of parameters, there are M samples, and K latent classes. Andrew's lecture can be briefly summarized as follows. We want to find $$\eqalign{ & \arg {\max _\theta }\left( {\sum\limits_{i = 1}^M {\log \left( {P\left( {{{\vec x}^{(i)}};\vec \theta } \right)} \right)} } \right) \cr & = \arg {\max _\theta }\left( {\sum\limits_{i = 1}^M {\log \left( {\sum\limits_{{z^{(i)}} = 1}^K {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} } \right)} } \right) \cr} $$ But it is hard. So instead we find a tight lower bound by the following steps: $$\eqalign{ & L = \sum\limits_{i = 1}^M {\log \left( {P\left( {{{\vec x}^{(i)}};\vec \theta } \right)} \right)} \cr & = \sum\limits_{i = 1}^M {\log \left( {\sum\limits_{{z^{(i)}} = 1}^K {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} } \right)} \cr & = \sum\limits_{i = 1}^M {\log \left( {\sum\limits_{{z^{(i)}} = 1}^K {Q\left( {{z^{(i)}}} \right){{P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \over {Q\left( {{z^{(i)}}} \right)}}} } \right)} \cr & = \sum\limits_{i = 1}^M {\log \left( {E\left[ {{{P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \over {Q\left( {{z^{(i)}}} \right)}}} \right]} \right)} \cr & \ge \sum\limits_{i = 1}^M {E\left[ {\log \left( {{{P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \over {Q\left( {{z^{(i)}}} \right)}}} \right)} \right]} \cr & = \sum\limits_{i = 1}^M {\sum\limits_{{z^{(i)}} = 1}^K {Q\left( {{z^{(i)}}} \right)\log \left( {{{P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \over {Q\left( {{z^{(i)}}} \right)}}} \right)} } \cr} $$ In E step, we set $$Q\left( {{z^{(i)}}} \right) = {{P\left( {{{\vec x}^{(i)}},{z^{(i)}};{{\vec \theta }_t}} \right)} \over {\sum\limits_{{z^{(i)}} = 1}^K {P\left( {{{\vec x}^{(i)}},{z^{(i)}};{{\vec \theta }_t}} \right)} }}$$ In M step, we find: $${{\vec \theta }_{t + 1}} = \arg {\max _\theta }\left( {\sum\limits_{i = 1}^M {\sum\limits_{{z^{(i)}} = 1}^K {Q\left( {{z^{(i)}}} \right)\log \left( {{{P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \over {Q\left( {{z^{(i)}}} \right)}}} \right)} } } \right)$$ My first question is that Andrew's representation seems slightly different from the traditional one, in which the M step involves finding $$\eqalign{ & \arg {\max _\theta }\left( {\sum\limits_{i = 1}^M {{E_{{z^{(i)}}|{{\vec x}^{(i)}},\vec \theta }}\left[ {\log \left( {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \right)} \right]} } \right) \cr & = \arg {\max _\theta }\left( {\sum\limits_{i = 1}^M {\sum\limits_{{z^{(i)}} = 1}^K {Q\left( {{z^{(i)}}} \right)\log \left( {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \right)} } } \right) \cr} $$ Is this due to Q is not a function of ${\vec \theta }$, therefore the log denominator Q under P is dropped off in argmax?

Second, mathematically, how is the lower bound function, $${\sum\limits_{i = 1}^M {\sum\limits_{{z^{(i)}} = 1}^K {Q\left( {{z^{(i)}}} \right)\log \left( {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} \right)} } }$$ easier to maximize than the original log likelihood function: $$\sum\limits_{i = 1}^M {\log \left( {\sum\limits_{{z^{(i)}} = 1}^K {P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)} } \right)} $$

Both of them need to deal with the same parameters in ${P\left( {{{\vec x}^{(i)}},{z^{(i)}};\vec \theta } \right)}$. Is this due to log sum is harder to maximize than sum of log?

Answer 1

Just to elaborate a little further: In terms of $\theta$ we have

\begin{align*} \sum_{i=1}^M \sum_{z^{(i)}=1}^K & Q(z^{(i)}) \log\left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q(z^{(i)})}\right) \\ &= \sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log P(x^{(i)},z^{(i)};\theta) - \sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log Q(z^{(i)}) \\ &= \sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log P(x^{(i)},z^{(i)};\theta) - const \end{align*}

so yes, maximizing $\sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log\left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q(z^{(i)})}\right)$ in $\theta$ is the same as maximizing $\sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log P(x^{(i)},z^{(i)};\theta)$ because they just deviate by a constant (in terms of $\theta$).

On the secons question: Just to add a few cents (i.e. one example) to the answer already given: Imagine the standard example of Gaussian Mixture Models. Here, $P(x^{(i)},z^{(i)};\theta) = e^{\text{someFunction}(x^{(i)};\theta_{z^{(i)}})}$ so that indeed, with the log inside the sum:

$$\sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \log P(x^{(i)},z^{(i)};\theta) = \sum_{i=1}^M \sum_{z^{(i)}=1}^K Q(z^{(i)}) \text{someFunction}(x^{(i)};\theta_{z^{(i)}}) $$

is easier to maximize than

$$ \sum_{i=1}^M \log \left( \sum_{z^{(i)}=1}^K P(x^{(i)},z^{(i)};\theta)\right) $$

because in the second equation...

1. you have a log in front of a sum which makes the gradients more "complicated" than the other way around
2. you cannot use the simplification $\log e^{*} = *$

(2. is particularly important in real world examples because many distributions that we use come in the shape of an exponential family...)