Calculating Complexity: DL(B)
Description Length of the Bayesian Network — 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:
, which stands for the number of bits required to represent the graph G of the Bayesian network,
represents the number of bits required to represent the set of probability tables P.
Calculating DL(G)
To calculate , we need to determine the number of nodes and the number of their parent nodes.
where
n is the number of random variables (nodes):
is the set of the random variables that are parents of in graph G
and is the number of parents of the random variable .
Calculating DL(P|G)
Computing is straightforward as it is proportional to the number of cells in all probability tables.
where
is the number of states of the random variable
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:
Last updated