Two hundred points are scattered on the unit square and labeled by which side of the diagonal $x_1 + x_2 = 1$ they fall on (an example after Hastie, Tibshirani and Friedman, 2009, Fig. 8.12). A decision stump, a tree with a single split, can only draw a horizontal or vertical line, so the best it can do here is a horizontal line a little above the middle of the square, which misclassifies a quarter of new points (test error 0.258 on 10,000 of them). Averaging 400 stumps fitted to bootstrap samples, as Bagging does, hardly helps (0.247): every bootstrap sample leads to nearly the same line, and an average of nearly identical horizontal lines is still a horizontal line. A stump is wrong here because of bias, not variance, and averaging cannot remove bias.
Boosting combines stumps differently. It fits them one after another, each to a version of the data that emphasizes the points the previous ones got wrong, and adds them up with weights. With 400 stumps, AdaBoost, the best-known boosting algorithm, builds a staircase that follows the diagonal and misclassifies 4.2% of the test points.
This article works AdaBoost by hand, derives it from a loss function, generalizes it to gradient boosting, and measures the settings that matter in practice. The overview in Introduction to Ensemble Models places boosting beside bagging and stacking.
From weak learners to a strong one
Boosting began as a question in computational learning theory. A weak learner is a method guaranteed only to do slightly better than random guessing on any distribution of training cases; a strong learner can reach any desired accuracy. Freund and Schapire (1997, §4) recount that Schapire had shown that any weak learner can be converted, or "boosted", into a strong one, and that Freund had then found a much more efficient method, boost-by-majority. Both work by calling the weak learner repeatedly, each time on a different distribution over the training cases that puts more weight on the hard ones, and combining the results. Boost-by-majority had a practical drawback: it needed to know in advance how much better than chance the weak learner would be. Freund and Schapire's new algorithm adjusted to the errors the weak learner actually made, so they called it AdaBoost, for adaptive boosting.
AdaBoost
Code the two classes as $y = +1$ and $y = -1$. AdaBoost keeps a weight $w_i$ on each of the $n$ training cases, starting with $w_i = 1/n$, and repeats, for $m = 1, 2, \dots, M$:
- Fit a classifier $G_m(x)$, with values $\pm 1$, to the training data using the weights $w_i$.
- Compute its weighted error rate, $\text{err}_m = \sum_i w_i\, I(y_i \ne G_m(x_i)) \big/ \sum_i w_i$.
- Compute its coefficient, $\beta_m = \frac{1}{2} \ln\bigl[(1 - \text{err}_m)/\text{err}_m\bigr]$.
- Multiply the weight of each misclassified case by $e^{\beta_m}$ and of each correctly classified case by $e^{-\beta_m}$, then divide all weights by their sum.
The final classifier is the sign of the weighted sum $F(x) = \sum_{m=1}^{M} \beta_m G_m(x)$. A classifier with error rate near 0 gets a large coefficient, one with error near one half a coefficient near 0, and the weights shift toward the cases the latest classifier missed. This is the form derived below. Freund and Schapire (1997) state it differently, shrinking the weights of correctly classified cases by $\text{err}_m / (1 - \text{err}_m)$ and leaving the others alone, and Hastie, Tibshirani and Friedman (2009, Algorithm 10.1) use the coefficient $2\beta_m$; both give the same weights after normalization and the same classifier.
The weak learner has to accept weights. A decision tree does, by using weighted counts in its split criterion. A method that cannot use weights can be given a sample drawn from the training cases with probabilities $w_i$ instead (Freund and Schapire, 1997, §4.1).
AdaBoost by hand
Ten points lie on a line at $x = 1, 2, \dots, 10$, with labels $+ + + - - + + + - -$. No single threshold separates them: the classes alternate in four runs. The weak learner is a stump that chooses a threshold $t$ and predicts one class for $x \le t$ and the other for $x > t$, whichever choice has the smallest weighted error. (This constructed example has no data behind it; its numbers are computed by the article's script.)
Round 1. All weights are 0.1. The best stump predicts $+$ for $x \le 8.5$ and $-$ above. It misclassifies points 4 and 5, so $\text{err}_1 = 0.2$ and $\beta_1 = \frac{1}{2}\ln(0.8/0.2) = \frac{1}{2}\ln 4 = 0.6931$. The two misclassified weights are multiplied by $e^{0.6931} = 2$ and the other eight by $e^{-0.6931} = 0.5$, giving 0.2 and 0.05; these add to $2 \times 0.2 + 8 \times 0.05 = 0.8$, and dividing by 0.8 gives new weights of 0.25 for points 4 and 5 and 0.0625 for the rest. Points 4 and 5 now carry half the total weight.
Round 2. On the new weights, the best stump predicts $+$ for $x \le 3.5$ and $-$ above. It gets 4 and 5 right and misclassifies points 6, 7 and 8, whose weights add to $3 \times 0.0625 = 0.1875$, so $\text{err}_2 = 0.1875$ and $\beta_2 = 0.7332$. After reweighting, points 1 to 3, 9 and 10 have weight 0.0385, points 4 and 5 have 0.1538, and points 6 to 8 have 0.1667.
Round 3. The best stump now predicts $-$ for $x \le 5.5$ and $+$ above. It misclassifies points 1, 2, 3, 9 and 10, with total weight $5 \times 0.0385 = 0.1923$, so $\beta_3 = 0.7175$.
The combined score, $F(x) = 0.6931\,G_1(x) + 0.7332\,G_2(x) + 0.7175\,G_3(x)$, takes four values:
| Points | $G_1$ | $G_2$ | $G_3$ | $F(x)$ | Label |
|---|---|---|---|---|---|
| 1, 2, 3 | + | + | − | 0.7088 | + |
| 4, 5 | + | − | − | −0.7576 | − |
| 6, 7, 8 | + | − | + | 0.6775 | + |
| 9, 10 | − | − | + | −0.7088 | − |
Its sign is right for all ten points, although each stump alone gets at least two wrong. Two details are worth noticing. After round 2 the combined classifier is worse than after round 1: $F = 0.6931 - 0.7332 = -0.0400$ for points 6 to 8, which flips them to the wrong side, and the training error rises from 0.2 to 0.3. AdaBoost does not promise that each round lowers the error; the third stump repairs the damage. And after every reweighting, the stump just fitted has a weighted error of exactly one half on the new weights: in round 1, points 4 and 5 carry 0.5 of the weight. Freund and Schapire (1997, §4.1) note this property: the update "exactly removes the advantage of the last hypothesis", so the next round cannot simply repeat the last stump.
AdaBoost as stagewise fitting of an additive model
AdaBoost was designed from learning theory, but Hastie et al. (2009, §10.4) show that it also follows from a statistical recipe. The final score $F(x) = \sum_m \beta_m G_m(x)$ is an additive model: a sum of simple functions with coefficients. Fitting all the terms at once to minimize a loss over the training data is hard. Forward stagewise additive modeling (Hastie et al., 2009, Algorithm 10.2) adds one term at a time and never revisits earlier terms: starting from $f_0(x) = 0$, at step $m$ choose the coefficient $\beta$ and the function $G$ to minimize
$$\sum_{i=1}^{n} L\bigl(y_i,\, f_{m-1}(x_i) + \beta\, G(x_i)\bigr),$$
and set $f_m(x) = f_{m-1}(x) + \beta_m G_m(x)$. AdaBoost is this recipe with the exponential loss
$$L(y, f) = e^{-y f}.$$
The product $y f$ is the margin of Loss Functions for Classification: positive when the sign of $f$ is right, negative when it is wrong. The exponential loss is small for large positive margins and grows exponentially for negative ones.
The weights appear. With the exponential loss, the criterion at step $m$ is
$$\sum_{i} e^{-y_i (f_{m-1}(x_i) + \beta G(x_i))} = \sum_{i} w_i^{(m)} e^{-\beta y_i G(x_i)}, \qquad w_i^{(m)} = e^{-y_i f_{m-1}(x_i)}.$$
The factor $w_i^{(m)}$ depends only on the model so far, not on $\beta$ or $G$, so it acts as a weight on case $i$. It is large for cases the current model gets wrong by a wide margin.
The classifier minimizes the weighted error. For a classifier with values $\pm 1$, $y_i G(x_i)$ is $+1$ when $G$ is right and $-1$ when it is wrong. Splitting the sum into the two groups, and writing $W = \sum_i w_i^{(m)}$ and $\text{err}$ for the weighted error rate of $G$,
$$\sum_i w_i^{(m)} e^{-\beta y_i G(x_i)} = e^{-\beta} \sum_{y_i = G(x_i)} w_i^{(m)} + e^{\beta} \sum_{y_i \ne G(x_i)} w_i^{(m)} = W \bigl[ e^{-\beta} (1 - \text{err}) + e^{\beta}\, \text{err} \bigr].$$
For any $\beta > 0$, this is $W\bigl[e^{-\beta} + (e^{\beta} - e^{-\beta})\,\text{err}\bigr]$, increasing in err, so the best $G$ is the one with the smallest weighted error: step 1 of AdaBoost (Hastie et al., 2009, eqs. 10.10 to 10.11).
The coefficient. Setting the derivative with respect to $\beta$ to zero, $-e^{-\beta}(1 - \text{err}) + e^{\beta}\,\text{err} = 0$, so $e^{2\beta} = (1 - \text{err})/\text{err}$ and
$$\beta_m = \frac{1}{2} \ln \frac{1 - \text{err}_m}{\text{err}_m},$$
step 3 (Hastie et al., 2009, eq. 10.12). It is positive whenever the classifier beats chance, $\text{err}_m < 1/2$.
The reweighting. The next step's weights are $w_i^{(m+1)} = e^{-y_i f_m(x_i)} = w_i^{(m)} e^{-\beta_m y_i G_m(x_i)}$: multiplied by $e^{\beta_m}$ for misclassified cases and $e^{-\beta_m}$ for the others, step 4. Only the relative weights matter, so the weights can be normalized to sum to 1 at each step. With normalized weights the sum after the update is
$$Z_m = e^{\beta_m}\, \text{err}_m + e^{-\beta_m} (1 - \text{err}_m) = 2\sqrt{\text{err}_m (1 - \text{err}_m)},$$
and dividing by it gives each misclassified case its old weight times $1/(2\,\text{err}_m)$ and each correctly classified case its old weight times $1/(2(1 - \text{err}_m))$. The misclassified cases then hold $\text{err}_m / (2\,\text{err}_m) = 1/2$ of the total weight, which is why the last classifier always has weighted error one half. In round 1 of the example, $Z_1 = 2\sqrt{0.2 \times 0.8} = 0.8$, the sum computed there.
Hastie et al. (2009, §10.5) note that this equivalence was discovered about five years after AdaBoost was introduced. It changed how boosting is understood: not as a clever reweighting scheme, but as a greedy fit of an additive model to a particular loss, which suggests replacing the loss.
What AdaBoost estimates, and its training error
The score estimates half the log-odds. Over all functions $f$, the expected exponential loss given $x$ is minimized by
$$f^*(x) = \frac{1}{2} \ln \frac{\Pr(y = 1 \mid x)}{\Pr(y = -1 \mid x)}$$
(Hastie et al., 2009, eq. 10.16), so AdaBoost's score estimates half the log-odds that the case belongs to class $+1$, and $\Pr(y = 1 \mid x)$ can be estimated as $1/(1 + e^{-2F(x)})$. The logistic loss of logistic regression has the same minimizer up to the factor of one half, which is why the two losses lead to the same classification rule in the limit of infinite data (Loss Functions for Classification).
The training error falls exponentially. A case is misclassified exactly when its margin $y_i F(x_i)$ is negative, and then $e^{-y_i F(x_i)} \ge 1$; when it is classified correctly, $e^{-y_i F(x_i)} > 0$. So the training error is at most the average exponential loss. Unrolling the normalized updates, the average exponential loss after $M$ rounds is exactly the product of the normalizers, giving
$$\frac{1}{n}\sum_{i=1}^{n} I\bigl(y_i F(x_i) < 0\bigr) \;\le\; \frac{1}{n}\sum_{i=1}^{n} e^{-y_i F(x_i)} \;=\; \prod_{m=1}^{M} 2\sqrt{\text{err}_m (1 - \text{err}_m)},$$
the bound of Freund and Schapire (1997, Theorem 6). If every round's classifier beats chance by some margin $\gamma$, with $\text{err}_m \le 1/2 - \gamma$, each factor is at most $\sqrt{1 - 4\gamma^2} \le e^{-2\gamma^2}$, and the training error falls at least as fast as $e^{-2M\gamma^2}$. In the example the factors are 0.8, 0.7806 and 0.7882, and the average exponential loss after three rounds is their product, 0.4922, which the training error, 0, respects.
On the diagonal data the bound behaves the same way over many more rounds. The average exponential loss equals the product of the normalizers at every round, and the training error is always below it.
| Stumps | 1 | 5 | 10 | 20 | 50 | 100 | 200 | 400 |
|---|---|---|---|---|---|---|---|---|
| Training error | 0.215 | 0.145 | 0.050 | 0.020 | 0.005 | 0 | 0 | 0 |
| Exponential loss | 0.8216 | 0.4455 | 0.3376 | 0.2226 | 0.1141 | 0.0598 | 0.0280 | 0.0086 |
| Test error | 0.2585 | 0.1512 | 0.0729 | 0.0449 | 0.0345 | 0.0301 | 0.0390 | 0.0416 |
The training error first reaches 0 at round 53, returns briefly to small positive values until round 80 and stays at 0 after that, but the exponential loss keeps falling, because AdaBoost keeps widening the margins of cases already classified correctly; Hastie et al. (2009, §10.4) show the same pattern on a simulated problem.
Does boosting overfit?
A bound on the training error says nothing about new data, and boosting can overfit. On the diagonal data the test error is lowest, 0.0290, at round 95, and rises to 0.0416 by 400 rounds as the staircase starts to bend around individual training points. The rise is slow, and much smaller than the gain from the first 50 rounds.
Mislabeled data are a harder test. Twenty training sets of 200 points were each boosted twice, once with clean labels and once with 20% of the labels flipped, and tested against clean labels. With clean labels the median test error levels off at about 0.053 and stays there through 1,000 rounds. With flipped labels it reaches its minimum, 0.146, at 69 rounds and then climbs, to 0.199 at 1,000. The cause is the exponential loss. A mislabeled point sits on the wrong side of the true boundary, so a good classifier gives it a large negative margin, and its weight $e^{-y_i F(x_i)}$ grows exponentially; later stumps are increasingly spent on fitting the flipped labels. Hastie et al. (2009, §10.6) make this argument: the exponential loss concentrates far more influence on badly misclassified cases than the logistic loss, which spreads it more evenly, and the performance of AdaBoost has been observed to "dramatically degrade" when training labels are wrong. Gradient boosting with the logistic loss, described next, was designed in part to mitigate this (§10.7). With data like these, the number of rounds is a tuning parameter, chosen on validation data or by Cross-Validation.
Gradient boosting
Forward stagewise fitting works with any loss, but only the exponential loss gives a step as simple as AdaBoost's. Friedman (2001) found a general method by viewing the fitting as numerical optimization. Think of the model's predictions at the $n$ training cases, $\mathbf{f} = (f(x_1), \dots, f(x_n))$, as the parameters to be optimized, and the training loss $\sum_i L(y_i, f(x_i))$ as the function to minimize. Steepest descent would move $\mathbf{f}$ in the direction of the negative gradient, whose components are
$$r_{im} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f = f_{m-1}}, \qquad i = 1, \dots, n.$$
These pseudo-residuals say how each training prediction should change to reduce the loss fastest. But the gradient is defined only at the training cases, and a model must predict elsewhere. Friedman's solution is to fit a regression tree to the pseudo-residuals by least squares, the tree being the member of the base-learner family that points most nearly in the direction of the negative gradient, and to take a step along it. For trees he also chose each leaf's step separately, a line search within each leaf (Friedman, 2001, §4.3). In the form Hastie et al. (2009, Algorithm 10.3) give for trees, the algorithm is:
- Start from the best constant, $f_0(x) = \arg\min_c \sum_i L(y_i, c)$. Then, for $m = 1$ to $M$, repeat steps 2 to 5.
- Compute the pseudo-residuals $r_{im}$ at the current model $f_{m-1}$.
- Fit a regression tree with $J$ leaves to the $r_{im}$, giving leaf regions $R_{1m}, \dots, R_{Jm}$.
- In each leaf, choose the value $\gamma_{jm} = \arg\min_\gamma \sum_{x_i \in R_{jm}} L(y_i, f_{m-1}(x_i) + \gamma)$.
- Update $f_m(x) = f_{m-1}(x) + \nu \sum_{j} \gamma_{jm} I(x \in R_{jm})$.
The factor $\nu$ is the learning rate, discussed below. Friedman's algorithms take $\nu = 1$ at first, and he introduced the learning rate later in the same paper (§5). The loss enters only through the pseudo-residuals and the leaf values:
- Squared error, $L = \frac{1}{2}(y - f)^2$: the pseudo-residual is the ordinary residual $y_i - f_{m-1}(x_i)$, and each leaf's value is the mean residual in it. Gradient boosting fits trees to the residuals of the model so far.
- Absolute error, $L = |y - f|$: the pseudo-residual is the sign of the residual, and each leaf's value is the median residual in it, which makes the fit resistant to outliers (Loss Functions for Regression).
- Logistic loss for classification: the pseudo-residual is $y_i - p_i$, the difference between the 0/1 outcome and the current predicted probability.
So gradient boosting extends boosting to regression, to robust losses and to probability estimation, with a regression tree as the weak learner throughout (Friedman, 2001; Hastie et al., 2009, Table 10.2).
Gradient boosting by hand
Regression Trees grew a tree by hand on the first eight patients of the diabetes study (Efron, Hastie, Johnstone and Tibshirani, 2004), predicting disease progression from BMI and the serum measurement S5. The same eight patients show gradient boosting with squared error, stumps on either input, and a learning rate of $\nu = 0.5$:
| Patient | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| BMI | 32.1 | 21.6 | 30.5 | 25.3 | 23.0 | 22.6 | 22.0 | 26.2 |
| S5 | 4.8598 | 3.8918 | 4.6728 | 4.8903 | 4.2905 | 4.1897 | 3.9512 | 4.2485 |
| Progression $y$ | 151 | 75 | 141 | 206 | 135 | 97 | 138 | 63 |
Start. The best constant under squared error is the mean, $f_0 = 125.75$. The training residual sum of squares (RSS) is 14,885.50.
Round 1. The residuals $y_i - 125.75$ are 25.25, −50.75, 15.25, 80.25, 9.25, −28.75, 12.25 and −62.75. The best stump for them is the root split found in Regression Trees, S5 at most 4.2695, which puts patients 2, 6, 7 and 8 on the left with mean residual −32.5 and the other four on the right with mean residual +32.5. Half of each step is added: predictions become $125.75 - 16.25 = 109.5$ on the left and $125.75 + 16.25 = 142$ on the right. The RSS falls to 8,548.00. With $\nu = 1$ the step would be the whole tree, and the RSS would be 6,435.50.
Round 2. The new residuals are 9, −34.5, −1, 64, −7, −12.5, 28.5 and −46.5. Patient 4, with residual 64, is now the largest error, and the best stump isolates it: S5 at most 4.87505, with mean residual 64 on the right and −9.1429 for the other seven. Half of each is added, and the RSS falls to 5,037.14.
Round 3. The residuals are 13.57, −29.93, 3.57, 32.00, −2.43, −7.93, 33.07 and −41.93. The best stump splits at S5 at most 4.7663, separating patients 1 and 4 (mean residual 22.7857) from the rest (−7.5952). After the update the predictions are 148.82 for patient 1, 185.39 for patient 4, 133.63 for patients 3 and 5, and 101.13 for patients 2, 6, 7 and 8, and the RSS is 3,998.77. scikit-learn's GradientBoostingRegressor with the same settings gives the same eight predictions.
Each round fits the current errors, not the original outcomes, and each takes only half a step. The model creeps toward the data rather than jumping to it. If the rounds continue, it gets there: after 10 rounds the RSS is 1,553.81, after 50 it is 35.79, and after 200 it is 0. Given enough rounds, boosting fits eight patients exactly, noise included, which is why the number of rounds has to be limited.
Shrinkage: the learning rate and the number of trees
Friedman (2001, §5) found that scaling each update by a learning rate $0 < \nu \le 1$ improved predictions considerably, more than limiting the number of trees alone. Shrinkage introduces a trade-off: a smaller $\nu$ needs more trees to reach the same fit, so the two must be chosen together. In his simulations smaller values of $\nu$ gave lower test error, with diminishing returns below about 0.125, and required correspondingly more trees. Hastie et al. (2009, §10.12.1) give the practical rule that has followed: set $\nu$ small, below 0.1, and choose the number of trees by early stopping on validation data. The price is computation, since the number of trees, and with it the cost, grows as $\nu$ falls.
The trade-off can be measured on Friedman's (1991) first test problem, used throughout this topic: ten inputs uniform on $[0, 1]$, five of them irrelevant, and
$$y = 10 \sin(\pi x_1 x_2) + 20 (x_3 - 0.5)^2 + 10 x_4 + 5 x_5 + \varepsilon, \qquad \varepsilon \sim N(0, 1).$$
Thirty training sets of 500 cases were drawn (seed 11), and gradient boosting with squared error and trees of depth 3 was run on each with five learning rates. The test error at 2,000 test points, including the noise variance of 1, was recorded after every tree.
| Learning rate $\nu$ | Best number of trees | Test MSE there | Best per run, median (IQR) | Test MSE at the last tree |
|---|---|---|---|---|
| 1 | 8 | 6.334 | 6.125 (5.584 to 6.527) | 7.314 (1,000 trees) |
| 0.5 | 38 | 3.550 | 3.516 (3.358 to 3.730) | 3.619 (1,000) |
| 0.1 | 349 | 2.524 | 2.522 (2.462 to 2.615) | 2.559 (2,000) |
| 0.05 | 919 | 2.526 | 2.520 (2.448 to 2.576) | 2.532 (3,000) |
| 0.01 | 3,467 | 2.522 | 2.518 (2.424 to 2.584) | 2.527 (5,000) |
The second and third columns are read from the median curve over the 30 runs; the fourth gives the median and interquartile range of each run's own best test error. A random forest of 500 trees ($m = 7$) on the same training sets has a median test error of 4.473, and a single fully grown tree 10.442.
The table shows Friedman's pattern. Without shrinkage, boosting overfits after 8 trees, and its best error, 6.334, is worse than the random forest's. Halving the step size gets to 3.550. A learning rate of 0.1 reaches 2.524, and smaller rates reach essentially the same error, 2.52, with 3 and 10 times as many trees. Small learning rates also make the number of trees less critical: at $\nu = 0.01$ the error at 5,000 trees, 2.527, is barely above the minimum. Friedman (2001, §5) observed that the reason shrinkage helps so much was not clear, and noted that shrinking each step is not the same as shrinking the final model, which in his experiments helped only marginally.
The other main setting is the size of the trees. A tree with $d$ splits can involve at most $d$ inputs in each term it adds, so the depth limits the order of interactions the boosted model can represent (James, Witten, Hastie and Tibshirani, 2021, §8.2.3). With stumps, $d = 1$, the model is a sum of functions of one input each, an additive model; Stacking shows boosted stumps failing on the interaction in Friedman's problem that depth-3 trees capture. James et al. (2021, §8.2.3) list the three tuning parameters of boosted trees as the number of trees, the learning rate and the number of splits, and note that boosting, unlike bagging and random forests, can overfit if the number of trees is too large, "although this overfitting tends to occur slowly if at all". A further refinement, fitting each tree to a random half of the cases, is described by Hastie et al. (2009, §10.12.2) as both faster and often more accurate.
Boosting on real data
On the diabetes data, with the 10-fold cross-validation folds of Multiple Linear Regression and a learning rate of 0.05, the cross-validated $R^2$ depends on the number of trees and their depth:
| Tree depth | 50 trees | 100 | 200 | 300 | 500 | 1,000 | Best (trees) |
|---|---|---|---|---|---|---|---|
| 1 (stumps) | 0.396 | 0.439 | 0.448 | 0.449 | 0.443 | 0.432 | 0.449 (246) |
| 2 | 0.447 | 0.458 | 0.447 | 0.428 | 0.397 | 0.344 | 0.459 (106) |
| 3 | 0.447 | 0.442 | 0.409 | 0.390 | 0.354 | 0.314 | 0.450 (70) |
Deeper trees reach their best sooner and then overfit faster: with 1,000 trees, depth 3 has fallen to 0.314 while stumps still score 0.432. At their best the three are within 0.01 of each other and within 0.02 of the random forest (0.443; Random Forests), and all fall short of least squares on the ten inputs, 0.484. These data appear close to linear, and with 442 patients the flexible methods tried in this collection find little beyond a linear model. The best values in the table were picked with the test folds in view, so they are optimistic. Choosing the number of trees inside each training fold, by early stopping on a fifth of the fold, gives honest $R^2$ values of 0.424, 0.420 and 0.414 for depths 1, 2 and 3, lower both because the choice is made without the test fold and because each model is fitted to only four fifths of its training fold.
On the breast cancer data (Wolberg, Mangasarian, Street and Street, 1993), with the stratified folds of Random Forests, AdaBoost with stumps reaches a cross-validated accuracy of 0.975 with 100 stumps and 0.977 with 500, against 0.961 for a random forest and 0.923 for a single tree, and the same as logistic regression (0.977; Bagging). Gradient boosting with trees of depth 2, a learning rate of 0.05 and early stopping reaches 0.960.
Boosting and bagging compared
| Bagging | Boosting | |
|---|---|---|
| Members fitted | independently, in parallel | in sequence, each depending on the last |
| Data each member sees | a bootstrap sample | all cases, reweighted (AdaBoost) or with residuals as targets (gradient boosting) |
| Typical members | deep trees: low bias, high variance | stumps or small trees: high bias, low variance |
| Combination | plain average or vote | weighted sum |
| Mainly reduces | variance | bias, though it also reduces variance |
| More members | never overfits (error settles) | can overfit, usually slowly |
| Noisy labels | robust | sensitive, especially with the exponential loss |
| Main settings | number of members | number of trees, learning rate, tree size |
The two are often presented as opposites, bagging for variance and boosting for bias, and the diagonal example shows the clearest case, where only boosting can help. The difference is less sharp in practice. Hastie et al. (2009, §10.1) argue that the resemblance between boosting and bagging-style committees is "at best superficial": boosting is a way of fitting an additive model, and it can reduce variance as well as bias. On Friedman's problem with 500 training cases, boosted depth-3 trees beat the random forest by a wide margin, 2.52 against 4.47, and still reach about 2.53 to 2.56 at the last tree for learning rates of 0.1 and below, so the gap does not depend on choosing the number of trees with the test data in view. That is one smooth simulated problem. On the diabetes and breast cancer data above, boosting and the random forest are within 0.02 of each other. A random forest needs little tuning and tolerates noisy labels; a boosted model needs its number of trees, learning rate and tree size chosen, and on Friedman's problem that tuning paid off.
In Python
import numpy as np
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingRegressor
from sklearn.tree import DecisionTreeClassifier
# AdaBoost with stumps (the default base model)
ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=400, random_state=0)
# Gradient boosting on Friedman's problem
rng = np.random.default_rng(11)
X = rng.random((500, 10))
y = (10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2
+ 10 * X[:, 3] + 5 * X[:, 4] + rng.normal(0, 1, 500))
gb = GradientBoostingRegressor(n_estimators=3000, learning_rate=0.05, max_depth=3,
n_iter_no_change=20, validation_fraction=0.2, random_state=0)
gb.fit(X, y)
print(gb.n_estimators_) # number of trees kept by early stopping
AdaBoostClassifier implements the algorithm above for two or more classes (the multiclass extension is called SAMME); its default base model is a stump, and its learning_rate multiplies each coefficient, as $\nu$ does in gradient boosting. Older tutorials show algorithm="SAMME.R", a variant using class probabilities; it has been removed from recent versions of scikit-learn. GradientBoostingRegressor and GradientBoostingClassifier implement gradient boosting with loss (squared error by default for regression, the logistic loss for classification), learning_rate (default 0.1), n_estimators (default 100), max_depth (default 3) and subsample for fitting each tree to a random fraction of the cases. Setting n_iter_no_change holds out validation_fraction of the training data and stops adding trees when the validation loss stops improving, and staged_predict returns the predictions after each tree, which is how the curves in this article were drawn. For large datasets, HistGradientBoostingRegressor and HistGradientBoostingClassifier bin the inputs first and are much faster; the scikit-learn documentation describes them as inspired by LightGBM. The numbers in this article are computed by tools/experiments/data-science/boosting.py in the site's repository.
References
- Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. record · 12 pages
- Freund, Y., and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139. Section and theorem numbers and quotations follow the authors' preprint of December 19, 1996. record · 2 pages
- Friedman, J. H. (1991). Multivariate adaptive regression splines. The Annals of Statistics, 19(1), 1–67. record · 4 pages
- Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5), 1189–1232. Section numbers follow the author's preprint (IMS 1999 Reitz Lecture, dated February 24, 1999, modified April 19, 2001). record · 2 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
- Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages