Bagging, Random Forests, and Extremely Randomized Trees

Bagging, random forests, and Extra Trees combine trees fitted with different random choices. Averaging can reduce variation in their predictions, but the members also need useful signal: unrelated predictions are not automatically good predictions. Bagging changes the training rows through bootstrap sampling, random forests also randomize the features considered at each split, and Extra Trees randomizes split thresholds. These choices trade individual-tree fit against the benefit of combining trees.

Bootstrap sampling and the 63.2% rule

In ordinary bagging, each tree receives \(n\) draws with replacement from \(n\) training rows. A row can be drawn several times, so \(n\) draws do not mean \(n\) distinct rows. On one draw the chance of missing a particular row is \(1-1/n\); over all draws it is \((1-1/n)^n\). This approaches \(1/e\), about 0.368. Thus the expected fraction of distinct rows included is \(1-(1-1/n)^n\), approaching 0.632. With a different number of draws \(b\), the exclusion probability is \((1-1/n)^b\).

import numpy as np

rng = np.random.default_rng(0)
for n in (10, 100, 1000, 10_000):
    frac = [len(np.unique(rng.integers(0, n, n))) / n for _ in range(2000)]
    print(f"n={n:6d}  in-bag {np.mean(frac):.5f}   out-of-bag {1 - np.mean(frac):.5f}"
          f"   1-1/e = {1 - np.exp(-1):.5f}")
# n=    10  in-bag 0.65455   out-of-bag 0.34545   1-1/e = 0.63212
# n=   100  in-bag 0.63501   out-of-bag 0.36499   1-1/e = 0.63212
# n=  1000  in-bag 0.63211   out-of-bag 0.36789   1-1/e = 0.63212
# n= 10000  in-bag 0.63216   out-of-bag 0.36784   1-1/e = 0.63212

The table averages 2,000 bootstrap samples at each size. At \(n=1000\), it reports 0.63211, close to the limiting 0.63212 but not identical at the printed precision. Both finite sample size and simulation variation matter. Rows absent from a tree’s bootstrap sample are out-of-bag (OOB) for that tree. To predict one training row without using trees fitted on it, average only those trees’ predictions. Different rows use different subsets of trees.

OOB scoring reuses trees already fitted for the ensemble, avoiding several separate training runs. It still requires predicting and aggregating the excluded rows. It is not the same procedure as leave-one-out cross-validation, and its bias need not have a fixed sign. Ordinary row-wise OOB evaluation is most useful when randomly held-out rows represent the prediction task. New-group or future-time prediction generally requires group-aware or time-aware evaluation instead.

Tree similarity and predictive performance

At a fixed prediction input, suppose each tree’s prediction has finite variance \(\sigma^2\) across repeated training samples and tree randomness, and every pair has correlation \(\rho\). Expanding the variance of their average gives \(\sigma^2/m+(m-1)\rho\sigma^2/m=\rho\sigma^2+(1-\rho)\sigma^2/m\). If these quantities remain fixed as trees are added, the second term approaches zero while the first remains. For \(\sigma^2=1\) and \(\rho=0.2\), the variance is 0.28 at 10 trees, 0.208 at 100, and 0.2008 at 1,000. Gains diminish; they do not stop at a universal tree count.

Random forests choose a new random subset of candidate features at each split. Restricting max_features can make trees less similar by preventing a strong feature from being available everywhere. It can also weaken individual trees, and it does not force different trees to choose different features. We compare those effects on a synthetic regression problem.

import numpy as np
from sklearn.ensemble import RandomForestRegressor
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split

X, y = make_regression(n_samples=800, n_features=20, n_informative=10,
                       noise=8.0, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.4, random_state=0)

print(f"{'max_features':>13} {'pred corr':>10} {'single R2':>10} {'ensemble R2':>12}")
for mf in (1, 3, 7, 20):
    m = RandomForestRegressor(n_estimators=60, max_features=mf,
                              random_state=0).fit(X_tr, y_tr)
    P = np.column_stack([t.predict(X_te) for t in m.estimators_])   # rows are inputs; columns are trees
    corr = np.corrcoef(P.T)[np.triu_indices(len(m.estimators_), 1)].mean()
    single = np.mean([t.score(X_te, y_te) for t in m.estimators_])
    print(f"{mf:13d} {corr:10.4f} {single:10.4f} {m.score(X_te, y_te):12.4f}")
#  max_features  pred corr  single R2  ensemble R2
#             1     0.0691    -0.5726       0.4010
#             3     0.1874    -0.2305       0.6154
#             7     0.3383     0.0617       0.7254
#            20     0.4654     0.2270       0.7481

