Random forests, gradient boosting and XGBoost, then the honest comparison of two models

Bagging: why an average of trees has less variance

If you train many trees on slightly different copies of the data and average them, the wobble of each tree partly cancels out, as long as the trees do not all make the same mistakes.

The expected squared error of a model splits into noise, squared bias and variance. A deep, unpruned tree has a small bias, because it follows the data closely, and a large variance: remove a few rows and the first split changes, and with it the whole tree. Breiman (1996) called such procedures unstable and showed that they are precisely the ones that gain from averaging. An average keeps the bias of its members and only works on the variance.

To get many trees from one data set, bagging (bootstrap aggregating) uses the bootstrap of Efron (1979): draw $n$ rows with replacement from the $n$ training rows, train a deep tree on the draw, repeat $B$ times and average the predictions. A given row is missed by one draw with probability $1 - 1/n$, so by all $n$ draws with probability $(1 - 1/n)^n$, which tends to $e^{-1}$.

On the 18,000 training rows of the course, each draw therefore holds about 11,378 distinct rows, and the remaining 36.8 % are out of bag for that tree. The key formula of the section is the variance of an average of $B$ trees, each of variance $\sigma^2$, with pairwise correlation $\rho$ (Hastie, Tibshirani and Friedman, 2009, equation 15.1).

The proof is a counting argument: the variance of a sum is the sum of all covariances, there are $B$ diagonal terms worth $\sigma^2$ and $B(B-1)$ cross terms worth $\rho\sigma^2$, and everything is divided by $B^2$. The second term fades as trees are added; the first, $\rho\sigma^2$, is a floor that no number of trees can move.

Check for ten trees and $\rho = 0.3$, using the count: ten diagonal terms and ninety cross terms give $(10 + 90 \times 0.3)/100 = 0.37$, the same as $0.3 + 0.7/10$. Going from 100 to 1,000 trees buys 0.006 of variance; bringing $\rho$ from 0.3 down to 0.1 would buy 0.2. The lesson for practice: decorrelate first.

Back to contents.

Random forests: decorrelate the trees

A random forest is bagging plus one trick: at each split, a tree may only choose among a few randomly drawn variables, so the trees stop looking alike.

In the credit data one variable, the repayment status of the last month, dominates. Plain bagging puts it at the root of nearly every tree, the trees resemble each other, $\rho$ is high and the variance hits its floor. Breiman's 2001 random forest offers each node only $m$ variables drawn out of $p$. With the scikit-learn default for classification, $m = \lfloor\sqrt{23}\rfloor = 4$, the dominant variable is available at a given root only about 17 % of the time. Each tree gets slightly worse, the forest gets better. With $m = p$ you are back to bagging.

The algorithm

1. Resample. For each of the $B$ trees, draw a bootstrap sample of the training rows.
2. Grow without pruning. At every node, draw $m$ candidate variables and split on the best of them; let the tree grow deep so that its bias stays low.
3. Average. Predict with the mean of the trees; scikit-learn averages probabilities, Breiman's original rule takes a majority vote.

Breiman also proved that the forest's error converges as $B$ grows: more trees cost time and memory, never accuracy. The number of trees is therefore not a setting that overfits; you raise it until the out-of-bag error stops moving. That error is a free validation: each row is predicted only by the trees whose bootstrap draw missed it, roughly 184 trees out of 500.

• max_features acts on $\rho$ and is usually the most influential setting (Probst, Wright and Boulesteix, 2019).
• min_samples_leaf smooths the probabilities: one-row leaves make each tree answer 0 or 1.
• n_estimators only acts on the vanishing term; it is set by watching the out-of-bag curve, not tuned.
• A forest's probabilities tend to avoid 0 and 1, so check the reliability curve before using them with a decision threshold.

Back to contents.

Variable importance: MDI is biased, permutation is honest

The importance score built into a forest favours variables with many possible cut points, so measure importance instead by scrambling a column on unseen data and seeing how much the score drops.

The mean decrease in impurity (MDI), the feature_importances_ attribute of scikit-learn, adds up the Gini gains of every split made on variable $j$, weighted by the share $p(t)$ of rows reaching the node, and averages over trees. Permutation importance asks a different question: how much validation AUC do we lose if the link between $j$ and the target is broken by shuffling its column?

