# How to compute the KL-distance between 2 Bayesian networks?

Suppose I have a Bayesian network that can be factorized like this:

P(A,B,C,D)=P(A)*P(B)*P(C|A,B)*P(D|C)

Each of the variable is a binary and I've got all the tables of conditional probabilistic distribution.

I then simulate from this network and got a synthetic data-set:

    A  B  C  D
1  0  0  1
0  1  0  1
1  0  1  1
etc.


I then estimate the parameters (the probabilities) with MLE and Bayesian estimator from the synthetic data and would like to compare these 2 learners by their KL-distances against the true distribution at various sample sizes.

However, I'm not sure how to do it. The book I read about the relative entropy of Bayesian network just has notations in it and it's very hard to follow.

Thanks!

## 1 Answer

Each of your models is a joint distribution for the random variables $A, B, C, D$. This means you can calculate the probability according to each model that the random variables take particular values: $p(A=a, B=b, C=c, D=d)$. I'll use the shorthand $p(a, b, c, d)$ to mean the same thing (uppercase letters are random variables, lowercase are particular values).

Say the the true distribution is $p$ and the model is $q$.

In your case, the formula for KL divergence is:

$$D_{KL}(p \parallel q) = \sum_{a, b, c, d \in \{0, 1\}} p(a, b, c, d) \log \frac{p(a, b, c, d)}{q(a, b, c, d)}$$

The sum is taken over all possible values of $A, B, C, D$. You have 4 variables with 2 possible values each, so there are 16 possible joint configurations: $\{A=0, B=0, C=0, D=0\}$, $\{A=0, B=0, C=0, D=1\}$, etc. Loop over the 16 possible configurations. Determine the probability of each configuration according to each model. Plug those values into the expression above, taking the sum over all configurations.

• Thanks, but what if there are more nodes that makes it hard to enumerate the probability of each of its configuration? I've seen a formula in Koller and Friedman that I can somehow use the conditional probability distribution table without calculating the full joint, but that's where I got stuck actually. @user20160 – mackbox Aug 2 '16 at 23:20