ENID
Lensa ML

Bagging & Random Forests

Step 1 of 6: Bootstrap Sampling

Many datasets from one, with replacement

160 training points, two noisy moons, plus two pure-noise columns the trees can also split on. Accuracies use 1,000 fresh test points.

sample #1
Distinct points drawn (of 160)
104 = 65%
Drawn more than once
43 (max ×4)
Left out: out-of-bag (hollow)
56 = 35%

A bootstrap sample draws 160 points from the 160 with replacement. Bigger marks were drawn more than once (up to 4 times here); hollow ones weren't drawn at all. Each draw misses a given point with probability 159/160, so a point is left out of the whole sample with probability (1 − 1/160)^160 ≈ 1/e ≈ 37%, and about 63% are in. This sample has 104 distinct points. Draw a few more: each is a slightly different version of the same dataset, as if you'd collected it again. That's what lets one dataset train many different trees.

Draw a few bootstrap samples and compare the counts. Each one keeps about 63% of the points, some of them several times, and leaves about 37% out. Statisticians use the bootstrap to estimate how much a quantity would vary if the data were collected again (Efron, 1979); bagging uses the same trick to manufacture many slightly different training sets from one.

Step 2 of 6: Bagging

Jagged trees vote into a smooth boundary

1 tree60 treesone tree on all the datatest accuracy
Trees in the vote1
One full tree on all 160 points
83.5%
Vote of 1 bootstrap tree
80.1%
Gain over the single tree
-3.4 pts

A decision tree grown until every leaf is pure fits its training data perfectly, noise and all, so its boundary is jagged and changes a lot when the data changes: the six small panels are trees grown on six different bootstrap samples. Bagging (bootstrap aggregating) grows one tree per bootstrap sample and lets them vote. With one tree you get 80.1%, below the 83.5% of a single tree on all the data, because each bootstrap tree sees only ~63% of the points. Add trees. The improvement levels off after a few dozen trees.

Drag the number of trees and compare the forest's boundary with the six individual trees. Fully grown trees have low bias and high variance: they fit the data closely but change a lot from sample to sample. Averaging their votes keeps the low bias and cancels much of the variance. Breiman (1996) introduced bagging; it helps unstable learners such as deep trees and does little for stable ones such as linear regression.

Step 3 of 6: Random Feature Subsets

Weaker trees that disagree more

columns tried at each split:
0.4488.7%mtry 10.6189.5%mtry 20.6989.4%mtry 30.7189.1%mtry 4tree-to-tree correlation ρforest accuracy (100 trees)
Average single tree
83.2%
Correlation between trees
0.71
Forest of 100
89.1%

Bootstrap trees still look alike: they all split first on the strongest column. A random forest adds one twist: at every split, a tree may only choose among a random subset of mtry columns. With all 4 allowed (plain bagging), trees agree with each other at ρ = 0.71. Weaker but more different trees can make a better average, as the next step shows. With only 4 columns the effect here is small; with hundreds of columns, where a few strong ones would dominate every tree, it matters much more, which is why the default is about √(number of columns) for classification.

Switch mtry and compare the correlation and accuracy bars. Restricting each split to a random subset of columns forces trees to use different columns, so they make different mistakes. Breiman's random forest (2001) combines this with bagging; common defaults are √p columns for classification and p/3 for regression, where p is the number of columns. Extremely randomised trees go further and also pick the split threshold at random.

Step 4 of 6: Why Correlation Sets the Floor

ρσ² + (1 − ρ)σ²/N

00.250.50.751floor ρσ² = 0.60σ²mtry 1mtry 2mtry 3mtry 41255075100trees Nvariance of the average ÷ σ² (dashed grey: independent trees)
Correlation ρ0.60
Trees N20
Variance of the average (× σ²)
0.620
If trees were independent
0.050
Floor no number of trees can beat
0.600

Averaging N predictions that each have variance σ² and pairwise correlation ρ gives variance ρσ² + (1 − ρ)σ²/N. The second term shrinks as you add trees; the first never does. At ρ = 0.60 and N = 20, the average keeps 62% of a single tree's variance, and no number of trees gets it below 60%. That's why more trees eventually stop helping, and why random forests decorrelate: the green ticks are the correlations actually measured in step 3, 0.44, 0.61, 0.69, 0.71 for mtry 1 to 4. Lowering ρ lowers the floor itself, at the price of slightly worse individual trees.

