1use faer::Mat;
6
7use crate::dataset::Dataset;
8use crate::error::CIError;
9use crate::kernel::{
10 center, dense_len_guard, gamma_pvalue, kernel_matrix, median_length_scale, standardized,
11 Bandwidth, Kernel, KernelChoice,
12};
13use crate::rng::{shuffle_identity, SplitMix64};
14use crate::strategy::{CIResult, CITest, DataType, IndependenceRule, TestMeta};
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
18pub enum NullDistribution {
19 #[default]
21 Gamma,
22 Permutation {
24 n_permutations: usize,
26 seed: u64,
28 },
29}
30
31#[derive(Debug, Clone, PartialEq, Default)]
33pub struct Hsic {
34 pub kernel: KernelChoice,
36 pub bandwidth: Bandwidth,
38 pub null_dist: NullDistribution,
40}
41
42impl Hsic {
43 #[must_use]
45 pub fn new() -> Self {
46 Self::default()
47 }
48}
49
50#[must_use]
52pub(crate) fn hsic_heuristic_length_scale(n: usize) -> f64 {
53 if n < 200 {
54 0.8
55 } else if n < 1200 {
56 0.5
57 } else {
58 0.3
59 }
60}
61
62fn column_kernel(
64 data: &Dataset,
65 col: usize,
66 points: &Mat<f64>,
67 choice: &KernelChoice,
68 bandwidth: Bandwidth,
69) -> Kernel {
70 let explicit = match choice {
71 KernelChoice::Auto => None,
72 KernelChoice::All(k) => Some(*k),
73 KernelChoice::PerColumn(map) => data.name_of(col).and_then(|n| map.get(n)).copied(),
74 };
75 explicit.unwrap_or_else(|| Kernel::Rbf {
76 length_scale: match bandwidth {
77 Bandwidth::Heuristic => hsic_heuristic_length_scale(points.nrows()),
78 Bandwidth::Median => median_length_scale(points.as_ref()),
79 },
80 })
81}
82
83fn inner(a: &Mat<f64>, b: &Mat<f64>) -> f64 {
85 let mut s = 0.0;
86 for j in 0..a.ncols() {
87 for i in 0..a.nrows() {
88 s += a[(i, j)] * b[(i, j)];
89 }
90 }
91 s
92}
93
94pub(crate) fn hsic_unconditional(
96 data: &Dataset,
97 x: usize,
98 y: usize,
99 kernel: &KernelChoice,
100 bandwidth: Bandwidth,
101 null_dist: NullDistribution,
102) -> Result<CIResult, CIError> {
103 let n = data.n_rows();
104 dense_len_guard(n)?;
105 let px = standardized(data, &[x], 1.0)?;
106 let py = standardized(data, &[y], 1.0)?;
107 let kernel_x = column_kernel(data, x, &px, kernel, bandwidth);
108 let kernel_y = column_kernel(data, y, &py, kernel, bandwidth);
109 let mut kx = kernel_matrix(kernel_x, px.as_ref());
110 let mut ky = kernel_matrix(kernel_y, py.as_ref());
111
112 let (sum_x, tr_x) = sum_and_trace(&kx);
114 let (sum_y, tr_y) = sum_and_trace(&ky);
115 center(&mut kx);
116 center(&mut ky);
117
118 let stat = inner(&kx, &ky);
119 let denom = (inner(&kx, &kx) * inner(&ky, &ky)).sqrt();
120 let effect = if denom > 0.0 { stat / denom } else { 0.0 };
121
122 #[allow(clippy::cast_precision_loss)]
123 let p_value = match null_dist {
124 NullDistribution::Permutation {
125 n_permutations,
126 seed,
127 } => {
128 let mut rng = SplitMix64::new(seed);
129 let mut perm = vec![0usize; n];
130 let mut count = 0usize;
131 for _ in 0..n_permutations {
132 shuffle_identity(&mut rng, &mut perm);
133 let mut s = 0.0;
134 for j in 0..n {
135 for i in 0..n {
136 s += kx[(i, j)] * ky[(perm[i], perm[j])];
137 }
138 }
139 if s >= stat {
140 count += 1;
141 }
142 }
143 (1 + count) as f64 / (1 + n_permutations) as f64
144 }
145 NullDistribution::Gamma => {
146 if n < 6 {
147 1.0
148 } else {
149 let nf = n as f64;
150 let n_pairs = nf * (nf - 1.0);
151 let mut pp = 0.0;
152 let mut diag_sq = 0.0;
153 for j in 0..n {
154 for i in 0..n {
155 let v = kx[(i, j)] * ky[(i, j)];
156 pp += v * v;
157 if i == j {
158 diag_sq += v * v;
159 }
160 }
161 }
162 let off = (pp - diag_sq) / 36.0;
163 let factor = 72.0 * (nf - 4.0) * (nf - 5.0) / (n_pairs * (nf - 2.0) * (nf - 3.0));
164 let var = factor * off / n_pairs;
165 let mu_x = (sum_x - tr_x) / n_pairs;
166 let mu_y = (sum_y - tr_y) / n_pairs;
167 let mean = (tr_x / nf - mu_x) * (tr_y / nf - mu_y) / nf;
168 gamma_pvalue(stat / nf, nf * mean, nf * nf * var)?
169 }
170 }
171 };
172
173 Ok(CIResult {
174 statistic: Some(stat),
175 p_value,
176 dof: None,
177 effect_size: Some(effect),
178 })
179}
180
181fn sum_and_trace(k: &Mat<f64>) -> (f64, f64) {
183 let mut sum = 0.0;
184 let mut tr = 0.0;
185 for j in 0..k.ncols() {
186 for i in 0..k.nrows() {
187 sum += k[(i, j)];
188 }
189 tr += k[(j, j)];
190 }
191 (sum, tr)
192}
193
194impl CITest for Hsic {
195 fn validate(&self, data: &Dataset) -> Result<(), CIError> {
196 if let NullDistribution::Permutation { n_permutations, .. } = self.null_dist {
197 if n_permutations < 1 {
198 return Err(CIError::InvalidConfig(
199 "n_permutations must be >= 1".to_string(),
200 ));
201 }
202 }
203 self.kernel.validate(data)
204 }
205
206 fn test_impl(
207 &self,
208 data: &Dataset,
209 x: usize,
210 y: usize,
211 z: &[usize],
212 ) -> Result<CIResult, CIError> {
213 if !z.is_empty() {
214 return Err(CIError::InvalidQuery(
215 "HSIC does not support a conditioning set; use KCI".to_string(),
216 ));
217 }
218 hsic_unconditional(data, x, y, &self.kernel, self.bandwidth, self.null_dist)
219 }
220
221 fn meta(&self) -> TestMeta {
222 TestMeta {
223 name: "hsic",
224 data_types: &[DataType::Continuous],
225 symmetric: true,
226 rule: IndependenceRule::PValueGe,
227 }
228 }
229}
230
231#[cfg(test)]
232#[allow(
233 clippy::float_cmp,
234 clippy::cast_precision_loss,
235 clippy::many_single_char_names,
236 clippy::similar_names
237)]
238mod tests {
239 use super::*;
240 use crate::dataset::{ColumnKind, Dataset};
241 use crate::error::CIError;
242 use crate::kernel::{Bandwidth, Kernel, KernelChoice};
243 use crate::rng::SplitMix64;
244 use crate::strategy::CITest;
245 use std::collections::BTreeMap;
246
247 fn uniform(rng: &mut SplitMix64) -> f64 {
248 ((rng.next_u64() >> 11) as f64 + 0.5) / (1u64 << 53) as f64
249 }
250
251 fn normals(rng: &mut SplitMix64, n: usize) -> Vec<f64> {
252 let mut out = Vec::with_capacity(n);
253 while out.len() < n {
254 let (u1, u2) = (uniform(rng), uniform(rng));
255 let r = (-2.0 * u1.ln()).sqrt();
256 out.push(r * (2.0 * std::f64::consts::PI * u2).cos());
257 out.push(r * (2.0 * std::f64::consts::PI * u2).sin());
258 }
259 out.truncate(n);
260 out
261 }
262
263 fn ds(cols: Vec<(&str, ColumnKind, Vec<f64>)>) -> Dataset {
264 Dataset::from_columns(
265 cols.into_iter()
266 .map(|(n, k, v)| (n.to_string(), k, v))
267 .collect(),
268 )
269 .unwrap()
270 }
271
272 fn two(x: Vec<f64>, y: Vec<f64>) -> Dataset {
273 ds(vec![
274 ("x", ColumnKind::Continuous, x),
275 ("y", ColumnKind::Continuous, y),
276 ])
277 }
278
279 fn pearson(x: &[f64], y: &[f64]) -> f64 {
280 let n = x.len() as f64;
281 let mx = x.iter().sum::<f64>() / n;
282 let my = y.iter().sum::<f64>() / n;
283 let sxy: f64 = x.iter().zip(y).map(|(a, b)| (a - mx) * (b - my)).sum();
284 let sxx: f64 = x.iter().map(|a| (a - mx) * (a - mx)).sum();
285 let syy: f64 = y.iter().map(|b| (b - my) * (b - my)).sum();
286 sxy / (sxx * syy).sqrt()
287 }
288
289 fn rel(a: f64, b: f64) -> f64 {
290 (a - b).abs() / b.abs().max(1e-300)
291 }
292
293 fn indep(n: usize, seed: u64) -> Dataset {
294 let mut rng = SplitMix64::new(seed);
295 two(normals(&mut rng, n), normals(&mut rng, n))
296 }
297
298 #[test]
299 fn linear_kernel_matches_closed_form() {
300 let mut rng = SplitMix64::new(1);
301 let x = normals(&mut rng, 50);
302 let e = normals(&mut rng, 50);
303 let y: Vec<f64> = x.iter().zip(&e).map(|(a, b)| 0.5 * a + b).collect();
304 let r = pearson(&x, &y);
305 let d = two(x, y);
306 let t = Hsic {
307 kernel: KernelChoice::All(Kernel::Linear),
308 ..Hsic::new()
309 };
310 let res = t.test(&d, 0, 1, &[]).unwrap();
311 assert!(rel(res.statistic.unwrap(), (49.0 * r) * (49.0 * r)) < 1e-12);
312 assert!(rel(res.effect_size.unwrap(), r * r) < 1e-12);
313 assert_eq!(res.dof, None);
314 }
315
316 #[test]
317 fn heuristic_length_scale_bands() {
318 for n in [5, 199] {
319 assert_eq!(hsic_heuristic_length_scale(n), 0.8);
320 }
321 for n in [200, 1199] {
322 assert_eq!(hsic_heuristic_length_scale(n), 0.5);
323 }
324 for n in [1200, 5000] {
325 assert_eq!(hsic_heuristic_length_scale(n), 0.3);
326 }
327 }
328
329 #[test]
330 fn tiny_sample_gamma_p_is_one() {
331 let d = two(vec![1., 2., 3., 4., 5.], vec![2., 1., 4., 3., 7.]);
332 let res = Hsic::new().test(&d, 0, 1, &[]).unwrap();
333 assert_eq!(res.p_value, 1.0);
334 assert!(res.statistic.unwrap().is_finite());
335 }
336
337 #[test]
338 fn symmetric_in_x_and_y() {
339 let d = indep(40, 3);
340 let a = Hsic::new().test(&d, 0, 1, &[]).unwrap();
341 let b = Hsic::new().test(&d, 1, 0, &[]).unwrap();
342 assert!(rel(a.statistic.unwrap(), b.statistic.unwrap()) < 1e-12);
343 assert!((a.p_value - b.p_value).abs() < 1e-12);
344 assert!(rel(a.effect_size.unwrap(), b.effect_size.unwrap()) < 1e-12);
345 }
346
347 #[test]
348 fn permutation_p_value_bounds_and_determinism() {
349 let t = Hsic {
350 null_dist: NullDistribution::Permutation {
351 n_permutations: 19,
352 seed: 7,
353 },
354 ..Hsic::new()
355 };
356 let d = indep(100, 11);
357 let p = t.test(&d, 0, 1, &[]).unwrap().p_value;
358 let k = p * 20.0;
359 assert!((k - k.round()).abs() < 1e-9 && (1.0..=20.0).contains(&k.round()));
360 assert_eq!(p, t.test(&d, 0, 1, &[]).unwrap().p_value);
361 assert!(p > 0.05, "{p}");
362
363 let mut rng = SplitMix64::new(5);
364 let x = normals(&mut rng, 100);
365 let e = normals(&mut rng, 100);
366 let y: Vec<f64> = x.iter().zip(&e).map(|(a, b)| a * a + 0.01 * b).collect();
367 let p = t.test(&two(x, y), 0, 1, &[]).unwrap().p_value;
368 assert_eq!(p, 1.0 / 20.0);
369 }
370
371 #[test]
372 fn rejects_conditioning_set() {
373 let mut rng = SplitMix64::new(2);
374 let d = ds(vec![
375 ("x", ColumnKind::Continuous, normals(&mut rng, 30)),
376 ("y", ColumnKind::Continuous, normals(&mut rng, 30)),
377 ("z", ColumnKind::Continuous, normals(&mut rng, 30)),
378 ]);
379 assert!(matches!(
380 Hsic::new().test(&d, 0, 1, &[2]),
381 Err(CIError::InvalidQuery(_))
382 ));
383 }
384
385 #[test]
386 fn rejects_invalid_config() {
387 let d = indep(30, 4);
388 let t = Hsic {
389 null_dist: NullDistribution::Permutation {
390 n_permutations: 0,
391 seed: 0,
392 },
393 ..Hsic::new()
394 };
395 assert!(matches!(t.validate(&d), Err(CIError::InvalidConfig(_))));
396 assert!(matches!(
397 t.test(&d, 0, 1, &[]),
398 Err(CIError::InvalidConfig(_))
399 ));
400 for ell in [0.0, -1.0, f64::NAN] {
401 let t = Hsic {
402 kernel: KernelChoice::All(Kernel::Rbf { length_scale: ell }),
403 ..Hsic::new()
404 };
405 assert!(matches!(t.validate(&d), Err(CIError::InvalidConfig(_))));
406 }
407 let mut m = BTreeMap::new();
408 m.insert("nope".to_string(), Kernel::Linear);
409 let t = Hsic {
410 kernel: KernelChoice::PerColumn(m),
411 ..Hsic::new()
412 };
413 assert!(matches!(t.validate(&d), Err(CIError::UnknownColumn(_))));
414 }
415
416 #[test]
417 fn works_with_unrelated_discrete_columns() {
418 let mut rng = SplitMix64::new(9);
419 let d = ds(vec![
420 ("x", ColumnKind::Continuous, normals(&mut rng, 20)),
421 ("y", ColumnKind::Continuous, normals(&mut rng, 20)),
422 (
423 "d",
424 ColumnKind::Discrete,
425 (0..20).map(|i| f64::from(i % 3)).collect(),
426 ),
427 ]);
428 assert!(Hsic::new().test(&d, 0, 1, &[]).is_ok());
429 }
430
431 #[test]
432 fn perfectly_dependent_is_finite() {
433 let mut rng = SplitMix64::new(13);
434 let x = normals(&mut rng, 200);
435 let y: Vec<f64> = x.iter().map(|a| 2.0 * a).collect();
436 let res = Hsic::new().test(&two(x, y), 0, 1, &[]).unwrap();
437 assert!(res.statistic.unwrap().is_finite());
438 assert!(res.p_value < 1e-6, "{}", res.p_value);
439 }
440
441 #[test]
442 fn dependent_vs_independent_gamma() {
443 let mut rng = SplitMix64::new(21);
444 let x = normals(&mut rng, 300);
445 let e = normals(&mut rng, 300);
446 let y: Vec<f64> = x
447 .iter()
448 .zip(&e)
449 .map(|(a, b)| (3.0 * a).sin() + 0.1 * b)
450 .collect();
451 let p = Hsic::new().test(&two(x, y), 0, 1, &[]).unwrap().p_value;
452 assert!(p < 1e-6, "{p}");
453 let p = Hsic::new()
454 .test(&indep(300, 22), 0, 1, &[])
455 .unwrap()
456 .p_value;
457 assert!(p > 0.01, "{p}");
458 let t = Hsic {
459 bandwidth: Bandwidth::Median,
460 ..Hsic::new()
461 };
462 assert!(t.test(&indep(300, 22), 0, 1, &[]).unwrap().p_value > 0.01);
463 }
464}