Árboles de Chow-Liu y divergencia de Kullback Leibler

Question

Estoy leyendo el libro de David Barber sobre razonamiento bayesiano y aprendizaje automático. En la sección 9.5.4 cubre los árboles de Chow-Liu, y estoy teniendo dificultades para entender el flujo de las ecuaciones después de que él introduce la divergencia KL como una forma de encontrar la mejor distribución aproximada. He escrito el problema a continuación.

Consideremos una distribución multivariante $p(x)$ que deseamos aproximar con una distribución $q(x)$ . Además, restringimos la aproximación $q(x)$ para ser una BN en la que cada nodo tiene como máximo 1 padre. En primer lugar, suponemos que hemos elegido un etiquetado particular de las variables D para que los hijos tengan índices de padres más altos que sus padres. La restricción de padre único del DAG significa entonces:

$q(x) = \prod ^D_{i=1}q(x_i|x_{pa(i)})$
$pa(i)<i$ o $pa(i) = \varnothing$ , donde $pa(i)$ es el índice de padre único del nodo $i$ .

Para encontrar la mejor distribución aproximada de esta clase restringida, podemos minimizar la divergencia KL:

$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)})}$

Mi pregunta es si estamos definiendo la divergencia KL como $KL(q|p) = \left \langle log\:q(x) - log\:p(x)\right \rangle_{q(x)}$

Entonces, ¿cómo se convirtió el subíndice en ${p(x_i, x_{pa(i)})}$ y no $p(x_i)$ en la ecuación antes de esto?

Answer 1

Desde $\log q(x_i | x_{\text{Pa}(i)})$ es una función de las variables aleatorias $x_i$ y $x_{\text{Pa}(i)}$ debemos tomar la expectativa con respecto a la distribución conjunta $p(x_i, x_{\text{Pa}(i)})$ .

Aquí está la secuencia completa de ecuaciones. $$\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*}$$ donde, de nuevo, la última igualdad se deduce del hecho de que $\log q(x_i | x_{\text{Pa}(i)})$ depende sólo de $x_i$ y $x_{\text{Pa}(i)}$ en lugar de todo el $x$ .