Calculating Complexity: DL(B)

Description Length of the Bayesian Network — DL(B)

$DL(B)$ is the number of bits required to represent a Bayesian network. We can break down this value into the sum of two components:

$DL(G)$ , which stands for the number of bits required to represent the graph $G$ of the Bayesian network,

$DL(P \mid G)$ represents the number of bits required to represent the set of probability tables $P$ .

$\displaystyle DL(B) = DL(G) + DL(P \mid G)$

To calculate $DL(G)$ , we need to determine the number of nodes and the number of their parent nodes.

$\displaystyle DL(G) = \sum_{i=1}^n \left( \log_2(n) + \log_2 \binom{n}{\lvert P_{a_i}\rvert} \right)$

where

$n$ is the number of random variables (nodes): ${X_1},...,{X_n}$

$P{a_i}$ is the set of the random variables that are parents of ${X_i}$ in graph $G$

and $P{a_i}$ is the number of parents of the random variable ${X_i}$ .

Computing $DL(P \mid G)$ is straightforward as it is proportional to the number of cells in all probability tables.

$\displaystyle DL(P \mid G) = \sum_{i=1}^n \left( \prod_{j=1}^{\lvert P_{a_i}\rvert} S_j \times (S_i - 1) \times DL(p) \right)$

where

${S_i}$ is the number of states of the random variable ${X_i}$

$p$ is the probability associated with the cell.

As the probability p cannot be known prior to learning the network, we use the following classical heuristic in BayesiaLab:

$\displaystyle DL(p) = \frac{\log_2(N)}{2}$