|title||Minimum Description Length|
The Minimum Description Length (MDL) score is a two-component score that has been traditionally used in the Artificial Intelligence community for estimating the number of bits required to represent a model and the data given this model. For structural learning of Bayesian networks, the model is the Bayesian network (graph plus probability tables), whereas the number of bits for representing the data given the Bayesian network is inversely proportional to the probability of the observations returned by the model.
represents the BayesiaLab Structural Coefficient (the default value is 1), a parameter that allows changing the weight of the MDL structural part (the lower its value, the greater the complexity of the resulting networks),
- DL(B) the number of bits to represent the Bayesian network B (graph and probabilities), and
- DL(D|B) the number of bits to represent the dataset D given the Bayesian network B.
|title||Bayesian Network Part|
The number of bits to represent a Bayesian network is equal to the number of bits to represent the structure plus the number of bits to represent the probability distributions.
where G refers to the Graphical structure, and P to the set of Probability tables.
The coding of the structure implies the identification of each node plus its parents.
n is the number of random variables (nodes):
is the set of the random variables that are parents of in the graph G
- and is
and is the number of parents of random variable .
The number of bits to represent the probability distributions is proportional to the number of cells of the conditional probability tables.
- val(X) represents is the number of states of random variable X,
- p is the probability recorded in associated with the cell.
As this probability is not known prior to learning the network, we are using the following classical heuristic:
where N is the size number of observations in the datasetdata set.
The number of bits for representing the data given the Bayesian network is inversely proportional to the probability of the observations returned by the model.
- is the n-dimensional observation described in row j, and
- is the joint probability of this observation returned by the Bayesian network B.
The chain rule allows rewriting this equation with:
For each candidate Bayesian network, which is generated during the search and evaluated with the MDL score, the corresponding parameters are computed using Maximum Likelihood Estimation.