Skip to main content

fastcit_core/ci_tests/
gcm.rs

1//! Generalized covariance measure (GCM) conditional-independence test
2//! (continuous data), after Shah & Peters (2020).
3//!
4//! X and Y are linearly regressed on `[1, Z]`; with residuals `r_x`, `r_y` and
5//! `u = r_x ∘ r_y`, the statistic is `T = Σu / (√n · std(u))` (population
6//! standard deviation), asymptotically N(0, 1) under H₀. The p-value is
7//! `2 · P(N > |T|)` and the effect size is `|cor(r_x, r_y)|`.
8
9use faer::Mat;
10use statrs::distribution::{ContinuousCDF, Normal};
11
12use crate::dataset::Dataset;
13use crate::error::CIError;
14use crate::residual::{design_matrix, ols_residuals_multi};
15use crate::strategy::{CIResult, CITest, DataType, IndependenceRule, TestMeta};
16
17/// Relative threshold below which a residual is treated as exactly zero.
18const RESIDUAL_TOL: f64 = 1e-10;
19
20/// Generalized covariance measure test (linear residualization).
21#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
22pub struct Gcm;
23
24impl Gcm {
25    /// Construct the test (no configuration).
26    #[must_use]
27    pub fn new() -> Self {
28        Self
29    }
30}
31
32/// Residuals of continuous column `col` on `design`, as a plain vector.
33fn residual_of(
34    data: &Dataset,
35    design: &Mat<f64>,
36    col: usize,
37    name: &str,
38) -> Result<Vec<f64>, CIError> {
39    let values = data.continuous(col)?;
40    let n = values.len();
41    let target = Mat::from_fn(n, 1, |i, _| values[i]);
42    let res = ols_residuals_multi(design.as_ref(), target.as_ref())?;
43    let r: Vec<f64> = (0..n).map(|i| res[(i, 0)]).collect();
44    let max_abs = values.iter().fold(0.0_f64, |m, v| m.max(v.abs()));
45    let (lo, hi) = values
46        .iter()
47        .fold((f64::INFINITY, f64::NEG_INFINITY), |(l, h), &v| {
48            (l.min(v), h.max(v))
49        });
50    if lo >= hi {
51        return Err(CIError::DegenerateData(format!("{name} is constant")));
52    }
53    #[allow(clippy::cast_precision_loss)]
54    let nf = n as f64;
55    #[allow(clippy::cast_precision_loss)]
56    let mean = values.iter().sum::<f64>() / nf;
57    let scale: f64 = values.iter().map(|v| (v - mean).powi(2)).sum();
58    let res_ss: f64 = r.iter().map(|v| v * v).sum();
59    let noise = nf * f64::EPSILON * f64::EPSILON * max_abs * max_abs;
60    if !res_ss.is_finite() || res_ss <= RESIDUAL_TOL * RESIDUAL_TOL * scale + noise {
61        return Err(CIError::DegenerateData(format!(
62            "residual of {name} given Z has no variance"
63        )));
64    }
65    Ok(r)
66}
67
68#[allow(clippy::many_single_char_names, clippy::similar_names)] // x, y, z, t, n are the standard names
69impl CITest for Gcm {
70    fn test_impl(
71        &self,
72        data: &Dataset,
73        x: usize,
74        y: usize,
75        z: &[usize],
76    ) -> Result<CIResult, CIError> {
77        data.continuous(x)?;
78        data.continuous(y)?;
79        for &c in z {
80            data.continuous(c)?;
81        }
82        let design = design_matrix(data, z)?;
83        let rx = residual_of(data, &design, x, "X")?;
84        let ry = residual_of(data, &design, y, "Y")?;
85
86        #[allow(clippy::cast_precision_loss)]
87        let n = rx.len() as f64;
88        let u: Vec<f64> = rx.iter().zip(&ry).map(|(a, b)| a * b).collect();
89        let sum_u: f64 = u.iter().sum();
90        let mean_u = sum_u / n;
91        let std_u = (u.iter().map(|v| (v - mean_u).powi(2)).sum::<f64>() / n).sqrt();
92        if !(std_u.is_finite() && std_u > 0.0) {
93            return Err(CIError::DegenerateData(
94                "residual products have zero variance".to_string(),
95            ));
96        }
97        let t = sum_u / (n.sqrt() * std_u);
98
99        let normal = Normal::new(0.0, 1.0)
100            .map_err(|e| CIError::Numeric(format!("normal distribution: {e}")))?;
101        let p_value = 2.0 * normal.sf(t.abs());
102
103        let mx = rx.iter().sum::<f64>() / n;
104        let my = ry.iter().sum::<f64>() / n;
105        let (mut cov_xy, mut var_x, mut var_y) = (0.0, 0.0, 0.0);
106        for (a, b) in rx.iter().zip(&ry) {
107            cov_xy += (a - mx) * (b - my);
108            var_x += (a - mx).powi(2);
109            var_y += (b - my).powi(2);
110        }
111        let effect = (cov_xy / (var_x.sqrt() * var_y.sqrt())).abs();
112        if !effect.is_finite() {
113            return Err(CIError::DegenerateData(
114                "residual correlation is undefined".to_string(),
115            ));
116        }
117        Ok(CIResult {
118            statistic: Some(t),
119            p_value,
120            dof: None,
121            effect_size: Some(effect),
122        })
123    }
124
125    fn meta(&self) -> TestMeta {
126        TestMeta {
127            name: "gcm",
128            data_types: &[DataType::Continuous],
129            symmetric: true,
130            rule: IndependenceRule::PValueGe,
131        }
132    }
133}
134
135#[cfg(test)]
136#[allow(
137    clippy::cast_precision_loss,
138    clippy::many_single_char_names,
139    clippy::needless_range_loop,
140    clippy::unreadable_literal
141)] // test helpers: small n, explicit math
142mod tests {
143    use super::*;
144    use crate::dataset::ColumnKind;
145
146    fn lcg(n: usize, seed: u64) -> Vec<f64> {
147        let mut s = seed;
148        (0..n)
149            .map(|_| {
150                s = s
151                    .wrapping_mul(6364136223846793005)
152                    .wrapping_add(1442695040888963407);
153                #[allow(clippy::cast_precision_loss)]
154                let v = (s >> 11) as f64 / (1u64 << 53) as f64;
155                v - 0.5
156            })
157            .collect()
158    }
159
160    fn cols(n: usize) -> (Vec<f64>, Vec<f64>, Vec<f64>, Vec<f64>) {
161        let z1 = lcg(n, 1);
162        let z2 = lcg(n, 2);
163        let ex = lcg(n, 3);
164        let ey = lcg(n, 4);
165        let x = (0..n).map(|i| 1.5 * z1[i] - z2[i] + ex[i]).collect();
166        let y = (0..n)
167            .map(|i| 0.5 + z1[i] + 2.0 * z2[i] + ex[i] * 0.3 + ey[i])
168            .collect();
169        (x, y, z1, z2)
170    }
171
172    fn ds(cs: Vec<(&str, ColumnKind, Vec<f64>)>) -> Dataset {
173        Dataset::from_columns(
174            cs.into_iter()
175                .map(|(n, k, v)| (n.to_string(), k, v))
176                .collect(),
177        )
178        .unwrap()
179    }
180
181    fn formula(rx: &[f64], ry: &[f64]) -> (f64, f64, f64) {
182        let n = rx.len() as f64;
183        let u: Vec<f64> = rx.iter().zip(ry).map(|(a, b)| a * b).collect();
184        let m = u.iter().sum::<f64>() / n;
185        let sd = (u.iter().map(|v| (v - m).powi(2)).sum::<f64>() / n).sqrt();
186        let t = u.iter().sum::<f64>() / (n.sqrt() * sd);
187        let p = 2.0 * Normal::new(0.0, 1.0).unwrap().sf(t.abs());
188        let mx = rx.iter().sum::<f64>() / n;
189        let my = ry.iter().sum::<f64>() / n;
190        let cov_xy: f64 = rx.iter().zip(ry).map(|(a, b)| (a - mx) * (b - my)).sum();
191        let var_x: f64 = rx.iter().map(|a| (a - mx).powi(2)).sum();
192        let var_y: f64 = ry.iter().map(|b| (b - my).powi(2)).sum();
193        (t, p, (cov_xy / (var_x.sqrt() * var_y.sqrt())).abs())
194    }
195
196    fn center(v: &[f64]) -> Vec<f64> {
197        let m = v.iter().sum::<f64>() / v.len() as f64;
198        v.iter().map(|a| a - m).collect()
199    }
200
201    /// Residuals of `v` on `[1, z1, z2]` via explicit normal equations.
202    fn normal_eq_residuals(v: &[f64], z1: &[f64], z2: &[f64]) -> Vec<f64> {
203        let n = v.len();
204        let rows: Vec<[f64; 3]> = (0..n).map(|i| [1.0, z1[i], z2[i]]).collect();
205        let mut a = [[0.0f64; 4]; 3];
206        for (r, &t) in rows.iter().zip(v) {
207            for i in 0..3 {
208                for j in 0..3 {
209                    a[i][j] += r[i] * r[j];
210                }
211                a[i][3] += r[i] * t;
212            }
213        }
214        for c in 0..3 {
215            let p = (c..3)
216                .max_by(|&i, &j| a[i][c].abs().total_cmp(&a[j][c].abs()))
217                .unwrap();
218            a.swap(c, p);
219            for r in 0..3 {
220                if r != c {
221                    let f = a[r][c] / a[c][c];
222                    for k in c..4 {
223                        a[r][k] -= f * a[c][k];
224                    }
225                }
226            }
227        }
228        let beta: Vec<f64> = (0..3).map(|i| a[i][3] / a[i][i]).collect();
229        rows.iter()
230            .zip(v)
231            .map(|(r, &t)| t - (0..3).map(|i| beta[i] * r[i]).sum::<f64>())
232            .collect()
233    }
234
235    #[test]
236    fn unconditional_matches_closed_form() {
237        let (x, y, _, _) = cols(40);
238        let data = ds(vec![
239            ("x", ColumnKind::Continuous, x.clone()),
240            ("y", ColumnKind::Continuous, y.clone()),
241        ]);
242        let r = Gcm::new().test(&data, 0, 1, &[]).unwrap();
243        let (t, p, e) = formula(&center(&x), &center(&y));
244        assert!((r.statistic.unwrap() - t).abs() < 1e-12);
245        assert!((r.p_value - p).abs() < 1e-12);
246        assert!((r.effect_size.unwrap() - e).abs() < 1e-12);
247        assert_eq!(r.dof, None);
248    }
249
250    #[test]
251    fn conditional_uses_ols_residuals() {
252        let (x, y, z1, z2) = cols(60);
253        let data = ds(vec![
254            ("x", ColumnKind::Continuous, x.clone()),
255            ("y", ColumnKind::Continuous, y.clone()),
256            ("z1", ColumnKind::Continuous, z1.clone()),
257            ("z2", ColumnKind::Continuous, z2.clone()),
258        ]);
259        let r = Gcm::new().test(&data, 0, 1, &[2, 3]).unwrap();
260        let rx = normal_eq_residuals(&x, &z1, &z2);
261        let ry = normal_eq_residuals(&y, &z1, &z2);
262        let (t, p, e) = formula(&rx, &ry);
263        assert!((r.statistic.unwrap() - t).abs() < 1e-10);
264        assert!((r.p_value - p).abs() < 1e-10);
265        assert!((r.effect_size.unwrap() - e).abs() < 1e-10);
266    }
267
268    #[test]
269    fn symmetric_in_x_and_y() {
270        let (x, y, z1, _) = cols(50);
271        let data = ds(vec![
272            ("x", ColumnKind::Continuous, x),
273            ("y", ColumnKind::Continuous, y),
274            ("z", ColumnKind::Continuous, z1),
275        ]);
276        let a = Gcm::new().test(&data, 0, 1, &[2]).unwrap();
277        let b = Gcm::new().test(&data, 1, 0, &[2]).unwrap();
278        assert!((a.statistic.unwrap() - b.statistic.unwrap()).abs() < 1e-12);
279        assert!((a.p_value - b.p_value).abs() < 1e-12);
280        assert!((a.effect_size.unwrap() - b.effect_size.unwrap()).abs() < 1e-12);
281    }
282
283    #[test]
284    fn discrete_column_is_wrong_kind() {
285        let (x, y, z1, _) = cols(20);
286        let codes: Vec<f64> = (0..20).map(|i| f64::from(i % 3)).collect();
287        let d = ColumnKind::Discrete;
288        let c = ColumnKind::Continuous;
289        for (kx, ky, kz) in [(d, c, c), (c, d, c), (c, c, d)] {
290            let data = ds(vec![
291                ("x", kx, if kx == d { codes.clone() } else { x.clone() }),
292                ("y", ky, if ky == d { codes.clone() } else { y.clone() }),
293                ("z", kz, if kz == d { codes.clone() } else { z1.clone() }),
294            ]);
295            assert!(matches!(
296                Gcm::new().test(&data, 0, 1, &[2]),
297                Err(CIError::WrongColumnKind(_))
298            ));
299        }
300    }
301
302    #[test]
303    fn x_determined_by_z_is_degenerate() {
304        let (_, y, z1, _) = cols(30);
305        let x: Vec<f64> = z1.iter().map(|v| 2.0 * v + 1.0).collect();
306        let data = ds(vec![
307            ("x", ColumnKind::Continuous, x),
308            ("y", ColumnKind::Continuous, y),
309            ("z", ColumnKind::Continuous, z1),
310        ]);
311        assert!(matches!(
312            Gcm::new().test(&data, 0, 1, &[2]),
313            Err(CIError::DegenerateData(_))
314        ));
315    }
316
317    #[test]
318    fn constant_x_or_y_is_degenerate() {
319        let (x, y, z1, _) = cols(30);
320        let k = vec![0.1; 30];
321        for z in [vec![], vec![2usize]] {
322            for (xs, ys) in [(k.clone(), y.clone()), (x.clone(), k.clone())] {
323                let data = ds(vec![
324                    ("x", ColumnKind::Continuous, xs),
325                    ("y", ColumnKind::Continuous, ys),
326                    ("z", ColumnKind::Continuous, z1.clone()),
327                ]);
328                assert!(matches!(
329                    Gcm::new().test(&data, 0, 1, &z),
330                    Err(CIError::DegenerateData(_))
331                ));
332            }
333        }
334    }
335
336    #[test]
337    fn negating_y_flips_statistic_sign() {
338        let (x, y, _, _) = cols(40);
339        let neg: Vec<f64> = y.iter().map(|v| -v).collect();
340        let mk = |ys| {
341            ds(vec![
342                ("x", ColumnKind::Continuous, x.clone()),
343                ("y", ColumnKind::Continuous, ys),
344            ])
345        };
346        let a = Gcm::new().test(&mk(y), 0, 1, &[]).unwrap();
347        let b = Gcm::new().test(&mk(neg), 0, 1, &[]).unwrap();
348        assert!((a.statistic.unwrap() + b.statistic.unwrap()).abs() < 1e-12);
349        assert!((a.p_value - b.p_value).abs() < 1e-12);
350    }
351}