Drag ρ and N, then try the measured correlations. The formula Var = ρσ² + (1 − ρ)σ²/N holds for an average of N identically distributed predictions with pairwise correlation ρ. It explains both why adding trees helps quickly at first and then stops, and why the random-feature trick pays off: it lowers ρ, and with it the floor. Adding trees never causes overfitting in a random forest; it only costs time.

Step 5 of 6: Out-of-Bag Error

A validation score from the points each tree skipped

70%80%90%138204580100test accuracy (1,000 new points)out-of-bag accuracy (training points only)trees
Trees30
Out-of-bag accuracy
88.1%
Test accuracy
89.1%
Training points with an OOB vote
160 / 160

Each tree never saw about 37% of the training points, so those points can test it. The out-of-bag (OOB) estimate lets every training point be voted on only by the trees that left it out, then scores those votes. With 30 trees it reads 88.1% against 89.1% on 1,000 brand-new points. Once there are a few dozen trees the two curves track each other, so a random forest gets a validation score for free, without holding any data back. It's the same idea as cross-validation, with the bootstrap doing the splitting.

Drag the number of trees and compare the two curves. OOB estimates use only the trees that didn't train on a point, so with few trees they score a much smaller forest and are pessimistic. From a few dozen trees on they are close to a held-out estimate, which makes them a cheap way to tune mtry or tree depth. They don't remove the need for a final test set when you also tune many settings.

Step 6 of 6: Feature Importance

Two ways to ask, and the noise test

x₁28.3%x₂53.0%noise A8.7%noise B10.0%
Share credited to the two noise columns
19%
Most important column
x₂
Accuracy lost shuffling x₂
20.8 pts

Impurity importance adds up how much each column reduced Gini impurity across all splits of all trees. It's free to compute, but it's measured on the training data, and fully grown trees keep splitting on noise to purify their last leaves. Here the two pure-noise columns get 19% of the credit. This bias towards columns with many possible split points is well known (Strobl et al., 2007). Switch to permutation importance.

Switch between the two importance measures and compare the noise columns. Impurity importance is computed from training splits and is biased towards columns with many unique values, including pure noise. Permutation importance on held-out data avoids that bias and has a natural scale (accuracy lost), but correlated columns share credit and can both look unimportant. SHAP values are a third option that explains individual predictions as well as global importance.

What is a random forest?

A random forest is an ensemble of decision trees, each trained on a bootstrap sample of the data and limited to a random subset of features at every split. For classification the forest takes a majority vote of its trees, and for regression it averages their predictions. Training each tree on a resampled copy of the data is called bagging, short for bootstrap aggregating. The random feature subsets are what turn bagged trees into a random forest.

Random forests are a default choice for tabular data because they work well with little tuning, handle mixed feature types, and do not overfit as more trees are added. They are used in credit risk, fraud detection, ecology, genomics, and remote sensing. They also come with two useful by-products: an out-of-bag estimate of test error and feature importance scores.

Key ideas

  • Bagging trains each model on a bootstrap sample drawn with replacement and combines their predictions.
  • A bootstrap sample contains about 63.2% of the unique training points.
  • Averaging many high-variance trees reduces variance without adding much bias.
  • Random forests also limit each split to a random subset of features, which decorrelates the trees.
  • Out-of-bag points give a built-in estimate of test error.
  • Adding more trees does not cause overfitting; it only stabilizes the ensemble.

Common questions

What is the difference between bagging and a random forest?

Bagging trains every tree on a bootstrap sample but lets each split consider all features. A random forest adds a second source of randomness, a random subset of features at every split. That makes the trees less correlated, so averaging them reduces variance further.

How many trees should a random forest have?

Enough that the error stops improving, often a few hundred. More trees never make the forest overfit, but the gains shrink while training and prediction get slower. Plotting OOB error against the number of trees shows where it levels off.

Is a random forest better than gradient boosting?

Well-tuned gradient boosting usually reaches higher accuracy on tabular data, because it reduces bias by fitting each tree to the errors of the earlier ones. Random forests are easier to tune, harder to overfit, and train their trees in parallel. A common workflow starts with a random forest as a baseline and moves to boosting for the last few points of accuracy.

Can a random forest overfit?

Its error does not rise as trees are added, but a forest can still overfit noisy data when its trees grow very deep on few samples. Limiting tree depth or raising the minimum number of samples per leaf helps in that case. Checking the OOB error is a quick way to spot it.

Related explainers

References

  1. Breiman (2001), "Random Forests", Machine Learning
  2. Breiman (1996), "Bagging Predictors", Machine Learning
  3. James, Witten, Hastie & Tibshirani, "An Introduction to Statistical Learning", chapter 8: Tree-Based Methods

Last updated