# Minimizing KL divergence from a given distribution, according to a graph

Given $n$ discrete random variables $X_1,...,X_n$, a distribution $p$ on $X=(X_1,...,X_d)$ and a DAG (Directed Acyclic Graph) $G$ on $\{1,...,d\}$, which is the distribution $q$ factorizing with $G$ and minimizing the Kullback-Liebler divergence $D(p||q)$ with $p$ ?

I tried to use optimisation using Lagrange with constraints :

• $\sum\limits_{x\in\mathcal{X}}q(x)=1$
• $\forall x\in \mathcal{X},\ q(x)=\prod\limits_{i=1}^n q(x_i|x_{\pi_i})= \prod\limits_{i=1}^n \frac{q(x_i,x_{\pi_i})}{q(x_{\pi_i})} =\prod\limits_{i=1}^n \frac{\sum\limits_{x_j:j\not\in\pi_i\cup\{i\}}q(x)}{\sum\limits_{x_j:j\not\in\pi_i}q(x)}$

But unfortunately the second one is so complicated, particularly during the derivation stage, that this method led me nowhere. Since there is no explicit correction in the book where this question is asked, I am a bit puzzled about it.

Reminder : $q$ factorizes according to $G \Leftrightarrow$ $\forall x\in \mathcal{X},\ q(x)=\prod\limits_{i=1}^n q(x_i|x_{\pi_i})$ ($\Leftrightarrow \forall x\in \mathcal{X},\ q(x)=\prod\limits_{i=1}^n f_i(x_i,x_{\pi_i})$), $\pi_i$ representing the set of the parents of $i$ in $G$.

• When you write "the book", could you indicate which book it is? Thank you. – Xi'an Jan 2 '15 at 20:30
• It is a book written by Michael Jordan, and currently in preparation (not edited yet). – Thrastylon Jan 2 '15 at 22:25
• I imagine you wanted to write "Given $d$ discrete random varaibles..."? Also, $\mathcal{X}$ is where samples live (i.e $X \in \mathcal{X}$)? – Yair Daon Sep 5 '15 at 23:26

In the most general case I guess there is no closed form solution and it can be tackled with Bayesian Network structure learning algorithm when what you have is a dataset of observations for $X$.