Skip to main content

fastcit_core/
kernel.rs

1//! Kernel types and dense kernel-matrix helpers shared by HSIC and KCI.
2//!
3//! Points are row-major `faer::Mat<f64>` (n rows x d columns). All helpers
4//! follow the pgmpy reference numerics (sklearn `RBF`, numpy median).
5
6use std::collections::BTreeMap;
7
8use faer::{Mat, MatRef};
9use statrs::distribution::{ContinuousCDF, Gamma};
10
11use crate::dataset::Dataset;
12use crate::error::CIError;
13
14/// A positive-definite kernel on standardized points.
15#[derive(Debug, Clone, Copy, PartialEq)]
16pub enum Kernel {
17    /// Gaussian kernel `exp(-||a - b||^2 / (2 l^2))`.
18    Rbf {
19        /// Length scale `l`; must be finite and positive.
20        length_scale: f64,
21    },
22    /// Linear kernel `a . b`.
23    Linear,
24}
25
26/// How a default RBF length scale is chosen.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
28pub enum Bandwidth {
29    /// Fixed sample-size heuristic.
30    #[default]
31    Heuristic,
32    /// Median pairwise distance rule.
33    Median,
34}
35
36/// Which kernel(s) to use for the columns of a query.
37#[derive(Debug, Clone, PartialEq, Default)]
38pub enum KernelChoice {
39    /// Test-specific default kernel.
40    #[default]
41    Auto,
42    /// One kernel for every column.
43    All(Kernel),
44    /// A kernel per named column.
45    PerColumn(BTreeMap<String, Kernel>),
46}
47
48impl Kernel {
49    /// Check the kernel parameters.
50    ///
51    /// # Errors
52    /// [`CIError::InvalidConfig`] if an RBF length scale is not finite and > 0.
53    pub fn validate(&self) -> Result<(), CIError> {
54        if let Kernel::Rbf { length_scale } = *self {
55            if !(length_scale.is_finite() && length_scale > 0.0) {
56                return Err(CIError::InvalidConfig(format!(
57                    "RBF length_scale must be finite and > 0, got {length_scale}"
58                )));
59            }
60        }
61        Ok(())
62    }
63}
64
65impl KernelChoice {
66    /// Validate every kernel and that every `PerColumn` key names a column.
67    ///
68    /// # Errors
69    /// [`CIError::InvalidConfig`] for a bad kernel, [`CIError::UnknownColumn`]
70    /// for an unknown column name.
71    pub fn validate(&self, data: &Dataset) -> Result<(), CIError> {
72        match self {
73            KernelChoice::Auto => Ok(()),
74            KernelChoice::All(k) => k.validate(),
75            KernelChoice::PerColumn(map) => {
76                for (name, k) in map {
77                    if data.index_of(name).is_none() {
78                        return Err(CIError::UnknownColumn(name.clone()));
79                    }
80                    k.validate()?;
81                }
82                Ok(())
83            }
84        }
85    }
86}
87
88/// Reject sample sizes whose dense `n x n` matrix would overflow `isize`.
89pub(crate) fn dense_len_guard(n: usize) -> Result<(), CIError> {
90    let ok = n
91        .checked_mul(n)
92        .and_then(|v| v.checked_mul(8))
93        .is_some_and(|b| isize::try_from(b).is_ok());
94    if ok {
95        Ok(())
96    } else {
97        Err(CIError::DegenerateData(format!(
98            "too many rows ({n}) for a dense kernel matrix"
99        )))
100    }
101}
102
103/// Stack `cols`, each standardized (ddof = 1) and multiplied by `scale`.
104pub(crate) fn standardized(
105    data: &Dataset,
106    cols: &[usize],
107    scale: f64,
108) -> Result<Mat<f64>, CIError> {
109    let n = data.n_rows();
110    if n < 2 {
111        return Err(CIError::DegenerateData(
112            "at least 2 rows are required".into(),
113        ));
114    }
115    let mut out = Mat::<f64>::zeros(n, cols.len());
116    #[allow(clippy::cast_precision_loss)]
117    let nf = n as f64;
118    for (j, &c) in cols.iter().enumerate() {
119        let v = data.continuous(c)?;
120        let mean = v.iter().sum::<f64>() / nf;
121        let var = v.iter().map(|x| (x - mean) * (x - mean)).sum::<f64>() / (nf - 1.0);
122        let sd = var.sqrt();
123        if !(sd.is_finite() && sd > 0.0) {
124            return Err(CIError::DegenerateData(format!(
125                "column {} has zero or non-finite variance",
126                data.name_of(c).unwrap_or("?")
127            )));
128        }
129        for (i, x) in v.iter().enumerate() {
130            out[(i, j)] = (x - mean) / sd * scale;
131        }
132    }
133    Ok(out)
134}
135
136/// Dense kernel matrix over the rows of `points`.
137#[must_use]
138#[allow(clippy::many_single_char_names)]
139pub(crate) fn kernel_matrix(kernel: Kernel, points: MatRef<'_, f64>) -> Mat<f64> {
140    let n = points.nrows();
141    let d = points.ncols();
142    let mut k = Mat::<f64>::zeros(n, n);
143    match kernel {
144        Kernel::Rbf { length_scale } => {
145            for i in 0..n {
146                for j in i..n {
147                    let mut s = 0.0;
148                    for c in 0..d {
149                        let diff = points[(i, c)] / length_scale - points[(j, c)] / length_scale;
150                        s += diff * diff;
151                    }
152                    let v = (-0.5 * s).exp();
153                    k[(i, j)] = v;
154                    k[(j, i)] = v;
155                }
156            }
157        }
158        Kernel::Linear => {
159            for i in 0..n {
160                for j in i..n {
161                    let mut s = 0.0;
162                    for c in 0..d {
163                        s += points[(i, c)] * points[(j, c)];
164                    }
165                    k[(i, j)] = s;
166                    k[(j, i)] = s;
167                }
168            }
169        }
170    }
171    k
172}
173
174/// In-place centering: `K - colmean - colmean[:, None] + mean(colmean)`.
175pub(crate) fn center(k: &mut Mat<f64>) {
176    let n = k.nrows();
177    if n == 0 {
178        return;
179    }
180    #[allow(clippy::cast_precision_loss)]
181    let nf = n as f64;
182    let colmean: Vec<f64> = (0..k.ncols())
183        .map(|j| (0..n).map(|i| k[(i, j)]).sum::<f64>() / nf)
184        .collect();
185    let total = colmean.iter().sum::<f64>() / nf;
186    for j in 0..k.ncols() {
187        for i in 0..n {
188            k[(i, j)] = k[(i, j)] - colmean[j] - colmean[i] + total;
189        }
190    }
191}
192
193/// Median pairwise Euclidean distance (zeros dropped) divided by sqrt(2);
194/// `1.0` if there is no non-zero distance.
195#[must_use]
196pub(crate) fn median_length_scale(points: MatRef<'_, f64>) -> f64 {
197    let n = points.nrows();
198    let d = points.ncols();
199    let mut dist = Vec::with_capacity(n * n.saturating_sub(1) / 2);
200    for i in 0..n {
201        for j in (i + 1)..n {
202            let mut s = 0.0;
203            for c in 0..d {
204                let diff = points[(i, c)] - points[(j, c)];
205                s += diff * diff;
206            }
207            let r = s.sqrt();
208            if r > 0.0 {
209                dist.push(r);
210            }
211        }
212    }
213    let m = dist.len();
214    if m == 0 {
215        return 1.0;
216    }
217    let cmp = |a: &f64, b: &f64| a.total_cmp(b);
218    let hi_idx = m / 2;
219    let (lower, hi, _) = dist.select_nth_unstable_by(hi_idx, cmp);
220    let hi = *hi;
221    let median = if m % 2 == 1 {
222        hi
223    } else {
224        let lo = lower.iter().copied().max_by(cmp).unwrap_or(hi);
225        f64::midpoint(lo, hi)
226    };
227    median / std::f64::consts::SQRT_2
228}
229
230/// Gamma-approximation p-value from the null mean and variance.
231pub(crate) fn gamma_pvalue(stat: f64, mean: f64, var: f64) -> Result<f64, CIError> {
232    if var <= 0.0 || mean <= 0.0 {
233        return Ok(1.0);
234    }
235    let shape = mean * mean / var;
236    let scale = var / mean;
237    let g = Gamma::new(shape, 1.0 / scale)
238        .map_err(|e| CIError::Numeric(format!("gamma construction failed: {e}")))?;
239    Ok(g.sf(stat))
240}
241
242#[cfg(test)]
243#[allow(clippy::float_cmp)]
244mod tests {
245    use super::*;
246    use crate::dataset::ColumnKind;
247
248    fn col(v: &[f64]) -> Mat<f64> {
249        Mat::from_fn(v.len(), 1, |i, _| v[i])
250    }
251
252    #[test]
253    fn rbf_and_linear_entries() {
254        let p = col(&[0.0, 1.0, 3.0]);
255        let k = kernel_matrix(Kernel::Rbf { length_scale: 2.0 }, p.as_ref());
256        assert!((k[(0, 1)] - (-0.125f64).exp()).abs() < 1e-15);
257        assert!((k[(0, 2)] - (-1.125f64).exp()).abs() < 1e-15);
258        for i in 0..3 {
259            assert_eq!(k[(i, i)], 1.0);
260        }
261        let l = kernel_matrix(Kernel::Linear, p.as_ref());
262        assert_eq!(l[(1, 2)], 3.0);
263    }
264
265    #[test]
266    fn centering_zeroes_row_and_column_sums() {
267        let p = col(&[0.3, -1.0, 2.0, 0.7]);
268        let mut k = kernel_matrix(Kernel::Rbf { length_scale: 1.0 }, p.as_ref());
269        center(&mut k);
270        for i in 0..4 {
271            let r: f64 = (0..4).map(|j| k[(i, j)]).sum();
272            let c: f64 = (0..4).map(|j| k[(j, i)]).sum();
273            assert!(r.abs() < 1e-12 && c.abs() < 1e-12);
274        }
275    }
276
277    #[test]
278    fn median_length_scale_drops_zero_distances() {
279        let s2 = std::f64::consts::SQRT_2;
280        assert!((median_length_scale(col(&[0.0, 1.0, 3.0]).as_ref()) - 2.0 / s2).abs() < 1e-15);
281        assert!((median_length_scale(col(&[0.0, 0.0, 1.0]).as_ref()) - 1.0 / s2).abs() < 1e-15);
282        assert_eq!(median_length_scale(col(&[5.0, 5.0]).as_ref()), 1.0);
283        // even count: distances {1,2,3,4,...}
284        let m = median_length_scale(col(&[0.0, 1.0, 2.0]).as_ref());
285        assert!((m - 1.0 / s2).abs() < 1e-15); // {1,1,2} -> 1
286    }
287
288    #[test]
289    fn gamma_pvalue_closed_form_and_degenerate_moments() {
290        let p = gamma_pvalue(3.0, 2.0, 2.0).unwrap();
291        assert!((p - 0.199_148_273_471_455_78).abs() < 1e-14);
292        assert_eq!(gamma_pvalue(3.0, 0.0, 2.0).unwrap(), 1.0);
293        assert_eq!(gamma_pvalue(3.0, -1.0, 2.0).unwrap(), 1.0);
294        assert_eq!(gamma_pvalue(3.0, 2.0, 0.0).unwrap(), 1.0);
295    }
296
297    #[test]
298    fn standardized_rejects_constant_and_discrete_columns() {
299        let d = Dataset::from_columns(vec![
300            ("a".into(), ColumnKind::Continuous, vec![1.0, 2.0, 4.0]),
301            ("c".into(), ColumnKind::Continuous, vec![1.0, 1.0, 1.0]),
302            ("d".into(), ColumnKind::Discrete, vec![0.0, 1.0, 0.0]),
303        ])
304        .unwrap();
305        let m = standardized(&d, &[0], 2.0).unwrap();
306        let sum: f64 = (0..3).map(|i| m[(i, 0)]).sum();
307        assert!(sum.abs() < 1e-12);
308        let ss: f64 = (0..3).map(|i| m[(i, 0)] * m[(i, 0)]).sum();
309        assert!((ss - 4.0 * 2.0).abs() < 1e-12);
310        assert!(matches!(
311            standardized(&d, &[1], 1.0),
312            Err(CIError::DegenerateData(_))
313        ));
314        assert!(matches!(
315            standardized(&d, &[2], 1.0),
316            Err(CIError::WrongColumnKind(_))
317        ));
318    }
319
320    #[test]
321    fn kernel_validation_rejects_bad_length_scales() {
322        for l in [0.0, -1.0, f64::NAN, f64::INFINITY] {
323            assert!(matches!(
324                Kernel::Rbf { length_scale: l }.validate(),
325                Err(CIError::InvalidConfig(_))
326            ));
327        }
328        assert!(Kernel::Rbf { length_scale: 0.5 }.validate().is_ok());
329        assert!(Kernel::Linear.validate().is_ok());
330    }
331
332    #[test]
333    fn per_column_choice_rejects_unknown_columns() {
334        let d = Dataset::from_columns(vec![("a".into(), ColumnKind::Continuous, vec![1.0, 2.0])])
335            .unwrap();
336        let mut m = BTreeMap::new();
337        m.insert("a".to_string(), Kernel::Linear);
338        assert!(KernelChoice::PerColumn(m.clone()).validate(&d).is_ok());
339        m.insert("zz".to_string(), Kernel::Linear);
340        assert!(matches!(
341            KernelChoice::PerColumn(m).validate(&d),
342            Err(CIError::UnknownColumn(_))
343        ));
344    }
345
346    #[test]
347    fn dense_len_guard_rejects_overflow() {
348        assert!(matches!(
349            dense_len_guard(usize::MAX / 2),
350            Err(CIError::DegenerateData(_))
351        ));
352        assert!(dense_len_guard(1000).is_ok());
353    }
354}