Bagging - Random Forest Regressor/Classifier

What you’ll learn

• the bootstrap, and the derivation of the 63.2% / 36.8% split
• out-of-bag scoring — a validation estimate that costs nothing
• bagging against pasting, and why the resampling that seems wasteful wins
• what a random forest adds beyond bagging, and why it lowers correlation
• Extra-Trees, which makes each tree worse and the ensemble better
• why feature_importances_ favours high-cardinality columns, measured

Intuition

The Power of Ensembles established that averaging cancels variance only when the members disagree. Bagging manufactures that disagreement mechanically: train each model on a different random sample of the same data.

A deep decision tree is the ideal member. It has low bias, catastrophic variance, and — because the greedy split search amplifies small differences — two trees grown on slightly different samples can look nothing alike. High variance and low correlation are exactly what averaging needs.

diagram Diagram mermaid

  flowchart TD
  D["Training set, n rows"] --> B1["bootstrap 1
n rows, with replacement"]
  D --> B2["bootstrap 2"]
  D --> B3["bootstrap ..."]
  B1 --> T1["deep tree 1"]
  B2 --> T2["deep tree 2"]
  B3 --> T3["deep tree m"]
  T1 --> A["Average (regression)
or vote (classification)"]
  T2 --> A
  T3 --> A

The math: what a bootstrap sample contains

Draw $n$ rows with replacement from a set of $n$. For any particular row, the chance of not being picked on one draw is $1 - 1/n$, and the draws are independent:

$$P(\text{row never drawn}) = \left(1 - \frac{1}{n}\right)^{n}$$

As $n$ grows this converges to a familiar constant:

$$\lim_{n\to\infty}\left(1 - \frac{1}{n}\right)^{n} = e^{-1} \approx 0.3679$$ $$\boxed{\;\text{in-bag} \approx 63.2\%, \qquad \text{out-of-bag} \approx 36.8\%\;}$$

figure Coverage converges almost immediately matplotlib

At n = 20 the fraction is already 0.6415; by n = 100 it is 0.6340. The limit 1 - 1/e = 0.6321 is reached for practical purposes almost at once.

$n$	fraction of distinct rows
5	0.6723
20	0.6415
100	0.6340
1,000	0.6323
$\infty$	0.6321

Each tree therefore misses about a third of the data — and those rows are a ready-made validation set for that tree, at no extra cost.

See it move

Twenty rows, drawn with replacement twenty times. Watch which rows get picked more than once and which are left out entirely — the leftovers are that tree’s out-of-bag set.

sketch Drawing a bootstrap sample p5.js Pause Restart

Twenty rows are drawn with replacement. Rows picked once or more turn blue with their count; rows never picked stay amber and form the out-of-bag set.

Out-of-bag scoring

For each training row, average the predictions of only those trees that never saw it. That is a genuine held-out estimate, computed during training, using data you already paid for.

oob.py

from sklearn.datasets import make_moons
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
 
X, y = make_moons(n_samples=800, noise=0.32, random_state=4)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)
 
for n in (10, 100, 400):
    forest = RandomForestClassifier(n_estimators=n, oob_score=True,
                                    random_state=0, n_jobs=-1).fit(X_tr, y_tr)
    print(f"n={n:<4} oob {forest.oob_score_:.4f}   held-out test {forest.score(X_te, y_te):.4f}")
 
# n=10   oob 0.8482   held-out test 0.9250
# n=100  oob 0.8857   held-out test 0.9333
# n=400  oob 0.8946   held-out test 0.9292

Two honest observations:

• OOB is systematically pessimistic, by 3 to 4 points here. Each row is scored by only the ~37% of trees that excluded it, so the effective ensemble is a third the size.
• The pessimism shrinks as trees are added, from 7.7 points at $n = 10$ to 3.5 at $n = 400$. At 10 trees only about 4 vote on each row, which is not an ensemble.

Use OOB for quick iteration on large data where cross-validation is expensive. Use cross-validation for the number you report.

Bagging against pasting

Bagging samples with replacement; pasting samples without. Pasting sounds cleaner — no duplicated rows — and it loses:

bagging_vs_pasting.py

from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier
 
bagging = BaggingClassifier(DecisionTreeClassifier(), n_estimators=100,
                            bootstrap=True, oob_score=True,
                            random_state=0, n_jobs=-1).fit(X_tr, y_tr)
pasting = BaggingClassifier(DecisionTreeClassifier(), n_estimators=100,
                            bootstrap=False,
                            random_state=0, n_jobs=-1).fit(X_tr, y_tr)
 
print(f"bagging  test {bagging.score(X_te, y_te):.4f}   oob {bagging.oob_score_:.4f}")
print(f"pasting  test {pasting.score(X_te, y_te):.4f}")
 
# bagging  test 0.9417   oob 0.8786
# pasting  test 0.8833

Bagging wins by 5.8 points. The reason is the correlation term from the previous page: sampling with replacement makes the training sets more different from each other, so $\rho$ falls. Each individual tree is slightly worse — it has seen only 63% of the distinct rows — and the ensemble is much better. Duplicated rows are a feature.

Pasting without replacement on 100 estimators reuses nearly the same rows every time, so the trees are near-identical and averaging them accomplishes little.

What a random forest adds

Bagging alone leaves a problem. If one feature is strongly predictive, every tree will split on it first, whatever rows it received. The trees stay correlated through the feature, not the data.

A random forest fixes this by sampling features at each split, not just rows:

$$\text{max\_features} = \sqrt{n} \;\text{(classification)}, \qquad \text{max\_features} = n \;\text{(regression, scikit-learn default)}$$

With $\sqrt{n}$ features considered per split, the dominant feature is unavailable for most splits, forcing trees to find alternative structure. Individual trees get worse; $\rho$ drops; the ensemble improves.

figure One tree, ten trees, three hundred matplotlib

The single tree is certain everywhere and wrong in places. The forest's surface is smooth, and the shading near the boundary is genuine uncertainty rather than a hard edge.

figure Where adding trees stops paying matplotlib

Both curves flatten by roughly 60 trees. More trees never hurt accuracy — unlike almost every other capacity knob — they simply cost time and memory.

Reading the plot

1. n_estimators is not a regularisation parameter. Adding trees cannot overfit; each is an independent draw and the average converges. Anything else in this curriculum with “more” on the dial eventually turns against you.
2. The plateau arrives quickly. By 60 trees the curve is flat. Going 100 → 400 changed held-out accuracy from 0.9333 to 0.9292 — noise, not improvement.
3. OOB tracks the test curve in shape, sitting a few points below. Useful for choosing n_estimators even though its level is pessimistic.

Set n_estimators as high as your latency budget allows, then tune the parameters that actually trade off — max_depth, min_samples_leaf, max_features.

Extra-Trees

Extremely Randomised Trees go one step further: instead of searching for the best threshold on each sampled feature, they pick thresholds at random and keep the best of those.

	Random Forest	Extra-Trees
Rows	Bootstrap sample	Whole set by default
Features per split	Random subset	Random subset
Threshold	Best found by search	Random, best of the random ones
Individual tree quality	Better	Worse
Correlation between trees	Higher	Lower
Training speed	Slower	Much faster — no threshold search

Measured on the same split: random forest 0.9333, Extra-Trees 0.9375. Deliberately worse members, a better ensemble, and faster to train. It is worth trying whenever a forest is your baseline.

Feature importance lies

figure Four features: two informative, two pure noise matplotlib

Impurity importance ranks the continuous noise column above the informative binary one. Permutation importance, measured on held-out data, correctly gives it nothing.

Measured on a constructed dataset where two columns carry signal and two are pure noise:

Feature	Impurity importance	Permutation importance
signal, continuous	0.5902	+0.2785
signal, binary	0.1727	+0.0206
noise, continuous	0.2245	−0.0089
noise, binary	0.0126	+0.0006

Impurity importance ranks a pure-noise column second, above a genuinely informative one. The mechanism is mechanical: a continuous feature offers hundreds of candidate split points, a binary feature offers exactly one. More chances to win a split by luck means more accumulated impurity reduction.

Permutation importance shuffles one column in the held-out data and measures how much the score drops. Noise scores zero because destroying noise costs nothing.

permutation_importance.py

from sklearn.inspection import permutation_importance
 
result = permutation_importance(forest, X_test, y_test,
                                n_repeats=15, random_state=0, n_jobs=-1)
 
for name, mean, std in sorted(zip(names, result.importances_mean,
                                  result.importances_std),
                              key=lambda row: -row[1]):
    print(f"{name:<14} {mean:+.4f} +/- {std:.4f}")

Permutation importance has its own failure mode

With two correlated columns, shuffling one leaves the model able to recover the information from the other, so both look unimportant. Check the correlation matrix before concluding a feature is useless.

pch.algoTag Random Forest Supervised · Classification and Regression · Bagging ensemble

pch.algoApi sklearn.ensemble.RandomForestClassifier / RandomForestRegressor

pch.algoAssumes

• The base learner is high-variance and low-bias — a deep tree
• Bootstrap samples and feature subsets produce genuinely different trees
• Axis-aligned rectangular regions can approximate the target

pch.algoCost

pch.algoTrain

O(m · n · log m · trees)

pch.algoPredict

O(depth · trees)

pch.algoMemory

O(nodes · trees)

m = samples, n = features; training parallelises perfectly across trees

pch.algoHyperparams

• n_estimators default 100 More is never worse for accuracy, only slower. Set it by your latency budget; the curve plateaus around 60 to 100 here.
• max_features default sqrt (clf) / 1.0 (reg) The correlation dial. Lower means more diverse, weaker trees. Worth tuning — regression often benefits from about 0.3.
• max_depth default None Unlimited is usually right for a forest, because averaging handles the variance a single tree could not.
• min_samples_leaf default 1 Raise to 5 to 20 on noisy data — the most effective regularisation knob here.
• oob_score default False Enables the free validation estimate. Pessimistic by a few points, and it needs enough trees to be stable.
• class_weight default None 'balanced_subsample' reweights per bootstrap sample, which is the right variant for imbalanced data.

pch.algoReachFor

• You want a strong tabular baseline with almost no tuning
• Features are on mixed scales and you do not want to preprocess
• You need something robust to outliers and irrelevant columns
• Training can be parallelised across cores

pch.algoLookElsewhere

• You need an interpretable model — 300 trees is not a set of rules
• Prediction latency is tight; every tree runs on every request
• The data is very high-dimensional and sparse, such as text — linear models win there
• You need to extrapolate beyond the training range; trees predict a constant outside it

Pitfalls

Tuning n_estimators as if it could overfit

It cannot. Time spent searching over 100 against 500 trees is better spent on max_features or min_samples_leaf. Set it high and move on.

Trusting feature_importances_

It ranked pure noise second in the measurement above. Use permutation_importance on held-out data for any ranking you intend to act on.

Expecting a forest to extrapolate

Every leaf predicts a constant, so predictions outside the training range are flat. A forest trained on prices up to 500k will never predict 900k, however large the house.

Out-of-bag scores with too few trees

At 10 trees only about 4 vote on each row, and scikit-learn may warn that some rows have no OOB prediction at all. Below roughly 50 trees the estimate is unreliable.

Compare

Model	Trains in parallel	Overfits with more members	Needs scaling	Interpretable
Single tree	—	Yes, with depth	No	Yes, when shallow
Random Forest	Yes	No	No	No
Extra-Trees	Yes	No	No	No
AdaBoost	No — sequential	Yes	No	No
Gradient Boosting	No — sequential	Yes	No	No

The “trains in parallel” column is the practical difference between this page and the next two. Bagging is embarrassingly parallel; boosting is inherently sequential.

pch.quizTag pch.quizDefaultTitle

1. Why does a bootstrap sample contain only about 63.2% of the distinct rows?

   A Because scikit-learn samples 63% by default B Because P(a row is never drawn in n draws with replacement) = (1 - 1/n)^n, which converges to 1/e = 0.368 C Because duplicates are removed D Because 37% is held out deliberately
   pch.quizShowAnswer

   B — Because P(a row is never drawn in n draws with replacement) = (1 - 1/n)^n, which converges to 1/e = 0.368 — It falls straight out of sampling with replacement. The missing 36.8% is what makes out-of-bag scoring free.

2. Bagging scored 0.9417 and pasting 0.8833 on the same data. Why does sampling with replacement win?

   A Bagging uses more data B Replacement makes the training sets more different from each other, lowering correlation between trees — and correlation is what caps the averaging gain C Pasting has a bug D Duplicated rows carry extra information
   pch.quizShowAnswer

   B — Replacement makes the training sets more different from each other, lowering correlation between trees — and correlation is what caps the averaging gain — Each bagged tree is slightly worse for seeing only 63% of distinct rows, and the ensemble is much better because rho fell.

3. What does a random forest add on top of bagging?

   A It uses more trees B It samples a random subset of features at every split, so trees cannot all key on the same dominant feature C It uses a different loss function D It prunes each tree
   pch.quizShowAnswer

   B — It samples a random subset of features at every split, so trees cannot all key on the same dominant feature — Row sampling alone leaves trees correlated through a dominant feature. Feature sampling at each split forces them to find alternative structure.

4. Impurity importance gave a pure-noise continuous column 0.2245 — second highest. Why?

   A The column was not really noise B A continuous column offers hundreds of candidate thresholds, so it wins splits by chance far more often than a binary column with one C The forest was undertrained D Impurity importance is broken and should never be used
   pch.quizShowAnswer

   B — A continuous column offers hundreds of candidate thresholds, so it wins splits by chance far more often than a binary column with one — The bias is mechanical and favours high-cardinality features. Permutation importance on held-out data correctly scored the same column at -0.0089.

🧪 Try It Yourself

Exercise 1 – Derive the 63.2%

pch.exerciseTag pch.exerciseTitle

Exercise 2 – Free validation with out-of-bag scoring

pch.exerciseTag pch.exerciseTitle

Exercise 3 – Bagging against pasting

pch.exerciseTag pch.exerciseTitle

Exercise 4 – Extra-Trees against a forest

pch.exerciseTag pch.exerciseTitle

Exercise 5 – Catch impurity importance lying

pch.exerciseTag pch.exerciseTitle

Recap

• A bootstrap sample of size $n$ contains $1 - (1-1/n)^n \to 63.2\%$ of the distinct rows; the remaining 36.8% is the out-of-bag set.
• OOB scoring is free and systematically pessimistic — 0.8857 against a true 0.9333 at 100 trees.
• Bagging beat pasting 0.9417 to 0.8833, because replacement lowers the correlation between trees.
• A random forest samples features at every split, so no single dominant feature can keep the trees correlated.
• Extra-Trees randomises thresholds too: worse trees, lower correlation, better ensemble (0.9375), faster training.
• n_estimators cannot overfit — set it by your latency budget, and tune max_features and min_samples_leaf instead.
• Impurity importance ranked pure noise second. Use permutation importance on held-out data.

Exercise 6 – How much of the data does one tree see?

pch.exerciseTag pch.exerciseTitle

Next

Continue to Boosting - Introduction to AdaBoost — the opposite strategy: instead of averaging strong models trained in parallel, chain weak ones sequentially so each fixes the last one’s mistakes.