Skip to main content

fastcit_core/
discrete.rs

1//! Discrete contingency-table machinery operating on factorized `Dataset` codes.
2//!
3//! This is the discrete back-end for the power-divergence family of
4//! conditional-independence tests (see [`crate::ci_tests`]): it builds `(X, Y)`
5//! count tables from integer codes, applies the power-divergence statistic for a
6//! given parameter `λ` (with optional Yates' continuity correction on 2×2
7//! tables), and aggregates over the strata defined by the conditioning set `Z`.
8//!
9//! The statistic matches `scipy.stats.chi2_contingency(table, lambda_=λ,
10//! correction=yates)`, which is how the golden fixture was generated. For a table
11//! with observed counts `O`, marginals `R_i`, `C_j`, total `N` and expected
12//! `E_ij = R_i * C_j / N`:
13//!
14//! - `λ = 0`   (log-likelihood / G-test): `2 * Σ O·ln(O/E)`.
15//! - `λ = −1`  (modified log-likelihood): `2 * Σ E·ln(E/O)`.
16//! - otherwise (incl. `λ = 1`, `2/3`, `−1/2`):
17//!   `(2 / (λ·(λ+1))) · Σ ( O^(λ+1)/E^λ − O )`.
18//!
19//! The `O^(λ+1)/E^λ − O` form is used (rather than `O·((O/E)^λ − 1)`) because it
20//! is `O = 0`-safe for every `λ > −1`: at `O = 0` the term is `0` instead of the
21//! `0·∞ = NaN` the naive form would produce for `λ < 0`.
22//!
23//! Conditional tests consume a cached row partition for the conditioning set,
24//! tabulating each stratum in turn.
25
26use crate::strata::StrataPartition;
27
28/// The parameter `λ` selecting a member of the power-divergence family.
29const LAMBDA_LOG_LIKELIHOOD: f64 = 0.0;
30/// The parameter `λ` for the modified log-likelihood (Neyman) statistic.
31const LAMBDA_MODIFIED: f64 = -1.0;
32
33/// A dense `rows × cols` contingency table of counts, stored row-major.
34pub(crate) struct ContingencyTable {
35    rows: usize,
36    cols: usize,
37    counts: Vec<f64>,
38}
39
40impl ContingencyTable {
41    /// Allocate a zeroed `rows × cols` table.
42    fn zeros(rows: usize, cols: usize) -> Self {
43        Self {
44            rows,
45            cols,
46            counts: vec![0.0; rows * cols],
47        }
48    }
49
50    #[inline]
51    fn add(&mut self, r: usize, c: usize) {
52        self.counts[r * self.cols + c] += 1.0;
53    }
54
55    /// Zero the table for reuse across strata.
56    fn reset(&mut self) {
57        self.counts.fill(0.0);
58    }
59
60    /// Iterate over the rows of the table as count slices.
61    fn rows(&self) -> impl Iterator<Item = &[f64]> {
62        self.counts.chunks_exact(self.cols)
63    }
64}
65
66/// Per-table result: `(statistic, degrees_of_freedom)`.
67type TableStat = (f64, usize);
68
69/// One cell's contribution to the power-divergence statistic, given the
70/// (possibly Yates-corrected) observed count `observed` and expected `expected`.
71///
72/// `expected` is guaranteed `> 0` by the caller (active marginals and total are
73/// positive). Returns `f64::INFINITY` for the `λ = −1`, `O = 0`, `E > 0` cell,
74/// which propagates to a `+∞` statistic and hence `p = 0`.
75#[inline]
76fn power_divergence_term(observed: f64, expected: f64, lambda: f64) -> f64 {
77    if lambda == LAMBDA_LOG_LIKELIHOOD {
78        // 2 * O * ln(O / E), with O*ln(O) -> 0 at O = 0.
79        if observed == 0.0 {
80            0.0
81        } else {
82            2.0 * observed * (observed / expected).ln()
83        }
84    } else if lambda == LAMBDA_MODIFIED {
85        // 2 * E * ln(E / O); at O = 0 (E > 0) this is +inf.
86        if observed == 0.0 {
87            f64::INFINITY
88        } else {
89            2.0 * expected * (expected / observed).ln()
90        }
91    } else {
92        // (2 / (λ(λ+1))) * ( O^(λ+1)/E^λ − O ).
93        // O = 0-safe for λ > −1: the bracket is 0 at O = 0.
94        let bracket = observed.powf(lambda + 1.0) / expected.powf(lambda) - observed;
95        (2.0 / (lambda * (lambda + 1.0))) * bracket
96    }
97}
98
99/// Power-divergence statistic and dof for one table, applying Yates' continuity
100/// correction on 2×2 tables when `yates` is set.
101///
102/// Returns `None` if the table is degenerate for testing: fewer than 2 active
103/// rows/columns, or a zero total (the stratum should then be skipped). dof is
104/// computed over the *active* sub-table (rows/columns with a non-zero marginal),
105/// matching scipy/pgmpy which drop empty categories.
106fn power_divergence_table(table: &ContingencyTable, lambda: f64, yates: bool) -> Option<TableStat> {
107    // Marginals over the global shape.
108    let mut row_sums = vec![0.0; table.rows];
109    let mut col_sums = vec![0.0; table.cols];
110    for (row, row_sum) in table.rows().zip(row_sums.iter_mut()) {
111        for (&v, col_sum) in row.iter().zip(col_sums.iter_mut()) {
112            *row_sum += v;
113            *col_sum += v;
114        }
115    }
116    let total: f64 = row_sums.iter().sum();
117    if total == 0.0 {
118        return None;
119    }
120
121    // Active rows/cols are those with a non-zero marginal.
122    let active_rows = row_sums.iter().filter(|&&s| s > 0.0).count();
123    let active_cols = col_sums.iter().filter(|&&s| s > 0.0).count();
124    if active_rows < 2 || active_cols < 2 {
125        return None;
126    }
127
128    let dof = (active_rows - 1) * (active_cols - 1);
129    // Yates' correction applies to the active 2×2 table (dof == 1), for all λ.
130    let use_yates = yates && dof == 1;
131
132    let mut statistic = 0.0;
133    for (row, &row_sum) in table.rows().zip(row_sums.iter()) {
134        if row_sum == 0.0 {
135            continue;
136        }
137        for (&observed, &col_sum) in row.iter().zip(col_sums.iter()) {
138            if col_sum == 0.0 {
139                continue;
140            }
141            let expected = row_sum * col_sum / total;
142            // Active marginals are > 0 and total > 0, so expected > 0.
143            let corrected = if use_yates {
144                // Yates: shrink O toward E by clamping (O − E) to [−0.5, 0.5].
145                observed - (observed - expected).clamp(-0.5, 0.5)
146            } else {
147                observed
148            };
149            statistic += power_divergence_term(corrected, expected, lambda);
150        }
151    }
152
153    Some((statistic, dof))
154}
155
156/// Result of the discrete power-divergence test.
157pub(crate) struct DiscreteOutcome {
158    pub statistic: f64,
159    pub dof: usize,
160}
161
162/// Unconditional `(X, Y)` power-divergence statistic for parameter `lambda`,
163/// with Yates' correction when `yates` is set. Returns a zero statistic with
164/// `dof == 0` when the table is degenerate (single active row/column).
165pub(crate) fn power_divergence_unconditional(
166    x_codes: &[usize],
167    y_codes: &[usize],
168    kx: usize,
169    ky: usize,
170    lambda: f64,
171    yates: bool,
172) -> DiscreteOutcome {
173    let mut table = ContingencyTable::zeros(kx, ky);
174    for (&xc, &yc) in x_codes.iter().zip(y_codes) {
175        table.add(xc, yc);
176    }
177    let (statistic, dof) = power_divergence_table(&table, lambda, yates).unwrap_or((0.0, 0));
178    DiscreteOutcome { statistic, dof }
179}
180
181/// Conditional power-divergence statistic for parameter `lambda`: tabulate
182/// each stratum of `partition` into one reused table over the *global* X/Y
183/// cardinalities, skip degenerate strata, and sum the statistic and dof.
184/// Yates' correction is applied per active 2×2 stratum when `yates` is set.
185pub(crate) fn power_divergence_conditional(
186    x_codes: &[usize],
187    y_codes: &[usize],
188    kx: usize,
189    ky: usize,
190    partition: &StrataPartition,
191    lambda: f64,
192    yates: bool,
193) -> DiscreteOutcome {
194    let mut table = ContingencyTable::zeros(kx, ky);
195    let mut statistic = 0.0;
196    let mut dof = 0;
197    for s in 0..partition.n_strata() {
198        table.reset();
199        let lo = partition.starts[s] as usize;
200        let hi = partition.starts[s + 1] as usize;
201        for &row in &partition.rows[lo..hi] {
202            table.add(x_codes[row as usize], y_codes[row as usize]);
203        }
204        if let Some((stat, table_dof)) = power_divergence_table(&table, lambda, yates) {
205            statistic += stat;
206            dof += table_dof;
207        }
208    }
209    DiscreteOutcome { statistic, dof }
210}
211
212#[cfg(test)]
213mod tests {
214    use super::*;
215    use crate::strata::build_strata_partition;
216
217    const LAMBDA_PEARSON: f64 = 1.0;
218    const LAMBDA_CRESSIE_READ: f64 = 2.0 / 3.0;
219    const LAMBDA_FREEMAN_TUKEY: f64 = -0.5;
220
221    fn table(rows: usize, cols: usize, counts: &[f64]) -> ContingencyTable {
222        ContingencyTable {
223            rows,
224            cols,
225            counts: counts.to_vec(),
226        }
227    }
228
229    #[test]
230    fn yates_2x2_matches_scipy_pearson() {
231        // Table [[10, 0], [0, 10]] with Yates: each |O-E|=5 shrinks by 0.5.
232        // E = 5 everywhere; corrected diff = 4.5; stat = 4*(4.5^2/5) = 16.2.
233        let x = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
234        let y = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
235        let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, true);
236        assert!((out.statistic - 16.2).abs() < 1e-9, "got {}", out.statistic);
237        assert_eq!(out.dof, 1);
238    }
239
240    #[test]
241    fn yates_can_be_disabled() {
242        // Same table without Yates: stat = 4*(5^2/5) = 20.
243        let x = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
244        let y = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
245        let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, false);
246        assert!((out.statistic - 20.0).abs() < 1e-9, "got {}", out.statistic);
247        assert_eq!(out.dof, 1);
248    }
249
250    #[test]
251    fn independent_table_zero_statistic() {
252        // Perfectly balanced 2x2 -> chi-square 0 (after Yates, still ~0).
253        let x = vec![0, 0, 1, 1];
254        let y = vec![0, 1, 0, 1];
255        let out = power_divergence_unconditional(&x, &y, 2, 2, LAMBDA_PEARSON, true);
256        assert!(out.statistic.abs() < 1e-12);
257        assert_eq!(out.dof, 1);
258    }
259
260    #[test]
261    fn single_category_degenerate() {
262        let x = vec![0, 0, 0, 0];
263        let y = vec![0, 1, 0, 1];
264        let out = power_divergence_unconditional(&x, &y, 1, 2, LAMBDA_PEARSON, true);
265        assert_eq!(out.dof, 0);
266        assert!(out.statistic.abs() < 1e-12);
267    }
268
269    #[test]
270    fn modified_likelihood_zero_cell_is_infinite() {
271        // λ = −1 with a structural zero where E > 0 -> +∞ statistic.
272        // 3×3 (dof != 1 so no Yates) with a zero in an active row/col.
273        let t = table(3, 3, &[5.0, 5.0, 0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0]);
274        let (stat, dof) = power_divergence_table(&t, LAMBDA_MODIFIED, true).unwrap();
275        assert!(stat.is_infinite() && stat > 0.0, "got {stat}");
276        assert_eq!(dof, 4);
277    }
278
279    #[test]
280    fn zero_cell_finite_for_lambda_gt_minus_one() {
281        // For λ > −1 a zero observed cell contributes a finite (0) term, never NaN.
282        let t = table(3, 3, &[5.0, 5.0, 0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0]);
283        for lambda in [
284            LAMBDA_PEARSON,
285            LAMBDA_LOG_LIKELIHOOD,
286            LAMBDA_CRESSIE_READ,
287            LAMBDA_FREEMAN_TUKEY,
288        ] {
289            let (stat, _) = power_divergence_table(&t, lambda, true).unwrap();
290            assert!(stat.is_finite(), "lambda {lambda} gave {stat}");
291        }
292    }
293
294    /// Deterministic LCG so the parity tests need no rand dependency.
295    fn lcg_codes(seed: &mut u64, n: usize, card: usize) -> Vec<usize> {
296        (0..n)
297            .map(|_| {
298                *seed = seed
299                    .wrapping_mul(6_364_136_223_846_793_005)
300                    .wrapping_add(1_442_695_040_888_963_407);
301                ((*seed >> 33) as usize) % card
302            })
303            .collect()
304    }
305
306    /// Independent naive reference: group rows by the Z-code tuple with a
307    /// `HashMap`, tabulate each group, and sum statistic/dof.
308    fn naive_conditional(
309        x: &[usize],
310        y: &[usize],
311        kx: usize,
312        ky: usize,
313        z: &[(&[usize], usize)],
314        lambda: f64,
315        yates: bool,
316    ) -> DiscreteOutcome {
317        let n = x.len();
318        let mut strata: std::collections::HashMap<Vec<usize>, Vec<usize>> =
319            std::collections::HashMap::new();
320        for i in 0..n {
321            let key: Vec<usize> = z.iter().map(|(codes, _)| codes[i]).collect();
322            strata.entry(key).or_default().push(i);
323        }
324        let mut statistic = 0.0;
325        let mut dof = 0;
326        for idx in strata.values() {
327            let mut table = ContingencyTable::zeros(kx, ky);
328            for &i in idx {
329                table.add(x[i], y[i]);
330            }
331            if let Some((stat, table_dof)) = power_divergence_table(&table, lambda, yates) {
332                statistic += stat;
333                dof += table_dof;
334            }
335        }
336        DiscreteOutcome { statistic, dof }
337    }
338
339    fn assert_outcomes_match(fast: &DiscreteOutcome, slow: &DiscreteOutcome, label: &str) {
340        assert_eq!(fast.dof, slow.dof, "dof {label}");
341        let scale = fast.statistic.abs().max(slow.statistic.abs()).max(1.0);
342        assert!(
343            (fast.statistic - slow.statistic).abs() <= 1e-9 * scale
344                || (fast.statistic.is_infinite() && slow.statistic.is_infinite()),
345            "stat {label}: {} vs {}",
346            fast.statistic,
347            slow.statistic
348        );
349    }
350
351    #[test]
352    fn conditional_matches_naive_grouping() {
353        let mut seed = 0x00C0_FFEE_u64;
354        for (n, kx, ky, z_cards) in [
355            (200, 2, 2, vec![2]),
356            (500, 3, 4, vec![2, 3]),
357            (350, 2, 3, vec![3, 2, 4]),
358            (64, 4, 4, vec![5]),
359            (30, 2, 2, vec![100, 100]), // exercises the HashMap densify arm
360        ] {
361            let x = lcg_codes(&mut seed, n, kx);
362            let y = lcg_codes(&mut seed, n, ky);
363            let z: Vec<(Vec<usize>, usize)> = z_cards
364                .iter()
365                .map(|&c| (lcg_codes(&mut seed, n, c), c))
366                .collect();
367            let z_ref: Vec<(&[usize], usize)> = z.iter().map(|(v, c)| (v.as_slice(), *c)).collect();
368            let partition = build_strata_partition(&z_ref, n);
369            for lambda in [1.0, 0.0, -1.0, 2.0 / 3.0, -0.5] {
370                let fast = power_divergence_conditional(&x, &y, kx, ky, &partition, lambda, true);
371                let slow = naive_conditional(&x, &y, kx, ky, &z_ref, lambda, true);
372                assert_outcomes_match(&fast, &slow, &format!("λ={lambda} n={n}"));
373            }
374        }
375    }
376
377    #[test]
378    fn overflow_path_matches_naive() {
379        // 64 conditioning columns of cardinality 2 -> 2^64 overflows usize,
380        // forcing the in-builder hashed grouping. 8 rows.
381        let n = 8;
382        let x: Vec<usize> = (0..n).map(|i| i % 2).collect();
383        let y: Vec<usize> = (0..n).map(|i| (i / 2) % 2).collect();
384        let z_cols: Vec<Vec<usize>> = (0..64)
385            .map(|c| (0..n).map(|i| (i >> (c % 3)) % 2).collect())
386            .collect();
387        let z_ref: Vec<(&[usize], usize)> = z_cols.iter().map(|v| (v.as_slice(), 2)).collect();
388        let partition = build_strata_partition(&z_ref, n);
389        let fast = power_divergence_conditional(&x, &y, 2, 2, &partition, 1.0, true);
390        let slow = naive_conditional(&x, &y, 2, 2, &z_ref, 1.0, true);
391        assert_outcomes_match(&fast, &slow, "overflow");
392    }
393}