Skip to main content

qualia_core_db/solvers/learning/trees/
boosting.rs

1//! Gradient boosting for regression (ISL ch 8.2.3) — fit an additive ensemble of
2//! shallow CART trees, each trained on the residuals of the running prediction
3//! under squared-error loss (so the negative gradient *is* the residual). Predictions
4//! are `init + ν·Σ treeₘ(x)` with learning rate `ν`. Built on [`super::decision_tree`].
5
6use crate::solvers::learning::trees::decision_tree::{DecisionTree, TreeParams};
7use crate::solvers::learning::LearningError;
8use crate::solvers::statistics::descriptive::mean;
9
10/// A fitted gradient-boosting regressor.
11#[derive(Debug, Clone)]
12pub struct GradientBoosting {
13    init: f64,
14    trees: Vec<DecisionTree>,
15    learning_rate: f64,
16    p: usize,
17}
18
19impl GradientBoosting {
20    /// Fit `n_estimators` shallow trees by stage-wise residual fitting. `learning_rate`
21    /// (`ν`, typically 0.05–0.3) shrinks each tree's contribution. Fails closed on
22    /// shape mismatch / empty ensemble / non-positive learning rate.
23    pub fn fit_regressor(
24        x: &[f64],
25        y: &[f64],
26        n: usize,
27        p: usize,
28        n_estimators: usize,
29        learning_rate: f64,
30        params: TreeParams,
31    ) -> Result<Self, LearningError> {
32        if n == 0 || p == 0 || x.len() != n * p || y.len() != n {
33            return Err(LearningError::InvalidDimension);
34        }
35        if n_estimators == 0 || !(learning_rate > 0.0) {
36            return Err(LearningError::InsufficientData);
37        }
38
39        let init = mean(y).ok_or(LearningError::InsufficientData)?;
40        let mut pred = vec![init; n];
41        let mut residual = vec![0.0; n];
42        let mut trees = Vec::with_capacity(n_estimators);
43
44        for _ in 0..n_estimators {
45            for i in 0..n {
46                residual[i] = y[i] - pred[i]; // negative gradient of ½(y−F)²
47            }
48            let tree = DecisionTree::fit_regressor(x, &residual, n, p, params)?;
49            // Update the running prediction.
50            for i in 0..n {
51                pred[i] += learning_rate * tree.predict_row(&x[i * p..(i + 1) * p]);
52            }
53            trees.push(tree);
54        }
55
56        Ok(Self {
57            init,
58            trees,
59            learning_rate,
60            p,
61        })
62    }
63
64    /// Prediction for one feature row.
65    pub fn predict_row(&self, q: &[f64]) -> f64 {
66        self.init + self.learning_rate * self.trees.iter().map(|t| t.predict_row(q)).sum::<f64>()
67    }
68
69    /// Predictions for `m` rows of `x`.
70    pub fn predict(&self, x: &[f64], m: usize) -> Vec<f64> {
71        (0..m)
72            .map(|i| self.predict_row(&x[i * self.p..(i + 1) * self.p]))
73            .collect()
74    }
75
76    /// Estimator count.
77    pub fn n_estimators(&self) -> usize {
78        self.trees.len()
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use crate::solvers::learning::metrics::regression::{mse, r2_score};
86
87    #[test]
88    fn boosting_reduces_error_with_more_stages() {
89        // Nonlinear target; more boosting stages drive training error down.
90        let n = 50;
91        let x: Vec<f64> = (0..n).map(|i| i as f64 / 10.0).collect();
92        let y: Vec<f64> = x.iter().map(|&xi| (xi).sin() * 3.0 + 0.5 * xi).collect();
93        let params = TreeParams {
94            max_depth: 3,
95            ..TreeParams::default()
96        };
97        let few = GradientBoosting::fit_regressor(&x, &y, n, 1, 5, 0.1, params).unwrap();
98        let many = GradientBoosting::fit_regressor(&x, &y, n, 1, 200, 0.1, params).unwrap();
99        let mse_few = mse(&y, &few.predict(&x, n)).unwrap();
100        let mse_many = mse(&y, &many.predict(&x, n)).unwrap();
101        assert!(
102            mse_many < mse_few,
103            "more stages should fit better: {mse_many} !< {mse_few}"
104        );
105        // A well-trained ensemble explains most of the variance.
106        assert!(r2_score(&y, &many.predict(&x, n)).unwrap() > 0.9);
107    }
108
109    #[test]
110    fn single_stage_is_init_plus_one_tree() {
111        let x = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
112        let y = [1.0, 2.0, 1.0, 5.0, 6.0, 5.0];
113        let gb = GradientBoosting::fit_regressor(
114            &x,
115            &y,
116            6,
117            1,
118            1,
119            0.5,
120            TreeParams {
121                max_depth: 2,
122                ..TreeParams::default()
123            },
124        )
125        .unwrap();
126        assert_eq!(gb.n_estimators(), 1);
127        // Prediction is finite and within the data range envelope.
128        let p = gb.predict_row(&[3.5]);
129        assert!(p.is_finite());
130    }
131
132    #[test]
133    fn guards() {
134        assert_eq!(
135            GradientBoosting::fit_regressor(&[1.0], &[1.0], 1, 1, 0, 0.1, TreeParams::default())
136                .unwrap_err(),
137            LearningError::InsufficientData
138        );
139        assert_eq!(
140            GradientBoosting::fit_regressor(&[1.0], &[1.0], 1, 1, 10, 0.0, TreeParams::default())
141                .unwrap_err(),
142            LearningError::InsufficientData
143        );
144    }
145}