Learning high-dimensional directed acyclic graphs with latent and selection variables

Abstract

We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) when allowing arbitrarily many latent and selection variables. The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. However, FCI is computationally infeasible for large graphs. We therefore propose the new RFCI algorithm, which is much faster than FCI. In some situations the output of RFCI is slightly less informative, in particular with respect to conditional independence information. However, we prove that any causal information in the output of RFCI is correct in the asymptotic limit. We also define a class of graphs on which the outputs of FCI and RFCI are identical. We prove consistency of FCI and RFCI in sparse high-dimensional settings, and demonstrate in simulations that the estimation performances of the algorithms are very similar. All software is implemented in the R-package pcalg.

Published in at http://dx.doi.org/10.1214/11-AOS940 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• High-dimensional graphs and variable selection with the Lasso
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• Estimating high-dimensional intervention effects from observational data
• Learning high-dimensional directed acyclic graphs with latent and selection variables
• Markov equivalence for ancestral graphs
• Adjacency-Faithfulness and Conservative Causal Inference

Cited by in corpus (21)

• Learning high-dimensional directed acyclic graphs with latent and selection variables
• CAM: Causal additive models, high-dimensional order search and penalized regression
• A fast PC algorithm for high dimensional causal discovery with multi-core PCs
• A Survey on Causal Discovery: Theory and Practice
• A generalized back-door criterion
• Causal Structure Learning: a Combinatorial Perspective
• cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU
• Causal Etiology of the Research of James M. Robins
• Uniform random generation of large acyclic digraphs
• Non-Parametric Causality Detection: An Application to Social Media and Financial Data
• A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption
• Nonlinear Causal Discovery with Confounders
• Causal Reasoning in Software Quality Assurance: A Systematic Review
• Causal Inference with Latent Variables: Recent Advances and Future Prospectives
• A Combinatorial Solution to Causal Compatibility
• Marginal integration for nonparametric causal inference
• Discovery and inference of a causal network with hidden confounding
• Fast Parallel Bayesian Network Structure Learning
• Nonparametric causal structure learning in high dimensions
• Causal evidence for the primordiality of colours in trans-Neptunian objects
• Spatio-Temporal Graphical Counterfactuals: An Overview