One practical shortcoming of the ML score is that in comparing two models with graphical structure G and G ′ where G contains a proper subset of the edges of G ′ the ML score will never favor G . Thus, when using an ML score to choose among models without restricting the class of graphical structures, a fully connected structure is guaranteed to have a maximal score. This is problematic due to the potential for poor generalization error when using the resulting approximation. This problem is often called overfitting. When using this principle it is best to restrict the class of alternative structures under consideration in some suitable manner.

The minimum description length score can be viewed as a penalized version of the ML
score

$$Score_{\,M\,DL}\left(G,D\right)=Score_{\,M\,UL}\left(G,D\right)-\frac{d\log N}{2}\tag{2}$$ $$=\sum_{i}LocalScore_{\,M\,DL}\left(G,D\right)$$ $$LocalScore_{\,M\,DL}\left(X_{i},pa\left(X_{i}\right)\right)=$$ $$LocalScore_{\,ML}-\frac{\#(pa\left(X_{i}\right))\times(\#(X_{i})-1)\times\log N}{2}$$

where d = ∑ i ( \# ( pα ( X i )) × ( \# ( X i ) − 1)) and \# ( Y ) is used to denote the number of possible distinct assignments for a set of variables Y and the number of assignments for the empty set of variables is \#(0) = 1. The penalty term leads to more parsimonious models, thus, alleviating the overfitting problem described above.

Finally, a Bayesian score requires a prior over the alternative models and, for each model, a prior over the distributions. A commonly used family of priors for directed graphical models is described by Cooper & Herskovits (1992). In their approach, one assumes a uniform prior on alternative graphs, P(G) å 1, and an "uninformative" prior over distributions.

These assumptions lead to the following scoring function;

$$\begin{array}{r c l}{{S c o r\,e_{B a y e\,s}(G,D)}}&{{=}}&{{\log P(D|G)+\log P(G)}}\\ {{}}&{{}}&{{\propto}}&{{\sum_{i}L o c a l\,S c o r\,e_{B a y e\,s}(X_{i}\,,p a(X_{i}\,))}}\end{array}$$
$$Local\,Score_{Bayes}(X_{i},pa(X_{i}))=$$ $$\log\prod_{pa(x_{i})}\frac{(\#(X_{i})-1)!}{(\#(X_{i})-1)+N(pa(x_{i})))!}\prod_{x_{i}}N(x_{i},pa(x_{i}))!\tag{3}$$

Although not as apparent as in the MDL score, the Bayesian score also has a built-in tendency for parsimony that alleviates the problems of overfitting. The hardness results presented below can be extended to a variety of alternative types of priors including the BDe prior with an empty prior model (see Heckerman et al. 1995).

The problem of finding the optimal directed graphical model for a given class of structures G and data D is the problem of finding the structure G E G that maximizes Score ( G, D ).