Abstract
Additive regression trees are flexible non-parametric models and popular off-the-shelf tools for real-world non-linear regression. In application domains, such as bioinformatics, where there is also demand for probabilistic predictions with measures of uncertainty, the Bayesian additive regression trees (BART) model, introduced by Chipman et al. (2010), is increasingly popular. As data sets have grown in size, however, the standard Metropolis-Hastings algorithms used to perform inference in BART are proving inadequate. In particular, these Markov chains make local changes to the trees and suffer from slow mixing when the data are high-dimensional or the best fitting trees are more than a few layers deep. We present a novel sampler for BART based on the Particle Gibbs (PG) algorithm (Andrieu et al., 2010) and a top-down particle filtering algorithm for Bayesian decision trees (Lakshminarayanan et al., 2013). Rather than making local changes to individual trees, the PG sampler proposes a complete tree to fit the residual. Experiments show that the PG sampler outperforms existing samplers in many settings.
Introduction
Bayesian Additive Regression Trees (BART) represent a powerful class of non-parametric models for non-linear regression. By combining the flexibility of ensemble tree methods with a Bayesian framework, BART provides not only competitive predictive performance—often rivaling neural networks and random forests—but also robust uncertainty quantification. However, as datasets increase in dimensionality and complexity, the traditional inference methods for BART face significant scalability challenges.
The standard approach to fitting BART models relies on Markov Chain Monte Carlo (MCMC) using the "CGM" sampler. This algorithm explores the posterior distribution of tree structures through local Metropolis-Hastings moves, such as growing a branch, pruning a leaf, or swapping nodes. While effective for simpler problems, these local edits often lead to poor mixing in high-dimensional spaces or when the optimal trees are deep. The sampler can become trapped in local modes, resulting in inaccurate predictions and unreliable posterior estimates.
The PG-BART Framework
To address these limitations, we introduce PG-BART, a novel inference engine based on the Particle Gibbs (PG) framework. The core innovation of PG-BART is the shift from incremental, local tree modifications to "global" proposals that generate entire tree structures in a single step.
The algorithm utilizes Conditional Sequential Monte Carlo (CSMC) to propose a complete tree from scratch. This process follows a top-down approach, as illustrated in Figure 1.
In each iteration of the PG sampler, a set of candidate trees (particles) is generated by recursively splitting nodes based on the data. To maintain the validity of the MCMC chain, one particle is always "clamped" to the tree structure from the previous iteration. New particles are sampled according to their ability to fit the current residual—the portion of the target variable not yet explained by other trees in the BART ensemble. By integrating this PG sampler into the standard Bayesian backfitting framework, we replace inefficient local edit steps with a more holistic exploration of the tree space.
Experimental Evaluation
We evaluated the performance of PG-BART against standard samplers (CGM and GrowPrune) using a variety of synthetic and real-world benchmarks, including the synthetic Hypercube-$D$ dataset and real-world datasets such as CaliforniaHouses, YearPredictionMSD, and CTslices (384 features).
Key Results
The experimental results demonstrate that PG-BART significantly improves mixing and convergence speed, especially in challenging scenarios.
- Superior Mixing: On the synthetic Hypercube-7 dataset, the standard CGM sampler achieved an Effective Sample Size (ESS) of only 1.16, indicating it was essentially stuck. In contrast, PG-BART achieved an ESS of 422.96, a massive improvement in reliability.
- High-Dimensional Robustness: On the CTslices dataset, PG-BART's ESS was more than double that of the next best competitor (11.8 vs. 5.0), highlighting its effectiveness in navigating high-dimensional feature spaces.
- Convergence Speed: As shown in Figure 2, trace plots reveal that PG-BART (blue) converges to the correct log-likelihood and tree complexity much faster than CGM (black) or GrowPrune (red). While traditional methods often remain stuck at sub-optimal complexity levels for thousands of iterations, PG-BART quickly identifies the appropriate model structure.
Discussion and Conclusion
The primary insight of this work is that in complex posterior landscapes, building a new, high-quality tree from scratch is often more efficient than attempting to reach it through a sequence of local edits. While a single iteration of the Particle Gibbs sampler is computationally more expensive than a single local move, its superior exploration capabilities result in a much higher "ESS per second" for complex problems. PG-BART is particularly robust to the depth of the underlying true trees, providing a more accurate representation of the posterior than local samplers that may get trapped in shallow structures.
Summary updated