This paper, presented at the 35th Canadian Conference on Artificial Intelligence, provides a much-needed reality check for how we evaluate and choose scoring functions for Bayesian network structure learning.
TL;DR
While most research focuses on finding a single "best" Bayesian network, this study reveals that the optimal scoring function changes significantly when using model averaging. By scaling experiments to larger networks, the authors demonstrate that the BDeu and qNML scoring functions outperform traditional favorites like BIC when combining multiple models to improve accuracy and discovery.
What Problem Does This Paper Address?
Bayesian networks (BNs) are powerful tools for "knowledge discovery"—mapping out the causal and probabilistic relationships between variables. To learn a BN from data, researchers use a scoring function to evaluate how well a proposed graph fits the data.
However, the field has been stuck in two ruts:
- Small Scale: Most empirical studies only look at tiny networks (under 20 variables).
- The "Winner-Take-All" Fallacy: Studies usually focus on finding one single best-scoring network. In practice, it is often better to use model averaging, which combines many high-scoring networks to provide a more robust "consensus" view and better density estimation.
The authors set out to determine which scoring functions actually perform best when you aren't just looking for one "lucky" graph, but are instead averaging across many.
Methods
The researchers compared five discrete scoring functions:
- Standard: AIC (Akaike Information Criterion), BIC/MDL (Bayesian Information Criterion), and BDeu (Bayesian Dirichlet equivalent uniform).
- Recent/Novel: qBDJ and qNML (Quotient Normalized Maximum Likelihood).
They tested these scores across two primary model averaging frameworks:
- The Bootstrap: Resampling the original dataset many times and learning a network for each sample.
- The Credible Set: Finding all networks that are "near-optimal" (within a certain score threshold of the best one) and weighting them.
To handle the massive computational cost of finding optimal structures for larger networks, they used GOBNILP, a state-of-the-art solver based on integer programming.
Datasets
The study used a robust mix of data:
- UCI Repository: 16 real-world datasets (e.g., census income, heart disease) ranging from 10 to 45 variables.
- bnlearn Repository: 10 well-known "ground truth" networks (e.g., Alarm, Insurance, Win95pts) with up to 76 variables.
- Synthetic Ground Truths: 80 additional networks were constructed based on the UCI datasets to provide a total of 90 ground truth benchmarks for evaluation.
Key Insights and Ideas
- The "Best" Score is Context-Dependent: Previous literature often recommended BIC for knowledge discovery. This paper shows that for model averaging, BIC is often too conservative (penalizing complexity too harshly), leading to many missing edges.
- BDeu’s Surprising Resilience: BDeu is technically "irregular" (it can yield unnecessarily complex structures in a single-network setting). However, in the bootstrap framework, this tendency actually helps it capture relationships that other scores miss, making it the top performer there.
- qNML is the New Contender: For the credible set framework, the recently proposed qNML score was the clear winner for knowledge discovery, balancing precision and recall better than the older standards.
- Density Estimation vs. Structure: If your goal is simply to predict data (density estimation), AIC is the clear winner. Interestingly, BIC—the darling of many structure-learning papers—was the worst performer for density estimation.
Key Results
The authors used the Borda count (a social choice ranking system) to aggregate results across hundreds of experiments:
- Knowledge Discovery (Bootstrap): BDeu was the preferred choice in most scenarios.
- Knowledge Discovery (Credible Set): qNML was the best choice for identifying the true underlying structure.
- Density Estimation: AIC dominated, with qNML trailing slightly behind as a strong second.
- Scalability: AIC and BIC are much easier to compute at scale because they have more effective "pruning rules" that allow the algorithm to ignore bad parent sets early. Scores like BDeu and qNML required manual limits on parent sets to finish within the 24-hour computation limit for larger networks.
Limitations and Future Work
The authors acknowledge that while they scaled up to 76 variables, modern "big data" can involve thousands of variables. Current exact model averaging methods (like the credible set) struggle to scale that far without significant approximations.
Additionally, the BDeu score relies on a hyperparameter ($\alpha$, the equivalent sample size) that is notoriously difficult to set correctly. While they used $\alpha=1$, future work could explore how sensitive these model-averaging results are to different hyperparameter choices.
Summary updated