A simple approach for finding the globally optimal Bayesian network structure

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.

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

References in corpus (2)

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

Cited by in corpus (18)

• Bayesian network learning with cutting planes
• A hybrid algorithm for Bayesian network structure learning with application to multi-label learning
• On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter
• Bayesian structure learning using dynamic programming and MCMC
• Exact Structure Discovery in Bayesian Networks with Less Space
• Learning networks determined by the ratio of prior and data
• An Improved Admissible Heuristic for Learning Optimal Bayesian Networks
• Modeling Discrete Interventional Data using Directed Cyclic Graphical Models
• Computing Posterior Probabilities of Structural Features in Bayesian Networks
• Advances in Learning Bayesian Networks of Bounded Treewidth
• Bayesian Model Averaging Using the k-best Bayesian Network Structures
• Learning the Bayesian Network Structure: Dirichlet Prior versus Data
• Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search
• Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
• Structure Learning in Bayesian Networks of Moderate Size by Efficient Sampling
• Exact Maximum Margin Structure Learning of Bayesian Networks
• Robust learning Bayesian networks for prior belief
• On Finding Optimal Polytrees