A simple approach for finding the globally optimal Bayesian network structure

2012/06/27 by Tomi Silander, Silander, Tomi, Petri Myllymäki +2 · 6 citations
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Quality and Management #FOS: Computer and information sciences #Multi-Criteria Decision Making #cs.AI

paper · pdf · doi:10.48550/arxiv.1206.6875

Appears in Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (UAI2006)

arxiv created 2012/06/27 · openalex publication_date 2012/06/27 · arxiv updated 2012/07/02 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

We study the problem of learning the best Bayesian network structure with respect to a decomposable score such as BDe, BIC or AIC. This problem is known to be NP-hard, which means that solving it becomes quickly infeasible as the number of variables increases. Nevertheless, in this paper we show that it is possible to learn the best Bayesian network structure with over 30 variables, which covers many practically interesting cases. Our algorithm is less complicated and more efficient than the techniques presented earlier. It can be easily parallelized, and offers a possibility for efficient exploration of the best networks consistent with different variable orderings. In the experimental part of the paper we compare the performance of the algorithm to the previous state-of-the-art algorithm. Free source-code and an online-demo can be found at http://b-course.hiit.fi/bene.

Citations

• Large-Sample Learning of Bayesian Networks is NP-Hard
• A Transformational Characterization of Equivalent Bayesian Network Structures

Cited by

• Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning
• Learning networks determined by the ratio of prior and data
• On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter
• Modeling Discrete Interventional Data using Directed Cyclic Graphical Models
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables
• An Improved Admissible Heuristic for Learning Optimal Bayesian Networks
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Bayesian network learning with cutting planes
• Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization
• Bayesian structure learning using dynamic programming and MCMC
• Learning the Bayesian Network Structure: Dirichlet Prior versus Data
• Exact Structure Discovery in Bayesian Networks with Less Space
• Computing Posterior Probabilities of Structural Features in Bayesian Networks
• GoT-CD: Graph-of-Thoughts Causal Discovery and the Fragility of Post-hoc Path-Specific Fairness Audits

Related

• A Greedy, Flexible Algorithm to Learn an Optimal Bayesian Network Structure
• An Efficient Procedure for Computing Bayesian Network Structure Learning
• Learning the structure of Bayesian Networks: A quantitative assessment\n of the effect of different algorithmic schemes
• An Improved Admissible Heuristic for Learning Optimal Bayesian Networks
• Learning Bayesian Network Structure from Massive Datasets: The "Sparse\n Candidate" Algorithm