Abstract
This paper presents an extensive empirical evaluation of Bayesian network structure learning (BNSL) strategies, comparing approximate local search against provably optimal algorithms. The core finding is that "exact" algorithms, despite their computational cost, consistently produce networks that generalize better to unseen data, especially when allowed more complex structures (higher parent limits) and larger training sets.
Introduction
Learning the structure of a Bayesian Network (BN) from data is an NP-hard problem. Researchers typically choose between two paths: approximate methods (like hill climbing), which are fast but offer no guarantees, and exact methods (like Integer Linear Programming or A* search), which guarantee the highest-scoring structure but require exponential time and memory. The fundamental question addressed is whether the extra effort of finding a mathematically "optimal" structure is justified by improved generalization or if it merely leads to overfitting.
Methodology
The authors compared four distinct learning strategies:
- Hill Climbing with Tabu List (tabu): A local search method exploring the space of directed acyclic graphs (DAGs).
- Max-Min Hill Climbing (mmhc): A hybrid approach using statistical pruning followed by local search.
- Chow-Liu (cl): An efficient algorithm for optimal tree-structured networks.
- Provably Optimal (opt): Algorithms (A* and ILP) that find the global maximum of the scoring function.
Performance was evaluated using the BDeu scoring function, Structural Hamming Distance (SHD), and Predictive Likelihood. The study also varied the "parent limit" (k)—the maximum number of incoming edges allowed for any node—to assess the impact of structural constraints on generalization.
Datasets
The study utilized 29 datasets:
- UCI Repository ("Real-world"): 16 datasets from actual observations (e.g., agaricus, letter).
- Synthetic ("sam"): 13 datasets generated from known benchmark networks (e.g., alarm, insurance). Datasets ranged from 30 to 20,000 records and 17 to 60 variables.
Key Results and Discussion
The Overfitting Paradox
Approximate methods like tabu often performed worse when the parent limit was increased from 2 to 8, as the extra degrees of freedom were used to overfit training data. In contrast, exact methods (opt) effectively utilized the larger search space to find structures with better generalization.
Real-world vs. Synthetic Data
On synthetic datasets, even simple algorithms like Chow-Liu performed well. However, on real-world UCI data, the gap between exact and approximate methods widened significantly. Exact methods showed much more consistent performance across diverse data types.
Data Volume and Sparsity
Increased data volume generally improved model quality. Notably, for some datasets, exact algorithms with limited data could outperform local search algorithms using the full dataset. Additionally, mmhc tended to produce overly sparse networks on smaller datasets due to conservative statistical pruning.
Conclusion
Exact BNSL algorithms consistently achieve better predictive likelihood than approximate counterparts, particularly on real-world data and when allowed higher structural complexity. While computationally demanding, the resulting improvements in generalization suggest that exact methods are preferable when model quality is paramount. Future work should explore Bayesian Model Averaging and alternative complexity constraints like bounded treewidth.
Summary updated