Abstract. Many relations of scientific interest are nonlinear, and even in linear systems distributions are often non--Gaussian, for example in fMRI BOLD data. A class of search procedures for causal relations in high dimensional data relies on sample derived conditional independence decisions. The most common applications rely on Gaussian tests that can be systematically erroneous in nonlinear non--Gaussian cases. Recent work ), Tillman et al. (2009 ), Zhang et al. (2011 ) has proposed conditional independence tests using Reproducing Kernel Hilbert Spaces (RKHS). Among these, perhaps the most efficient has been KCI (Kernel Conditional Independence, Zhang et al. (2011)), with computational requirements that grow effectively at least as O(N 3 ), placing it out of range of large sample size analysis, and restricting its applicability to high dimensional data sets. We propose a class of O(N 2 ) tests using conditional correlation independence (CCI) that require a few seconds on a standard workstation for tests that require tens of minutes to hours for the KCI method, depending on degree of parallelization, with similar accuracy. For accuracy on difficult nonlinear, non--Gaussian data sets, we also compare a recent test due to Harris & Drton (2013) , applicable to nonlinear, non--Gaussian distributions in the Gaussian copula, as well as to partial correlation, a linear Gaussian test. 2 1. Introduction. Tests of conditional independence for nonlinear or non--Gaussian data have used a reproducing kernel Hilbert space (RKHS). An excellent representative of these tests, Zhang, et al.'s KCI ("Kernel Conditional Independence"), was shown to have good accuracy for linear Gaussian data used with the well--known PC search algorithm (Spirtes et al., 2000) . We find the test is accurate for nonlinear, non--Gaussian data as well. But despite the fact that the test scales better than previous such tests ( Gretton et al. (2009 ), Tillman et al. (2009 ), it does not scale well enough for general use. In general, it scales cubically with sample size, for sample size 1000 can require several seconds per test, 1 and in high dimensional problems PC and other constraint based search algorithms may call for thousands to tens of thousands of such tests. A novel method, CCI ("Conditional Correlation Independence"), is proposed for the nonlinear, non--Gaussian case that is at least as accurate as KCI on small data sets but scales up to much larger problems. (The term "conditional correlation" is as in Baba et al., 2004. and Lawrance, 1976.) The framework of RKHS is replaced by a simpler set of mathematical ideas: The first is that X _||_ Y just in case cov(f(X), g(Y)) = 0 for all functions f and g, where X and Y are arbitrarily distributed. The second is that one only needs to test f and g in a functional basis for an appropriate space of functions. The third is that zero covariance of arbitrarily distributed X and Y can be tested using a generalized Fisher Z test of zero correlation if X and Y have finite fourth moments. The fourth idea is that X _||_ Y | Z just in case (up to a faithfulness condition) the nonparametric residuals of X regressed onto Z are independent of the nonparametric residuals of Y regressed onto Z, for models in which errors are additive. Using these ideas, a relatively simple algorithm can be devised that matches the KCI test in small sample performance and scales to large numbers of variables with sample sizes in the thousands. Hoyer et al. (2009) and also target the nonlinear, non--Gaussian case, and aim to learn both structure and orientation in same routine, though their methods do not scale up well. Under the assumption of additive noise, Hoyer et al. suggest two methods, one for pairs of variables, one for larger models, with an example given of 4 variables. Under the same assumption of additive noise, Mooij suggest a more streamlined method for larger models, with an example provided using 7 variables. The pairwise method of Hoyer et al. considers an adjacency X------Y where, say, Y = f(X) + e, where e _||_ X. In general, as they show, except for a few special cases, when f is nonlinear there is no backwards model X = g(Y) + e', where e' _||_ Y. Thus a simple test suffices. Calculate the residuals rX of regressing X nonlinearly onto Y and the residuals rY of regressing rY nonlinearly onto X. If rX is independent of Y but rY is not independent of X, orient Y---->X; if the reverse is true, orient X---->Y; if both rX is independent of Y and rY is independent of X, do not orient the edge. If rX is dependent on rY and rY is dependent on rX, the graph is, as they say, more complicated. The method for larger numbers of variables (they suggest up to 7) is to consider all possible DAGs over the variables, calculate for each DAG the residual of each variable conditional on its parents, and accept models for which all of these residuals are independent. DAGs for which an accepted submodel exists are not returned. Since this algorithm does not scale well to many variables, it is not further considered as a method for learning structure. The Mooij et al. approach first sorts the variables high to low by their residuals regressed nonlinearly
As a direct extension of partial correlation, REF , for example, suggests to regress X on Z and Y on Z and then test for independence between the residuals.
A Scalable Conditional Independence Test for Nonlinear, Non-Gaussian Data
ArXiv
ArXiv
Mathematics Computer Science