The array P has one row per held-out input and one column per tree. The correlation column averages pairwise correlations of these prediction columns across inputs. It is not an estimate of the fixed-input, repeated-training correlation \(\rho\) in the formula above: it includes variation in the signal as inputs change. Even two accurate models can have highly correlated predictions. Here max_features=1 gives low prediction correlation but mean individual-tree R² of −0.57 and ensemble R² of 0.401. Negative R² means a larger squared error than the constant held-out-target mean used in the score’s denominator.

At max_features=20, all features are available and the estimator acts as bagging of randomized-tie-breaking regression trees. Mean individual-tree R² rises to 0.227 and the ensemble reaches 0.748, the best of the four settings tested. These settings change individual errors as well as dependence, so minimizing the displayed correlation is not the tuning objective. Select by predictive performance on validation data; the test comparisons here illustrate behavior and should not become a repeatedly optimized final test.

In scikit-learn’s random forests, the default feature count per split is approximately \(\sqrt p\) for classification and all \(p\) features for regression. These are starting settings, not consequences of a voting theorem. The classifier averages tree class probabilities and chooses the class with the largest average; it does not generally take a hard majority vote of tree labels. Correlated, unequal-quality trees also do not satisfy the independent, identical-voter assumptions of the simple Condorcet calculation.

Extremely randomized trees

For numeric features, Extra Trees draws a random candidate threshold within each selected feature’s range at the node, then chooses the best valid split among those candidates. By default it fits every tree to the whole training set (bootstrap=False), while the random forest uses bootstrap samples. The following comparison changes both threshold selection and sampling. It cannot isolate either change on its own.

import numpy as np, time
from sklearn.ensemble import RandomForestRegressor, ExtraTreesRegressor

for name, cls in (("RandomForest", RandomForestRegressor),
                  ("ExtraTrees", ExtraTreesRegressor)):
    t0 = time.perf_counter()
    m = cls(n_estimators=200, random_state=0, n_jobs=1).fit(X_tr, y_tr)
    fit_ms = (time.perf_counter() - t0) * 1000
    P = np.column_stack([t.predict(X_te) for t in m.estimators_])
    corr = np.corrcoef(P.T)[np.triu_indices(200, 1)].mean()
    single = np.mean([t.score(X_te, y_te) for t in m.estimators_])
    print(f"{name:13s} pred corr {corr:.4f}"
          f"  single R2 {single:.4f}  ensemble R2 {m.score(X_te, y_te):.4f}")
    print(f"{name} fit time {fit_ms:.1f} ms")
# RandomForest  pred corr 0.4659  single R2 0.2303  ensemble R2 0.7563
# RandomForest fit time 625.2 ms # varies by machine
# ExtraTrees    pred corr 0.4407  single R2 0.2241  ensemble R2 0.8062
# ExtraTrees fit time 420.9 ms # varies by machine

Extra Trees reaches held-out R² about 0.806 here, compared with about 0.756 for the random forest. Fit times are one measurement per estimator and depend on hardware, implementation, and system load. Random thresholds avoid searching all threshold locations, which can reduce computation; Extra Trees still has to evaluate candidates and partition the rows. Using every training row also changes the work per tree. The measured ratio is not a universal speedup.

A randomly chosen threshold can give less immediate training impurity reduction than the best threshold among the same valid candidates. That does not by itself establish greater population bias or smaller variance for the completed ensemble. Noise level, sample size, feature representation, and tree settings all affect the result. This one synthetic dataset does not establish a rule that Extra Trees wins on noisy data and loses on clean data.

Limits of averaging

For a fixed distribution of base learners, the expected average prediction equals their common expected prediction. Averaging alone therefore preserves that bias while reducing the part of variance due to independent random variation. However, fitting to bootstrap samples or changing split rules changes the base-learner distribution and can also change bias relative to a single full-data fit. A stump is a tree with just one split. An average of regression stumps can build an additive staircase with many steps, but it still cannot represent general interactions between features.

With one input feature and constant leaves, every finite tree ensemble is constant beyond its outermost thresholds, though each tree can return a different constant there. With several inputs, this statement applies along an axis while other coordinates are held fixed. Impurity-based feature importance can also retain the preference for features with many split candidates. Combining trees does not convert a measure of training impurity reduction into evidence of population usefulness or causality.

Exercises

1. Diminishing gains from more trees. Track held-out mean squared error as the ensemble grows from 1 to 500 trees. Distinguish the observed error curve from the theoretical variance formula.

