PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Eric V. Strobl, Kun Zhang, Shyam Visweswaran

arXiv:1702.03877v2stat.MEstat.ML

TL;DR

CCD algorithms need fast, accurate conditional-independence tests, but KCIT is costly on large datasets. The paper introduces RCIT and RCoT, which approximate KCIT with random Fourier features. Both scale linearly in practice and support CCD graphs at least as accurate as KCIT while substantially reducing runtime.

  • Problem

    CCD algorithms may require thousands of CI-test p-values, while KCIT scales at least quadratically with sample size and is too slow for large datasets.

  • Method

    RCIT and RCoT approximate KCIT using random Fourier features and linear ridge-regression computations.

  • Results

    RCIT and RCoT scale linearly in practice, return p-values orders of magnitude faster than KCIT, and yield CCD structures at least as accurate.

  • Takeaways & Limitations

    RCIT and RCoT can make non-parametric causal discovery more accessible by shortening CCD runtimes while preserving graph-recovery accuracy.

  • Takeaways & Limitations

    The approach substitutes conditional independence with conditional uncorrelatedness, which may not hold for every conditionally dependent relationship and complicates interpretation outside common cases.

Abstract

from arXiv · show

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 cubicly 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.

1. The Problem

CCD algorithms depend on many conditional-independence tests, making speed and accuracy central to their usability. Existing non-parametric and kernel-based approaches address flexibility but face computational challenges at large sample sizes.

  • The Problem: CCD algorithms can request p-values from thousands of conditional-independence tests, even for sparse graphs.Fast and accurate CI testing is therefore important for applying CCD methods across datasets.
  • The Problem: Parametric tests such as partial correlation and chi-squared testing rely on distributional or discreteness assumptions.Permutation-based methods can extend related strategies when variables are not necessarily discrete.
  • The Problem: Discretizing continuous conditioning variables suffers from the curse of dimensionality as conditioning-set size increases.The number of contingency-table cells grows exponentially with the conditioning set size.
  • The Problem: KCIT uses reproducing-kernel Hilbert-space characterizations of conditional independence and tests vanishing nonlinear regression residuals.Kernel methods are known for strong empirical performance in high-dimensional settings.
  • The Problem: Kernel-based CI tests scale at least quadratically with sample size, with KCIT bottlenecks in kernel-matrix eigendecomposition and inversion.Kernel-matrix construction itself generally scales at least quadratically.
  • The Problem: RCIT and RCoT use random Fourier features to approximate KCIT, scaling linearly in practice while retaining comparable accuracy.They return p-values several orders of magnitude faster than KCIT on large samples, and CCD graphs have nearly identical accuracy.

2. Characterizations of Conditional Independence

The paper characterizes conditional independence through probability identities and dependence restrictions on functions or RKHS representations. These views connect nonlinear residual relationships with familiar covariance and partial-correlation concepts.

  • Probability characterization: Conditional independence X ⊥⊥Y |Z means the conditional joint distribution factors into the product of the conditional distributions.Equivalent formulations require PX|YZ = PX|Z and PY|XZ = PY|Z.
  • Characterization by RKHSs: The cross-covariance operator ΣXY represents dependence between functions of X and functions of Y in their RKHSs.The operator maps from HY to HX.
  • Characterization by RKHSs: The partial cross-covariance operator measures covariance between RKHS functions of X and Y after accounting for RKHS functions of Z.It generalizes the role of a linear partial cross-covariance matrix.
  • Characterization by RKHSs: Using characteristic kernels links vanishing partial cross-covariance to conditional independence under stated integrability and density assumptions.The proposition uses characteristic kernels and an RKHS density condition.
  • Characterization by L2 spaces: An alternative characterization requires residual functions of (X,Z) and (Y,Z), after conditioning on Z, to be uncorrelated.This formulation is presented through constrained L2 spaces and equivalent conditions.
  • Characterization by L2 spaces: For jointly Gaussian variables, conditional independence is equivalent to zero linear partial correlation ρXY·Z.The paper presents the residual-uncorrelatedness condition as a generalization of the Gaussian case.
  • Characterization by L2 spaces: Partial cross-covariance is unconditional covariance of residuals after subtracting conditional expectations, unlike conditional cross-covariance, which retains conditioning on Z.The distinction is the extra conditioning in the latter definition.
  • Characterization by L2 spaces: The RKHS characterization is more useful here because a characteristic-kernel RKHS may be much smaller than the corresponding L2 space.The paper contrasts RKHS functions with the broader class of L2 functions.

3. Test Statistic & its Asymptotic Distribution

