Source-linked AI summary
Kernel-based Conditional Independence Test and Application in Causal Discovery
Kun Zhang, Jonas Peters, Dominik Janzing, Bernhard Schoelkopf
TL;DR
Testing conditional independence for continuous variables is difficult because existing approaches struggle with high-dimensional conditioning sets and may rely on restrictive assumptions. The paper proposes KCI-test, which uses kernel characterizations, a kernel-matrix statistic, and an asymptotic null distribution. It reports computationally appealing testing that is less sensitive to conditioning-set dimensionality, while noting performance trade-offs and hyperparameter risks.
Problem
Conditional independence testing for continuous variables is challenging because existing methods can require density estimation, discretization, large samples, or restrictive assumptions.
Method
KCI-test uses conditional-independence characterizations in RKHSs to construct a kernel-matrix statistic and derive its null distribution, estimated by Monte Carlo simulation or Gamma approximation.
Results
KCI-test is computationally appealing and less sensitive to the dimensionality of the conditioning set than other methods.
Takeaways & Limitations
The method provides a convenient conditional-independence test that avoids explicit conditional or joint-density estimation and discretization.
Takeaways & Limitations
In linear-Gaussian simulations, partial correlation had much smaller Type II errors than KCI-test, and unsuitable hyperparameters can increase Type I or Type II errors.
Abstract
from arXiv · showhide
Conditional independence testing is an important problem, especially in Bayesian network learning and causal discovery. Due to the curse of dimensionality, testing for conditional independence of continuous variables is particularly challenging. We propose a Kernel-based Conditional Independence test (KCI-test), by constructing an appropriate test statistic and deriving its asymptotic distribution under the null hypothesis of conditional independence. The proposed method is computationally efficient and easy to implement. Experimental results show that it outperforms other methods, especially when the conditioning set is large or the sample size is not very large, in which case other methods encounter difficulties.
1 Introduction
Conditional independence testing is central to causal discovery and Bayesian network learning but is difficult for continuous variables without restrictive assumptions. KCI-test addresses these challenges with a kernel-based statistic and a derived null distribution, avoiding density estimation and discretization.
- Conditional independence supports parsimonious probabilistic models and plays a central role in causal discovery and Bayesian network learning.
- Testing continuous-variable conditional independence is difficult because traditional approaches often assume linear relations with additive Gaussian errors.Under those assumptions, conditional independence reduces to testing zero partial or conditional correlation.
- Nonlinearity and non-Gaussian noise can make linear-Gaussian conditional-independence tests produce incorrect conclusions.
- Conditional-density methods become difficult when the conditioning set is large, while discretization methods face rapidly increasing sample-size requirements.
- CIPERM combines a kernel-based conditional-dependence measure with local bootstrap or permutation, but becomes unreliable as conditioning dimensionality increases.
- KCI-test computes a kernel-matrix statistic, derives its null asymptotic distribution, and avoids explicit density estimation and discretization.The method is described as computationally appealing and less sensitive to the dimensionality of the conditioning set.
2 Characterization of Independence and Conditional Independence
The paper formulates conditional independence for continuous variables through kernel and function-space characterizations rather than explicit density estimation. These characterizations connect conditional independence to uncorrelated residual functions and motivate kernel-matrix testing procedures.
- In implementation, centralized kernel matrices are formed from sample data, with Gaussian kernels used by default and analogous constructions for Y and Z.The centralized matrix is eKX = HKXH, where H centers the n × n kernel matrix.
- The problem is to test X ⊥⊥Y |Z from i.i.d. samples of continuous variables without assumptions on distributions or functional forms.Direct density estimation is difficult in high dimensions because required sample sizes increase exponentially with data dimension.
- Conditional independence means pX|Y,Z = pX|Z, equivalently pY|X,Z = pY|Z or pXY|Z = pX|ZpY|Z.
- The RKHS approach characterizes conditional independence using conditional cross-covariance operators associated with suitable kernels.This avoids explicitly involving conditional or joint densities.
- An equivalent function-space characterization requires residual functions of (X,Z) and (Y,Z), after conditioning on Z, to be uncorrelated.The construction uses constrained L2 spaces and nonlinear regression to form residual functions.
- The kernel characterization restricts attention to functions in RKHSs associated with characteristic kernels, which may be smaller than the full L2 function spaces.The paper notes that this gives the operator-based characterization practical advantages over considering all L2 functions.
3 A Kernel-Based Conditional Independence Test
The paper develops a kernel-based conditional independence test by combining residualized kernel representations with an asymptotic null distribution, enabling convenient testing from kernel matrices.
- 3.1 General results: Kernel-based asymptotic results characterize statistics formed from kernel matrices when functions of the variables are uncorrelated.The results support both unconditional independence testing and the later conditional independence test.
- 3.2 Unconditional independence testing: The unconditional statistic nTr(eKX eKY) has an asymptotic distribution determined by kernel eigenvalues under independence.Its empirical null distribution can be simulated using weighted sums of chi-squared variables to obtain p-values.
- 3.3 Conditional independence testing: The KCI-test residualizes kernel representations of X and Y with respect to Z using kernel ridge regression before measuring their conditional dependence.The residualization uses RZ = I − eKZ(eKZ + εI)^−1 and produces the matrices eK X|Z and eKY |Z.
- 3.3 Conditional independence testing: Under H0, the conditional statistic nTr(eK X|Z eKY |Z) has an asymptotic distribution represented by a weighted sum of squared standard Gaussian variables.The weights are eigenvalues derived from the stacked residualized kernel features.
- 3.3 Conditional independence testing: KCI computes p-values by simulating the approximate null distribution or by fitting a two-parameter Gamma distribution from the statistic’s mean and variance.The Gamma approximation avoids calculating the full eigenvalue set and simulating the null distribution, improving computational efficiency.
- 3.4 Practical considerations: The method’s accuracy depends on regression-function complexity and regularization: underfitting can increase Type I errors, while overfitting can increase Type II errors.Very small ε can also make residualized kernel matrices nearly vanish and expose the procedure to rounding-error degradation.
4 Experiments
Experiments evaluate KCI-test on synthetic and real data, comparing error behavior, computational efficiency, and causal-discovery performance. KCI-test is less sensitive to conditioning-set dimensionality and recovers causal structure more accurately than the compared methods in the reported experiments.
- KCI-test was evaluated on synthetic and real data and applied to causal discovery, including comparisons with CIPERM and partial correlation.
- The simulations varied conditioning-set dimensionality D from 1 to 5 and sample sizes n = 200 and 400 across two effectiveness cases.
- The derived null distribution approximated the 1% and 5% quantiles well for both sample sizes, with Type I error probabilities close to the specified significance levels.
- As D increased, Type II errors increased, whereas increasing the sample size from 200 to 400 made Type II errors quickly approach zero.
- Compared with CIPERM, KCI-test was less sensitive to conditioning-set dimensionality, while CIPERM’s Type II error increased rapidly toward 1 when D exceeded 3.
- In a linear Gaussian simulation, partial correlation had much smaller Type II errors than KCI-test, while both methods had similar Type I errors.
- With PC on simulated DAGs, KCI-test achieved the best recovery of the correct Markov equivalence class among KCI-test, CIPERM, and partial correlation.
- In the Boston Housing data, PCKCI-test and PCCIPERM produced overlapping and distinct links, including KCI-test links between RM and MED and between IND and NOX.
5 Conclusion
The paper concludes that KCI-test provides a practical kernel-based approach to conditional independence testing. It combines a kernel-matrix statistic with a null distribution obtained by simulation or Gamma approximation, and reported experiments suggest gains in accuracy and speed.
- KCI-test uses uncorrelatedness of functions in suitable RKHSs and computes its statistic from kernel matrices.
- The null distribution under conditional independence can be generated by Monte Carlo simulation or approximated with a two-parameter Gamma distribution.
- Reported results on simulated and real-world data suggest that KCI-test outperforms existing techniques in both accuracy and speed.
Appendix: Proofs
The appendix establishes asymptotic behavior of kernel-matrix eigenvectors and related test statistics, including cases with repeated eigenvalues. These results support the limiting distributions used in the paper’s theoretical derivations.
- For a simple eigenvalue, √nVx,i(ˇx) converges in probability to the corresponding normalized eigenfunction values.
- Orthogonal transformations of finite kernel feature vectors converge in probability to vectors of normalized eigenfunction evaluations for both X and Y.
- The central-limit and continuous-mapping arguments yield multivariate-normal limits for the constructed vectors and transfer those limits to the test-statistic components.
- With eigenvalue multiplicity r + 1, an orthogonal rotation aligns the scaled eigenvector block with the corresponding eigenfunction space.The associated eigenfunctions are non-unique, so the result is stated in terms of the space SX,k.
- Under independence, the covariance structure simplifies through vanishing non-diagonal terms, allowing the asymptotic forms of the test statistics to be obtained.
- The appendix also derives conditional means and variances of the approximated statistics using chi-square moments and independence across eigencomponent indices.