Subset verification and search algorithms for causal DAGs

• URL: http://arxiv.org/abs/2301.03180v3
• Date: Tue, 13 Feb 2024 05:11:17 GMT
• Title: Subset verification and search algorithms for causal DAGs
• Authors: Davin Choo, Kirankumar Shiragur
• Abstract summary: We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges) We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
• Score: 13.108039226223793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning causal relationships between variables is a fundamental task in causal inference and directed acyclic graphs (DAGs) are a popular choice to represent the causal relationships. As one can recover a causal graph only up to its Markov equivalence class from observations, interventions are often used for the recovery task. Interventions are costly in general and it is important to design algorithms that minimize the number of interventions performed. In this work, we study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges). Under the assumptions of faithfulness, causal sufficiency, and ideal interventions, we study this problem in two settings: when the underlying ground truth causal graph is known (subset verification) and when it is unknown (subset search). For the subset verification problem, we provide an efficient algorithm to compute a minimum sized interventional set; we further extend these results to bounded size non-atomic interventions and node-dependent interventional costs. For the subset search problem, in the worst case, we show that no algorithm (even with adaptivity or randomization) can achieve an approximation ratio that is asymptotically better than the vertex cover of the target edges when compared with the subset verification number. This result is surprising as there exists a logarithmic approximation algorithm for the search problem when we wish to recover the whole causal graph. To obtain our results, we prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.

Related papers

• Sample Efficient Bayesian Learning of Causal Graphs from Interventions [6.823521786512908]
  This study considers a Bayesian approach for learning causal graphs with limited interventional samples. We show theoretically that our proposed algorithm will return the true causal graph with high probability. We present a case study showing how this algorithm could be modified to answer more general causal questions without learning the whole graph.
  arXiv  Detail & Related papers  (2024-10-26T05:47:56Z)
• Adaptive Online Experimental Design for Causal Discovery [9.447864414136905]
  Causal discovery aims to uncover cause-and-effect relationships encoded in causal graphs. We focus on data interventional efficiency and formalize causal discovery from the perspective of online learning. We propose a track-and-stop causal discovery algorithm that adaptively selects interventions from the graph separating system.
  arXiv  Detail & Related papers  (2024-05-19T13:26:33Z)
• Causal Discovery under Off-Target Interventions [18.92683981229985]
  Causal graph discovery is a significant problem with applications across various disciplines. This work addresses the causal discovery problem under the setting of interventions with the natural goal of minimizing the number of interventions performed.
  arXiv  Detail & Related papers  (2024-02-13T05:43:49Z)
• Meek Separators and Their Applications in Targeted Causal Discovery [17.84347390320128]
  We focus on two well-motivated problems: subset search and causal matching. We present an efficient algorithm to find Meek separators that are of small sizes. Our results provide the first known average-case provable guarantees for both problems.
  arXiv  Detail & Related papers  (2023-10-30T23:15:27Z)
• Predictive Coding beyond Correlations [59.47245250412873]
  We show how one of such algorithms, called predictive coding, is able to perform causal inference tasks. First, we show how a simple change in the inference process of predictive coding enables to compute interventions without the need to mutilate or redefine a causal graph.
  arXiv  Detail & Related papers  (2023-06-27T13:57:16Z)
• Nonparametric Identifiability of Causal Representations from Unknown Interventions [63.1354734978244]
  We study causal representation learning, the task of inferring latent causal variables and their causal relations from mixtures of the variables. Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show to be irresolvable from interventional data.
  arXiv  Detail & Related papers  (2023-06-01T10:51:58Z)
• New metrics and search algorithms for weighted causal DAGs [7.424262881242935]
  We study causal graph discovery via adaptive interventions with node-dependent costs. We define a new benchmark that captures the worst-case interventional cost for any search algorithm. We provide adaptive search algorithms that achieve logarithmic approximations under various settings.
  arXiv  Detail & Related papers  (2023-05-08T03:48:37Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Active Bayesian Causal Inference [72.70593653185078]
  We propose Active Bayesian Causal Inference (ABCI), a fully-Bayesian active learning framework for integrated causal discovery and reasoning. ABCI jointly infers a posterior over causal models and queries of interest. We show that our approach is more data-efficient than several baselines that only focus on learning the full causal graph.
  arXiv  Detail & Related papers  (2022-06-04T22:38:57Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Learning Neural Causal Models with Active Interventions [83.44636110899742]
  We introduce an active intervention-targeting mechanism which enables a quick identification of the underlying causal structure of the data-generating process. Our method significantly reduces the required number of interactions compared with random intervention targeting. We demonstrate superior performance on multiple benchmarks from simulated to real-world data.
  arXiv  Detail & Related papers  (2021-09-06T13:10:37Z)

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.