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

Question

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

Answer 1

If you have the constraint that your DAG is indeed a tree, then the searched distribution appears to be the one you can learn with the Chow-Liu algorithm.

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