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 (45)

• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Bayesian network learning with cutting planes
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• High-dimensional learning of linear causal networks via inverse covariance estimation
• 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
• Survey on Models and Techniques for Root-Cause Analysis
• Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs
• Advances in Bayesian Network Learning using Integer Programming
• Parameterized Complexity Results for Exact Bayesian Network Structure Learning
• Exact Structure Discovery in Bayesian Networks with Less Space
• Inferring large graphs using l1-penalized likelihood
• Optimizing regularized Cholesky score for order-based learning of Bayesian networks
• Learning Structures of Bayesian Networks for Variable Groups
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• 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
• Bayesian Structure Learning by Recursive Bootstrap
• Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks
• 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
• Approximate learning of high dimensional Bayesian network structures via pruning of Candidate Parent Sets
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
• Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
• Exact Maximum Margin Structure Learning of Bayesian Networks
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables
• Switching Regression Models and Causal Inference in the Presence of Discrete Latent Variables
• Structure Learning in Bayesian Networks of Moderate Size by Efficient Sampling
• Active Structure Learning of Bayesian Networks in an Observational Setting
• A polynomial-time algorithm for learning nonparametric causal graphs
• Exact Learning Augmented Naive Bayes Classifier
• Robust learning Bayesian networks for prior belief
• Learning Bayesian Networks with Low Rank Conditional Probability Tables
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Solving All Regression Models For Learning Gaussian Networks Using Givens Rotations
• On Finding Optimal Polytrees
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• Causal Discovery of Flight Service Process Based on Event Sequence
• Renormalized Normalized Maximum Likelihood and Three-Part Code Criteria For Learning Gaussian Networks
• Learning All Credible Bayesian Network Structures for Model Averaging