Skip to main content

fastcit_core/ci_tests/
hsic.rs

1//! Hilbert-Schmidt independence criterion (HSIC) test for two continuous
2//! variables, matching pgmpy's `HSIC` (gamma null) with an additional
3//! deterministic permutation null.
4
5use 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/// How the null distribution of the HSIC statistic is approximated.
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
18pub enum NullDistribution {
19    /// Gamma approximation from the null moments (fast).
20    #[default]
21    Gamma,
22    /// Monte-Carlo permutation null, reproducible from `seed`.
23    Permutation {
24        /// Number of permutations; must be at least 1.
25        n_permutations: usize,
26        /// Seed of the deterministic permutation stream.
27        seed: u64,
28    },
29}
30
31/// HSIC independence test (`X ⊥ Y`, no conditioning set).
32#[derive(Debug, Clone, PartialEq, Default)]
33pub struct Hsic {
34    /// Kernel selection.
35    pub kernel: KernelChoice,
36    /// Bandwidth rule for default RBF kernels.
37    pub bandwidth: Bandwidth,
38    /// Null-distribution approximation.
39    pub null_dist: NullDistribution,
40}
41
42impl Hsic {
43    /// pgmpy defaults: default kernels, heuristic bandwidth, gamma null.
44    #[must_use]
45    pub fn new() -> Self {
46        Self::default()
47    }
48}
49
50/// Default per-column RBF length scale by sample size.
51#[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
62/// Kernel for one column under `choice`, with the default RBF as fallback.
63fn 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
83/// Frobenius inner product of two equally sized matrices.
84fn 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
94/// Unconditional HSIC of columns `x` and `y`; also KCI's empty-Z fallback.
95pub(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    // Uncentered moments needed by the gamma null.
113    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
181/// Sum of all entries and trace of a square matrix.
182fn 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}