A Fast Non-parametric Approach for Causal Structure Learning in Polytrees

• URL: http://arxiv.org/abs/2111.14969v1
• Date: Mon, 29 Nov 2021 21:26:48 GMT
• Title: A Fast Non-parametric Approach for Causal Structure Learning in Polytrees
• Authors: Mona Azadkia, Armeen Taeb, Peter B\"uhlmann
• Abstract summary: We develop DAG-FOCI, a fast algorithm for causal structure learning with no assumptions on the functional relationships and noise. We demonstrate the applicability of DAG-FOCI on real data from computational biology citesachs2005causal and illustrate the robustness of our methods to violations of assumptions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of causal structure learning with no assumptions on the functional relationships and noise. We develop DAG-FOCI, a computationally fast algorithm for this setting that is based on the FOCI variable selection algorithm in \cite{azadkia2019simple}. DAG-FOCI requires no tuning parameter and outputs the parents and the Markov boundary of a response variable of interest. We provide high-dimensional guarantees of our procedure when the underlying graph is a polytree. Furthermore, we demonstrate the applicability of DAG-FOCI on real data from computational biology \cite{sachs2005causal} and illustrate the robustness of our methods to violations of assumptions.

Related papers

• Causal discovery for linear causal model with correlated noise: an Adversarial Learning Approach [5.276544734565369]
  This paper proposes an approach based on the f-GAN framework, learning the binary causal structure independent of specific weight values.<n>We prove that this problem is equivalent to minimizing the f-divergence between the true data distribution and the model-generated distribution.
  arXiv  Detail & Related papers  (2026-01-04T04:40:04Z)
• Nonlinear Causal Discovery through a Sequential Edge Orientation Approach [5.807183284468881]
  We propose a sequential procedure to orient undirected edges in a completed partial DAG.<n>We prove that this procedure can recover the true causal DAG assuming a restricted ANM.<n>We develop a novel constraint-based algorithm for learning causal DAGs under nonlinear ANMs.
  arXiv  Detail & Related papers  (2025-06-05T21:08:13Z)
• LOCAL: Learning with Orientation Matrix to Infer Causal Structure from Time Series Data [51.47827479376251]
  LOCAL is a highly efficient, easy-to-implement, and constraint-free method for recovering dynamic causal structures. Asymptotic Causal Learning Mask (ACML) and Dynamic Graph Learning (DGPL) Experiments on synthetic and real-world datasets demonstrate that LOCAL significantly outperforms existing methods.
  arXiv  Detail & Related papers  (2024-10-25T10:48:41Z)
• Induced Covariance for Causal Discovery in Linear Sparse Structures [55.2480439325792]
  Causal models seek to unravel the cause-effect relationships among variables from observed data. This paper introduces a novel causal discovery algorithm designed for settings in which variables exhibit linearly sparse relationships.
  arXiv  Detail & Related papers  (2024-10-02T04:01:38Z)
• Non-negative Weighted DAG Structure Learning [12.139158398361868]
  We address the problem of learning the true DAGs from nodal observations. We propose a DAG recovery algorithm based on the method that is guaranteed to return ar.
  arXiv  Detail & Related papers  (2024-09-12T09:41:29Z)
• Order-based Structure Learning with Normalizing Flows [7.972479571606131]
  Estimating causal structure of observational data is a challenging search problem that scales super-exponentially with graph size. Existing methods use continuous relaxations to make this problem computationally tractable but often restrict the data-generating process to additive noise models (ANMs) We present Order-based Structure Learning with Normalizing Flows (OSLow), a framework that relaxes these assumptions using autoregressive normalizing flows.
  arXiv  Detail & Related papers  (2023-08-14T22:17:33Z)
• Heteroscedastic Causal Structure Learning [2.566492438263125]
  We tackle the heteroscedastic causal structure learning problem under Gaussian noises. By exploiting the normality of the causal mechanisms, we can recover a valid causal ordering. The result is HOST (Heteroscedastic causal STructure learning), a simple yet effective causal structure learning algorithm.
  arXiv  Detail & Related papers  (2023-07-16T07:53:16Z)
• Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
  We propose a dynamic causal space for DAG structure learning, coined CASPER. It integrates the graph structure into the score function as a new measure in the causal space to faithfully reflect the causal distance between estimated and ground truth DAG.
  arXiv  Detail & Related papers  (2023-06-05T12:20:40Z)
• On the Sparse DAG Structure Learning Based on Adaptive Lasso [39.31370830038554]
  We develop a data-driven DAG structure learning method without the predefined threshold, called adaptive NOTEARS [30] We show that adaptive NOTEARS enjoys the oracle properties under some specific conditions. Furthermore, simulation results validate the effectiveness of our method, without setting any gap of edges around zero.
  arXiv  Detail & Related papers  (2022-09-07T05:47:59Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs [77.34726150561087]
  We introduce the R package for causal discovery and causal effect estimation from observational data. Our implementation scales efficiently with the number of observations and, whenever the DAGs are sufficiently sparse, the number of variables in the dataset. We then illustrate the main functions and algorithms on both real and simulated datasets.
  arXiv  Detail & Related papers  (2022-01-28T09:30:32Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables [28.893119229428713]
  We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables. In particular, we generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formalize the IP-based ADMG learning model.
  arXiv  Detail & Related papers  (2021-02-05T12:10:16Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)

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.