A Novel Algorithm for Scalable and Accurate Bayesian Network Learning

Laura E. Brown, Ioannis Tsamardinos, Constantin F. AliferisMedInfo 2004 · DOI

TL;DR

This paper introduces Max-Min Hill-Climbing (MMHC), a new algorithm for learning Bayesian Networks (BNs) from data that significantly improves upon existing methods like Sparse Candidate (SC). MMHC achieves more accurate network structures, better probability estimates, and is substantially more scalable, especially for large datasets, by intelligently estimating parent sets and avoiding the need for users to guess critical parameters.

What Problem Does This Paper Address?

Bayesian Networks (BNs) are powerful tools for decision support and causal discovery, particularly in fields like biomedicine. However, learning these networks from data has been a significant challenge, especially as datasets grow larger. Traditional algorithms struggle to scale beyond a few hundred variables, making it difficult to leverage the wealth of data now available in areas like genomics and clinical informatics. The Sparse Candidate (SC) algorithm was a step forward, but it relies on a user-defined parameter (k, the maximum number of parents) that, if set incorrectly, can lead to suboptimal or even erroneous network structures. This paper addresses the need for a BN learning algorithm that is both accurate and highly scalable, without requiring users to guess critical structural parameters.

Methods

The paper introduces the Max-Min Hill-Climbing (MMHC) algorithm, which builds upon and improves the Sparse Candidate (SC) algorithm. The core innovation lies in how MMHC estimates the "candidate parent sets" for each variable. Instead of relying on heuristics and multiple iterations like SC, MMHC uses the Max-Min Parents and Children (MMPC) algorithm. MMPC is a constraint-based method that soundly and efficiently identifies a superset of the true parents and children for a given target variable. This has several key advantages:

  • Automatic Parameter Setting: MMPC determines the candidate sets individually for each variable, eliminating the need for the user to guess the k parameter.
  • Improved Accuracy: MMPC's more accurate candidate set estimation leads to discovered networks that are structurally closer to the true data-generating network.
  • Computational Efficiency: MMHC requires only one iteration of candidate set estimation and hill-climbing, making it significantly faster than SC, which often needs multiple iterations.

The MMHC algorithm then performs a standard greedy hill-climbing search, but crucially, it only considers adding edges where the potential parent is in the MMPC-derived candidate set.

Datasets

The authors evaluated their algorithm on several real-world BN datasets from medicine and biology:

  • Alarm: A BN used in an expert system for monitoring intensive care patients.
  • Child: A network for diagnosing congenital heart defects in infants.
  • Munin: A BN used in an electromyography assistant application.
  • Gene: A network modeling gene regulatory pathways, constructed using a procedure similar to previous SC evaluations.

Additionally, they created synthetic networks by tiling and interconnecting copies of the Alarm network (Alarm3 and Alarm5) to test scalability with a controlled number of variables.

Key Insights and Ideas

  • The "k" parameter in SC is a double-edged sword: While it helps constrain the search space, an incorrect choice of k can severely degrade the accuracy of the learned network. Over-constraining (k too low) can lead to errors propagating throughout the network, causing false positives and missing true edges.
  • MMPC provides a principled way to estimate candidate parents: By leveraging conditional independence tests, MMPC can identify a superset of true parents and children more reliably than SC's heuristics. This is crucial for accurate BN learning.
  • One iteration is often enough: MMHC's strategy of using MMPC for initial candidate set estimation means it can achieve high-quality results in a single search cycle, drastically improving efficiency compared to SC's iterative approach.
  • Scalability is paramount: As datasets grow, algorithms that exhibit exponential time complexity (like SC with increasing k) become intractable. MMHC's linear growth in computation time with the number of variables makes it a much more viable option for modern large-scale data analysis.

Key Results

  • Improved Accuracy: MMHC consistently outperformed SC in terms of BDeu score (a measure of how well the network captures the data's probability distribution) across most datasets and sample sizes. For example, for Munin with 5000 samples, MMHC's network was 2.8 times more probable than SC's.
  • Fewer Structural Errors: MMHC made significantly fewer structural errors (incorrectly added, deleted, or reversed edges) compared to SC, especially when learning from larger datasets. This is critical for causal discovery applications.
  • Significant Speedup: MMHC was substantially faster than SC, particularly on larger networks. For Alarm5, MMHC was about 63 times faster, and for the Gene network, it was 49 times faster.
  • Scalability: MMHC's computation time grew linearly with the number of variables, whereas SC showed exponential growth, highlighting MMHC's superior scalability for large datasets.

Limitations and Future Work

  • Computational Cost of MMPC: While MMHC is more efficient overall, the MMPC algorithm itself can be computationally intensive, especially when conditional independence tests fail frequently, leading to large candidate sets. This was observed to be the case for the Child and Munin networks with small sample sizes.
  • Future Work: The authors suggest exploring improvements such as incorporating the "monotone faithfulness" assumption to further enhance time efficiency and using different statistical tests to increase accuracy. They also plan to compare MMHC with other standard BN learning algorithms on a broader range of datasets.

Summary updated

BibTeX
@inproceedings{brown2004novel,
  author = {Laura E. Brown and Ioannis Tsamardinos and Constantin F. Aliferis},
  title = {{A Novel Algorithm for Scalable and Accurate Bayesian Network Learning}},
  booktitle = {MedInfo},
  year = {2004},
  doi = {10.3233/978-1-60750-949-3-711},
}

Loading related content...

Figure