Every point is left out of about 37 % of the bootstrap samples, so the trees that never saw it give an honest prediction for it. Compute the out-of-bag error by hand and from scratch, then measure feature importance by impurity and by permutation, and see why the first can mislead.
ML02.2.4L2 Intermediate25 minIn review (what this means)
The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
Compute the out-of-bag prediction and the out-of-bag error of a bagged ensemble, by hand and from scratch.
Compare the out-of-bag error with 5-fold cross-validation and with scikit-learn’s oob_score_.
Define mean decrease in impurity and compute it by hand for a small tree.
Show that impurity importance favours a meaningless high-cardinality column, and use permutation importance on held-out data instead.
The question
To know how well a forest predicts, we usually hold data back or refit it five times for cross-validation. Yet every tree in the forest was grown without about a third of the points. Can those left-out points test the forest for free? And once it works, which features is it using?
From the last lesson
1. What does a random forest change in the tree grower, compared with bagging?
Show answer
At every node it draws max_features of the features at random and searches only those for the best split.
2. Why does a random forest not overfit as more trees are added?
Show answer
Its vote is an average over random draws, and adding trees moves it towards a fixed limit rather than making the model more complex.
Intuition
Write the trees along one side of a table and the points along the other, and mark which points each tree’s bootstrap sample drew. The empty cells are the important ones: a tree that never saw a point can judge it fairly.
ML02.2.4-F1
The first six bootstrap samples of the twelve points from lesson ML02.2.2. Each point’s out-of-bag jury is the set of trees whose sample left it out. Point 6 has four.
Each point gets its own jury, about 37 % of the trees, and the jury’s vote is a prediction made without that point. Do this for every point and count the mistakes: that is the out-of-bag error. It needs no data set aside and no refitting.
Build it up
Step 1. Record the samples. While growing tree \(m\), keep the list of points its bootstrap sample drew. The others are out of bag for that tree.
Step 2. Ask each jury. For point \(i\), collect the votes (or predictions) of only those trees for which \(i\) was out of bag, and combine them as the forest would.
Step 3. Score. Compare each point’s out-of-bag prediction with its label and average the mistakes. A point whose jury is empty, because every tree happened to draw it, is skipped.
Step 4. Compare with the training error. The full vote on a training point includes trees that were fitted to that very point, so it is optimistic. Fifty bagged trees on the twelve points had a training error of 0 of 12 (lesson ML02.2.2); their out-of-bag error is 4 of 12.
The formal statement
NoteDefinition: out-of-bag prediction and error
Let \(O_i\) be the set of trees whose bootstrap sample does not contain example \(i\). The out-of-bag prediction for \(i\) is the vote (or the average) of the trees in \(O_i\) at \(\vect{x}_i\). The out-of-bag error is the error of these predictions over all examples with a non-empty \(O_i\).
How big is a jury? Each tree leaves point \(i\) out with chance \({(1 - 1/n)^n} \approx 0.368\) (lesson ML02.2.2), independently of the other trees, so the jury size is binomial with mean \({B(1 - 1/n)^n}\). With \(B = 300\) trees and \(n = 569\) that is about 110 trees. The chance that a point has no jury at all is \({\big(1 - (1 - 1/n)^n\big)^B}\), about \(0.632^B\): 0.010 for \(B = 10\), but only about \(10^{-5}\) for \(B = 25\).
Why it is honest. No tree in \(O_i\) saw example \(i\), so their vote on it is a genuine prediction for an unseen point, as in cross-validation. The out-of-bag prediction uses about \(0.37B\) trees, not \(B\), so it scores a slightly smaller forest, and a forest gets better with more trees. Hastie, Tibshirani and Friedman note that the out-of-bag error is almost identical to \(n\)-fold cross-validation.
Importance by impurity. A tree lowers impurity at every split. For a node \(t\) with \(n_t\) of the \(n\) training points, impurity \({I(t)}\) and children \(L\) and \(R\), the weighted impurity decrease is
The mean decrease in impurity (MDI) of feature \(j\) adds up \({\Delta(t)}\) over the nodes that split on \(j\). scikit-learn scales each tree’s importances to sum to 1 and averages over the trees.
ML02.2.4-F3
Mean decrease in impurity for the full tree of the twelve points. Each split’s weighted Gini drop is credited to its feature.
For the tree above, the root drops \({\tfrac{12}{12}\big(\tfrac12 - \tfrac{5}{18}\big)} = \tfrac{2}{9}\). The left child, with 6 points and Gini \(\tfrac{5}{18}\), splits into two pure leaves: \({\tfrac{6}{12}\big(\tfrac{5}{18} - 0\big)} = \tfrac{5}{36}\). The right child splits into a pure leaf of 4 and a node of 2 with Gini \(\tfrac12\):
The last node drops \(\tfrac{2}{12}\cdot\tfrac12 = \tfrac{1}{12}\). So \(x_1\) gets \(\tfrac29 + \tfrac1{12} = \tfrac{11}{36}\) and \(x_2\) gets \(\tfrac5{36} + \tfrac1{18} = \tfrac7{36}\). They add up to \(\tfrac12\), the root’s impurity, because every leaf is pure. Scaled to sum to 1, the importances are \(11/18 \approx 0.611\) and \(7/18 \approx 0.389\).
Importance by permutation. Take a fitted model and a held-out set. Shuffle the values of feature \(j\) among the held-out rows, which breaks its link with the label and keeps everything else, and measure how much the score falls. Repeat the shuffle a few times and average. A feature the model depends on for real predictions makes the score fall; a feature that only helped it memorise the training data does not.
Worked example
The out-of-bag error of six trees on the twelve points, by hand. The trees are the six of the anchor figure. Each tree’s vote at each point is written in the cells where that point was left out.
ML02.2.4-F2
The worked example. Each column’s outlined cells are that point’s jury, and the jury’s majority is its out-of-bag answer.
Read the columns one at a time.
Point 1, (1, 1), class 0: trees 5 and 6 left it out and both vote 0. Right.
Point 4, (2, 3), class 0: only tree 3 left it out, and it votes 1. Wrong. A one-tree jury is a noisy one.
Point 6, (5, 5), class 0: trees 1, 2, 3 and 6 vote 1, 1, 1, 1. Wrong. Surrounded by class 1, the odd point is always misjudged by trees that did not memorise it.
Point 11, (2, 5), class 1: trees 2, 4 and 5 all vote 0. Wrong, for the same reason.
Point 12, (6, 5), class 1: trees 1, 3, 4 and 6 vote 1, 1, 0, 1, a majority of 3 to 1 for class 1. Right.
The other seven points are right as well, so the out-of-bag error is \(3/12 = 0.25\). The juries have 29 members in all, \(29/12 \approx 2.4\) per point, or 40 % of the six trees; the expected share is \({(11/12)^{12}} \approx 35\) %.
Code
First the out-of-bag error from scratch on all 569 patients of load_breast_cancer: 300 trees, each a DecisionTreeClassifier with max_features="sqrt" grown on our own bootstrap sample, so this is a random forest whose bookkeeping we do ourselves.
import numpy as npfrom sklearn.datasets import load_breast_cancerfrom sklearn.ensemble import RandomForestClassifierfrom sklearn.model_selection import cross_val_scorefrom sklearn.tree import DecisionTreeClassifierX, y = load_breast_cancer(return_X_y=True)n, B =len(y), 300rng = np.random.default_rng(0)votes = np.zeros((n, 2)) # out-of-bag votes for class 0 and class 1left_out = []for _ inrange(B): idx = rng.integers(0, n, size=n) tree = DecisionTreeClassifier(max_features="sqrt", random_state=int(rng.integers(1_000_000))) tree.fit(X[idx], y[idx]) out = np.setdiff1d(np.arange(n), idx) # the points this tree never saw left_out.append(len(out) / n) votes[out, tree.predict(X[out])] +=1judged = votes.sum(axis=1) >0oob_error = np.mean(votes[judged].argmax(axis=1) != y[judged])print(f"left out per tree {np.mean(left_out):.3f}, jury size {votes.sum(axis=1).mean():.1f}, "f"points judged {judged.sum()}, out-of-bag error {oob_error:.4f}")forest = RandomForestClassifier(n_estimators=300, oob_score=True, random_state=0).fit(X, y)cv = cross_val_score(RandomForestClassifier(n_estimators=300, random_state=0), X, y, cv=5)print(f"scikit-learn out-of-bag error {1- forest.oob_score_:.4f}, 5-fold CV error {1- cv.mean():.4f}")
left out per tree 0.366, jury size 109.9, points judged 569, out-of-bag error 0.0387
scikit-learn out-of-bag error 0.0351, 5-fold CV error 0.0369
Three estimates of the same thing: 0.039 from scratch, 0.035 from scikit-learn (with different random draws) and 0.037 from five refits. Each is a count of about 20 mistakes in 569, so they agree within a couple of patients.
ML02.2.4-F4
The out-of-bag error of scikit-learn’s forest as trees are added, against 5-fold cross-validation. With 10 trees the juries are small and the estimate is pessimistic; from about 25 trees on it sits at the cross-validation level.
Now importance. First mean decrease in impurity from scratch for one tree, using the arrays scikit-learn keeps in tree_, checked against feature_importances_ on the twelve points.
raw drops: [0.30555556 0.19444444] scaled: [0.611 0.389] library: [0.611 0.389]
Finally the bias. A made-up clinic table of 800 patients has three real features with few values (smoker: 0 or 1, age band: 0 to 3, exercise: 0 or 1) that drive the label, and a record number from 1 to 800 that has nothing to do with it. Fit a forest on 60 % and compare the two importances.
smoker MDI 0.207 permutation on held-out data 0.125
age band MDI 0.129 permutation on held-out data 0.069
exercise MDI 0.118 permutation on held-out data 0.027
record number MDI 0.546 permutation on held-out data 0.003
test accuracy with the record number 0.734375 without it 0.8
MDI ranks the record number first, at 0.546. Its 480 distinct values in the training rows offer hundreds of thresholds, and fully grown trees use them to split small mixed nodes until they are pure, which counts as impurity decrease on the training data. On held-out data, shuffling it changes the score by 0.003: the model gains nothing real from it. It even hurts: the forest without it scores 0.800 on the test patients, against 0.734 with it.
Explore
The vote grid of lesson ML02.2.2 reports the out-of-bag error of its vote. Start with \(B = 1\) and add trees: at first some points have no jury and are skipped; then the out-of-bag error settles while the training error sits at or near 0.
Pitfalls
ML02.2.4-F5
Wrong beside right. Impurity importance, computed from the training data, crowns a meaningless record number. Permutation importance on held-out data gives it nothing.
“feature_importances_ tells me which features matter for prediction.”
It tells you which features the trees split on while fitting the training data, and it favours features with many distinct values. Use permutation importance on held-out data to ask what the model needs to predict new cases.
“Permutation importance is safe on any data.”
On the training data it is fooled the same way: the forest memorised the record numbers, so shuffling them there hurts (0.259 in this table, the largest of the four). Use held-out data. And with two correlated features, shuffling one leaves the model the other, so both look less important than they are; neither measure says what would happen if a feature were removed and the model refitted.
“The out-of-bag error of a small forest is a fine estimate.”
With 10 trees each jury has about four members and some points have none: here the estimate was 0.065, nearly twice the 0.035 of a large forest. Read the out-of-bag error only once it has settled as trees are added.
Check yourself
Recall
1. What is the out-of-bag jury of a training point?
Show answer
The trees whose bootstrap sample did not contain that point.
2. About what fraction of the trees is in each point’s jury, and how many is that for 300 trees and 569 points?
Show answer
About \({(1 - 1/n)^n} \approx 0.368\) of them: \({300 \times 0.3675} \approx 110\) trees.
3. Why is the training error of a bagged forest a poor estimate of its test error?
Show answer
Every training point was fitted by the trees that drew it, so the full vote is optimistic. The fifty trees on the twelve points had training error 0 of 12 and out-of-bag error 4 of 12.
4. What does mean decrease in impurity add up for a feature?
Show answer
The weighted impurity decrease \({\Delta(t)}\) of every node that splits on that feature, over all the trees, with each tree’s importances scaled to sum to 1 before averaging.
5. How is permutation importance computed?
Show answer
Shuffle one feature’s values in a held-out set, measure how much the model’s score falls, repeat and average.
Exercises
1.★ With \(n = 100\) points, how many members does a point’s out-of-bag jury have on average in a forest of 500 trees?
Show solution
\({(1 - 1/100)^{100}} = 0.366\), so on average \({500 \times 0.366} = 183\) trees.
2.★★ A tree on 10 points splits the root (5 of each class) into a node of 6 points (5 of class 0, 1 of class 1) and a pure node of 4 points of class 1, using \(x_1\). The node of 6 splits on \(x_2\) into two pure nodes. Find each feature’s MDI and their scaled shares.
Show solution
The root has Gini \(\tfrac12\). The node of 6 has Gini \(1 - {(\tfrac56)^2} - {(\tfrac16)^2} = \tfrac{10}{36} = \tfrac{5}{18}\), the node of 4 has Gini 0. The root drops \({\tfrac{10}{10}\big(\tfrac12 - \tfrac{6}{10}\cdot\tfrac{5}{18}\big)} = \tfrac12 - \tfrac16 = \tfrac13\), credited to \(x_1\). The node of 6 drops \(\tfrac{6}{10}\cdot\tfrac{5}{18} = \tfrac16\), credited to \(x_2\). The total is \(\tfrac12\), the root’s impurity, and the shares are \(\tfrac23\) and \(\tfrac13\).
3.★★★ Show that, for a tree whose leaves are all pure, the raw MDI values of all the features add up to the impurity of the root.
Show solution
Write \({w(t)} = n_t/n\), so that \({\Delta(t)} = {w(t)I(t)} - {w(L)I(L)} - {w(R)I(R)}\), because \(\tfrac{n_t}{n}\cdot\tfrac{n_L}{n_t} = {w(L)}\). Add \({\Delta(t)}\) over all split nodes. Every node other than the root appears once with a plus sign (as a parent, if it splits) and once with a minus sign (as a child). Every split node except the root therefore cancels, and what is left is \({w(\text{root})I(\text{root})}\) minus the weighted impurities of the leaves. The root has \(w = 1\), and pure leaves have \(I = 0\), so the sum is \({I(\text{root})}\). For the twelve points it is \(\tfrac12\).
Summary card
Each point is judged by the trees that never saw it.
ML02.2.4-F1
A jury for every point, for free.
Out-of-bag error. Vote each point with its jury \(O_i\), about \(0.368B\) trees; close to cross-validation.
Library.RandomForestClassifier(oob_score=True), then oob_score_.
MDI. The weighted impurity drops \({\Delta(t)}\) of a feature’s splits, added up: training data only, biased to many-valued features.
Permutation importance. Score drop when a feature is shuffled in held-out data: sklearn.inspection.permutation_importance.
Further. Importance, partial dependence and SHAP in full: ML04.9.
Sources and next steps
Sources. Each was opened and checked against this lesson on 15 November 2026.
Trevor Hastie, Robert Tibshirani and Jerome Friedman, The Elements of Statistical Learning, 2nd edition, corrected 12th printing. Section 15.3.1: the out-of-bag predictor averages only the trees whose bootstrap sample did not contain the observation, and the out-of-bag error is almost identical to \(N\)-fold cross-validation. Section 15.3.2: split-criterion improvements accumulated per variable, and the permutation measure, which “does not measure the effect on prediction were this variable not available”.
Leo Breiman, Random Forests, January 2001 (published in Machine Learning 45, 5 to 32). Section 3.1: out-of-bag estimates, with about one third of the instances left out of each bootstrap training set.
scikit-learn developers, User Guide, Section 1.11.2.5: Feature importance evaluation. Mean decrease in impurity, and the warning that it is computed from training statistics and favours high-cardinality features; oob_score=True in Section 1.11.2.3.
scikit-learn developers, User Guide, Section 5.2: Permutation feature importance. The definition as the score drop after shuffling one feature (5.2.1), its relation to impurity importance and the high-cardinality bias (5.2.2), and the effect of correlated features (5.2.3).
Next.ML02.3 AdaBoost builds trees one after another instead of side by side, to reduce bias rather than variance. Importance, partial dependence and SHAP are treated in full in ML04.9.
