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 a need for uncertainty quantification, Bayesian Additive Regression Trees (BART) are often preferred. However, standard inference methods for BART frequently struggle to "mix"—meaning they get stuck in local configurations—when dealing with high-dimensional data or deep tree structures. This paper introduces PG-BART, a novel inference method that uses Particle Gibbs to propose entire trees at once rather than making tiny local edits, significantly improving the efficiency and accuracy of the model in complex settings.
Introduction: The Mixing Problem in BART
Bayesian Additive Regression Trees (BART) have become a staple in the machine learning toolkit for non-linear regression, particularly when uncertainty measures like credible intervals are required. The standard approach to posterior inference in BART relies on Metropolis-Hastings Markov Chain Monte Carlo (MCMC). This "engine" explores the vast space of possible tree structures by making small, incremental changes: growing a branch, pruning a leaf, or swapping internal nodes.
While effective for simple problems, these local moves become a significant bottleneck as datasets grow in complexity. In high-dimensional spaces or when the underlying function requires deep trees, the sampler often becomes trapped in local modes. It finds it difficult to "undo" a series of moves to explore a better region of the tree space, leading to poor mixing. Consequently, the algorithm may require an impractical number of iterations to converge to a reliable posterior distribution, or worse, provide a biased view of uncertainty.
Methods: Proposing Whole Trees via Particle Gibbs
To overcome the limitations of local-move samplers, the authors propose PG-BART, which replaces the standard Metropolis-Hastings step with a Particle Gibbs (PG) framework. The core idea is to propose an entire tree structure in a single step, rather than incrementally editing one.
Top-Down Particle Filtering
The algorithm utilizes Sequential Monte Carlo (SMC) to grow a "cloud" of candidate trees from the root down. At each step of the SMC process, particles (representing partial trees) are extended by choosing split variables and thresholds.
Conditional SMC and Backfitting
To maintain the validity of the MCMC chain, PG-BART employs "Conditional SMC." In each iteration, one particle is "clamped" to the tree structure from the previous iteration, while all other particles are sampled anew. This ensures that the sampler targets the correct posterior distribution. At the end of an SMC pass, a single tree is sampled from the particle cloud based on its likelihood weight relative to the current residuals.
This PG sampler is integrated into the standard Bayesian backfitting framework. In an ensemble of $m$ trees, each tree is updated sequentially by fitting the residuals left by the other trees. By allowing for "whole-tree" jumps, PG-BART can escape local optima that would trap standard samplers for thousands of iterations.
Experimental Setup and Datasets
The performance of PG-BART was benchmarked against standard samplers, including the Chipman, George, and McCulloch (CGM) sampler and the GrowPrune sampler, across several datasets:
- Hypercube-D (Synthetic): A dataset designed to test tree depth. Labels are generated based on the vertices of a $D$-dimensional hypercube, requiring a tree with $2^D$ leaves to model correctly.
- CaliforniaHouses: A medium-dimensional real-world dataset ($D=6$).
- YearPredictionMSD: A high-dimensional dataset ($D=90$).
- CTslices: A very high-dimensional dataset ($D=384$).
Key Results: Efficiency and Convergence
The primary advantage of PG-BART is its superior mixing and faster convergence, especially in high-dimensional settings.
Superior Mixing
On the synthetic Hypercube-7 dataset, the standard CGM sampler's Effective Sample Size (ESS) was nearly zero (1.16), indicating it was essentially stuck. In contrast, PG-BART maintained a robust ESS of 422.96. Similar results were observed on the high-dimensional CTslices dataset, where PG-BART achieved an ESS of 11.838, significantly outperforming CGM (2.511) and GrowPrune (5.025).
Convergence Speed
Trace plots of log-likelihood and the number of leaves demonstrate that PG-BART reaches the high-probability regions of the posterior much faster than its competitors.
As shown in the figures, standard samplers often get "stuck" overestimating or underestimating tree complexity (Mean # leaves) for long periods. PG-BART's ability to re-imagine the tree from scratch every iteration allows it to find the optimal complexity and achieve lower Training and Test MSE more rapidly.
Conclusion and Future Directions
PG-BART represents a significant step forward for Bayesian non-parametric regression. By leveraging Particle Gibbs, it bypasses the "local traps" of traditional MCMC, providing more reliable posterior samples in complex, high-dimensional regimes.
While the per-iteration computational cost of PG-BART is higher due to the particle filtering step, the gain in sample quality (ESS) often results in a lower total time to convergence. Future work may explore even more advanced SMC techniques, such as backward simulation or ancestral sampling, to further enhance mixing. Additionally, extending this framework to classification and non-Gaussian likelihood models remains a promising avenue for research.
Summary updated