1use 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
20const EIGEN_RELATIVE_CUTOFF: f64 = 1e-5;
22
23#[derive(Debug, Clone, PartialEq)]
25pub struct Kci {
26 pub kernel: KernelChoice,
28 pub bandwidth: Bandwidth,
30 pub epsilon: f64,
32}
33
34impl Kci {
35 #[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#[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
67fn 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
82fn 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
92fn 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
102fn 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
109fn 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 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}