Chow-Liu trees and Kullback Leibler divergence

Question

I'm reading David Barber's book on Bayesian Reasoning and Machine Learning. At Section 9.5.4 he covers Chow-Liu trees, and I am having difficulties understanding the flow of the equations after he introduces KL divergence as a way to find the best approximating distribution. I have typed out the problem below.

Consider a multivariate distribution $p(x)$ that we wish to approximate with a distribution $q(x)$. Furthermore, we constrain the approximation $q(x)$ to be a BN in which each node has at most 1 parent. First we assume that we have chosen a particular labeling of D variables so that children have higher parent indices than their parents. The DAG single parent constraint then means:

$q(x) = \prod ^D_{i=1}q(x_i|x_{pa(i)})$
$pa(i)<i$ , or $pa(i) = \varnothing$, where $pa(i)$ is the single parent index of node $i$.

To find the best approximating distribution of this constrained class, we may minimise the KL divergence:

$KL(p|q) = \left \langle log\:p(x)\right \rangle_{p(x)} - \sum^D_{i=1}\left \langle log\:q(x_i|x_{pa(i)})\right \rangle_{p(x_i, x_{pa(i)})}$

My question is if we are defining the KL divergence as $KL(q|p) = \left \langle log\:q(x) - log\:p(x)\right \rangle_{q(x)}$

Then how did the subscript turn out to become ${p(x_i, x_{pa(i)})}$ and not $p(x_i)$ in the equation before this?

Answer 1

Since $\log q(x_i | x_{\text{Pa}(i)})$ is a function of the random variables $x_i$ and $x_{\text{Pa}(i)}$, we must take the expectation with respect to the joint distribution $p(x_i, x_{\text{Pa}(i)})$.

Here's the full sequence of equations. $$ \begin{align*} \text{KL}(p|q) & = \langle \log p(x) - \log q(x) \rangle_{p(x)} \\ & = \langle \log p(x) \rangle_{p(x)} - \langle \log q(x) \rangle_{p(x)} && \text{(linearity of expectation)} \\ & = \langle \log p(x) \rangle_{p(x)} - \left\langle \log \textstyle\prod ^D_{i=1}q(x_i|x_{\text{Pa}(i)}) \right\rangle_{p(x)} \\ & = \langle \log p(x) \rangle_{p(x)} - \left\langle \textstyle\sum ^D_{i=1} \log q(x_i|x_{\text{Pa}(i)}) \right\rangle_{p(x)} \\ & = \langle \log p(x) \rangle_{p(x)} - \textstyle\sum ^D_{i=1} \langle \log q(x_i|x_{\text{Pa}(i)}) \rangle_{p(x)} && \text{(linearity of expectation)} \\ & = \langle \log p(x) \rangle_{p(x)} - \textstyle\sum ^D_{i=1} \langle \log q(x_i|x_{\text{Pa}(i)}) \rangle_{p(x_i, x_{\text{Pa}(i)})} \end{align*} $$ where, again, the last equality follows from the fact that $\log q(x_i | x_{\text{Pa}(i)})$ depends only on $x_i$ and $x_{\text{Pa}(i)}$ rather than all of $x$.