Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks

Abstract

One of the basic tasks for Bayesian networks (BNs) is that of learning a network structure from data. The BN-learning problem is NP-hard, so the standard solution is heuristic search. Many approaches have been proposed for this task, but only a very small number outperform the baseline of greedy hill-climbing with tabu lists; moreover, many of the proposed algorithms are quite complex and hard to implement. In this paper, we propose a very simple and easy-to-implement method for addressing this task. Our approach is based on the well-known fact that the best network (of bounded in-degree) consistent with a given node ordering can be found very efficiently. We therefore propose a search not over the space of structures, but over the space of orderings, selecting for each ordering the best network consistent with it. This search space is much smaller, makes more global search steps, has a lower branching factor, and avoids costly acyclicity checks. We present results for this algorithm on both synthetic and real data sets, evaluating both the score of the network found and in the running time. We show that ordering-based search outperforms the standard baseline, and is competitive with recent algorithms that are much harder to implement.

Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

Cited by in corpus (15)

• CAM: Causal additive models, high-dimensional order search and penalized regression
• Parameterized Complexity Results for Exact Bayesian Network Structure Learning
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• Optimizing regularized Cholesky score for order-based learning of Bayesian networks
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• Approximate learning of high dimensional Bayesian network structures via pruning of Candidate Parent Sets
• A Recursive Markov Boundary-Based Approach to Causal Structure Learning
• Marginal integration for nonparametric causal inference
• Learning directed acyclic graphs via bootstrap aggregating
• Improving Accuracy of Permutation DAG Search using Best Order Score Search
• Learning the structure of Bayesian Networks: A quantitative assessment of the effect of different algorithmic schemes
• A Traveling Salesman Learns Bayesian Networks
• Solving All Regression Models For Learning Gaussian Networks Using Givens Rotations
• Renormalized Normalized Maximum Likelihood and Three-Part Code Criteria For Learning Gaussian Networks