In the deck's illustration, a validation AUC of 0.780 falls to 0.742, 0.748 and 0.745 over three shuffles of the repayment variable, an importance of $0.780 - 0.745 = 0.035$. Strobl, Boulesteix, Zeileis and Hothorn (2007) explained why MDI misleads. A continuous variable offers thousands of thresholds, and one of them always separates the classes a little by chance; a binary variable gets a single try. MDI is computed on the training rows, where the bottom of a deep tree splits on noise and books it as gain. And it describes what the tree used, not what predicts. In a simulation shown in the deck, a pure noise column comes third under MDI and near zero under permutation.

Back to contents.

Gradient boosting: gradient descent over predictions

Boosting builds trees one after another, and each new tree is trained to correct the errors that the sum of the previous trees still makes.

AdaBoost (Freund and Schapire, 1997) reweighted misclassified points so that the next weak learner focused on them. Friedman, Hastie and Tibshirani (2000) read it as an additive model fitted for an exponential loss, which opened the door to any loss. Friedman (2001) then recast boosting as the gradient descent of the course, with one change of unknown: instead of a parameter vector, the unknown is the vector of $n$ predictions $F(x_i)$. The descent direction for client $i$ is the pseudo-residual.

A raw descent step would say nothing about a client outside the training set, so a regression tree $h_m$ is fitted to the $r_{im}$ and added with a small step $\nu$. For the squared loss the pseudo-residual is the plain error $y - F$. For the log loss, with $p = \sigma(F)$, the chain rule and $\sigma' = p(1-p)$ give the model's surprise.

Worked example: three points, stumps, ν = 0.5

Take the points $(1, 1)$, $(2, 5)$, $(3, 12)$ and the squared loss. The start is the mean, $F_0 = 6$, so the first residuals are $-5, -1, 6$. A stump (a tree with one split) compares the cut at 1.5 (sum of squares 24.5) with the cut at 2.5 (sum 8) and keeps 2.5, predicting $-3$ on the left and 6 on the right. Half of it is added. In round 2 the residuals are $-3.5, 0.5, 3$, and now the cut at 1.5 wins (3.125 against 8): the second tree splits where the first did not, because it works on what is left.

Three settings hang together. A small learning rate (shrinkage) generalises better at the price of more trees: in the deck's simulation, $\nu = 0.5$ reaches its best validation loss after 5 trees and then degrades, while $\nu = 0.05$ bottoms out at 87 trees in a wide valley. Trees stay short, because depth sets the order of interactions, and boosting reduces bias by adding weak learners rather than variance by averaging strong ones: Hastie et al. recommend 4 to 8 leaves. The number of trees then becomes an output of early stopping on a validation set.

Back to contents.

XGBoost: a Newton step per leaf

XGBoost is the same boosting with a better local approximation of the loss, a penalty on leaves, and engineering that makes it fast and tolerant of missing values.

Chen and Guestrin (2016) replace each client's loss by its second-order Taylor expansion around the current model, with gradient $g_i$ and curvature $h_i$ (for the log loss, $p_i - y_i$ and $p_i(1 - p_i)$), and add a penalty $\gamma$ per leaf and $\lambda$ on the squared leaf values. Since a tree gives the same value $w_j$ to every client of leaf $j$, the objective splits into one parabola per leaf, with a closed-form minimum.

Worked example: four clients, λ = 1, γ = 0

1. Gradients. Two defaults predicted at 0.6 and 0.3, two good clients at 0.4 and 0.2: $g = (-0.4, -0.7, 0.4, 0.2)$ and $h = (0.24, 0.21, 0.24, 0.16)$.
2. One leaf. $G = -0.5$, $H = 0.85$, so $w^{\star} = 0.5/1.85 = 0.270$, so everyone goes up a little, because the two missed defaults weigh more.
3. Two leaves. Defaults apart: $w_L^{\star} = 1.1/1.45 = 0.759$, and for the good clients $w_R^{\star} = -0.6/1.40 = -0.429$, against $-1.5$ without $\lambda$, which shows how the penalty shrinks small leaves.
4. Gain. $\tfrac12(0.834 + 0.257 - 0.135) = 0.478$, far above the 0.000 and 0.095 of the two splits that isolate one client. With $\gamma = 0.5$ no split would pass: pruning is built into growth.

