Ensembles: bagging, random forests and gradient boosting

Wisdom of crowds, with a formula

Suppose you have $B$ models whose predictions each have variance $\sigma^2$ and pairwise correlation $\rho$. The variance of their average is

Two lessons fall out immediately. The second term vanishes as $B\to\infty$, so averaging is free variance reduction. The first term does not vanish: if your models make correlated mistakes, no amount of averaging removes them. Ensembling is therefore a game of decorrelation. Numbers: with $\sigma^2=1$, $\rho=0.3$ and $B=100$, the ensemble variance is $0.3 + 0.7/100 = 0.307$ — a 3× reduction, capped by $\rho$. This is the bias–variance decomposition of 3.5 Evaluating models: metrics, validation and the bias–variance trade-off put to work: trees have low bias and huge variance, so they are the perfect raw material.

Bagging and random forests

Bagging (bootstrap aggregating) trains each model on a bootstrap sample: $n$ draws with replacement from the $n$ training points. Each bootstrap sample contains about $1-(1-1/n)^n \to 1-1/e \approx 63.2\%$ of the unique points; the other 36.8% are out-of-bag (OOB) and act as a free validation set for that tree. Averaging the predictions (or voting) reduces variance without touching bias.

Random forests add a second source of randomness to push $\rho$ down: at every split, only a random subset of $m$ features is considered — typically $m\approx\sqrt{d}$ for classification and $d/3$ for regression. Without this, every tree would grab the same dominant feature at the root and the trees would be highly correlated. Forests use deep, unpruned trees (low bias), hundreds of them (large $B$), and are remarkably hard to overfit by adding trees: more trees only lowers the $1/B$ term. The main knobs are $m$ (max_features) and min_samples_leaf.

Forests also give two kinds of feature importance: mean decrease in impurity (fast, biased) and permutation importance (shuffle a feature on OOB data, measure the drop) — prefer the latter (3.13 Feature engineering, data quality and data-centric ML).

Boosting: fit what is still wrong

Boosting builds an additive model sequentially,

where each $h_m$ is a small tree ("weak learner", depth 3–8) and $\nu\in(0,1]$ is the learning rate. At step $m$ we would like $h_m$ to minimize $\sum_i L\big(y_i,\,F_{m-1}(\mathbf{x}_i)+h(\mathbf{x}_i)\big)$. Friedman's insight: treat the vector of training predictions $F=(F(\mathbf{x}_1),\dots,F(\mathbf{x}_n))$ as the parameter and do gradient descent in function space. The negative gradient at the current model is the pseudo-residual

and we fit the tree $h_m$ to the targets $r_i^{(m)}$ (a regression tree, whatever the original task) and take a step $F_m = F_{m-1} + \nu h_m$.

Math check. For squared loss $L=\tfrac12(y-F)^2$ the pseudo-residual is $r_i = y_i - F_{m-1}(\mathbf{x}_i)$: the ordinary residual. "Fit a tree to the residuals" is literally a gradient step. For binary log loss with $p_i=\sigma(F_{m-1}(\mathbf{x}_i))$ the pseudo-residual is $r_i = y_i - p_i$ — the same form as the logistic-regression gradient in 3.3 Logistic regression and softmax classification.

Because every tree corrects the previous ensemble, boosting reduces bias (unlike bagging). It can overfit if you add too many trees, so the number of trees $M$ is chosen by early stopping on a validation set, and shrinkage $\nu$ (0.01–0.3) trades more trees for better generalization. Stochastic gradient boosting subsamples rows (and columns) per tree, which both speeds things up and decorrelates. AdaBoost, the original boosting algorithm, is the special case of exponential loss, where fitting the gradient becomes re-weighting misclassified points.

XGBoost, LightGBM and CatBoost

XGBoost (2016) replaced the first-order gradient step with a second-order Taylor expansion of the loss, giving every tree a closed-form objective. With $g_i = \partial_F L$ and $h_i = \partial_F^2 L$ at the current prediction, a tree $f$ with leaf weights $w_j$ is scored by

where $T$ is the number of leaves. Minimizing over the weights of leaf $j$ (with $G_j=\sum_{i\in j} g_i$, $H_j=\sum_{i\in j} h_i$) gives

The gain formula replaces Gini/entropy: splits are chosen by how much they reduce the regularized second-order loss, and $\gamma$, $\lambda$ are explicit regularizers. XGBoost also learns default directions for missing values and parallelizes split finding.

LightGBM (2017) made boosting fast on big data: histogram-based splits (bin each feature into ≈255 buckets), leaf-wise (best-first) growth instead of level-wise, gradient-based one-side sampling (keep large-gradient rows), and exclusive feature bundling for sparse features. CatBoost (2017) attacked target leakage in categorical encoding with ordered target statistics (each row's encoding uses only "earlier" rows) and ordered boosting, uses symmetric (oblivious) trees that are fast at inference, and has excellent defaults.

When tree ensembles beat deep learning

For typical tabular data — heterogeneous columns, tens to hundreds of thousands of rows, irregular target functions, uninformative features — gradient-boosted trees still beat neural networks on average (Grinsztajn et al., 2022): trees are robust to irrelevant features, naturally model sharp, axis-aligned interactions, and need no scaling or architecture search. Deep learning wins on raw perceptual data (images, audio, text) and whenever pretrained representations can be transferred (5.4 Transfer learning and training CNNs in practice, 7.5 Encoder-only: BERT and friends (and sentence embeddings)). The best of both: feed neural embeddings (of text columns, say) into a GBDT as features.

A practical tuning recipe: start with LightGBM or XGBoost defaults; set a small learning rate (0.03–0.1) and let early stopping choose the number of trees; then tune depth/number of leaves, min_child_weight (leaf size), row and column subsampling (0.7–0.9), and $\lambda$/$\alpha$ regularization with a quick random search. Always evaluate with the same cross-validation protocol as your baseline (3.5 Evaluating models: metrics, validation and the bias–variance trade-off).

Where this shows up later

• Cross-validated evaluation and leakage-safe pipelines — 3.5 Evaluating models: metrics, validation and the bias–variance trade-off, 3.13 Feature engineering, data quality and data-centric ML; the full tabular project — 3.14 Project: end-to-end tabular ML with scikit-learn.
• Boosting is gradient descent in function space; the parameter-space version with momentum and Adam is 4.5 Optimizers and learning-rate schedules.
• Averaging predictions returns as self-consistency voting in LLM decoding — 8.5 Decoding and sampling, model ensembling in evaluation — 8.7 Evaluating LLMs, and voting/parallelization patterns in agents — 10.5 Agentic workflow patterns; mixture-of-experts layers combine specialized sub-networks — 7.11 Mixture of Experts.