Compare the gains from 1 to 10, 10 to 100, and 100 to 500 trees. Check whether every successive recorded value decreases.

import numpy as np
from sklearn.ensemble import RandomForestRegressor
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split

X, y = make_regression(n_samples=1200, n_features=20, n_informative=10,
                       noise=10.0, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.4, random_state=0)

full = RandomForestRegressor(n_estimators=500, random_state=0).fit(X_tr, y_tr)
preds = np.column_stack([t.predict(X_te) for t in full.estimators_])

for m in (1, 2, 5, 10, 25, 50, 100, 250, 500):
    running = preds[:, :m].mean(1)
    mse = np.mean((running - y_te) ** 2)
    print(f"{m:4d} trees   test MSE {mse:9.2f}")
#    1 trees   test MSE  29954.67
#    2 trees   test MSE  21042.83
#    5 trees   test MSE  15802.82
#   10 trees   test MSE  12801.16
#   25 trees   test MSE  12098.94
#   50 trees   test MSE  11699.54
#  100 trees   test MSE  11346.59
#  250 trees   test MSE  11242.22
#  500 trees   test MSE  11168.40

2. Out-of-bag against cross-validation. Compare the OOB score to a 5-fold cross-validated score using the same forest settings, and time both.

Compare the scores and measured costs, remembering that the training-set sizes and the number of trees used per row differ.

import numpy as np, time
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score

X, y = make_classification(n_samples=3000, n_features=20, n_informative=8,
                           random_state=0)

t0 = time.perf_counter()
m = RandomForestClassifier(n_estimators=300, oob_score=True,
                           random_state=0).fit(X, y)
t_oob = time.perf_counter() - t0

t0 = time.perf_counter()
cv = cross_val_score(RandomForestClassifier(n_estimators=300, random_state=0),
                     X, y, cv=5).mean()
t_cv = time.perf_counter() - t0

print(f"OOB accuracy {m.oob_score_:.4f}")
print(f"OOB fit and scoring time {t_oob:.2f} s")
print(f"CV accuracy {cv:.4f}")
print(f"five-fold CV time {t_cv:.2f} s")
print(f"accuracy difference {abs(m.oob_score_ - cv):.4f}")
print(f"time ratio {t_cv / t_oob:.1f}x")
# OOB accuracy 0.9507
# OOB fit and scoring time 1.80 s # varies by machine
# CV accuracy 0.9513
# five-fold CV time 7.06 s # varies by machine
# accuracy difference 0.0007
# time ratio 3.9x # varies by machine

3. Random forests do not fix extrapolation. Fit a forest to a rising trend and predict beyond the training range, then compare against a linear model and against a forest given a detrended target.

You should get: an ensemble that is as flat outside the data as any one of its members.

import numpy as np
from sklearn.ensemble import RandomForestRegressor
from sklearn.linear_model import LinearRegression

rng = np.random.default_rng(0)
x = rng.uniform(0, 10, 600)
y = 2.0 * x + rng.normal(size=600)               # linear conditional mean with additive noise
X = x.reshape(-1, 1)

rf = RandomForestRegressor(n_estimators=300, random_state=0).fit(X, y)
lin = LinearRegression().fit(X, y)

# a forest on the residual after removing a fitted linear trend
resid_rf = RandomForestRegressor(n_estimators=300, random_state=0).fit(
    X, y - lin.predict(X))

print(f"{'x':>6} {'true mean':>8} {'forest':>9} {'linear':>9} {'linear+forest':>15}")
for xq in (5.0, 9.5, 12.0, 20.0, 50.0):
    q = np.array([[xq]])
    print(f"{xq:6.1f} {2 * xq:8.1f} {rf.predict(q)[0]:9.3f}"
          f" {lin.predict(q)[0]:9.3f} {(lin.predict(q) + resid_rf.predict(q))[0]:15.3f}")
#      x true mean    forest    linear   linear+forest
#    5.0     10.0     9.409     9.944           9.409
#    9.5     19.0    20.401    18.977          20.408
#   12.0     24.0    20.091    23.995          24.138
#   20.0     40.0    20.091    40.053          40.196
#   50.0    100.0    20.091   100.270         100.413

References

• Breiman, L. (1996). Bagging Predictors. Machine Learning.
• Breiman, L. (2001). Random Forests. Machine Learning.
• Geurts, P., Ernst, D., & Wehenkel, L. (2006). Extremely randomized trees. Machine Learning.