PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Regression Tree Ensembles that Adapt to Smoothness and Sparsity

Antonio Ricardo Linero, Yun Yang

arXiv:1707.09461v3stat.ME

TL;DR

Tree ensembles can be insufficiently smooth and vulnerable to high-dimensionality. The paper develops SBART, which uses sparsity-inducing soft decision trees within BART, and shows promising empirical performance alongside posterior contraction near minimax rates for sparse and additive functions, with adaptation to unknown smoothness and sparsity. The authors also identify model-support consistency as an open question.

  • Problem

    Bayesian tree-based regression models have limited smoothness, suffer from dimensionality problems, and have relatively little frequentist theory for large-sample behavior.

  • Method

    SBART embeds carefully designed soft decision trees and sparsity-inducing priors on splitting probabilities within the Bayesian additive regression trees framework.

  • Results

    SBART achieves minimax-optimal or near-minimax posterior contraction for sparse and additive functions in high dimensions while adapting to unknown smoothness and sparsity levels.

  • Takeaways & Limitations

    The framework offers a smoother, sparse Bayesian tree approach with theoretical support and minimal modifications to existing BART fitting strategies.

  • Takeaways & Limitations

    The paper identifies consistent estimation of the model support as an unresolved question.

Abstract

from arXiv · show

Ensembles of decision trees are a useful tool for obtaining for obtaining flexible estimates of regression functions. Examples of these methods include gradient boosted decision trees, random forests, and Bayesian CART. Two potential shortcomings of tree ensembles are their lack of smoothness and vulnerability to the curse of dimensionality. We show that these issues can be overcome by instead considering sparsity inducing soft decision trees in which the decisions are treated as probabilistic. We implement this in the context of the Bayesian additive regression trees framework, and illustrate its promising performance through testing on benchmark datasets. We provide strong theoretical support for our methodology by showing that the posterior distribution concentrates at the minimax rate (up-to a logarithmic factor) for sparse functions and functions with additive structures in the high-dimensional regime where the dimensionality of the covariate space is allowed to grow near exponentially in the sample size. Our method also adapts to the unknown smoothness and sparsity levels, and can be implemented by making minimal modifications to existing BART algorithms.

1 Introduction

The paper introduces SBART, an ensemble of sparsity-inducing soft decision trees designed to address the nonsmoothness and high-dimensional limitations of Bayesian tree models. It provides empirical and theoretical evidence that SBART adapts to smoothness, sparsity, and additive structure while retaining practical compatibility with BART.

  • Decision-tree regression estimators are piecewise constant, limiting adaptation to higher smoothness, while prediction performance deteriorates as dimensionality increases.
  • SBART replaces standard BART trees with carefully designed soft decision trees whose probabilistic decisions provide smoother building blocks.
  • Sparsity-inducing priors on splitting probabilities allow SBART to exploit structural sparsity when the regression function depends on d ≪ p predictors.
  • For α-Hölder sparse functions, SBART achieves minimax-optimal posterior contraction in high dimensions where p grows nearly exponentially in n.For general smooth functions, the rate is n^-α/(2α+p) up to logarithmic terms.
  • SBART also attains near-minimax contraction for additive structures and adapts without prior knowledge of smoothness, component count, or interaction degree.The additive setting can allow o(n^β) active predictors for some β ∈ (0,1), compared with at most o(log n) in the general sparse case.
  • The method extends Bayesian backfitting with minimal modifications, while its theory links sum-of-trees estimators to kernel-type estimators and includes fractional-posterior concentration results.

2 Soft Bayesian sum of trees models

The model replaces deterministic tree paths with probabilistic gating, allowing soft Bayesian tree ensembles to smooth across covariate regions while inducing sparsity. The resulting framework supports smooth function estimation, adaptive information sharing, and practical prior choices for tree bandwidths and predictor selection.

  • Prior specification and implementation: The default SBART prior combines tree branching, bandwidth, and sparsity-inducing predictor-selection priors without requiring users to specify the sparsity level.The predictor prior can also be extended to penalize groups of predictors.
  • Soft decision trees: Soft trees send each predictor through a probabilistic path, with branch bandwidths controlling decision sharpness from hard-tree behavior to a constant model.Each leaf contributes through path probabilities rather than a deterministic indicator, and its influence depends on local bandwidths.
  • Soft decision trees: Soft leaves have global influence, enabling the model to borrow information across covariate regions with data-learned local smoothing.The degree of smoothing is determined by local bandwidth parameters.
  • Smoothness adaptation: BART ensembles can resemble nowhere-differentiable functions and are heuristically limited to Hölder smoothness no greater than α = 1.This limitation follows from the stated behavior of the BART prior as the number of trees grows.
  • Smoothness adaptation: Soft tree fits are infinitely differentiable, use few parameters, and can approximate linear relationships even with one tree.In the illustrated comparisons, these fits have lower variance and negligible bias, while BART remains insufficiently smooth.
  • Prior specification and implementation: Quantile-normalizing predictors makes the prior invariant under monotone transformations, while routine tuning approximations such as PSIS-LOO and WBIC can be unreliable.The authors report that validation selected T = 10, which also minimized the root mean squared error, while reasonable baseline performance required no further tuning.

3 Theoretical results

The paper develops theoretical guarantees for SBART, studying posterior concentration under sparse and additive regression structures. Its results establish adaptive near-minimax behavior for unknown smoothness and sparsity, under stated prior and model conditions.

  • Posterior framework: The analysis studies posterior convergence for Gaussian regression with truth f0 on [0,1]^p, including sparse and additive structures.The framework assumes Yi = f0(Xi) + ϵi and analyzes fractional posteriors, with posterior consistency for the usual posterior under stronger prior conditions.
  • Posterior framework: Sharp sup-norm small-ball probabilities provide the key theoretical ingredient for prior concentration around f0.The authors derive these probabilities for a wide class of tree-based models and use them to establish contraction conditions.
  • Assumptions and scope: The theoretical results rely on assumptions governing the gating function, tree count, bandwidths, splitting proportions, leaf coefficients, and tree depths.The usual posterior achieves the same convergence rate only under extra technical prior conditions controlling effective support and sieve existence.
  • Approximation theory: Soft decision trees can approximate any smooth d-dimensional function with optimally balanced tree count and approximation error.The approximation uses at most poly(ε^-1) suitably rescaled logistic trees; the construction bounds tree complexity in terms of τ and ε.
  • Contraction rates: The posterior contraction rate adapts to the unknown smoothness level α without requiring α to be known in advance.The resulting rate is near-minimax up to logarithmic terms.
  • Contraction rates: For sparse additive truths, the contraction rate also adapts to the additive structure and the unknown smoothness of each component.Each additive component may depend on only d_v covariates, and the corresponding rate aggregates component-specific smoothness and dimensionality terms.

4 Illustrations

The illustrations compare SBART with other methods on prediction, variable selection, approximation, and benchmark datasets. Across these experiments, SBART performs strongly, retaining sparsity benefits while improving smooth-function estimation and often achieving the best benchmark performance.

  • Friedman’s example: SBART performs best among the considered methods in Friedman’s example and improves substantially over DART in both low- and high-noise settings.The comparison includes BART, DART, boosting, lasso, and random forests, with methods evaluated by average RMSE.
  • Friedman’s example: DART and SBART remain largely invariant to nuisance-predictor dimension, whereas random forests, BART-CV, and boosting errors increase in log p.The lasso remains stable as p increases but has poor performance.
  • Variable selection: SBART has uniformly better precision than DART across λ and generally detects smaller signal levels, with recall differences reaching about 10%.When the signal is sufficiently high, both methods consistently detect all relevant predictors.
  • Variable selection: As λ increases, DART’s RMSE degrades while SBART’s remains roughly constant.The authors attribute this to DART needing more branches to capture additional signal, whereas SBART can represent the effects with fewer parameters.
  • Non-smooth functions: Soft-tree ensembles can outperform hard-tree ensembles even for a step function with a jump at x1 = 0.5.Both methods capture the discontinuity, but SBART performs better away from it.
  • Locally smooth functions: For a localized Daubechies wavelet, SBART adapts to constant regions and fast oscillations, while BART shows artifacts and wider credible bands.Figure 8 compares raw data with SBART and BART fits using pointwise 95% posterior credible bands.
  • Benchmark datasets: SBART or SBART-CV attains the best performance on 8 out of 10 benchmark datasets.Performance is measured by root mean predictive error normalized by SBART-CV, with method ranks reported for each dataset.
  • Benchmark datasets: SBART substantially outperforms all other methods on tecator, while SBART-CV substantially improves over SBART only on hatco.The hatco result indicates that tuning the number of trees can matter for optimal performance, although default SBART works well for most datasets.

5 Discussion

The paper introduces SBART, a Bayesian sum-of-trees framework using soft decision trees and sparsity-inducing priors. It reports practical and theoretical improvements, while identifying support recovery and extensions beyond regression as future directions.

  • SBART combines soft decision trees with sparsity-inducing priors in a new Bayesian sum-of-trees framework.
  • The method achieves meaningful improvements over existing methods in simulated experiments and practice.
  • Posterior concentration results are near-optimal and adaptive over smoothness classes when f0 is sparse.
  • The paper focuses on nonparametric regression, although the methodology is described as extending straightforwardly to other settings such as binary classification.Binary classification can be addressed using a probit link and data augmentation.
  • Whether the model consistently estimates the true predictor support remains an open question for future research.The support sets are defined by predictors appearing in the ensemble and predictors on which f0 depends.

A Proof of Lemma 1

The proof of Lemma 1 proceeds in three stages: approximate smooth functions by kernel convolutions, discretize the convolution, and represent each kernel component with a soft decision tree.

  • Step 1: The proof first establishes error bounds for approximating the target function with a kernel convolution.
  • Step 2: A continuous multidimensional kernel convolution is approximated by a discrete sum using an extension of location-mixture approximation results.The argument generalizes prior Gaussian-kernel and density-estimation results to kernels satisfying Assumption G and general function estimation.
  • Step 3: Each kernel component is represented by a soft decision tree with at most 2d splits, created by splitting twice along every coordinate.
  • Step 2: The target function is decomposed into positive and negative parts so kernel-mixture approximation can handle bounded functions that may take negative values.
  • Combining the three stages yields the claimed soft decision-tree approximation result.

B Proof of Theorem 2

The proof of Theorem 2 constructs a soft-tree approximation using a hierarchical prior over tree structures, split coordinates, bandwidths, and leaf values, then bounds its complexity and approximation error.

  • The constructed approximation uses at most C τ^-d log^d(ε^-1) trees and has sup-norm error at most C(τ^α + ετ^-d).
  • All approximation splits are restricted to the first d coordinates, with at most 2d times the number of trees in total.
  • The prior is specified hierarchically through the number and topology of trees, split coordinates, bandwidths, and leaf parameters.
  • The proof controls perturbation error and prior concentration using hierarchical tree probabilities and the stated prior assumptions.
  • Choosing τ = (log^(d+1) n/n)^-1/(2α+d), δ = τ^α, and ε = τ^(d+α) gives the claimed result.

C Proof of Theorem 4

The proof of Theorem 4 extends the single-function concentration argument to additive components by approximating each component separately and combining the resulting soft-tree ensembles.

  • The argument uses the prior concentration bound for the additive structure together with Theorem 2 for each component.
  • The proof applies the single-component result to V approximating functions, each targeting one additive component of f0.
  • The resulting approximation combines component-specific ensembles while preserving the same sum-of-soft-trees prior structure.

Supplementary Material to Soft Bayesian Additive Regression Trees: Ensembles that Adapt to Smoothness

The supplementary material identifies Antonio R. Linero and Yun Yang as the paper’s authors.

  • The paper is authored by Antonio R. Linero.
  • Yun Yang is listed as a coauthor.
  • The author line contains both Antonio R. Linero and Yun Yang.

S.1 MCMC details

The MCMC details describe Metropolis-Hastings updates for tree structures and bandwidths, together with Gibbs or slice-sampling updates for variance, leaf-scale, and prior parameters.

  • Tree-structure updates: Birth proposals select a leaf, predictor, and nonredundant cut point before transitioning to a branched tree.
  • Tree-structure updates: Death proposals select a non-grandparent branch and delete its two child nodes.
  • Tree-structure updates: Change proposals select a non-grandparent branch, predictor, and cut point to modify an existing split.
  • Parameter updates: The algorithm updates σ−2 using a Gamma full conditional under a flat prior and proposes σµ through a conjugate Gamma-based strategy.
  • Parameter updates: The parameter a is updated by slice sampling after transforming it to ρ = a/(a + λa).

S.2 Results for the Usual Posterior

Under stronger prior conditions, the paper establishes posterior-convergence results for soft tree ensembles using sieve, entropy, and prior-mass arguments.

  • Prior conditions: The proof verifies posterior-convergence conditions under stronger assumptions on tree count, bandwidth, leaf values, and tree depth.
  • Posterior contraction: The resulting posterior contraction rate is controlled by max{εn, ¯εn} under the L2(Pn) norm.
  • Sieve construction: A sieve construction bounds model complexity through tree depth, total leaves, and the number of distinct splitting directions.
  • Entropy and prior mass: The covering-entropy bound scales with dmax log p and a term involving nε² and tree depth.
  • Entropy and prior mass: The complement probability is bounded by exponentially decreasing terms under the stated prior-tail conditions.

S.3 Timing Comparisons and Potential Improvements

The timing analysis identifies sufficient-statistics computation as the main bottleneck relative to BART, while noting caching, parallelization, and other design changes as possible improvements.

  • Runtime bottlenecks: The primary speed bottleneck relative to BART is computing the sufficient statistics (Ω, bµ).
  • Potential improvements: 66% decrease in likelihood evaluation time is achieved relative to the current implementation through caching and reduced evaluations.
  • Potential improvements: Likelihood computations required by SBART can be parallelized.
  • Timing comparisons: SoftBart is roughly half the speed of BayesTree on the bbb dataset under the reported timing comparison.
  • Timing comparisons: Further optimization is required for SoftBart to match dbarts, which is nearly as efficient as randomForest and xgboost.
Loading 1707.09461v3…