Bagging builds trees in parallel to cut variance. Boosting builds them in sequence to cut bias: each new tree focuses on what the ensemble got wrong so far. This chapter develops boosting from AdaBoost (reweight the mistakes) to the more general and powerful gradient boosting (fit the residuals — gradient descent in function space), the engine behind XGBoost, LightGBM, and CatBoost.

The boosting idea

Boosting combines many weak learners (typically shallow trees — “stumps” or depth-3 trees) into a strong one by adding them sequentially. Each new learner is trained to correct the errors of the current ensemble, and predictions accumulate: \[F_M(x) = \sum_{m=1}^M \nu\, h_m(x),\] where \(h_m\) is the \(m\)-th tree and \(\nu\) is a small learning rate (shrinkage). Unlike bagging’s independent trees, boosting’s trees are deeply dependent — order matters.

AdaBoost: reweight the hard cases

AdaBoost (Freund & Schapire, 1997) keeps a weight on each training example. Start uniform; fit a weak classifier; increase the weights of misclassified points and decrease the weights of correct ones; fit the next classifier on the reweighted data; repeat. Final prediction is a weighted vote, where more accurate learners get larger say (\(\alpha_m=\tfrac12\ln\frac{1-\text{err}_m}{\text{err}_m}\)). Each round literally pays more attention to the examples the ensemble keeps getting wrong.

Gradient boosting: fit the residuals

Gradient boosting (Friedman, 2001) generalizes boosting to any differentiable loss \(L(y,F)\) by viewing it as gradient descent in function space. At each step, compute the negative gradient of the loss with respect to the current predictions — the pseudo-residuals \(r_i = -\big[\partial L(y_i,F(x_i))/\partial F(x_i)\big]\) — then fit a regression tree to those residuals and add it (scaled by \(\nu\)): \[F_m(x) = F_{m-1}(x) + \nu\, h_m(x),\qquad h_m \approx \text{tree fit to } r_i.\] For squared-error loss the pseudo-residuals are just the ordinary residuals \(y_i-F_{m-1}(x_i)\), so gradient boosting literally fits the errors and walks the predictions downhill.

Squared-error regression. Start with the mean \(F_0=\bar y\). Round 1: residuals \(r_i=y_i-\bar y\); fit a small tree to them; update \(F_1=F_0+\nu h_1\). Round 2: new residuals \(y_i-F_1(x_i)\) are smaller; fit another tree; update. After \(M\) rounds the residuals (and training loss) shrink steadily. The learning rate \(\nu\) controls step size — small \(\nu\) with many trees generalizes best.

Regularization: learning rate, subsampling, depth

Boosting can overfit if over-trained, so it is regularized on several axes: a small learning rate \(\nu\) (0.01–0.1) takes cautious steps (more trees needed but better generalization — “shrinkage”); early stopping on a validation set picks the number of trees \(M\); stochastic gradient boosting fits each tree on a random subsample of rows (and columns), adding bagging-style variance reduction; and shallow trees (depth 3–8) keep each learner weak. The big three — \(\nu\), \(M\), depth — must be tuned together: halve \(\nu\) and you roughly double the \(M\) you need.

Boosting is more sensitive than random forests. (1) Adding trees can overfit — unlike forests, \(M\) is a real overfitting knob; use early stopping. (2) Noisy labels / outliers hurt: AdaBoost in particular keeps up-weighting mislabeled points and can chase them; robust losses (Huber) or gradient boosting help. (3) Tune \(\nu\) and \(M\) jointly, not separately. (4) Sequential = slower to train and not as trivially parallel as a forest (though modern libraries parallelize within each tree).

“Gradient descent in function space” is the conceptual bridge from boosting to deep learning: both minimize a differentiable loss by following negative gradients — boosting adds a tree per step, a neural net updates weights per step. The pseudo-residual trick (fit the next learner to the gradient of any loss) lets boosted trees optimize log-loss, Poisson, ranking, and quantile objectives, just as autodiff lets networks optimize arbitrary losses. Gradient-boosted trees are also routinely stacked with neural networks (their outputs as features, or vice versa) in winning tabular pipelines (Chapter [ch:treemlai]).

from sklearn.ensemble import GradientBoostingClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
X, y = make_classification(n_samples=3000, n_informative=8, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, random_state=0)
for lr in [0.5, 0.1, 0.02]:
    gb = GradientBoostingClassifier(learning_rate=lr, n_estimators=300,
                                    max_depth=3).fit(Xtr, ytr)
    print(f"lr={lr}: test acc={gb.score(Xte, yte):.3f}")  # small lr usually generalizes best

Chapter summary

  • Boosting adds weak learners sequentially, each correcting the ensemble’s errors — it reduces bias.

  • AdaBoost reweights misclassified points each round and takes a weighted vote.

  • Gradient boosting fits each tree to the negative-gradient (pseudo-residuals) of any differentiable loss — gradient descent in function space.

  • Regularize with small learning rate, early stopping, row/column subsampling, and shallow trees; tune \(\nu\) and \(M\) together.

  • Boosting can overfit (unlike forests) and is sensitive to noise — but tuned well it is the most accurate tabular method.