Bagging & Random ForestsOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Bagging & Random Forests

A single decision tree overfits easily — it's high-variance. Bagging (Bootstrap Aggregating) trains many trees on random subsets of data and averages their predictions, dramatically reducing variance. In project-loop terms, an ensemble is a hypothesis-space move: instead of one model, your function family becomes averages of many — strictly more expressive, and much lower variance.

Deep dive
The ML Project Loop
Includes runnable notebook

Real-world examples: Credit scoring, customer churn prediction, medical diagnosis, any tabular data task.

Bagging (Bootstrap Aggregating)

  1. Create BB bootstrap samples (sample with replacement, same size as original)
  2. Train a decision tree on each sample
  3. Classification: majority vote. Regression: average predictions.

Each tree sees a different "view" of the data. Some points appear multiple times, others not at all (~37% are left out per tree). Averaging many diverse trees reduces variance without increasing bias.

f^bag(x)=1B∑b=1BTb(x)\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} T_b(\mathbf{x})

Watch how bootstrap resampling creates diverse trees, and how majority vote smooths the combined boundary:

Bagging: bootstrap resampling & majority-vote boundary

Bootstrap sample 1stump split (orange dashed)
Ensemble boundary (trees 1–3)majority vote shading
trees in ensemble3
current sample1 / 5
OOB size~9 OOB

Left: each tree sees a bootstrap resample (faint = not sampled, bold = included). Right: the majority-vote boundary smooths out as more trees are added — high-variance individual stumps average into a stable ensemble.

Why bagging works

Different bootstrap samples produce different trees, and averaging diverse estimates cancels their individual noise — like polling: one poll is noisy, but averaging 1000 polls gives a reliable estimate. If the trees were perfectly uncorrelated, the variance of the average would drop by a full factor of BB; the next section shows how close bagging actually gets.

How much does variance actually drop?

The "factor of BB" only holds if the trees are perfectly uncorrelated, but bagged trees aren't, since they share most of their data. For BB identically-distributed trees each with variance σ2\sigma^2 and pairwise correlation ρ\rho, the variance of their average is:

Var ⁣(1B∑bTb)=ρ σ2+1−ρB σ2.\text{Var}\!\left(\frac{1}{B}\sum_b T_b\right) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2.

Two terms with very different behavior:

  • The second term 1−ρBσ2\frac{1-\rho}{B}\sigma^2 vanishes as B→∞B\to\infty — adding more trees kills it.
  • The first term ρσ2\rho\sigma^2 is a floor that more trees cannot touch.

This is the key insight behind random forests: once you have enough trees, the only way to reduce variance further is to lower ρ\rho. Bagging alone leaves ρ\rho high (trees all latch onto the same dominant feature); random feature subsets at each split push ρ\rho down, lowering the floor. So RF attacks the term bagging can't.

Worked example

5 trees predict [cat, dog, cat, cat, dog] for a new image. Majority vote: cat (3 vs 2).

Python
# The idiom (for your own X_train / y_train / X_test / y_test):
from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier

bag = BaggingClassifier(
    estimator=DecisionTreeClassifier(max_depth=None),
    n_estimators=100,
    max_samples=0.8,       # each tree sees 80% of data
    max_features=1.0,      # all features
    bootstrap=True,
    random_state=42
)
bag.fit(X_train, y_train)
print(f"Bagging accuracy: {bag.score(X_test, y_test):.3f}")

Random Forests

Random Forests improve on bagging by adding feature randomization: at each split, only consider a random subset of mm features.

This decorrelates the trees further. They can't all rely on the same dominant feature:

TaskDefault mm
Classificationd\sqrt{d}
Regressiond/3d/3
f^RF(x)=1B∑b=1BTb(x,θb)\hat{f}_{\text{RF}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} T_b(\mathbf{x}, \theta_b)

where θb\theta_b are the random feature subsets for tree bb.

Python
from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=100,       # number of trees
    max_depth=10,           # limit tree depth
    max_features='sqrt',    # √d features per split
    min_samples_leaf=5,     # minimum samples in leaf
    random_state=42,
    n_jobs=-1               # use all CPU cores
)
rf.fit(X_train, y_train)
print(f"RF accuracy: {rf.score(X_test, y_test):.3f}")

Feature importance

Two main methods:

Mean Decrease in Impurity (MDI)

Sum the impurity decrease at each split across all trees, weighted by the number of samples reaching that split.

Python
import numpy as np

importances = rf.feature_importances_
for i in np.argsort(importances)[::-1][:5]:
    print(f"Feature {i}: {importances[i]:.3f}")

Permutation importance (more reliable)

Shuffle each feature and measure accuracy drop:

Python
from sklearn.inspection import permutation_importance

result = permutation_importance(rf, X_test, y_test, n_repeats=10, random_state=42)
for i in np.argsort(result.importances_mean)[::-1][:5]:
    print(f"Feature {i}: {result.importances_mean[i]:.3f} ± {result.importances_std[i]:.3f}")

MDI vs Permutation importance

MDI can be biased toward high-cardinality features (e.g., ID numbers). Permutation importance is more reliable but slower. Use permutation importance for final analysis, MDI for quick exploration.

Out-of-Bag (OOB) evaluation

Where does "~37%" come from? A bootstrap sample draws nn rows with replacement. The chance a specific row is not picked on one draw is 1−1n1-\tfrac1n, and draws are independent, so the chance it's missed by all nn draws is:

(1−1n)n  →  n→∞    e−1≈0.368.\left(1 - \frac{1}{n}\right)^{n} \;\xrightarrow{\;n\to\infty\;}\; e^{-1} \approx 0.368.

