To calculate the description length of the data given the Bayesian network, we utilize the fact that the description length is inversely proportional to the probability of the observed data inferred by the model.
where
The chain rule allows rewriting this equation with:
is the n-dimensional observation described in row , and
is the joint probability of this observation returned by the Bayesian network .
The Minimum Description Length Score (MDL Score) is derived from Information Theory and has been used extensively in the Artificial Intelligence community.
It consists of the sum of two components that estimate:
the minimum number of bits required to represent a model, and
the minimum number of bits required to represent the data given the model.
However, in the specific context of Bayesian networks, we need to explain the exact meaning and the notation of these two components:
Calculating Complexity: DL(B)Calculating Fit: DL(D|B)"the minimum number of bits required to represent a model" is denoted (="Description Length of the Bayesian network ") and refers to the structural complexity of the Bayesian network model , which includes the network graph and all probability tables.
For brevity, we often use the shorthand "complexity" or "structure" to refer to .
Small values of suggest a simple model structure, and large values a complex model.
The goal of this structural part is to apply Occam's Razor, or the law of parsimony, i.e., to choose the simplest hypothesis, all other things being equal.
"the minimum number of bits required to represent the data given the model" is denoted (="Description Length of the data given the Bayesian network ") and refers to the likelihood of the data with respect to the Bayesia network model .
The data likelihood is inversely proportional to the probability of the observed dataset, as inferred by the Bayesian network model.
Put simply, refers to the "fit" of the model to the data.
Small values of suggest a well-fitting model; large values, conversely, imply a poor fit.
BayesiaLab attempts to minimize the MDL Score by evaluating candidate networks during structural learning.
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.
To calculate , we need to determine the number of nodes and the number of their parent nodes.
DL(G) = \sum\limits_i^n {\left( {{{\log }_2}(n) + {{\log }_2}\left( {\begin{array}{*{20}{c}} n\\ {\left\| {P{a_i}} \right\|} \end{array}} \right)} \right)}
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 .
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: