Currently the most popular model selection criterion for learning Bayesian networks is the Bayesian mixture with a conjugate prior. This method has recently been reported to be very sensitive to the choice of prior hyper-parameters. On the other hand, the general model selection criteria, AIC and BIC are derived through asymptotics and their behavior is suboptimal for small sample sizes.

In this work we introduce a new effective scoring criterion for learning Bayesian network structures, the factorized normalized maximum likelihood. This score features no tunable parameters thus avoiding the sensitivity problems of Bayesian scores. The new scoring method also suggests a parametrization of the Bayesian network that is based on the conditional normalized maximum likelihood predictive distribution.