Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery

By Eric V. Strobl, Kun Zhang, Shyam Visweswaran. 2017

219 citations recorded by the source corpus.

Abstract Constraint-based causal discovery (CCD) algorithms require fast and accurate conditional independence (CI) testing. The Kernel Conditional Independence Test (KCIT) is currently one of the most popular CI tests in the non-parametric setting, but many investigators cannot use KCIT with large datasets because the test scales at least quadratically with sample size. We therefore devise two relaxations called the Randomized Conditional Independence Test (RCIT) and the Randomized conditional Correlation Test (RCoT) which both approximate KCIT by utilizing random Fourier features. In practice, both of the proposed tests scale linearly with sample size and return accurate p-values much faster than KCIT in the large sample size context. CCD algorithms run with RCIT or RCoT also return graphs at least as accurate as the same algorithms run with KCIT but with large reductions in run time.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability, Evaluation & Benchmarks, Causal Inference & Discovery

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bernhard Schölkopf
2. Simon Lacoste-Julien
3. Alexandre Lacoste
4. Yoshua Bengio
5. David Lopez-Paz
6. Krzysztof Chalupka
7. Diviyan Kalainathan
8. Pietro Perona

In Management Science and Operations Research

1. Thomas B. Berrett
2. Sébastien Lachapelle
3. Simon Lacoste-Julien
4. David Lopez-Paz
5. Pietro Perona
6. Isabelle M Guyon
7. Yi Wang
8. Frederick Eberhardt

In Statistics and Probability

1. Richard J. Samworth
2. Rina Foygel Barber
3. Yi Wang
4. Thomas B. Berrett
5. Sébastien Lachapelle
6. Simon Lacoste-Julien
7. David Lopez-Paz
8. Alexandre Drouin

In Evaluation & Benchmarks

1. David Lopez-Paz
2. Isabelle M Guyon
3. Michèle Sebag
4. Olivier Goudet
5. Diviyan Kalainathan
6. Thomas B. Berrett
7. Simon Lacoste-Julien
8. Alexandre Drouin

In Causal Inference & Discovery

1. Alexandre Lacoste
2. Simon Lacoste-Julien
3. Sébastien Lachapelle
4. Philippe Brouillard
5. Alexandre Drouin
6. Olivier Goudet
7. Diviyan Kalainathan
8. Isabelle M Guyon

Citations in the corpus

• Differentiable Causal Discovery from Interventional Data (2020, background): “For example, KCI-test scales in O(n(3)) [43] and HSIC in O(n(2)) [51].”
• Fast Conditional Independence Test for Vector Variables with Large Sample Sizes (2018, methodology): “To address this limitation, the Randomized Conditional Independence test (RCIT) [Strobl et al., 2017], uses a fast Fourier transform to speed up the matrix operations.”
• The conditional permutation test for independence while controlling for confounders (2018, methodology): “-dimensional projections of the data. Tests based on embedding 5 the data into reproducing kernel Hilbert spaces are studied in, for example, Fukumizu et al. [12], Zhang et al. [33] and Strobl et al. [25]. Other works use permutations of the data, including Doran et al. [10] and Sen et al. [21], whe”
• The conditional permutation test (2018, methodology): “Tests based on embedding the data into reproducing kernel Hilbert spaces are studied in, for example, Fukumizu et al. [9], Zhang et al. [27] and Strobl et al. [20].”
• Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, methodology): “…independence test (Zhang et al., 2012) with a Gamma null distribution (Gretton et al., 2005); • PC-RCIT: using the Randomized Conditional Independence Test (RCIT) with random Fourier features (Strobl et al., 2017); • PC-RCOT: the Randomized conditional Correlation Test (RCOT) (Strobl et al., 2017).”