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