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

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

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


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.