Skip to main content

qualia_core_db/solvers/learning/regression/
lasso.rs

1//! Lasso regression (ISL ch 6.2.2) — L1-penalized least squares by cyclic
2//! coordinate descent with soft-thresholding.
3//!
4//! Minimise `½‖y − Xβ‖² + λ‖β‖₁` (intercept not penalized; handled by centering).
5//! Unlike ridge, the L1 penalty drives some coefficients **exactly to zero**
6//! (variable selection). Coordinate descent updates one `βⱼ` at a time via the
7//! soft-threshold operator, keeping a running residual for O(np) per sweep.
8//! Scalar fit-loop → CPU (the per-coordinate dot is `Reduction`-class).
9
10use crate::solvers::learning::LearningError;
11use crate::solvers::statistics::descriptive::mean;
12
13/// A fitted lasso model.
14#[derive(Debug, Clone)]
15pub struct LassoModel {
16    pub coefficients: Vec<f64>,
17    pub intercept: f64,
18    pub lambda: f64,
19    pub n_iter: usize,
20    pub converged: bool,
21}
22
23impl LassoModel {
24    /// Prediction for one row.
25    pub fn predict_row(&self, x_row: &[f64]) -> f64 {
26        self.intercept
27            + self
28                .coefficients
29                .iter()
30                .zip(x_row)
31                .map(|(b, x)| b * x)
32                .sum::<f64>()
33    }
34    /// Predictions for rows.
35    pub fn predict(&self, x: &[f64], n: usize, p: usize) -> Vec<f64> {
36        (0..n)
37            .map(|i| self.predict_row(&x[i * p..(i + 1) * p]))
38            .collect()
39    }
40    /// Number of non-zero coefficients (the selected variables).
41    pub fn n_selected(&self) -> usize {
42        self.coefficients.iter().filter(|&&c| c != 0.0).count()
43    }
44}
45
46#[inline]
47fn soft_threshold(z: f64, gamma: f64) -> f64 {
48    if z > gamma {
49        z - gamma
50    } else if z < -gamma {
51        z + gamma
52    } else {
53        0.0
54    }
55}
56
57/// Fit lasso with penalty `lambda ≥ 0` by coordinate descent. `lambda = 0` reduces
58/// to OLS (up to the iteration tolerance). Fails closed on shape mismatch / `n < 2`.
59pub fn fit(
60    x: &[f64],
61    y: &[f64],
62    n: usize,
63    p: usize,
64    lambda: f64,
65    max_iter: usize,
66    tol: f64,
67) -> Result<LassoModel, LearningError> {
68    if n == 0 || p == 0 || x.len() != n * p || y.len() != n {
69        return Err(LearningError::InvalidDimension);
70    }
71    if n < 2 || lambda < 0.0 {
72        return Err(LearningError::InsufficientData);
73    }
74
75    // Centre predictors and response (so the intercept drops out of the penalty).
76    let mut xbar = vec![0.0; p];
77    let mut colbuf = vec![0.0; n];
78    for j in 0..p {
79        for i in 0..n {
80            colbuf[i] = x[i * p + j];
81        }
82        xbar[j] = mean(&colbuf).ok_or(LearningError::InsufficientData)?;
83    }
84    let ybar = mean(y).ok_or(LearningError::InsufficientData)?;
85    let mut xc = vec![0.0; n * p];
86    for i in 0..n {
87        for j in 0..p {
88            xc[i * p + j] = x[i * p + j] - xbar[j];
89        }
90    }
91    // Column squared norms zⱼ = Σ Xcᵢⱼ².
92    let mut znorm = vec![0.0; p];
93    for j in 0..p {
94        let mut s = 0.0;
95        for i in 0..n {
96            s += xc[i * p + j] * xc[i * p + j];
97        }
98        znorm[j] = s;
99    }
100
101    let mut beta = vec![0.0; p];
102    // Running residual r = yc − Xc·β  (β starts at 0 → r = yc).
103    let mut r: Vec<f64> = y.iter().map(|&yi| yi - ybar).collect();
104
105    let mut converged = false;
106    let mut iters = 0;
107    for it in 1..=max_iter.max(1) {
108        iters = it;
109        let mut max_delta = 0.0_f64;
110        for j in 0..p {
111            if znorm[j] == 0.0 {
112                continue; // constant predictor contributes nothing
113            }
114            // ρⱼ = Xcⱼ·r + zⱼ·βⱼ  (add back coordinate j's own contribution).
115            let mut rho = znorm[j] * beta[j];
116            for i in 0..n {
117                rho += xc[i * p + j] * r[i];
118            }
119            let new = soft_threshold(rho, lambda) / znorm[j];
120            let delta = new - beta[j];
121            if delta != 0.0 {
122                // r ← r − Xcⱼ·Δβ.
123                for i in 0..n {
124                    r[i] -= xc[i * p + j] * delta;
125                }
126                beta[j] = new;
127                max_delta = max_delta.max(delta.abs());
128            }
129        }
130        if max_delta < tol {
131            converged = true;
132            break;
133        }
134    }
135
136    let intercept = ybar
137        - beta
138            .iter()
139            .zip(xbar.iter())
140            .map(|(b, m)| b * m)
141            .sum::<f64>();
142    Ok(LassoModel {
143        coefficients: beta,
144        intercept,
145        lambda,
146        n_iter: iters,
147        converged,
148    })
149}
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154    use crate::solvers::learning::regression::linear;
155
156    #[test]
157    fn lambda_zero_approaches_ols() {
158        let x = [1.0, 5.0, 2.0, 4.0, 3.0, 3.0, 4.0, 2.0, 5.0, 1.0];
159        let y = [3.0, 4.0, 6.0, 8.0, 11.0];
160        let lasso = fit(&x, &y, 5, 2, 0.0, 5000, 1e-10).unwrap();
161        let ols = linear::fit(&x, &y, 5, 2, true).unwrap();
162        assert!((lasso.coefficients[0] - ols.coefficients[1]).abs() < 1e-4);
163        assert!((lasso.coefficients[1] - ols.coefficients[2]).abs() < 1e-4);
164        assert!((lasso.intercept - ols.coefficients[0]).abs() < 1e-4);
165    }
166
167    #[test]
168    fn large_penalty_zeros_all_coefficients() {
169        let x = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0];
170        let y = [2.0, 4.0, 6.0, 8.0, 10.0];
171        let m = fit(&x, &y, 5, 2, 1e6, 1000, 1e-9).unwrap();
172        assert_eq!(m.n_selected(), 0);
173        // Intercept falls back to the response mean.
174        assert!((m.intercept - 6.0).abs() < 1e-9);
175    }
176
177    #[test]
178    fn selects_the_relevant_predictor() {
179        // x1 drives y; x2 is pure noise → lasso should keep x1, zero x2.
180        let x = [1.0, 0.3, 2.0, -0.1, 3.0, 0.2, 4.0, -0.3, 5.0, 0.1, 6.0, 0.0];
181        let y = [2.0, 4.1, 5.9, 8.0, 10.1, 12.0]; // ≈ 2·x1
182        let m = fit(&x, &y, 6, 2, 1.0, 5000, 1e-10).unwrap();
183        assert!(m.converged);
184        assert!(
185            m.coefficients[0].abs() > 0.5,
186            "x1 should be selected: {}",
187            m.coefficients[0]
188        );
189        assert_eq!(m.coefficients[1], 0.0, "x2 (noise) should be zeroed");
190    }
191}