Optimizing Regularized Cholesky Score for Order-Based Learning of Bayesian Networks

Qiaoling Ye, Arash A. Amini, Qing ZhouIEEE TPAMI 2019 · DOI · OpenReview

TL;DR

This paper introduces ARCS, a novel method for learning Bayesian Networks (BNs) by optimizing a "regularized Cholesky score" over node orderings. ARCS combines global simulated annealing with a fast proximal gradient algorithm, significantly improving accuracy over existing methods for both observational and experimental data.

What Problem Does This Paper Address?

Learning the structure of Bayesian Networks (BNs) is crucial for understanding complex relationships between variables. Traditional methods often struggle with the high dimensionality and combinatorial complexity of the search space. Specifically, score-based methods that search over possible graph structures can be computationally prohibitive. While searching over "topological sorts" (ordered sequences of nodes) offers a more manageable search space and automatically enforces the acyclicity constraint of Directed Acyclic Graphs (DAGs), efficiently exploring this space and finding optimal structures remains challenging. Existing methods often get trapped in local optima or require computationally expensive steps. This paper aims to address these limitations by proposing a more efficient and accurate order-based search strategy.

Methods

The core of the proposed method, ARCS (Annealing on Regularized Cholesky Score), lies in its novel scoring function and optimization strategy.

  • Regularized Cholesky Score: The authors reformulate the problem of learning Gaussian BN structures as optimizing a "regularized Cholesky score." This score is derived from the Gaussian DAG likelihood and is connected to the problem of sparse Cholesky factorization. By introducing a concave penalty (Minimax Concave Penalty - MCP) to the Cholesky loss, the method encourages sparsity in the network structure, effectively breaking the symmetry that makes different topological sorts yield the same likelihood.
  • Order-Based Search: Instead of searching directly over DAGs, ARCS searches over the space of topological sorts (permutations of nodes). This significantly reduces the search space and guarantees acyclicity.
  • Global Optimization (Simulated Annealing): To explore the vast permutation space and avoid local optima, ARCS employs simulated annealing. This allows for a global search over possible node orderings.
  • Efficient Score Computation (Proximal Gradient): For each candidate permutation, computing its score involves optimizing a continuous problem over a lower triangular matrix. This is efficiently handled by a proximal gradient algorithm, which is well-suited for optimizing functions with both smooth and non-smooth components.
  • Data-Driven Parameter Selection: A Bayesian Information Criterion (BIC) is used to select the tuning parameters for the MCP penalty function, providing a principled way to adapt the regularization to the data.
  • Structure Refinement: After the annealing process, a constraint-based structure refinement step is applied to prune false positive edges, further improving accuracy.

Datasets

The paper evaluates ARCS on both simulated and real-world datasets.

  • Simulated Data: Data was generated from synthetic DAG structures and real-world networks (e.g., Asia, Sachs, Alarm, Barley) with varying numbers of variables ($p$) and edges ($s_0$), and different sample sizes ($n$). Both high-dimensional ($n < p$) and low-dimensional ($n > p$) settings were considered.
  • Real-World Networks: The authors used publicly available Bayesian networks from the bnlearn repository, including networks like Asia, Sachs, Alarm, Barley, Hailfinder, Andes, Hepar2, Win95pts, and Pigs. Some networks were duplicated to increase their size.

Key Insights and Ideas

  • Order-Based Search as Sparse Cholesky Factorization: The paper establishes a compelling link between learning Gaussian BN structures and the sparse Cholesky factorization problem. This provides a new perspective and allows leveraging techniques from numerical linear algebra.
  • Global Search + Local Optimization Synergy: ARCS effectively combines global search (simulated annealing over permutations) with efficient local optimization (proximal gradient for score computation). This hybrid approach is key to its success.
  • Concave Penalties for Sparsity: The use of Minimax Concave Penalty (MCP) is shown to be more effective than L1 penalties for promoting sparsity and achieving higher accuracy in BN structure learning.
  • Experimental Interventions Improve Accuracy: For learning causal structures, experimental interventions significantly improve accuracy, leading to lower SHDs and a reduced proportion of reversed edges compared to observational data alone.

Key Results

  • Substantial Accuracy Improvements: ARCS consistently outperformed existing state-of-the-art methods (CD, GES, HC, PC, MMHC, GA) across various datasets and settings, achieving significantly lower Structural Hamming Distances (SHD) and higher Jaccard Indices (JI). For instance, ARCS(GES) achieved SHD reductions of up to 40% on some networks.
  • Efficiency: The proximal gradient algorithm allows for efficient computation of the RC score, making the overall ARCS algorithm practical for larger networks.
  • Improved Parameter Selection: The BIC-based tuning parameter selection method proved effective, leading to better performance compared to methods with less principled parameter choices.
  • Experimental Data Advantage: ARCS demonstrated a significant advantage when using experimental intervention data, leading to more accurate causal structure recovery.

Limitations and Future Work

  • Computational Cost for Very Large Networks: While ARCS is efficient, the paper notes that for extremely large networks (e.g., $p > 50$), the annealing process might require more time to thoroughly search the permutation space. In such cases, initializing ARCS with estimates from other local methods and a low temperature is recommended.
  • Extension to Discrete BNs: The current framework is for Gaussian BNs. The authors suggest that extending ARCS to discrete BNs is a promising future direction, potentially by adapting the proximal gradient step for multinomial likelihoods.
  • Theoretical Properties: Future work could focus on establishing theoretical properties of the method, such as the consistency of the regularized Cholesky score and the convergence guarantees of the ARCS algorithm, especially when initialized with a good guess.
  • Alternative Operators for Annealing: Investigating different operators for proposing new permutations in the simulated annealing step could further enhance the search process.

Summary updated

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. We combine simulated annealing over permutation space 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 greedy and deterministic 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 outperformed existing methods by a substantial margin, demonstrating its great advantage in structure learning of Bayesian networks from both observational and experimental data. We also establish the consistency of our scoring function in estimating topological sorts and DAG structures in the large-sample limit. Source code of ARCS is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/yeqiaoling/arcs_bn</uri> .
BibTeX
@article{ye2019optimizing,
  author = {Qiaoling Ye and Arash A. Amini and Qing Zhou},
  title = {{Optimizing Regularized Cholesky Score for Order-Based Learning of Bayesian Networks}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2019},
  doi = {10.1109/tpami.2020.2990820},
}
Figure