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

Calculating DL(G)

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

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

Calculating DL(P|G)

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

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: