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|G)$ represents the number of bits required to represent the set of probability tables $P$ .

DL(B) = DL(G) + DL(P|G)

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

DL(G) = \sum_{i=1}^n \left( \log_2(n) + \log_2 \binom{n}{\|P_{a_i}\|} \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|G)$ is straightforward as it is proportional to the number of cells in all probability tables.

DL(P|G) = \sum\limits_i^n {\left( {\prod\limits_j^{\left\| {P{a_i}} \right\|} {{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:

DL(p) = \frac{{{{\log }_2}(N)}}{2}