A simple approach for finding the globally optimal Bayesian network\n structure

2012/06/27 by Tomi Silander, Silander, Tomi, Petri Myllymäki +1 · 4 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

paper · pdf · doi:10.48550/arxiv.1206.6875

openalex publication_date 2012/06/27 · 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\nrespect to a decomposable score such as BDe, BIC or AIC. This problem is known\nto be NP-hard, which means that solving it becomes quickly infeasible as the\nnumber of variables increases. Nevertheless, in this paper we show that it is\npossible to learn the best Bayesian network structure with over 30 variables,\nwhich covers many practically interesting cases. Our algorithm is less\ncomplicated and more efficient than the techniques presented earlier. It can be\neasily parallelized, and offers a possibility for efficient exploration of the\nbest networks consistent with different variable orderings. In the experimental\npart of the paper we compare the performance of the algorithm to the previous\nstate-of-the-art algorithm. Free source-code and an online-demo can be found at\nhttp://b-course.hiit.fi/bene.\n

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\n 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

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 Candidate" Algorithm