The paper constructs finite-dimensional randomized test statistics by projecting variables into random-feature spaces and estimating partial cross-covariance through regression residuals. Under the null, the statistic has a weighted chi-squared asymptotic distribution, while RCoT uses a finite-dimensional variant that is practical for large conditioning sets.

  • Test statistic: KCIT uses the squared Hilbert-Schmidt norm of the empirical partial cross-covariance operator to test the null hypothesis of conditional independence.RCIT instead approximates this quantity with the squared Frobenius norm of an empirical partial cross-covariance matrix.
  • Randomized feature construction: RCIT selects random functions of X, Y, and Z, then estimates conditional expectations using linear ridge regression over these finite-dimensional feature spaces.Random Fourier features approximate continuous shift-invariant kernels, including the Gaussian RBF kernel used by KCIT.
  • Validity of the randomized criterion: Conditional independence implies zero expected products across the selected feature spaces, while the reverse implication holds for an increasing number of distributions as feature counts grow.In the tested cases, the reverse direction held with only m, q = 5.
  • Asymptotic distribution: Under the null, the normalized vectorized partial cross-covariance converges to a multivariate Gaussian distribution with covariance matrix Π.The covariance matrix is defined for the vectorized product of residualized feature representations.
  • Asymptotic distribution: The null distribution of the test statistic is a positively weighted sum of independent χ2_1 random variables.The weights are the eigenvalues of Π, and the resulting cumulative distribution can be approximated through moment-based methods or numerical inversion.
  • RCoT: RCoT replaces the extended feature representation with a finite-dimensional partial cross-covariance matrix and is intended to replace RCIT when conditioning sets have size ≥4.The paper reports that RCoT usually rivals or outperforms RCIT and KCIT because its null distribution remains easy to calibrate when Z has large cardinality.

4. Experiments

The experiments compare RCIT, RCoT, and KCIT, using randomized tests with fast null-distribution approximations alongside KCIT with bootstrap calibration.

  • RCIT uses S with the Lindsay-Pilla-Basak approximation, while RCoT uses S′ with the same approximation.
  • KCIT uses S_K with a simulated null obtained by bootstrap.
  • The study focuses on sample sizes of at least 500 because KCIT with bootstrap can be applied directly at smaller sizes.Experiments used R on a laptop with a 2.60 GHz CPU and 16GB of RAM.

4.1. Hyperparameters

RCIT and RCoT share kernel hyperparameters selected with median-distance heuristics and use fixed numbers of random Fourier features; KCIT uses a separate heuristic.

  • RCIT and RCoT use median Euclidean distance heuristics across the first 500 samples to select Gaussian RBF bandwidths.
  • The randomized tests use 5 Fourier features for X̃, X, and Y, and 25 Fourier features for Z.
  • All original and Fourier variables are standardized to mean zero and unit variance for numerical stability.
  • KCIT sets its bandwidth using the squared median Euclidean distance between (X, Y), multiplied by twice the conditioning-set size.

4.2. Type I Error

Type I error experiments assess calibration under conditional independence across sample sizes and conditioning-set sizes, using KS statistics against the uniform p-value distribution.

  • The KS statistic measures the distance between the empirical CDF and a comparison CDF, converging to zero when the sample follows that distribution.
  • A well-calibrated CI test should produce uniformly distributed p-values, corresponding to a small KS statistic against Uniform([0, 1]).
  • Sample Size: All three tests have similar KS statistics across sample sizes with one conditioning variable, indicating comparable Type I error control.
  • Sample Size: RCIT and RCoT handle one million samples in slightly over 6 seconds, whereas KCIT runs out of memory at 5000 samples.
  • Conditioning Set Size: RCoT has the smallest KS statistics for nearly all conditioning-set sizes, followed by RCIT and KCIT.This indicates that RCoT best approximates the null distribution among the three tests.
  • Conditioning Set Size: 40.91 times faster than KCIT on average, RCIT and RCoT retain their runtime advantage as conditioning-set dimensionality increases.The reported 95% confidence interval is ±0.44, and all three tests scale linearly with conditioning-set dimensionality.

4.3. Power

Power experiments evaluate rejection under dependence across sample sizes and conditioning-set sizes, while also comparing runtime and calibration behavior.

  • AUPC measures test power as the area under the empirical CDF of p-values when the conditional-independence null is false.Higher power corresponds to an AUPC closer to one.
  • The power setup introduces a hidden common cause by adding the same error term to X and Y while excluding it from the conditioning set.
  • Sample Size: RCIT and RCoT have AUPC values comparable to KCIT at sample sizes 500, 1000, and 2000, while continuing to increase at larger sizes where KCIT lacks sufficient memory.
  • Sample Size: All three tests have similar power across the tested sample sizes.
  • RCIT and RCoT complete orders of magnitude faster than KCIT in the power experiments.
  • Conditioning Set Size: RCIT and RCoT maintain steady power as uninformative conditioning variables increase, whereas KCIT’s apparent power increase reflects a badly calibrated null distribution.

4.4. Causal Structure Discovery

