3
$\begingroup$

I am trying to understand the Expectation-Maximization algorithm and I am not able to get the intuition of a particular step. I am able to verify the mathematical derivation but I want to understand the why we encounter this particular term.
In the EM algorithm, we know that our log likelihood $\ln p(X|\theta)$ can be written as $\mathcal{L}(q,\theta) + KL(q||p)$.

And $\mathcal{L}(q,\theta) = \mathcal{Q}(θ, θ^{old}) + const$ where the $const$ is the entropy of the the distribution $q(Z)= p(Z|X,θ^{old})$. And the term $\mathcal{Q}(θ, θ^{old})$ represents the expectation of the complete-data log likelihood under the posterior distribution $p(Z|X,θ^{old})$. Here is what I am unable to grasp. Why does maximizing the expected value of complete data log likelihood under the posterior distribution w.r.t $θ$ give a better estimate $θ^{new}$?

I can get the intuition of why maximizing the log likelihood(and not the expected value of log likelihood under some distribution) gives the $θ_{max}$ as we know from the maximum likelihood estimation. But why maximizing the expectation of log likelihood under some distribution also give a better estimate of $θ$?

Also, here what I can mathematically see, $\mathcal{Q}(θ, θ^{old}) = \sum\limits_{Z} p(Z|X,θ^{old})\ln p(X,Z|θ)$
I can see that by expanding I get, $\ln p(X,Z|θ) = \ln p(Z|X,θ) + \ln p(X|θ)$ and substituting I get, $\sum\limits_{Z} p(Z|X,θ^{old})\ln p(Z|X,θ) + \sum\limits_{Z} p(Z|X,θ^{old})\ln p(X|θ)$, in which the 2nd term simply becomes $\ln p(X|θ)$ because it is independent of $Z$.
Thus, $\mathcal{Q}(θ, θ^{old}) = \sum\limits_{Z} p(Z|X,θ^{old})\ln p(Z|X,θ) + \ln p(X|θ)$. And when I substitute value of $\ln p(X|θ)$ and $\mathcal{L}(q,\theta)$ and rearranging, I get $\sum\limits_{Z} p(Z|X,θ^{old})\ln p(Z|X,θ) = -( KL(q||p) + const)$. I am not sure how to make sense of this.

I am referring to Section 9.4 of Patter Recognition and Machine Learning by C. Bishop, if that helps.

$\endgroup$

1 Answer 1

3
$\begingroup$

I think I got the intuition. I understood after reading the Variational inference part of the Approximate Inference chapter in the book and a section in the Wikipedia article of EM algorithm. I have replaced the $\sum$ with $\int$, so this holds for continuous Z as well. Here it goes.
We can write $p(X|θ)$ as $p(X|θ) = \frac{p(X,Z|θ)}{p(Z|X,θ)} = \frac{p(X,Z|θ)/q(Z)}{p(Z|X,θ)/q(Z)} $. Applying log we get, $\ln p(X|θ) = \ln \frac{p(X,Z|θ)}{q(Z)} - \ln\frac{p(Z|X,θ)}{q(Z)} $. Multiplying by $q(Z)$ on both sides and integrating w.r.t to Z we get $$ \ln p(X|θ) \int q(Z)dZ = \int q(Z) \ln \frac{p(X,Z|θ)}{q(Z)} dZ - \int q(Z) \ln\frac{p(Z|X,θ)}{q(Z)}dZ $$ So finally we can write $$ \ln p(X|θ) = \mathcal{L}(q,θ) + KL(q||p) $$ where $$\mathcal{L}(q,θ) = \int q(Z) \ln \frac{p(X,Z|θ)}{q(Z)} dZ $$ $$ KL(q||p) = -\int q(Z) \ln \frac{p(Z|X,θ)}{q(Z)} dZ $$ My intuition says that we want to express this as the familiar concept of lower bound(1st term) and KL divergence(2nd term). Here $q(Z)$ is our approximation of the latent variable posterior distribution and we want to make it as good an approximation as possible. Which means the KL divergence term will become 0 when $q(Z) = p(Z|X,θ)$(best possible). So here minimizing the KL divergence is equal to maximizing lower bound as both of them sum to $\ln p(X|θ)$ which is constant w.r.t Z. On expanding

$$\mathcal{L}(q,θ) = \int q(Z) \ln p(X,Z|θ)dZ - \int q(Z) \ln q(Z) dZ$$ To see how maximizing the expected complete-data log likelihood under the latent variable posterior distribution maximizes $\mathcal{L}(q,θ)$ at least as much, we do the following. We make an initial guess for $q(Z)$ by choosing a random value for $\theta$ and we get $q(Z) = p(Z|X,\theta^{old})$. Putting it in the above equation, we get, $$\mathcal{L}(q,θ) = \int p(Z|X,\theta^{old}) \ln p(X,Z|θ)dZ - \int p(Z|X,\theta^{old}) \ln p(Z|X,\theta^{old}) dZ \\ = \mathbb{E}[\ln p(X,Z)dZ] + const $$ where $const$ is the entropy of $p(Z|X,\theta^{old})$ and is independent of $\theta$. Now maximizing the expectation term w.r.t $\theta$ we get a better estimate of $\mathcal{L}(q)$ and since the KL divergence is non-negative, $\ln p(X)$ increases at least as much as the increase in $\mathcal{L}(q)$.

References:

  • Wikipedia - An alternate explanation that really clicked for me.
$\endgroup$
1
  • $\begingroup$ I also realize now that the last equation in the question $∑p(Z|X,θ^{old})\ln p(Z|X,θ)= −(KL(q||p) + const)$ can be rearranged and written as $∑p(Z|X,θ^{old})\ln p(Z|X,θ) + KL(q||p) = - const$ and so we see that maximizing the first term is equivalent to minimizing the second term and thus after getting the new improved estimate for $q(Z)$, $KL(q||p)$ value goes down and makes $\ln p(X|\theta)$ increase as we originally intended. $\endgroup$ Sep 27, 2020 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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