Bayesian Additive Regression Trees (BART) is a nonparametric Bayesian regression technique based on an ensemble of decision trees. It is part of the toolbox of many statisticians. The overall statistical quality of the regression is typically higher than other generic alternatives, and it requires less manual tuning, making it a good default choice. However, it is a niche method compared to natural competitors such as XGBoost, due to the longer running time, making sample sizes above 10000-100000 a nuisance. We present a GPU implementation of BART, up to 500x faster than the previous state of the art, making BART fast enough to be a viable option on large datasets, and showing that BART parallelizes better than its non-Bayesian counterparts. We also find that, to be as practical as tree boosting on large datasets, BART would need a scalable way to infer the number of trees, which we do not provide. Our implementation is available in the Python package bartz.
Figures & tables
Figure 1: Depiction and terminology of a decision tree. Adapted from Hill et al. (2020, fig. 1) .
Figure 2: Heap representation of a decision tree, with the maximum depth set to D=2 .
Figure 3: Left panel: Time to run an iteration (one sweep through all trees) of the algorithm vs. training set size n , comparing bartz with the previous fastest BART implementation ( dbarts ), XGBoost, and CatBoost, on CPU ( -M1pro ) and GPU ( -P5000 ). Gradient boosting requires only one iteration to produce a usable result, while BART requires O(1000) iterations, so the right panel shows the same data but with BART timings multiplied by an arbitrary factor 1000 to aid visual comparison of the lines. See Figures 5 and 6 for the complete results.
Figure 4: Test set mean squared error (MSE) ( left panel ) and coverage of 50% intervals on the latent mean ( right panel ) vs. training set size, comparing bartz with the most popular implementations of BART, to check they yield similar results. See Figures 7 and 8 for the full results.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Full version of Figure 3 , left panel. Time to run an iteration (one sweep through all trees) of the algorithm vs. training set size n , comparing bartz with the previous fastest BART implementation ( dbarts ), XGBoost, and CatBoost, for various settings of number of trees and number of predictors p , on CPU ( -M1pro ) and GPU ( -P5000 ). Take into account that gradient boosting requires only one iteration to produce a usable result, while BART requires O(1000) iterations. See Figure 6 for a version of this plot where the BART running time is multiplied by 1000.
Figure 6: Full version of Figure 3 , right panel. Time to run 1 iteration of XGBoost, CatBoost, or 1000 iterations of bartz , dbarts , vs. training set size n . This is the same data as Figure 5 .
Figure 7: Full version of Figure 4 , left panel. Test set mean squared error (MSE) vs. training set size n , comparing bartz with the most popular implementations of BART, to check they yield the same predictive performance, for various settings of number of trees and number of predictors p on data simulated as Equation 9 . The test set size is always 1000. The MSE is averaged over enough runs to reach a total training set size of at least 1000 for each point, capped at 10 runs. The data is re-generated independently for each method.
Figure 8: Full version of Figure 4 , right panel. Coverage of 50% credible intervals on the latent mean vs. training set size n , comparing bartz with the most popular implementations of BART, to check they yield the same predictive performance, for various settings of number of trees and number of predictors p on data simulated as Equation 9 . The test set size is always 1000. Coverage is averaged over enough runs to reach a total training set size of at least 1000 for each point, capped at 10 runs. The data is re-generated independently for each method.