For the squared loss, $h_i = 1$ and without $\lambda$ the optimal leaf is the mean of its residuals, which is exactly Friedman's version. Two engineering additions matter in practice: thresholds searched on quantile histograms (256 bins by default) rather than every value, and a learned default direction for missing values at each split. LightGBM (2017) grows trees leaf-wise for speed; CatBoost (2018) uses symmetric trees and ordered target statistics for categorical variables. Once tuned, the three usually land close to one another.

Back to contents.

Nested cross-validation: choose inside, measure outside

If you pick the best settings on some folds and then report the score on those same folds, you report the luckiest setting, not the true quality of the model.

Suppose twenty settings all have a true AUC of 0.770 and each cross-validated estimate carries noise with a standard deviation of 0.005. Keeping the best picks the luckiest: the maximum of twenty normal draws sits on average 1.87 standard deviations above the mean, so the reported score is near 0.779 for a model worth 0.770. Varma and Simon (2006) and Cawley and Talbot (2010) showed this selection bias can be as large as the gap between two algorithms.

The defence separates choosing from measuring. An outer loop splits the data into five folds; for each, a full inner cross-validation on the other four chooses the hyperparameters, the winner is retrained on those four and scored once on the held-out fold. The five scores measure the procedure "search, then train", not one fixed model. Early stopping is a setting like the others and happens in the inner loop.

from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score

inner = StratifiedKFold(3, shuffle=True, random_state=1)   # to choose
outer = StratifiedKFold(5, shuffle=True, random_state=1)   # to measure
search = GridSearchCV(model, grid, cv=inner, scoring="roc_auc")
scores = cross_val_score(search, X, y, cv=outer, scoring="roc_auc")
# five honest AUCs; refit search on all rows for the delivered model

A second trap hides in the spread of those scores. With five folds, two training sets share 75 % of their rows, so the fold scores are correlated. Their mean has the same variance as the forest: $\sigma^2/K$ plus a covariance floor $\gamma$. Bengio and Grandvalet (2004) proved that no unbiased estimator of this variance exists from a single cross-validation. With $\sigma^2 = 1$ and $\gamma = 0.3$, the true variance of the mean is 0.44 while the naive $s^2/K$ says 0.2.

Back to contents.

The corrected resampled t-test of Nadeau and Bengio

Because the folds overlap, the usual paired t-test is far too confident; the correction widens the error bar by a factor fixed in advance by the size of the folds.

Both models are scored on the same folds, so we work on the paired differences $d_k$ (challenger minus baseline), which removes what is specific to each fold. Dietterich (1998) showed that a t-test treating these differences as independent rejects equality far too often. Nadeau and Bengio (2003) replace $1/J$ by $1/J + n_2/n_1$, where $n_2/n_1$ is the size of the measured fold over the size of the training part: $1/4$ with five folds, $1/9$ with ten. Bouckaert and Frank (2004) confirmed it behaves well for repeated cross-validation.

Worked example: boosting against logistic regression on five folds

1. Differences. AUC gaps of 0.014, 0.002, 0.017, 0.006 and 0.011 (illustrative values from the deck): mean $\bar d = 0.010$, $s^2 = 3.65 \times 10^{-5}$, $s = 0.00604$.
2. Naive test. Standard error $\sqrt{s^2/5} = 0.00270$, $t = 3.70$, $p = 0.021$ with 4 degrees of freedom: it looks established.
3. Correction. Factor $1/5 + 1/4 = 0.45$ instead of 0.2: the variance is multiplied by 2.25 and the standard error by 1.5, to 0.00405.
4. Corrected test. $t = 2.47$, $p = 0.069$. The 95 % interval, $0.010 \pm 2.776 \times 0.00405$, runs from about $-0.001$ to $0.021$ and contains zero: the lead is not established.