The study evaluates PC, FCI, and RFCI with RCIT, RCoT, and KCIT on simulated graphs. RCIT and RCoT achieve comparable or better graph-recovery accuracy while substantially reducing runtime relative to KCIT.

  • Simulation design: 250 Gaussian DAGs with 20 vertices and expected neighborhood size E(N) = 2 were generated for evaluating PC, FCI, and RFCI.The experiments also introduced latent common causes and selection variables for FCI and RFCI.
  • CI-test behavior: When conditional dependence held, RCIT and RCoT completed much faster than KCIT while maintaining comparable AUPC values across sample sizes.The figure also examines conditioning-set size and associated runtimes.
  • Simulation design: The sample algorithms used RCIT, RCoT, KCIT, and Fisher’s z-test at α = 0.05, with oracle graphs obtained from ground truth.Each algorithm was evaluated on 250 datasets containing 500 samples.
  • Graph accuracy: PC with RCIT and RCoT outperformed PC with KCIT by a large margin in structural Hamming distance, with similar smaller advantages for FCI and RFCI.All kernel-based tests also outperformed Fisher’s z-test by a large margin in these comparisons.
  • Runtime: CCD algorithms using RCIT and RCoT completed at least 13 times faster on average than those using KCIT.Figure 3 reports mean SHD and runtime, with error bars representing 95% confidence intervals of the mean.

4.5. Real Data

The paper evaluates PC, FCI, and RFCI on bootstrapped CogUSA longitudinal data without a gold-standard graph. RCIT and RCoT generally perform better than KCIT for FCI and RFCI, while PC comparisons are less consistent.

  • Dataset and evaluation: The CogUSA dataset contains 815 samples, 18 variables, and two waves separated by two years after data cleaning.The analyses used PC, FCI, and RFCI with RCIT, RCoT, KCIT, and Fisher’s z-test at α = 0.05.
  • Dataset and evaluation: 30 bootstrapped datasets were analyzed, because the real-data study lacked a gold-standard solution set.Performance was summarized using mean counts of ancestral relations directed backwards in time and mean runtimes.
  • Results: FCI and RFCI using RCIT or RCoT performed better than the corresponding KCIT versions at the Bonferroni-corrected level.The reported comparisons include p < 2.2E-16 for both FCI comparisons and p = 4.13E-7 and 3.85E-8 for RFCI.
  • Results: PC with RCIT or RCoT yielded fewer false positive ancestral relations on average than PC with KCIT, but the comparisons did not reach the Bonferroni level.The PC comparisons were reported at p = 9.85E-3 and p = 0.056.
  • Interpretation: The authors trust FCI and RFCI outputs more strongly than PC outputs because FCI and RFCI allow latent common causes and selection bias.These features are described as often existing in real data.

5. Conclusion

The paper introduces RCIT and RCoT as fast random-Fourier-feature approximations to KCIT for nonparametric conditional-independence testing. The proposed tests preserve causal-discovery accuracy while greatly reducing computation time, with RCoT offering improved null calibration at larger conditioning-set sizes.

  • Contribution: RCIT and RCoT approximate KCIT by sampling Fourier features for fast nonparametric conditional-independence testing.Both tests are designed to produce p-values much faster than KCIT in large-sample settings.
  • Computational efficiency: RCIT and RCoT return p-values orders of magnitude faster than KCIT in the large-sample-size setting.The paper emphasizes this computational advantage as a central outcome of the proposed approximations.
  • Calibration: RCoT has a better-calibrated null distribution than KCIT, especially with larger conditioning-set sizes.The conclusion identifies null calibration as a specific advantage of RCoT over KCIT.
  • Evaluation scope: The real-data evaluation used a publicly available longitudinal dataset after removing redundant variables, variables with more than 1000 missing values, and samples with missing values.These cleaning steps define the scope of the reported real-data analysis.
  • Causal discovery: CCD algorithms using RCIT and RCoT recover graphical structures at least as accurately as those using KCIT while completing in a much shorter time frame.The authors connect these speedups to broader accessibility of nonparametric causal discovery.

6. Appendix

The appendix develops a central limit theorem for a sample covariance matrix under an i.i.d. assumption and positive definiteness of a covariance matrix. The proof uses the Cramer-Wold device, the univariate central limit theorem, and Slutsky’s lemma.

  • Proof setup: The appendix introduces sample covariance matrices for known and unknown expectation vectors before proving the central limit theorem.The proof is organized around linear projections of the covariance-matrix quantities.
  • Lemma 1: Lemma 1 assumes i.i.d. random k-vectors and positive definiteness of the covariance matrix of the vectorized upper-triangular covariance entries.The lemma states the asymptotic result under these assumptions.
  • Lemma 1: For an arbitrary vector a, the projected covariance terms have expectation aT vu(Σ1) and variance aT ˘Σ1a.These projections reduce the matrix result to a sequence of scalar random variables.
  • Proof: The proof applies the univariate central limit theorem to the projected sequence and uses Slutsky’s lemma for the relevant decomposed terms.The argument separately establishes convergence for the components before recombining them.
  • Proof: The lemma is concluded by invoking the Cramer-Wold device.This converts convergence of all linear projections into the stated multivariate result.
Loading 1702.03877v2…