##### Child pages
• Score-Based Learning Algorithms

## Key

• This line was removed.
• Formatting was changed.

...

Localtab Group
Localtab
active true 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.

where:

•

Image Added 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.
Localtab
title Bayesian Network Part
Localtab Group
Localtab
active true DL(B)

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.

Localtab
title DL(G)

The coding of the structure implies the identification of each node plus its parents.

where

• n is the number of random variables (nodes):

• Image Added is the set of the random variables that are parents of Image Added in the graph G

• and  is

and Image Added is the number of parents of random variable Image Added.

Localtab
title DL(P|G)

The number of bits to represent the probability distributions is proportional to the number of cells of the conditional probability tables.

where

• val(X) represents Image Added is the number of states of random variable XImage Added,
• 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.

Localtab
title Data Part

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.

where

• Image Added is the n-dimensional observation described in row j, and
• Image Added is the joint probability of this observation returned by the Bayesian network B.

The chain rule allows rewriting this equation with: