32  Boosting and Bayesian Additive Regression Trees

Random forests average many deep trees grown independently, which reduces variance. Boosting adds many small trees grown in sequence, each fitted to the errors left by those before it, which reduces bias. The fitted model is a sum of trees. Bayesian additive regression trees (BART) fit the same kind of model, a sum of small trees, by sampling from a posterior distribution instead of by sequential optimization. This chapter presents gradient boosting, its regularization, BART, and rule ensembles derived from boosted trees.

32.1 Additive models of trees

Both methods fit a model of the form

\[ f(x) = \sum_{m=1}^{M} T_m(x), \tag{32.1}\]

where each \(T_m\) is a small regression tree. The sum of \(M\) trees of depth \(d\) can represent interactions of up to \(d\) features, and, with many trees, smooth functions as sums of many small steps. Unlike the average of a random forest, the sum is not a combination of models that each predict the outcome: each tree contributes a small correction.

32.2 Gradient boosting

Forward stagewise fitting builds the sum one tree at a time, without changing the trees already fitted. For squared-error loss, each new tree is fitted to the current residuals, \(r_i = y_i - f_{m-1}(x_i)\), and added to the model with a small weight \(\nu\), the learning rate:

\[ f_m(x) = f_{m-1}(x) + \nu \, T_m(x) . \tag{32.2}\]

Gradient boosting generalizes this to any differentiable loss \(L\) (Friedman 2001). At each step, the tree is fitted to the negative gradient of the loss with respect to the current predictions, the pseudo-residuals

\[ r_i = -\left. \frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} \right|_{f = f_{m-1}}, \tag{32.3}\]

which for squared error are the ordinary residuals and for the log loss of a binary outcome are \(y_i - \hat p_i\). The procedure is gradient descent in the space of functions, with each tree approximating a step in the direction of steepest descent (AMDS: Gradient Descent). AdaBoost, the first widely used boosting algorithm, is equivalent to forward stagewise fitting with an exponential loss (Freund and Schapire 1997; Hastie et al. 2009).

Figure 32.1 shows gradient boosting with single-split trees, stumps, and learning rate 0.1, after 5, 50 and 500 rounds.

Figure 32.1: Gradient boosting of stumps with learning rate 0.1, after 5, 50 and 500 rounds, on 100 simulated cases.

After 5 rounds the model has captured little of the function; after 50 it follows its shape; after 500 it has begun to follow individual cases. Each round reduces the training error, and the number of rounds is the main control of complexity.

32.3 Regularization of boosting

Boosting overfits if run for too many rounds. Its hyperparameters control the rate and extent of fitting:

  • Number of rounds \(M\). Training error decreases with every round; validation error decreases and then increases. Early stopping ends fitting when the error on held-out cases has not improved for a number of rounds, and selects the round with the lowest validation error.
  • Learning rate \(\nu\). A small learning rate, such as 0.01 to 0.1, requires more rounds and typically gives lower test error than a large one with fewer rounds (Friedman 2001). \(\nu\) and \(M\) are chosen together.
  • Tree size, the number of leaves or the depth, sets the order of interactions each tree can represent. Small trees, with 4 to 32 leaves, are typical.
  • Subsampling of cases at each round, stochastic gradient boosting, reduces variance and computation (Friedman 2002); subsampling of features has the same effect as in random forests.
  • Penalties on the leaf values, \(L_1\) and \(L_2\), and minimum leaf sizes shrink each tree’s contribution.

Modern implementations, such as XGBoost (Chen and Guestrin 2016) and LightGBM (Ke et al. 2017), add second-order approximations of the loss, histogram-based split search, and native handling of missing values and categorical features. LightGBM grows each tree leaf-wise, splitting the leaf with the largest loss reduction rather than all leaves of a level, and limits tree size by the number of leaves.

32.4 Boosting and random forests

Table 32.1: Random forests and gradient boosting
Random forest Gradient boosting
Trees Deep, grown independently Small, grown sequentially
Combination Average Sum of shrunken corrections
Main effect on error Reduces variance Reduces bias, with variance controlled by \(\nu\) and \(M\)
Overfitting with more trees No Yes, without early stopping
Tuning required Little Learning rate, rounds, tree size

On tabular data, tuned gradient boosting is among the most accurate methods in benchmark studies (Grinsztajn et al. 2022).

32.5 Bayesian additive regression trees

BART models the outcome as a sum of \(m\) trees plus normal noise,

\[ y = \sum_{j=1}^{m} T_j(x) + \varepsilon, \qquad \varepsilon \sim N(0, \sigma^2), \tag{32.4}\]

and places prior distributions on the structure of each tree, its leaf values and \(\sigma^2\) (Chipman et al. 2010). The prior on structure makes a node at depth \(d\) split with probability \(\alpha(1 + d)^{-\beta}\), which favors small trees; the prior on leaf values shrinks each tree’s contribution toward zero, so that each tree explains a small part of the outcome. The posterior distribution is sampled by Markov chain Monte Carlo: a backfitting sampler updates one tree at a time given the residual of the others, by proposing to grow, prune or change it, and accepting the proposal with a probability determined by the posterior.

BART thus has the additive tree structure of boosting, and its regularization comes from the prior rather than from a learning rate and early stopping. The prediction is the average of the sampled sums of trees, and the spread of the samples is a posterior distribution of the regression function at each \(x\), from which credible intervals follow. The defaults of Chipman et al. (2010), \(m = 200\) trees, \(\alpha = 0.95\) and \(\beta = 2\), perform well without tuning in many problems. For binary outcomes, BART models the latent variable of a probit model. The grow-from-root algorithm of XBART fits the same model faster, and provides starting points for the MCMC (He et al. 2019; He and Hahn 2023).

32.6 Rule ensembles

Each path from the root of a tree to a node defines a rule, a conjunction of conditions such as “age ≥ 70 and serum creatinine ≥ 1.8”. RuleFit generates a large set of rules from the nodes of boosted trees, adds the original features as linear terms, and fits a lasso over rules and linear terms together (Friedman and Popescu 2008). The lasso selects a small subset. The result is a linear model whose terms are rules and features, which retains much of the accuracy of the ensemble in a form that lists the conditions it uses.

32.7 Summary

  • Gradient boosting builds a sum of small trees, each fitted to the negative gradient of the loss at the current model.
  • The learning rate and the number of rounds control complexity; early stopping on held-out data selects the number of rounds.
  • Boosting reduces bias; random forests reduce variance.
  • BART fits a sum of trees by posterior sampling, with priors that keep each tree small and its contribution shrunk, and quantifies uncertainty in the fitted function.
  • RuleFit converts boosted trees into a lasso over rules.

32.8 Further reading