Skip to main content

qualia_core_db/solvers/learning/classification/
discriminant.rs

1//! Discriminant analysis (ISL ch 4.4) — LDA (shared covariance ⇒ linear boundary)
2//! and QDA (per-class covariance ⇒ quadratic boundary). Both are Gaussian
3//! generative classifiers; the covariance inverse / log-determinant come from
4//! `linear_algebra::cholesky` (no new solver). Kernel-class `DenseLinear`.
5
6use crate::solvers::learning::LearningError;
7use crate::solvers::linear_algebra::cholesky::{
8    cholesky_determinant, cholesky_factor, cholesky_solve,
9};
10
11/// Per-class means + priors + the index map, shared setup for LDA and QDA.
12struct ClassStats {
13    classes: Vec<usize>,
14    priors: Vec<f64>,
15    means: Vec<f64>, // n_classes × p
16    counts: Vec<usize>,
17}
18
19fn class_stats(x: &[f64], y: &[usize], n: usize, p: usize) -> Result<ClassStats, LearningError> {
20    if n == 0 || p == 0 || x.len() != n * p || y.len() != n {
21        return Err(LearningError::InvalidDimension);
22    }
23    let mut classes: Vec<usize> = y.to_vec();
24    classes.sort_unstable();
25    classes.dedup();
26    let c = classes.len();
27    let mut priors = vec![0.0; c];
28    let mut means = vec![0.0; c * p];
29    let mut counts = vec![0usize; c];
30    let cls_idx = |cls: usize| classes.iter().position(|&v| v == cls).unwrap();
31    for i in 0..n {
32        let ci = cls_idx(y[i]);
33        counts[ci] += 1;
34        for j in 0..p {
35            means[ci * p + j] += x[i * p + j];
36        }
37    }
38    for ci in 0..c {
39        if counts[ci] == 0 {
40            return Err(LearningError::InsufficientData);
41        }
42        priors[ci] = counts[ci] as f64 / n as f64;
43        for j in 0..p {
44            means[ci * p + j] /= counts[ci] as f64;
45        }
46    }
47    Ok(ClassStats {
48        classes,
49        priors,
50        means,
51        counts,
52    })
53}
54
55// ── LDA ───────────────────────────────────────────────────────────────────────
56
57/// Linear Discriminant Analysis: one shared within-class covariance. The
58/// discriminant is linear, `δ_c(x) = xᵀwc + bc`.
59#[derive(Debug, Clone)]
60pub struct LdaModel {
61    pub classes: Vec<usize>,
62    w: Vec<f64>, // n_classes × p : Σ⁻¹ μ_c
63    b: Vec<f64>, // n_classes      : −½ μcᵀ Σ⁻¹ μc + ln π_c
64    p: usize,
65}
66
67impl LdaModel {
68    /// Fit LDA. Needs `n > n_classes` for a non-degenerate pooled covariance.
69    pub fn fit(x: &[f64], y: &[usize], n: usize, p: usize) -> Result<Self, LearningError> {
70        let cs = class_stats(x, y, n, p)?;
71        let c = cs.classes.len();
72        if n <= c {
73            return Err(LearningError::InsufficientData);
74        }
75        // Pooled within-class scatter → covariance Σ = S/(n−C).
76        let mut cov = vec![0.0; p * p];
77        let cls_idx = |cls: usize| cs.classes.iter().position(|&v| v == cls).unwrap();
78        for i in 0..n {
79            let ci = cls_idx(y[i]);
80            for a in 0..p {
81                let da = x[i * p + a] - cs.means[ci * p + a];
82                for bb in 0..p {
83                    let db = x[i * p + bb] - cs.means[ci * p + bb];
84                    cov[a * p + bb] += da * db;
85                }
86            }
87        }
88        let denom = (n - c) as f64;
89        for v in cov.iter_mut() {
90            *v /= denom;
91        }
92        let l = cholesky_of(&cov, p)?;
93
94        let mut w = vec![0.0; c * p];
95        let mut b = vec![0.0; c];
96        let mut mu = vec![0.0; p];
97        let mut wc = vec![0.0; p];
98        for ci in 0..c {
99            mu.copy_from_slice(&cs.means[ci * p..(ci + 1) * p]);
100            cholesky_solve(p, &l, &mu, &mut wc)?; // wc = Σ⁻¹ μ_c
101            w[ci * p..(ci + 1) * p].copy_from_slice(&wc);
102            let quad: f64 = mu.iter().zip(wc.iter()).map(|(m, w)| m * w).sum();
103            b[ci] = -0.5 * quad + cs.priors[ci].ln();
104        }
105        Ok(Self {
106            classes: cs.classes,
107            w,
108            b,
109            p,
110        })
111    }
112
113    /// LDA-predicts one row `q`.
114    pub fn predict_row(&self, q: &[f64]) -> usize {
115        let mut best = 0;
116        let mut best_s = f64::NEG_INFINITY;
117        for ci in 0..self.classes.len() {
118            let s: f64 = q
119                .iter()
120                .zip(&self.w[ci * self.p..(ci + 1) * self.p])
121                .map(|(x, w)| x * w)
122                .sum::<f64>()
123                + self.b[ci];
124            if s > best_s {
125                best_s = s;
126                best = ci;
127            }
128        }
129        self.classes[best]
130    }
131
132    /// LDA-predicts `m` rows in `x`.
133    pub fn predict(&self, x: &[f64], m: usize) -> Vec<usize> {
134        (0..m)
135            .map(|i| self.predict_row(&x[i * self.p..(i + 1) * self.p]))
136            .collect()
137    }
138}
139
140// ── QDA ───────────────────────────────────────────────────────────────────────
141
142/// Quadratic Discriminant Analysis: a separate covariance per class. The
143/// discriminant `δ_c(x) = −½ ln|Σc| − ½ (x−μc)ᵀ Σc⁻¹ (x−μc) + ln π_c`.
144#[derive(Debug, Clone)]
145pub struct QdaModel {
146    pub classes: Vec<usize>,
147    means: Vec<f64>,   // n_classes × p
148    chol: Vec<f64>,    // n_classes × p × p : Cholesky factors of Σ_c
149    log_det: Vec<f64>, // n_classes
150    log_prior: Vec<f64>,
151    p: usize,
152}
153
154impl QdaModel {
155    /// Fit QDA. Needs each class to have `> p` samples for a non-singular covariance.
156    pub fn fit(x: &[f64], y: &[usize], n: usize, p: usize) -> Result<Self, LearningError> {
157        let cs = class_stats(x, y, n, p)?;
158        let c = cs.classes.len();
159        let cls_idx = |cls: usize| cs.classes.iter().position(|&v| v == cls).unwrap();
160        let mut chol = vec![0.0; c * p * p];
161        let mut log_det = vec![0.0; c];
162        let mut log_prior = vec![0.0; c];
163        for ci in 0..c {
164            if cs.counts[ci] <= p {
165                return Err(LearningError::InsufficientData); // covariance would be singular
166            }
167            // Per-class covariance Σ_c = S_c/(n_c−1).
168            let mut cov = vec![0.0; p * p];
169            for i in 0..n {
170                if cls_idx(y[i]) != ci {
171                    continue;
172                }
173                for a in 0..p {
174                    let da = x[i * p + a] - cs.means[ci * p + a];
175                    for bb in 0..p {
176                        let db = x[i * p + bb] - cs.means[ci * p + bb];
177                        cov[a * p + bb] += da * db;
178                    }
179                }
180            }
181            let denom = (cs.counts[ci] - 1) as f64;
182            for v in cov.iter_mut() {
183                *v /= denom;
184            }
185            let l = cholesky_of(&cov, p)?;
186            log_det[ci] = cholesky_determinant(p, &l).max(1e-300).ln();
187            chol[ci * p * p..(ci + 1) * p * p].copy_from_slice(&l);
188            log_prior[ci] = cs.priors[ci].ln();
189        }
190        Ok(Self {
191            classes: cs.classes,
192            means: cs.means,
193            chol,
194            log_det,
195            log_prior,
196            p,
197        })
198    }
199
200    /// QDA-predicts one row `q`.
201    pub fn predict_row(&self, q: &[f64]) -> usize {
202        let p = self.p;
203        let mut diff = vec![0.0; p];
204        let mut sol = vec![0.0; p];
205        let mut best = 0;
206        let mut best_s = f64::NEG_INFINITY;
207        for ci in 0..self.classes.len() {
208            for j in 0..p {
209                diff[j] = q[j] - self.means[ci * p + j];
210            }
211            // Mahalanobis² = diffᵀ Σ⁻¹ diff via the Cholesky factor.
212            let l = &self.chol[ci * p * p..(ci + 1) * p * p];
213            if cholesky_solve(p, l, &diff, &mut sol).is_err() {
214                continue;
215            }
216            let maha: f64 = diff.iter().zip(sol.iter()).map(|(d, s)| d * s).sum();
217            let s = -0.5 * self.log_det[ci] - 0.5 * maha + self.log_prior[ci];
218            if s > best_s {
219                best_s = s;
220                best = ci;
221            }
222        }
223        self.classes[best]
224    }
225
226    /// QDA-predicts `m` rows in `x`.
227    pub fn predict(&self, x: &[f64], m: usize) -> Vec<usize> {
228        (0..m)
229            .map(|i| self.predict_row(&x[i * self.p..(i + 1) * self.p]))
230            .collect()
231    }
232}
233
234/// Cholesky factor of a `p×p` covariance, mapping a solver failure to `Singular`.
235fn cholesky_of(cov: &[f64], p: usize) -> Result<Vec<f64>, LearningError> {
236    let mut l = vec![0.0; p * p];
237    cholesky_factor(p, cov, &mut l).map_err(|_| LearningError::Singular)?;
238    Ok(l)
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244
245    // Two 2-D classes, well separated, enough points for per-class covariance.
246    fn data() -> (Vec<f64>, Vec<usize>, usize) {
247        let mut x = Vec::new();
248        let mut y = Vec::new();
249        // class 0 around (0,0)
250        for &(a, b) in &[
251            (0.0, 0.0),
252            (0.5, -0.3),
253            (-0.4, 0.2),
254            (0.2, 0.4),
255            (-0.3, -0.2),
256        ] {
257            x.push(a);
258            x.push(b);
259            y.push(0);
260        }
261        // class 1 around (5,5)
262        for &(a, b) in &[(5.0, 5.0), (5.4, 4.7), (4.6, 5.3), (5.1, 4.9), (4.8, 5.2)] {
263            x.push(a);
264            x.push(b);
265            y.push(1);
266        }
267        (x, y, 10)
268    }
269
270    #[test]
271    fn lda_separates_classes() {
272        let (x, y, n) = data();
273        let m = LdaModel::fit(&x, &y, n, 2).unwrap();
274        assert_eq!(m.classes, vec![0, 1]);
275        assert_eq!(m.predict_row(&[0.1, 0.1]), 0);
276        assert_eq!(m.predict_row(&[5.0, 5.0]), 1);
277        // Training accuracy is perfect on this separable set.
278        let preds = m.predict(&x, n);
279        assert!(preds.iter().zip(&y).all(|(a, b)| a == b));
280    }
281
282    #[test]
283    fn qda_separates_classes() {
284        let (x, y, n) = data();
285        let m = QdaModel::fit(&x, &y, n, 2).unwrap();
286        assert_eq!(m.predict_row(&[0.0, 0.0]), 0);
287        assert_eq!(m.predict_row(&[5.2, 4.8]), 1);
288        let preds = m.predict(&x, n);
289        assert!(preds.iter().zip(&y).all(|(a, b)| a == b));
290    }
291
292    #[test]
293    fn qda_fails_closed_on_too_few_per_class() {
294        // class 0 has 3 non-collinear points (fine); class 1 has only 2, p=2 →
295        // n_c ≤ p → its covariance would be singular → fail closed.
296        let x = [0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 5.0, 5.0, 6.0, 5.0];
297        let y = [0, 0, 0, 1, 1];
298        assert_eq!(
299            QdaModel::fit(&x, &y, 5, 2).unwrap_err(),
300            LearningError::InsufficientData
301        );
302    }
303}