Impact of Learning Strategies on the Quality of Bayesian Networks: An Empirical Evaluation

Brandon M. Malone, Matti Järvisalo, Petri MyllymäkiUAI 2015

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:

  1. Hill Climbing with Tabu List (tabu): A local search method exploring the space of directed acyclic graphs (DAGs).
  2. Max-Min Hill Climbing (mmhc): A hybrid approach using statistical pruning followed by local search.
  3. Chow-Liu (cl): An efficient algorithm for optimal tree-structured networks.
  4. 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.

Table of algorithms and summary of performance distributions.

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.

Performance distribution across UCI real-world datasets.

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

BibTeX
@inproceedings{malone2015impact,
  author = {Brandon M. Malone and Matti Järvisalo and Petri Myllymäki},
  title = {{Impact of Learning Strategies on the Quality of Bayesian Networks: An Empirical Evaluation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure