3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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