Constraint-based causal discovery (CCD) algorithms require fast and accurateconditional independence (CI) testing. The Kernel Conditional Independence Test(KCIT) is currently one of the most popular CI tests in the non-parametricsetting, but many investigators cannot use KCIT with large datasets because thetest scales cubicly with sample size. We therefore devise two relaxationscalled the Randomized Conditional Independence Test (RCIT) and the Randomizedconditional Correlation Test (RCoT) which both approximate KCIT by utilizingrandom Fourier features. In practice, both of the proposed tests scale linearlywith sample size and return accurate p-values much faster than KCIT in thelarge sample size context. CCD algorithms run with RCIT or RCoT also returngraphs at least as accurate as the same algorithms run with KCIT but with largereductions in run time.
展开▼