The deck's illustrative comparison table makes the same point at scale: with three seeds times five folds, a boosting ahead by 0.010 gets a corrected $p$ of 0.07 where the naive one would have printed 0.0008. Comparing three challengers to one baseline adds a further risk: if none truly wins, the chance that at least one test fires is $1 - 0.95^3 = 14.3$ %. The Bonferroni bound, $p < 0.05/3$, holds without any independence assumption.

Back to contents.

Key takeaways

1. An average of $B$ trees has variance $\rho\sigma^2 + (1 - \rho)\sigma^2/B$, so adding trees only removes the second term, lowering the correlation removes the floor.
2. A random forest is bagging plus a random draw of candidate variables at each node; more trees never overfit, and the out-of-bag error is a free check.
3. Impurity-based importance favours variables with many thresholds and is computed on training data; use permutation on the validation set, with a noise column as a control.
4. Gradient boosting fits each tree to the pseudo-residuals $-\partial L/\partial F$, which are $y - p$ for the log loss; use a small step, short trees and early stopping.
5. XGBoost's leaf value $-G/(H + \lambda)$ is a regularised Newton step, and its split gain compares the children's score to the parent's minus $\gamma$.
6. Choose hyperparameters in an inner loop and measure in an outer one; then compare models on paired differences with the Nadeau and Bengio correction, under a rule written beforehand.

Glossary

Bootstrap

A sample of $n$ rows drawn with replacement from the $n$ training rows; about 63.2 % of distinct rows appear in it.

Random forest

Bagging of deep trees in which each node may only split on $m$ variables drawn at random out of $p$.

Out-of-bag error

The error of each row predicted only by the trees that did not see it in their bootstrap sample.

Mean decrease in impurity (MDI)

Sum of the weighted impurity gains of the splits on a variable, averaged over trees; biased towards variables with many thresholds.

Permutation importance

Loss of validation score when a column is shuffled, which breaks its link with the target while keeping its distribution.

Pseudo-residual

Minus the derivative of the loss with respect to the current prediction, client by client; the target of the next boosting tree.

Learning rate (shrinkage)

The factor $\nu$ that multiplies each new tree before it is added; small values generalise better.

Early stopping

Stopping the addition of trees when the validation loss has not improved for a set number of rounds.

XGBoost

Gradient boosting with a second-order expansion, penalised leaves, histogram split search and native missing values (Chen and Guestrin, 2016).

Nested cross-validation

An inner cross-validation that chooses the settings inside each fold of an outer one that measures.

Corrected resampled t-test

Paired t-test on fold differences whose variance factor $1/J$ becomes $1/J + n_2/n_1$ (Nadeau and Bengio, 2003).

Preregistration

Writing the decision rule and metric before seeing the results, so that the choice cannot follow the numbers.

The other notes of the course

One public summary per deck, in the order of the course.

Previous: Kernels, SVM and decision treesNext: SHAP, fairness, PCA and clustering

1. IntroductionAI winters, jobs and method
2. ToolsKaggle, GitHub, Python: the tools
3. Session 1Project framing and least squares
4. Session 2Maximum likelihood and logistic regression
5. Session 3Gradient descent, ridge and lasso
6. Session 4Decision threshold and reproducible ML
7. HomeworkA defensible baseline model
8. Session 5Kernels, SVM and decision trees
9. Session 6Forests, boosting, honest comparison
10. Session 7SHAP, fairness, PCA and clustering
11. HomeworkA documented champion model
12. Session 8Neural networks, drift, conformal prediction
13. HomeworkA delivered machine learning project
14. Session 9Defending a machine learning project
15. ReferenceCredit default scoring project
16. ReferenceAsset returns: XGBoost and sentiment
17. ReferencePython code for every ML model
18. ReferenceDeep learning essentials
19. ReferenceOpen data ML projects by sector
20. ReferenceData and AI engineer handbook
21. ReferenceData engineering, SRE and cloud
22. ReferencePanorama of machine learning models

All the notes, as a reading list

Attention and transformers, step by step

About these notes

Written by the lecturer from the slides of the deck, as a public summary: the key ideas, the formulas and one worked example. The exercises, their solutions, the tests and the grading stay in the deck, for the students of the course.

Revision: 16 October 2026.