Skip to main content

fastcit_core/ci_tests/
kci.rs

1//! Kernel conditional-independence (KCI) test for continuous variables,
2//! matching pgmpy's `KCI` (gamma null from the eigenvalues of the
3//! Z-residualized kernels). With an empty conditioning set it reduces to
4//! [`Hsic`](crate::ci_tests::Hsic) with a gamma null.
5//!
6//! Cost: O(n²) memory and O(n³) time, as in pgmpy.
7
8use faer::linalg::solvers::DenseSolveCore;
9use faer::{Mat, Side};
10
11use crate::ci_tests::hsic::{hsic_unconditional, NullDistribution};
12use crate::dataset::Dataset;
13use crate::error::CIError;
14use crate::kernel::{
15    center, dense_len_guard, gamma_pvalue, kernel_matrix, median_length_scale, standardized,
16    Bandwidth, Kernel, KernelChoice,
17};
18use crate::strategy::{CIResult, CITest, DataType, IndependenceRule, TestMeta};
19
20/// Eigenvalue cut-off relative to the largest eigenvalue.
21const EIGEN_RELATIVE_CUTOFF: f64 = 1e-5;
22
23/// KCI conditional-independence test (`X ⊥ Y | Z`).
24#[derive(Debug, Clone, PartialEq)]
25pub struct Kci {
26    /// Kernel selection.
27    pub kernel: KernelChoice,
28    /// Bandwidth rule for default RBF kernels.
29    pub bandwidth: Bandwidth,
30    /// Ridge regularization `ε` of the Z-residualizer; finite and > 0.
31    pub epsilon: f64,
32}
33
34impl Kci {
35    /// pgmpy defaults: default kernels, heuristic bandwidth, `epsilon = 1e-3`.
36    #[must_use]
37    pub fn new() -> Self {
38        Self {
39            kernel: KernelChoice::default(),
40            bandwidth: Bandwidth::default(),
41            epsilon: 1e-3,
42        }
43    }
44}
45
46impl Default for Kci {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52/// Default RBF length scale `w · sqrt(|Z|)` by sample size.
53#[must_use]
54pub(crate) fn kci_heuristic_length_scale(n: usize, n_z: usize) -> f64 {
55    let w = if n < 200 {
56        1.2
57    } else if n < 1200 {
58        0.7
59    } else {
60        0.4
61    };
62    #[allow(clippy::cast_precision_loss)]
63    let root = (n_z as f64).sqrt();
64    w * root
65}
66
67/// Frobenius inner product of two equally sized matrices.
68fn inner(a: &Mat<f64>, b: &Mat<f64>) -> f64 {
69    let mut s = 0.0;
70    for j in 0..a.ncols() {
71        for i in 0..a.nrows() {
72            s += a[(i, j)] * b[(i, j)];
73        }
74    }
75    s
76}
77
78fn numeric<E: std::fmt::Debug>(what: &str, e: E) -> CIError {
79    CIError::Numeric(format!("{what} failed: {e:?}"))
80}
81
82/// Default RBF kernel for `points` under the bandwidth rule.
83fn default_rbf(points: &Mat<f64>, bandwidth: Bandwidth, n: usize, n_z: usize) -> Kernel {
84    Kernel::Rbf {
85        length_scale: match bandwidth {
86            Bandwidth::Heuristic => kci_heuristic_length_scale(n, n_z),
87            Bandwidth::Median => median_length_scale(points.as_ref()),
88        },
89    }
90}
91
92/// Kernel for a queried column (X or Y) under `choice`.
93fn queried_kernel(data: &Dataset, col: usize, points: &Mat<f64>, test: &Kci, n_z: usize) -> Kernel {
94    let explicit = match &test.kernel {
95        KernelChoice::Auto => None,
96        KernelChoice::All(k) => Some(*k),
97        KernelChoice::PerColumn(map) => data.name_of(col).and_then(|n| map.get(n)).copied(),
98    };
99    explicit.unwrap_or_else(|| default_rbf(points, test.bandwidth, points.nrows(), n_z))
100}
101
102/// Centered kernel matrix of `points`.
103fn centered_kernel(kernel: Kernel, points: &Mat<f64>) -> Mat<f64> {
104    let mut k = kernel_matrix(kernel, points.as_ref());
105    center(&mut k);
106    k
107}
108
109/// Kept eigenvectors scaled by `sqrt(eigenvalue)` of `½(A + Aᵀ)`.
110fn scaled_eigenvectors(a: &Mat<f64>) -> Result<Mat<f64>, CIError> {
111    let n = a.nrows();
112    let sym = Mat::<f64>::from_fn(n, n, |i, j| f64::midpoint(a[(i, j)], a[(j, i)]));
113    let eig = sym
114        .self_adjoint_eigen(Side::Lower)
115        .map_err(|e| numeric("eigendecomposition", e))?;
116    let (values, vectors) = (eig.S(), eig.U());
117    let w: Vec<f64> = (0..n).map(|i| values[i]).collect();
118    let max = w.iter().copied().fold(f64::NEG_INFINITY, f64::max);
119    let keep: Vec<usize> = (0..n)
120        .filter(|&i| w[i] > max * EIGEN_RELATIVE_CUTOFF)
121        .collect();
122    Ok(Mat::<f64>::from_fn(n, keep.len(), |i, c| {
123        vectors[(i, keep[c])] * w[keep[c]].sqrt()
124    }))
125}
126
127impl CITest for Kci {
128    fn validate(&self, data: &Dataset) -> Result<(), CIError> {
129        if !(self.epsilon.is_finite() && self.epsilon > 0.0) {
130            return Err(CIError::InvalidConfig(
131                "epsilon must be finite and > 0".to_string(),
132            ));
133        }
134        self.kernel.validate(data)
135    }
136
137    #[allow(
138        clippy::many_single_char_names,
139        clippy::similar_names,
140        reason = "mirrors the x/y/z and kx/ky/kz notation of the spec"
141    )]
142    fn test_impl(
143        &self,
144        data: &Dataset,
145        x: usize,
146        y: usize,
147        z: &[usize],
148    ) -> Result<CIResult, CIError> {
149        if z.is_empty() {
150            return hsic_unconditional(
151                data,
152                x,
153                y,
154                &self.kernel,
155                self.bandwidth,
156                NullDistribution::Gamma,
157            );
158        }
159        let n = data.n_rows();
160        dense_len_guard(n)?;
161        let n_z = z.len();
162
163        let px = standardized(data, &[x], 1.0)?;
164        let pz_half = standardized(data, z, 0.5)?;
165        let py = standardized(data, &[y], 1.0)?;
166        let pz = standardized(data, z, 1.0)?;
167        let x_aug = Mat::<f64>::from_fn(n, 1 + n_z, |i, j| {
168            if j == 0 {
169                px[(i, 0)]
170            } else {
171                pz_half[(i, j - 1)]
172            }
173        });
174
175        let kernel_z = match &self.kernel {
176            KernelChoice::All(k) => *k,
177            _ => default_rbf(&pz, self.bandwidth, n, n_z),
178        };
179        let kernel_x = queried_kernel(data, x, &x_aug, self, n_z);
180        let kernel_y = queried_kernel(data, y, &py, self, n_z);
181
182        let kx = centered_kernel(kernel_x, &x_aug);
183        let ky = centered_kernel(kernel_y, &py);
184        let mut kz = centered_kernel(kernel_z, &pz);
185        for i in 0..n {
186            kz[(i, i)] += self.epsilon;
187        }
188        let llt = kz
189            .llt(Side::Lower)
190            .map_err(|e| numeric("Cholesky factorization", e))?;
191        let mut rz = llt.inverse();
192        for j in 0..n {
193            for i in 0..n {
194                rz[(i, j)] *= self.epsilon;
195            }
196        }
197        let kxr = &rz * &kx * &rz;
198        let kyr = &rz * &ky * &rz;
199
200        let stat = inner(&kxr, &kyr);
201        let denom = (inner(&kxr, &kxr) * inner(&kyr, &kyr)).sqrt();
202        let effect = if denom > 0.0 { stat / denom } else { 0.0 };
203
204        let vx = scaled_eigenvectors(&kxr)?;
205        let vy = scaled_eigenvectors(&kyr)?;
206        let gx = &vx * vx.transpose();
207        let gy = &vy * vy.transpose();
208        let mut tr = 0.0;
209        let mut sq = 0.0;
210        for j in 0..n {
211            for i in 0..n {
212                let u = gx[(i, j)] * gy[(i, j)];
213                sq += u * u;
214                if i == j {
215                    tr += u;
216                }
217            }
218        }
219        let p_value = gamma_pvalue(stat, tr, 2.0 * sq)?;
220
221        Ok(CIResult {
222            statistic: Some(stat),
223            p_value,
224            dof: None,
225            effect_size: Some(effect),
226        })
227    }
228
229    fn meta(&self) -> TestMeta {
230        TestMeta {
231            name: "kci",
232            data_types: &[DataType::Continuous],
233            symmetric: false,
234            rule: IndependenceRule::PValueGe,
235        }
236    }
237}
238
239#[cfg(test)]
240#[allow(
241    clippy::float_cmp,
242    clippy::cast_precision_loss,
243    clippy::many_single_char_names,
244    clippy::similar_names
245)]
246mod tests {
247    use super::*;
248    use crate::ci_tests::Hsic;
249    use crate::dataset::ColumnKind;
250    use crate::rng::SplitMix64;
251    use std::collections::BTreeMap;
252
253    fn uniform(rng: &mut SplitMix64) -> f64 {
254        ((rng.next_u64() >> 11) as f64 + 0.5) / (1u64 << 53) as f64
255    }
256
257    fn normals(rng: &mut SplitMix64, n: usize) -> Vec<f64> {
258        let mut out = Vec::with_capacity(n);
259        while out.len() < n {
260            let (u1, u2) = (uniform(rng), uniform(rng));
261            let r = (-2.0 * u1.ln()).sqrt();
262            out.push(r * (2.0 * std::f64::consts::PI * u2).cos());
263            out.push(r * (2.0 * std::f64::consts::PI * u2).sin());
264        }
265        out.truncate(n);
266        out
267    }
268
269    fn cont(cols: Vec<(&str, Vec<f64>)>) -> Dataset {
270        Dataset::from_columns(
271            cols.into_iter()
272                .map(|(n, v)| (n.to_string(), ColumnKind::Continuous, v))
273                .collect(),
274        )
275        .unwrap()
276    }
277
278    /// Columns x, y, z with x = z + 0.5 e1, y = z + 0.5 e2.
279    fn chain(n: usize, seed: u64) -> Dataset {
280        let mut rng = SplitMix64::new(seed);
281        let z = normals(&mut rng, n);
282        let e1 = normals(&mut rng, n);
283        let e2 = normals(&mut rng, n);
284        let x = z.iter().zip(&e1).map(|(a, b)| a + 0.5 * b).collect();
285        let y = z.iter().zip(&e2).map(|(a, b)| a + 0.5 * b).collect();
286        cont(vec![("x", x), ("y", y), ("z", z)])
287    }
288
289    #[test]
290    fn empty_z_equals_default_hsic() {
291        let d = chain(60, 1);
292        let a = Kci::new().test(&d, 0, 1, &[]).unwrap();
293        let b = Hsic::new().test(&d, 0, 1, &[]).unwrap();
294        assert_eq!(a, b);
295    }
296
297    #[test]
298    fn heuristic_length_scale_bands() {
299        assert_eq!(kci_heuristic_length_scale(199, 1), 1.2);
300        assert_eq!(kci_heuristic_length_scale(200, 1), 0.7);
301        assert_eq!(kci_heuristic_length_scale(1199, 4), 1.4);
302        assert_eq!(kci_heuristic_length_scale(1200, 1), 0.4);
303    }
304
305    #[test]
306    fn asymmetric_in_x_and_y() {
307        let mut rng = SplitMix64::new(3);
308        let z = normals(&mut rng, 80);
309        let x = normals(&mut rng, 80);
310        let e = normals(&mut rng, 80);
311        let y = x.iter().zip(&e).map(|(a, b)| a + 0.3 * b).collect();
312        let d = cont(vec![("x", x), ("y", y), ("z", z)]);
313        let a = Kci::new().test(&d, 0, 1, &[2]).unwrap();
314        let b = Kci::new().test(&d, 1, 0, &[2]).unwrap();
315        assert!((a.statistic.unwrap() - b.statistic.unwrap()).abs() > 1e-9 * a.statistic.unwrap());
316    }
317
318    #[test]
319    fn per_column_entry_for_z_is_ignored() {
320        let d = chain(60, 5);
321        let x = ("x".to_string(), Kernel::Rbf { length_scale: 2.0 });
322        let with_z = BTreeMap::from([
323            x.clone(),
324            ("z".to_string(), Kernel::Rbf { length_scale: 5.0 }),
325        ]);
326        let without = BTreeMap::from([x]);
327        let a = Kci {
328            kernel: KernelChoice::PerColumn(with_z),
329            ..Kci::new()
330        };
331        let b = Kci {
332            kernel: KernelChoice::PerColumn(without),
333            ..Kci::new()
334        };
335        assert_eq!(
336            a.test(&d, 0, 1, &[2]).unwrap(),
337            b.test(&d, 0, 1, &[2]).unwrap()
338        );
339    }
340
341    #[test]
342    fn single_kernel_applies_to_z() {
343        let d = chain(60, 6);
344        let k = Kernel::Rbf { length_scale: 1.0 };
345        let all = Kci {
346            kernel: KernelChoice::All(k),
347            ..Kci::new()
348        };
349        let map = Kci {
350            kernel: KernelChoice::PerColumn(BTreeMap::from([
351                ("x".to_string(), k),
352                ("y".to_string(), k),
353            ])),
354            ..Kci::new()
355        };
356        assert_ne!(
357            all.test(&d, 0, 1, &[2]).unwrap().statistic,
358            map.test(&d, 0, 1, &[2]).unwrap().statistic
359        );
360    }
361
362    #[test]
363    fn conditional_independence_vs_dependence() {
364        let d = chain(200, 11);
365        let p = Kci::new().test(&d, 0, 1, &[2]).unwrap().p_value;
366        assert!(p > 0.01, "{p}");
367
368        let mut rng = SplitMix64::new(12);
369        let z = normals(&mut rng, 200);
370        let x = normals(&mut rng, 200);
371        let e = normals(&mut rng, 200);
372        let y = x.iter().zip(&e).map(|(a, b)| a + 0.3 * b).collect();
373        let d = cont(vec![("x", x), ("y", y), ("z", z)]);
374        let p = Kci::new().test(&d, 0, 1, &[2]).unwrap().p_value;
375        assert!(p < 1e-4, "{p}");
376    }
377
378    #[test]
379    fn rejects_invalid_epsilon_and_discrete_z() {
380        let d = chain(30, 7);
381        for eps in [0.0, -1.0, f64::NAN] {
382            let t = Kci {
383                epsilon: eps,
384                ..Kci::new()
385            };
386            assert!(matches!(t.validate(&d), Err(CIError::InvalidConfig(_))));
387            assert!(matches!(
388                t.test(&d, 0, 1, &[2]),
389                Err(CIError::InvalidConfig(_))
390            ));
391        }
392        let mut rng = SplitMix64::new(8);
393        let d = Dataset::from_columns(vec![
394            (
395                "x".to_string(),
396                ColumnKind::Continuous,
397                normals(&mut rng, 30),
398            ),
399            (
400                "y".to_string(),
401                ColumnKind::Continuous,
402                normals(&mut rng, 30),
403            ),
404            (
405                "z".to_string(),
406                ColumnKind::Discrete,
407                (0..30).map(|i| f64::from(i % 3)).collect(),
408            ),
409        ])
410        .unwrap();
411        assert!(matches!(
412            Kci::new().test(&d, 0, 1, &[2]),
413            Err(CIError::WrongColumnKind { .. })
414        ));
415    }
416
417    #[test]
418    fn perfectly_dependent_is_finite() {
419        let mut rng = SplitMix64::new(13);
420        let x = normals(&mut rng, 120);
421        let z = normals(&mut rng, 120);
422        let y = x.clone();
423        let d = cont(vec![("x", x), ("y", y), ("z", z)]);
424        let r = Kci::new().test(&d, 0, 1, &[2]).unwrap();
425        assert!(r.statistic.unwrap().is_finite());
426        assert!(r.p_value < 1e-6, "{}", r.p_value);
427    }
428
429    #[test]
430    fn works_with_unrelated_discrete_columns() {
431        let mut rng = SplitMix64::new(9);
432        let d = Dataset::from_columns(vec![
433            (
434                "x".to_string(),
435                ColumnKind::Continuous,
436                normals(&mut rng, 40),
437            ),
438            (
439                "y".to_string(),
440                ColumnKind::Continuous,
441                normals(&mut rng, 40),
442            ),
443            (
444                "z".to_string(),
445                ColumnKind::Continuous,
446                normals(&mut rng, 40),
447            ),
448            (
449                "d".to_string(),
450                ColumnKind::Discrete,
451                (0..40).map(|i| f64::from(i % 3)).collect(),
452            ),
453        ])
454        .unwrap();
455        assert!(Kci::new().test(&d, 0, 1, &[2]).is_ok());
456    }
457}