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

Strobl Eric V. (), Zhang Kun () and Visweswaran Shyam ()
Additional contact information
Strobl Eric V.: 6614University of Pittsburgh, Department of Biomedical Informatics, Pittsburgh, United States
Zhang Kun: 6612Carnegie Mellon University, Department of Philosophy, Pittsburgh, United States
Visweswaran Shyam: 6614University of Pittsburgh, Department of Biomedical Informatics, Pittsburgh, United States

Journal of Causal Inference, 2019, vol. 7, issue 1, 24

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.

Keywords: Conditional Independence Test; Random Fourier Features; Causal Discovery; Non-Parametric (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1515/jci-2018-0017 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:causin:v:7:y:2019:i:1:p:24:n:7

DOI: 10.1515/jci-2018-0017

Access Statistics for this article

Journal of Causal Inference is currently edited by Elias Bareinboim, Jin Tian and Iván Díaz

More articles in Journal of Causal Inference from De Gruyter
Bibliographic data for series maintained by Peter Golla ().