So each tree leaves out about 37% of the rows (e.g. n=100n=100 gives 0.3660.366). Those out-of-bag rows were never seen by that tree, so we can use them as a built-in validation set — no cross-validation needed:

Python
rf = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
rf.fit(X_train, y_train)
print(f"OOB accuracy: {rf.oob_score_:.3f}")  # ~same as test accuracy

Watch it run

The trace fits real CART regression trees over 50 independent training sets, so the variance formula above can be checked rather than restated.

Bagging — the variance floor, and why random forests raise σ² on purpose

1/6

One bootstrap sample: draw 160 row indices **with replacement**, so some rows arrive several times and others not at all. This draw left 61 of 160 rows out — 38.1%. The lesson derives the expected fraction as (1 − 1/n)^n, which converges to 1/e = 0.3679; at n = 100 that is 0.3660, matching the 0.366 the page quotes. Those left-out rows are the whole basis of OOB evaluation — this tree has genuinely never seen them, so they are a free validation set.

python
1for b in range(B):
2 idx = randint(0, n, size=n) # with replacement
3 oob = setdiff(arange(n), idx)
4
5 # random forest: also subsample features
6 tree = fit_tree(X[idx], y[idx],
7 max_features=mtry)
8
9 trees.append(tree)
10 for i in oob:
11 oob_pred[i].append(tree(X[i]))
12
13ensemble = mean(t(x) for t in trees)
14oob_error = mean((mean(oob_pred[i]) - y[i])**2)
state
(1 − 1/n)^n — the expected out-of-bag fraction
n(1 − 1/n)^n
100.3487
500.3642
1000.3660
1,0000.3677
10,0000.3679
this draw
n → 160distinct rows drawn → 99out of bag → 61 (38.1%)1/e → 0.3679

Real CART regression trees over 50 independent training sets, so the lesson's variance decomposition can be checked rather than restated. Measured ensemble variance tracks ρσ² + (1−ρ)σ²/B across a sweep of B, and the floor is visible: past about 30 trees the curve flattens onto ρσ² and more trees buy nothing. The payoff is what random forests actually trade — sampling 2 of 5 features drops correlation from 0.62 to 0.38 while *raising* per-tree variance, because a tree denied the best split is a worse estimator; the floor falls anyway. Finally the OOB estimate is checked against a held-out test set, including the reason it errs pessimistic: it evaluates a smaller ensemble than the one you ship.

What to notice:

  • Frame 3: the formula holds, and the floor is visible. Measured ensemble variance tracks ρσ2+1−ρBσ2\rho\sigma^2 + \frac{1-\rho}{B}\sigma^2 across a sweep of BB. By B=40B = 40 the second term is down to 0.02 while the first sits immovably at 0.18, so more trees buy essentially nothing.
  • Frame 4: averaging does not touch the bias. Single tree and 40-tree ensemble have the same bias at the probe point; only the variance collapses. Averaging is linear, so bagging cannot fix a systematically wrong model — only an unstable one. That is the gap boosting exists to attack.
  • Frame 5: what random forests actually trade. Sampling 2 of 5 features drops ρ\rho from 0.172 to 0.072 as promised, but per-tree variance σ2\sigma^2 rises from 1.05 to 1.83, because a tree denied the best split is a worse estimator. The floor ρσ2\rho\sigma^2 falls 28% anyway. RF deliberately accepts a worse individual model to buy decorrelation that more trees can exploit.
  • Frame 6: OOB against a real test set. Over 45 datasets the OOB error is +0.186 ± 0.111 above the held-out test error, about 6% — close enough to use, and biased in the conservative direction because an OOB prediction averages only the ~22 trees that excluded that row.

Strengths and weaknesses

✅ Strengths❌ Weaknesses
Robust to overfittingLess interpretable than single tree
Handles high-dimensional dataCan be slow for large datasets
ParallelizableCannot extrapolate (interpolation only)
Provides feature importanceStruggles with very sparse data
Minimal hyperparameter tuningBlack-box compared to single tree
Handles missing values

Random Forests are the best tabular baseline

If you have structured/tabular data and don't know where to start, try Random Forests first. They require minimal tuning, are robust to overfitting, and provide feature importance. Only move to gradient boosting if you need more accuracy.

Exercise

What does bagging primarily reduce in a model?

Need a hint?

Bagging averages multiple models trained on different subsets.

Exercise

How does permutation importance measure feature importance?

Need a hint?

It measures what happens when you shuffle a feature.

Exercise

What percentage of training samples are left out of each bootstrap sample in bagging?

Need a hint?

Each bootstrap sample draws n samples with replacement from n total.

Common mistakes

  1. Leaving trees completely unconstrained: cap complexity one way or the other: either max_depth=10, or if you keep max_depth=None, set min_samples_leaf=5 so leaves can't chase single points.
  2. Using too few trees: 10 trees is not enough. Use 100-500. More trees rarely hurt (diminishing returns), but few trees give noisy estimates.
  3. Ignoring feature scaling: Random Forests don't need scaling! They're invariant to monotonic transformations. Don't waste time preprocessing.

Key takeaways

  • Bagging trains models on bootstrap samples and averages them, cutting variance.
  • Random forests add per-split feature randomness to decorrelate the trees.
  • Out-of-bag rows give a built-in validation score.
  • Prefer permutation importance over impurity-based importance for reliability.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Bagging & Random ForestsKNN & Decision TreesLinear RegressionDecision TreesBoostingGradient Boosting in Prac…The ML Project LoopAdaBoost AlgorithmBias-Variance Decompositi…Decision Tree: Informatio…Uplift Modeling & Causal …