A permutation-based kernel conditional independence test

Abstract

Determining conditional independence (CI) re-lationships between random variables is a chal-lenging but important task for problems such as Bayesian network learning and causal discovery. We propose a new kernel CI test that uses a sin-gle, learned permutation to convert the CI test problem into an easier two-sample test problem. The learned permutation leaves the joint distri-bution unchanged if and only if the null hypoth-esis of CI holds. Then, a kernel two-sample test, which has been studied extensively in prior work, can be applied to a permuted and an unpermuted sample to test for CI. We demonstrate that the test (1) easily allows the incorporation of prior knowledge during the permutation step, (2) has power competitive with state-of-the-art kernel CI tests, and (3) accurately estimates the null distri-bution of the test statistic, even as the dimension-ality of the conditioning variable grows. 1