1use 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 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 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 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#[derive(Debug, Clone)]
119pub struct Bart {
120 draws: Vec<Vec<Tree>>, y_center: f64,
122 y_scale: f64,
123 p: usize,
124}
125
126fn 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 #[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 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 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 let mut tree_fit = vec![vec![0.0; n]; m];
175 let mut draws: Vec<Vec<Tree>> = Vec::new();
176
177 for it in 0..n_iter {
179 for j in 0..m {
180 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 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_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 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 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 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 pub fn n_draws(&self) -> usize {
250 self.draws.len()
251 }
252}
253
254fn 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 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 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]; let threshold = cut;
310 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; let log_trans = (n_grow / n_nog_new).ln(); let log_alpha = loglik_ratio + prior_ratio.ln() + log_trans;
337 if log_alpha >= 0.0 || rng.unit() < log_alpha.exp() {
338 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 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 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 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; 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 tree.nodes[nog].leaf = true;
407 compact(tree);
408 }
409 }
410}
411
412fn 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 }
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 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 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}