Skip to main content

qualia_core_db/solvers/learning/trees/
bart.rs

1//! Bayesian Additive Regression Trees (ISL ch 8.2.4, Chipman-George-McCulloch 2010)
2//! — a sum-of-trees regression model `y = Σⱼ gⱼ(x) + ε` fit by **Bayesian
3//! backfitting MCMC**: each tree is updated in turn against the partial residual via
4//! a grow/prune Metropolis-Hastings step with conjugate-normal leaves, and the noise
5//! variance is drawn from its inverse-gamma full conditional.
6//!
7//! The trees are kept deliberately small by the depth prior `p_split(d) =
8//! α(1+d)^{−β}`, so the ensemble is a sum of weak learners (like boosting, but with
9//! a full posterior). Prediction is the posterior-mean over retained MCMC draws,
10//! giving a smooth fit with built-in uncertainty. Kernel-class `Divergent` (the MCMC).
11
12use crate::solvers::learning::LearningError;
13
14#[derive(Debug, Clone)]
15struct Node {
16    leaf: bool,
17    feature: usize,
18    threshold: f64,
19    left: usize,
20    right: usize,
21    depth: usize,
22    mu: f64,
23}
24
25#[derive(Debug, Clone)]
26struct Tree {
27    nodes: Vec<Node>,
28}
29
30impl Tree {
31    fn root() -> Self {
32        Self {
33            nodes: vec![Node {
34                leaf: true,
35                feature: 0,
36                threshold: 0.0,
37                left: 0,
38                right: 0,
39                depth: 0,
40                mu: 0.0,
41            }],
42        }
43    }
44    /// Index of the leaf a point falls into.
45    fn leaf_of(&self, x_row: &[f64]) -> usize {
46        let mut n = 0;
47        loop {
48            let nd = &self.nodes[n];
49            if nd.leaf {
50                return n;
51            }
52            n = if x_row[nd.feature] <= nd.threshold {
53                nd.left
54            } else {
55                nd.right
56            };
57        }
58    }
59    fn predict(&self, x_row: &[f64]) -> f64 {
60        self.nodes[self.leaf_of(x_row)].mu
61    }
62    fn leaves(&self) -> Vec<usize> {
63        (0..self.nodes.len())
64            .filter(|&i| self.nodes[i].leaf)
65            .collect()
66    }
67    /// "nog" nodes: internal nodes whose both children are leaves (prunable).
68    fn nog_nodes(&self) -> Vec<usize> {
69        (0..self.nodes.len())
70            .filter(|&i| {
71                !self.nodes[i].leaf
72                    && self.nodes[self.nodes[i].left].leaf
73                    && self.nodes[self.nodes[i].right].leaf
74            })
75            .collect()
76    }
77}
78
79struct Rng(u64);
80impl Rng {
81    fn unit(&mut self) -> f64 {
82        self.0 = self
83            .0
84            .wrapping_mul(6364136223846793005)
85            .wrapping_add(1442695040888963407);
86        ((self.0 >> 11) as f64) / ((1u64 << 53) as f64)
87    }
88    fn below(&mut self, b: usize) -> usize {
89        (self.unit() * b as f64) as usize % b.max(1)
90    }
91    fn gaussian(&mut self) -> f64 {
92        let u1 = self.unit().max(1e-12);
93        let u2 = self.unit();
94        (-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos()
95    }
96    /// Gamma(shape a > 0, scale 1) via Marsaglia-Tsang.
97    fn gamma(&mut self, a: f64) -> f64 {
98        if a < 1.0 {
99            return self.gamma(a + 1.0) * self.unit().max(1e-12).powf(1.0 / a);
100        }
101        let d = a - 1.0 / 3.0;
102        let c = 1.0 / (9.0 * d).sqrt();
103        loop {
104            let x = self.gaussian();
105            let v = (1.0 + c * x).powi(3);
106            if v <= 0.0 {
107                continue;
108            }
109            let u = self.unit();
110            if u.ln() < 0.5 * x * x + d - d * v + d * v.ln() {
111                return d * v;
112            }
113        }
114    }
115}
116
117/// A fitted BART model: the retained posterior draws (each a forest of trees).
118#[derive(Debug, Clone)]
119pub struct Bart {
120    draws: Vec<Vec<Tree>>, // retained MCMC samples, each a Vec of m trees
121    y_center: f64,
122    y_scale: f64,
123    p: usize,
124}
125
126/// Leaf marginal log-likelihood up to terms common across a tree partition: with
127/// residual sum `s` over `n` points, leaf prior `N(0, σμ²)`, noise `σ²`.
128fn leaf_loglik(s: f64, n: f64, sigma2: f64, sigma_mu2: f64) -> f64 {
129    let denom = sigma2 + n * sigma_mu2;
130    0.5 * (sigma2 / denom).ln() + (sigma_mu2 * s * s) / (2.0 * sigma2 * denom)
131}
132
133impl Bart {
134    /// Fit BART. `m` trees, `n_iter` MCMC sweeps with `burn_in` discarded. `k`
135    /// controls the leaf prior (≈ 2). Fails closed on shape mismatch / degenerate y.
136    #[allow(clippy::too_many_arguments)]
137    pub fn fit(
138        x: &[f64],
139        y: &[f64],
140        n: usize,
141        p: usize,
142        m: usize,
143        n_iter: usize,
144        burn_in: usize,
145        k: f64,
146        seed: u64,
147    ) -> Result<Self, LearningError> {
148        if n < 2 || p == 0 || x.len() != n * p || y.len() != n || m == 0 || n_iter <= burn_in {
149            return Err(LearningError::InvalidDimension);
150        }
151        // Scale y to [-0.5, 0.5].
152        let ymin = y.iter().cloned().fold(f64::INFINITY, f64::min);
153        let ymax = y.iter().cloned().fold(f64::NEG_INFINITY, f64::max);
154        let y_center = 0.5 * (ymin + ymax);
155        let y_scale = (ymax - ymin).max(1e-9);
156        let ys: Vec<f64> = y.iter().map(|&v| (v - y_center) / y_scale).collect();
157
158        let sigma_mu = 0.5 / (k * (m as f64).sqrt());
159        let sigma_mu2 = sigma_mu * sigma_mu;
160        // Noise prior InvGamma(ν/2, νλ/2); ν=3, λ from the scaled-y variance.
161        let nu = 3.0;
162        let ybar = ys.iter().sum::<f64>() / n as f64;
163        let var_y = ys.iter().map(|&v| (v - ybar).powi(2)).sum::<f64>() / n as f64;
164        let lambda = var_y.max(1e-6);
165        let mut sigma2 = var_y.max(1e-6);
166
167        let alpha = 0.95;
168        let beta = 2.0;
169        let p_split = |d: usize| alpha * (1.0 + d as f64).powf(-beta);
170
171        let mut rng = Rng(seed ^ 0x9E3779B97F4A7C15);
172        let mut trees: Vec<Tree> = (0..m).map(|_| Tree::root()).collect();
173        // Running fitted values per tree at the training points.
174        let mut tree_fit = vec![vec![0.0; n]; m];
175        let mut draws: Vec<Vec<Tree>> = Vec::new();
176
177        // Precompute per-point membership lazily each tree update.
178        for it in 0..n_iter {
179            for j in 0..m {
180                // Partial residual R = ys − Σ_{k≠j} fit_k.
181                let mut r = ys.clone();
182                for (kk, fitk) in tree_fit.iter().enumerate() {
183                    if kk != j {
184                        for i in 0..n {
185                            r[i] -= fitk[i];
186                        }
187                    }
188                }
189                // One MH step (grow or prune) on tree j against R.
190                mh_step(
191                    &mut trees[j],
192                    x,
193                    &r,
194                    n,
195                    p,
196                    sigma2,
197                    sigma_mu2,
198                    &p_split,
199                    &mut rng,
200                );
201                // Sample leaf μ's (conjugate normal) and recompute this tree's fit.
202                sample_leaves(&mut trees[j], x, &r, n, sigma2, sigma_mu2, &mut rng);
203                for i in 0..n {
204                    tree_fit[j][i] = trees[j].predict(&x[i * p..(i + 1) * p]);
205                }
206            }
207            // Sample σ² from its inverse-gamma full conditional.
208            let mut sse = 0.0;
209            for i in 0..n {
210                let f: f64 = (0..m).map(|j| tree_fit[j][i]).sum();
211                sse += (ys[i] - f).powi(2);
212            }
213            let shape = (nu + n as f64) / 2.0;
214            let rate = (nu * lambda + sse) / 2.0;
215            sigma2 = (rate / rng.gamma(shape)).max(1e-9);
216
217            if it >= burn_in {
218                draws.push(trees.clone());
219            }
220        }
221
222        Ok(Self {
223            draws,
224            y_center,
225            y_scale,
226            p,
227        })
228    }
229
230    /// Posterior-mean prediction for one row (in the original y units).
231    pub fn predict_row(&self, x_row: &[f64]) -> f64 {
232        let mut acc = 0.0;
233        for forest in &self.draws {
234            let f: f64 = forest.iter().map(|t| t.predict(x_row)).sum();
235            acc += f;
236        }
237        let mean_scaled = acc / self.draws.len().max(1) as f64;
238        mean_scaled * self.y_scale + self.y_center
239    }
240
241    /// BART predictions.
242    pub fn predict(&self, x: &[f64], n: usize) -> Vec<f64> {
243        (0..n)
244            .map(|i| self.predict_row(&x[i * self.p..(i + 1) * self.p]))
245            .collect()
246    }
247
248    /// Posterior draw count.
249    pub fn n_draws(&self) -> usize {
250        self.draws.len()
251    }
252}
253
254/// Residual sum + count of points falling into each leaf of `tree`.
255fn leaf_stats(
256    tree: &Tree,
257    x: &[f64],
258    r: &[f64],
259    n: usize,
260    p: usize,
261) -> std::collections::HashMap<usize, (f64, f64)> {
262    let mut m: std::collections::HashMap<usize, (f64, f64)> = std::collections::HashMap::new();
263    for i in 0..n {
264        let l = tree.leaf_of(&x[i * p..(i + 1) * p]);
265        let e = m.entry(l).or_insert((0.0, 0.0));
266        e.0 += r[i];
267        e.1 += 1.0;
268    }
269    m
270}
271
272#[allow(clippy::too_many_arguments)]
273fn mh_step(
274    tree: &mut Tree,
275    x: &[f64],
276    r: &[f64],
277    n: usize,
278    p: usize,
279    sigma2: f64,
280    sigma_mu2: f64,
281    p_split: &impl Fn(usize) -> f64,
282    rng: &mut Rng,
283) {
284    let nogs = tree.nog_nodes();
285    let do_grow = nogs.is_empty() || rng.unit() < 0.5;
286
287    if do_grow {
288        let leaves = tree.leaves();
289        if leaves.is_empty() {
290            return;
291        }
292        let leaf = leaves[rng.below(leaves.len())];
293        // Gather this leaf's point indices.
294        let idx: Vec<usize> = (0..n)
295            .filter(|&i| tree.leaf_of(&x[i * p..(i + 1) * p]) == leaf)
296            .collect();
297        if idx.len() < 2 {
298            return;
299        }
300        // Pick a feature with ≥2 distinct values, and a threshold between two values.
301        let feature = rng.below(p);
302        let mut vals: Vec<f64> = idx.iter().map(|&i| x[i * p + feature]).collect();
303        vals.sort_by(|a, b| a.partial_cmp(b).unwrap_or(core::cmp::Ordering::Equal));
304        vals.dedup();
305        if vals.len() < 2 {
306            return;
307        }
308        let cut = vals[1 + rng.below(vals.len() - 1) - 1]; // a value with something above it
309        let threshold = cut;
310        // Split sums.
311        let (mut sl, mut nl, mut sr, mut nr) = (0.0, 0.0, 0.0, 0.0);
312        let mut s = 0.0;
313        for &i in &idx {
314            let v = r[i];
315            s += v;
316            if x[i * p + feature] <= threshold {
317                sl += v;
318                nl += 1.0;
319            } else {
320                sr += v;
321                nr += 1.0;
322            }
323        }
324        if nl < 1.0 || nr < 1.0 {
325            return;
326        }
327        let d = tree.nodes[leaf].depth;
328        let loglik_ratio = leaf_loglik(sl, nl, sigma2, sigma_mu2)
329            + leaf_loglik(sr, nr, sigma2, sigma_mu2)
330            - leaf_loglik(s, nl + nr, sigma2, sigma_mu2);
331        let ps = p_split(d);
332        let prior_ratio = (ps * (1.0 - p_split(d + 1)).powi(2) / (1.0 - ps)).max(1e-300);
333        let n_grow = leaves.len() as f64;
334        let n_nog_new = (tree.nog_nodes().len() + 1) as f64; // this leaf becomes a nog
335        let log_trans = (n_grow / n_nog_new).ln(); // P_prune=P_grow
336        let log_alpha = loglik_ratio + prior_ratio.ln() + log_trans;
337        if log_alpha >= 0.0 || rng.unit() < log_alpha.exp() {
338            // Perform the grow.
339            let li = tree.nodes.len();
340            let ri = li + 1;
341            let depth = d + 1;
342            tree.nodes.push(Node {
343                leaf: true,
344                feature: 0,
345                threshold: 0.0,
346                left: 0,
347                right: 0,
348                depth,
349                mu: 0.0,
350            });
351            tree.nodes.push(Node {
352                leaf: true,
353                feature: 0,
354                threshold: 0.0,
355                left: 0,
356                right: 0,
357                depth,
358                mu: 0.0,
359            });
360            let nd = &mut tree.nodes[leaf];
361            nd.leaf = false;
362            nd.feature = feature;
363            nd.threshold = threshold;
364            nd.left = li;
365            nd.right = ri;
366        }
367    } else {
368        // Prune a random nog node.
369        let nog = nogs[rng.below(nogs.len())];
370        let (lc, rc) = (tree.nodes[nog].left, tree.nodes[nog].right);
371        let idx: Vec<usize> = (0..n)
372            .filter(|&i| {
373                // points reaching `nog` then either child
374                let leaf = tree.leaf_of(&x[i * p..(i + 1) * p]);
375                leaf == lc || leaf == rc
376            })
377            .collect();
378        let (mut sl, mut nl, mut sr, mut nr) = (0.0, 0.0, 0.0, 0.0);
379        for &i in &idx {
380            let leaf = tree.leaf_of(&x[i * p..(i + 1) * p]);
381            if leaf == lc {
382                sl += r[i];
383                nl += 1.0;
384            } else {
385                sr += r[i];
386                nr += 1.0;
387            }
388        }
389        if nl < 1.0 || nr < 1.0 {
390            return;
391        }
392        let d = tree.nodes[nog].depth;
393        // Reverse of grow: ratio is the reciprocal.
394        let loglik_ratio = leaf_loglik(sl + sr, nl + nr, sigma2, sigma_mu2)
395            - leaf_loglik(sl, nl, sigma2, sigma_mu2)
396            - leaf_loglik(sr, nr, sigma2, sigma_mu2);
397        let ps = p_split(d);
398        let prior_ratio = ((1.0 - ps) / (ps * (1.0 - p_split(d + 1)).powi(2))).max(1e-300);
399        let n_nog = nogs.len() as f64;
400        let n_leaves_after = (tree.leaves().len() - 1) as f64; // two leaves → one
401        let log_trans = (n_nog / n_leaves_after).ln();
402        let log_alpha = loglik_ratio + prior_ratio.ln() + log_trans;
403        if log_alpha >= 0.0 || rng.unit() < log_alpha.exp() {
404            // Collapse `nog` to a leaf (children become dead but harmless; we
405            // rebuild a compact tree to keep indices valid).
406            tree.nodes[nog].leaf = true;
407            compact(tree);
408        }
409    }
410}
411
412/// Rebuild the tree dropping unreachable nodes (after a prune) so child indices
413/// stay valid.
414fn compact(tree: &mut Tree) {
415    let mut new_nodes = Vec::new();
416    let mut map = std::collections::HashMap::new();
417    fn visit(
418        old: usize,
419        src: &[Node],
420        new_nodes: &mut Vec<Node>,
421        map: &mut std::collections::HashMap<usize, usize>,
422    ) -> usize {
423        let id = new_nodes.len();
424        map.insert(old, id);
425        let mut nd = src[old].clone();
426        new_nodes.push(nd.clone());
427        if !src[old].leaf {
428            let l = visit(src[old].left, src, new_nodes, map);
429            let r = visit(src[old].right, src, new_nodes, map);
430            new_nodes[id].left = l;
431            new_nodes[id].right = r;
432        }
433        let _ = &mut nd;
434        id
435    }
436    visit(0, &tree.nodes, &mut new_nodes, &mut map);
437    tree.nodes = new_nodes;
438}
439
440fn sample_leaves(
441    tree: &mut Tree,
442    x: &[f64],
443    r: &[f64],
444    n: usize,
445    sigma2: f64,
446    sigma_mu2: f64,
447    rng: &mut Rng,
448) {
449    let p = x.len() / n;
450    let stats = leaf_stats(tree, x, r, n, p);
451    for (leaf, (s, cnt)) in stats {
452        let prec = cnt / sigma2 + 1.0 / sigma_mu2;
453        let mean = (s / sigma2) / prec;
454        let sd = (1.0 / prec).sqrt();
455        tree.nodes[leaf].mu = mean + sd * rng.gaussian();
456    }
457    // Leaves with no points keep μ = 0.
458}
459
460#[cfg(test)]
461mod tests {
462    use super::*;
463    use crate::solvers::learning::metrics::regression::r2_score;
464
465    #[test]
466    fn fits_a_nonlinear_function() {
467        // y = sin(x) over [0, 2π]; BART's sum-of-trees should track it well.
468        let n = 60;
469        let x: Vec<f64> = (0..n).map(|i| i as f64 * 0.1).collect();
470        let y: Vec<f64> = x.iter().map(|&xi| xi.sin()).collect();
471        let bart = Bart::fit(&x, &y, n, 1, 40, 250, 100, 2.0, 1).unwrap();
472        let preds = bart.predict(&x, n);
473        let r2 = r2_score(&y, &preds).unwrap();
474        assert!(r2 > 0.85, "BART R^2 too low: {r2}");
475        assert!(bart.n_draws() == 150);
476    }
477
478    #[test]
479    fn fits_a_two_feature_surface() {
480        // y depends on both features (a step in each).
481        let n = 80;
482        let mut x = vec![0.0; n * 2];
483        let mut y = vec![0.0; n];
484        for i in 0..n {
485            let a = (i % 8) as f64;
486            let b = (i / 8) as f64;
487            x[i * 2] = a;
488            x[i * 2 + 1] = b;
489            y[i] = if a > 3.5 { 2.0 } else { 0.0 } + if b > 4.5 { 1.0 } else { 0.0 };
490        }
491        let bart = Bart::fit(&x, &y, n, 2, 40, 200, 80, 2.0, 7).unwrap();
492        let r2 = r2_score(&y, &bart.predict(&x, n)).unwrap();
493        assert!(r2 > 0.8, "BART R^2 {r2}");
494    }
495
496    #[test]
497    fn guards() {
498        assert_eq!(
499            Bart::fit(&[1.0], &[1.0], 1, 1, 10, 20, 10, 2.0, 0).unwrap_err(),
500            LearningError::InvalidDimension
501        );
502    }
503}