Stable Structure Learning with HC-Stable and Tabu-Stable Algorithms

• URL: http://arxiv.org/abs/2504.01740v1
• Date: Wed, 02 Apr 2025 13:51:44 GMT
• Title: Stable Structure Learning with HC-Stable and Tabu-Stable Algorithms
• Abstract summary: We show that some widely-used score-based algorithms, as well as hybrid and constraint-based algorithms, suffer from the same issue.<n>We propose a novel solution for score-based greedy hill-climbing that eliminates instability by determining a stable node order.<n>Two implementations, HC-Stable and Tabu-Stable, are introduced. Tabu-Stable achieves the highest BIC scores across all networks, and the highest accuracy for categorical networks.
• Score: 6.691151987390148
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many Bayesian Network structure learning algorithms are unstable, with the learned graph sensitive to arbitrary dataset artifacts, such as the ordering of columns (i.e., variable order). PC-Stable attempts to address this issue for the widely-used PC algorithm, prompting researchers to use the "stable" version instead. However, this problem seems to have been overlooked for score-based algorithms. In this study, we show that some widely-used score-based algorithms, as well as hybrid and constraint-based algorithms, including PC-Stable, suffer from the same issue. We propose a novel solution for score-based greedy hill-climbing that eliminates instability by determining a stable node order, leading to consistent results regardless of variable ordering. Two implementations, HC-Stable and Tabu-Stable, are introduced. Tabu-Stable achieves the highest BIC scores across all networks, and the highest accuracy for categorical networks. These results highlight the importance of addressing instability in structure learning and provide a robust and practical approach for future applications. This extends the scope and impact of our previous work presented at Probabilistic Graphical Models 2024 by incorporating continuous variables. The implementation, along with usage instructions, is freely available on GitHub at https://github.com/causal-iq/discovery.

Related papers

• Scalable Bayesian Network Structure Learning Using Tsetlin Machine to Constrain the Search Space [10.753354249346073]
  The PC algorithm is a widely used method in causal inference for learning the structure of Bayesian networks.<n>Despite its popularity, the PC algorithm suffers from significant time complexity, particularly as the size of the dataset increases.<n>We propose a novel approach that utilise the Tsetlin Machine (TM) to construct Bayesian structures more efficiently.
  arXiv  Detail & Related papers  (2025-11-24T16:23:19Z)
• A Full DAG Score-Based Algorithm for Learning Causal Bayesian Networks with Latent Confounders [0.0]
  Causal Bayesian networks (CBN) are popular graphical probabilistic models that encode causal relations among variables. This paper introduces the first fully score-based structure learning algorithm searching the space of DAGs that is capable of identifying the presence of some latent confounders.
  arXiv  Detail & Related papers  (2024-08-20T20:25:56Z)
• Revisiting Nearest Neighbor for Tabular Data: A Deep Tabular Baseline Two Decades Later [76.66498833720411]
  We introduce a differentiable version of $K$-nearest neighbors (KNN) originally designed to learn a linear projection to capture semantic similarities between instances.<n>Surprisingly, our implementation of NCA using SGD and without dimensionality reduction already achieves decent performance on tabular data.<n>We conclude our paper by analyzing the factors behind these improvements, including loss functions, prediction strategies, and deep architectures.
  arXiv  Detail & Related papers  (2024-07-03T16:38:57Z)
• Generalization Bounds for Dependent Data using Online-to-Batch Conversion [0.6144680854063935]
  We upper bound the generalization error of batch learning algorithms trained on samples drawn from a mixing process. Our work does not require any stability assumptions on the batch learner. We prove that the EWA algorithm, a textbook family of online learning algorithms, satisfies our new notion of stability.
  arXiv  Detail & Related papers  (2024-05-22T14:07:25Z)
• GEC-DePenD: Non-Autoregressive Grammatical Error Correction with Decoupled Permutation and Decoding [52.14832976759585]
  Grammatical error correction (GEC) is an important NLP task that is usually solved with autoregressive sequence-to-sequence models. We propose a novel non-autoregressive approach to GEC that decouples the architecture into a permutation network. We show that the resulting network improves over previously known non-autoregressive methods for GEC.
  arXiv  Detail & Related papers  (2023-11-14T14:24:36Z)
• Fast Approximation of Similarity Graphs with Kernel Density Estimation [12.321755440062732]
  We present a new algorithm for constructing a similarity graph from a set $X$ of data points in $mathbbRd$. Our presented algorithm is based on the kernel density estimation problem, and is applicable for arbitrary kernel functions.
  arXiv  Detail & Related papers  (2023-10-21T00:32:47Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. Experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T10:18:33Z)
• Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
  We develop LIBO, an algorithm which adapts to the environment by learning from past experience. We assume a kernelized structure where the kernel is unknown but shared across all tasks. Our algorithm can be paired with any kernelized or linear bandit algorithm and guarantees optimal performance.
  arXiv  Detail & Related papers  (2022-10-27T14:48:49Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Hybrid Bayesian network discovery with latent variables by scoring multiple interventions [5.994412766684843]
  We present the hybrid mFGS-BS (majority rule and Fast Greedy equivalence Search with Bayesian Scoring) algorithm for structure learning from discrete data. The algorithm assumes causal insufficiency in the presence of latent variables and produces a Partial Ancestral Graph (PAG) Experimental results show that mFGS-BS improves structure learning accuracy relative to the state-of-the-art and it is computationally efficient.
  arXiv  Detail & Related papers  (2021-12-20T14:54:41Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.