Ensembles: forests and boosting

Neighbours, trees and ensemblesabout 10 minutes

If you average the guesses of many people about the weight of an ox, the average is often closer than nearly every individual guess (Francis Galton observed this at a country fair in 1906). The errors partly cancel. Ensembles apply the same idea to models.

Why averaging helps, precisely

Average $B$ models whose predictions each have variance $σ^{2}$ and pairwise correlation $ρ$ . The variance of the average is:

Var (\frac{1}{B} b = 1 \sum B f_{b}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}

Adding models only shrinks the second term. How correlated the models are sets a floor you can't average away.

With independent models ( $ρ = 0$ ) the variance falls like $1/ B$ . But models trained on the same data are correlated, and the $ρ σ^{2}$ term stays no matter how many you add. So the game is to make models that are individually good and different from each other.

Bagging and random forests

Bagging (bootstrap aggregating, Breiman 1996) trains each model on a bootstrap sample: $n$ examples drawn from the training set with replacement, so each model sees a slightly different dataset (about 63% of the unique examples). Averaging deep, unstable trees trained this way cuts their variance sharply.

Random forests (Breiman 2001) add one more source of difference: at every split, each tree may only consider a random subset of the features (often $d$ of them). This stops every tree from splitting on the same dominant feature and decorrelates them, lowering $ρ$ . Random forests are robust, need little tuning, and remain among the best off-the-shelf models for tabular data.

Boosting

Bagging builds models in parallel and averages them. Boosting builds them in sequence, each one fixing the mistakes of the ensemble so far. In gradient boosting (Friedman 2001), each new small tree is fitted to the residuals of the current ensemble (more generally, to the negative gradient of the loss), then added with a small weight, the learning rate:

F_{m} (x) = F_{m - 1} (x) + η h_{m} (x), h_{m} \approx - \frac{\partial L}{\partial F _{m - 1}}

That's gradient descent again, but in the space of functions: each tree is a step downhill. Bagging mainly reduces variance; boosting mainly reduces bias, and it can overfit if run too long, so the number of trees is tuned on validation data. Libraries like XGBoost, LightGBM and CatBoost implement it efficiently, and on tabular data (spreadsheets, databases) gradient-boosted trees still frequently beat deep learning.

try itedit the code and run it, nothing can break

python sleeps until you press run

Averaging decorrelated models (bagging, random forests) cuts variance; adding models that fix the current errors (boosting) cuts bias. Both are among the strongest tools for tabular data.

← Decision trees