Boosting and Gradient-Boosted Trees

Definition A stagewise additive model predicts with a sum of simple functions that are added one stage at a time. After $M$ stages it has the form

where $F_0$ is a starting model, usually a constant, each $h_m$ is a function returned by a base learner and each $\beta_m$ is a real coefficient. Forward stagewise fitting builds the sum greedily for a chosen loss $L$ and training examples $(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)$. At stage $m$ the earlier terms are frozen, and only the new term $\beta h$ is chosen, to make the training loss

small, after which $F_m = F_{m-1} + \beta_m h_m$. Earlier terms are never refitted, which separates this from fitting all the terms jointly. Boosting methods are the learning algorithms that build such a sum in sequence, with each new term responding to the errors of the current model. Bagging, by contrast, fits its trees independently on bootstrap samples and averages them. In the gradient boosting of this page every coefficient equals a fixed learning rate, $\beta_m = \nu$, and the size of each correction sits in the leaf values of the tree $h_m$.

Definition A weak learner, or base learner, is a fitting procedure that returns a function from a restricted class $\mathcal{H}$. Typical classes are decision stumps, which are trees with one split and two leaves, and regression trees limited to a small depth $d$ or a small number of leaves. In the classical analysis of boosting algorithms for binary labels, a learner is weak in a precise sense if there is a fixed $\gamma > 0$ such that, for every weighting of the training examples, it returns a classifier with weighted error at most $\tfrac12 - \gamma$, so it is reliably a little better than guessing. In gradient boosting the word is used more loosely for a low-capacity learner, usually a shallow regression tree fitted by least squares. Each leaf of a tree of depth $d$ is described by at most $d$ split conditions, so the tree is a sum of terms that each depend on at most $d$ features, and so is any sum of such trees. A sum of stumps is therefore additive in the features, of the form $f_1(x_1) + \dots + f_p(x_p)$, with no interactions.

Definition Let the loss $L(y, F)$ be differentiable in the prediction or score $F$ for each target value $y$. At stage $m$ the negative gradient, or pseudo-residual, of training example $i$ is the negative derivative of its loss with respect to the prediction, evaluated at the current prediction,

The vector $(r_{1m}, \dots, r_{nm})$ is the negative gradient of the training loss $\sum_i L(y_i, F_i)$ with respect to the vector $(F_1, \dots, F_n)$ of training predictions, at the current predictions. Moving those predictions a short enough step along it lowers the training loss whenever it is not the zero vector. For the squared loss $L(y, F) = \tfrac12 (y - F)^2$ the derivative is $F - y$, so the pseudo-residual is the ordinary residual $y_i - F_{m-1}(\mathbf{x}_i)$. For binary labels $y \in \{0, 1\}$ and a log-odds score $F$ with probability $p = \sigma(F)$, the log loss

equals $-\ln p$ when $y = 1$ and $-\ln(1 - p)$ when $y = 0$. Its derivative is $\sigma(F) - y$, so the pseudo-residual is $y_i - \sigma\bigl(F_{m-1}(\mathbf{x}_i)\bigr)$, the label minus the current probability. For the absolute loss $\lvert y - F \rvert$ it is $\operatorname{sign}(y - F)$ wherever $y \ne F$, and the loss has no derivative where $y = F$.

Definition Gradient boosting with a differentiable loss $L$, a class $\mathcal{H}$ of regression trees, a learning rate $0 < \nu \le 1$ and a number of stages $M$ fits training examples $(\mathbf{x}_i, y_i)$, $i = 1, \dots, n$, in three steps.

1. Set $F_0$ to the constant $c$ that minimizes $\sum_i L(y_i, c)$. For squared error this is the mean of the targets, and for the log loss it is $\ln\bigl(\bar{y}/(1 - \bar{y})\bigr)$, where the share $\bar{y}$ of positive labels must lie strictly between $0$ and $1$.
2. For $m = 1, \dots, M$, compute the pseudo-residuals $r_{im}$ at the current predictions, fit a tree $h_m$ from $\mathcal{H}$ to the pairs $(\mathbf{x}_i, r_{im})$ by greedy least-squares splitting, and set $F_m = F_{m-1} + \nu h_m$.
3. Return $F_M$, and for the log loss also the probability estimate $\sigma\bigl(F_M(\mathbf{x})\bigr)$.

The tree is an approximation of the negative gradient that can be evaluated at any input. Many implementations then replace each leaf value by the constant that lowers the original loss most on the examples in that leaf, or use second derivatives of the loss, and stochastic gradient boosting fits each tree to a random subsample of the rows. Residual fitting is the squared-error case. With $L = \tfrac12 (y - F)^2$ the pseudo-residuals are the ordinary residuals, a least-squares tree predicts the mean residual in each leaf, and the leaf adjustment just described changes nothing. Fitting ordinary residuals under a loss whose negative gradient is not a multiple of the residual, such as the log loss or the absolute loss, is a different algorithm, not gradient boosting for that loss.

Definition Shrinkage multiplies each fitted correction by a learning rate $\nu$ with $0 < \nu \le 1$ before adding it, so that $F_m = F_{m-1} + \nu h_m$. The number of stages $M$ is the number of fitted trees in the sum. Together with the tree size, set by the depth, the number of leaves or the minimum leaf size, and any row subsampling, they are hyperparameters, chosen with validation data or with cross-validation inside the training data and never with the test set. For squared error with least-squares leaf values, the values of a tree at the training inputs are the orthogonal projection of the residual vector onto the span of the tree’s leaf indicator vectors, so the training sum of squared errors changes by

It never increases for $0 < \nu \le 1$, and it falls strictly whenever the new tree is not zero at every training input. The loss on validation data usually falls at first and can rise later, once the trees start to fit noise. Early stopping adds stages while monitoring the validation loss, often stops after a set number of stages without improvement, and keeps the stage count with the lowest validation loss.

Definition AdaBoost, short for adaptive boosting, is a boosting algorithm for binary labels $y_i \in \{-1, +1\}$. It starts with weights $w_i = 1/n$ and repeats three steps for $m = 1, \dots, M$.

1. Fit a classifier $h_m$ with values in $\{-1, +1\}$ to the weighted training data, and compute its weighted error $e_m$, the total weight of the examples with $h_m(\mathbf{x}_i) \ne y_i$.
2. Provided $0 < e_m < \tfrac12$, give it the vote weight $\alpha_m = \tfrac12 \ln\bigl((1 - e_m)/e_m\bigr) > 0$.
3. Multiply each weight by $e^{-\alpha_m y_i h_m(\mathbf{x}_i)}$, which is $e^{-\alpha_m}$ for a correct example and $e^{\alpha_m}$ for a mistake, and divide by the total so that the weights again sum to $1$.

The final classifier is the sign of $F_M(\mathbf{x}) = \sum_m \alpha_m h_m(\mathbf{x})$, with a stated rule for a score of exactly $0$. An error $e_m = 0$ means a classifier that is perfect on the training data, and $e_m \ge \tfrac12$ means no improvement over guessing, so the standard algorithm stops in both cases instead of putting them into the logarithm. After each update, the examples misclassified by $h_m$ hold total weight exactly $\tfrac12$. The training error of the final classifier, counting a score of $0$ as an error, is at most

and this bound goes to $0$ as stages are added when every $e_m \le \tfrac12 - \gamma$ for a fixed $\gamma > 0$. When each classifier minimizes the weighted error over its class, AdaBoost is forward stagewise fitting of the exponential loss $e^{-yF}$, and its weights are proportional to $e^{-y_i F_{m-1}(\mathbf{x}_i)}$, the size of that loss’s negative gradient at each example.