Optimizing regularized Cholesky score for order-based learning of Bayesian networks

Abstract

Bayesian networks are a class of popular graphical models that encode causal and conditional independence relations among variables by directed acyclic graphs (DAGs). We propose a novel structure learning method, annealing on regularized Cholesky score (ARCS), to search over topological sorts, or permutations of nodes, for a high-scoring Bayesian network. Our scoring function is derived from regularizing Gaussian DAG likelihood, and its optimization gives an alternative formulation of the sparse Cholesky factorization problem from a statistical viewpoint, which is of independent interest. We combine global simulated annealing over permutations with a fast proximal gradient algorithm, operating on triangular matrices of edge coefficients, to compute the score of any permutation. Combined, the two approaches allow us to quickly and effectively search over the space of DAGs without the need to verify the acyclicity constraint or to enumerate possible parent sets given a candidate topological sort. The annealing aspect of the optimization is able to consistently improve the accuracy of DAGs learned by local search algorithms. In addition, we develop several techniques to facilitate the structure learning, including pre-annealing data-driven tuning parameter selection and post-annealing constraint-based structure refinement. Through extensive numerical comparisons, we show that ARCS achieves substantial improvements over existing methods, demonstrating its great potential to learn Bayesian networks from both observational and experimental data.

arXiv comment15 pages, 7 figures, 5 tables

References in corpus (22)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Nearly unbiased variable selection under minimax concave penalty
• A simple approach for finding the globally optimal Bayesian network structure
• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Covariance Estimation: The GLM and Regularization Perspectives
• Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks
• Sparse inverse covariance estimation with the lasso
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Inferring large graphs using l1-penalized likelihood
• Penalized Estimation of Directed Acyclic Graphs From Discrete Data
• Scaling up Greedy Causal Search for Continuous Variables

Cited by in corpus (8)

• Distributed Learning of Generalized Linear Causal Networks
• Mitigating Prior Errors in Causal Structure Learning: A Resilient Approach via Bayesian Networks
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms
• Bayesian Inference Forgetting
• From Target Tracking to Targeting Track -- Part II: Regularized Polynomial Trajectory Optimization
• Sparse Cholesky covariance parametrization for recovering latent structure in ordered data
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• Learning Gaussian DAGs from Network Data