6.2 Bagging, Random Forests, and OOB: How Error Correlation Limits Averaging

A deep tree can fit training data closely yet choose a different root split after a small change in the sample. Averaging trees trained on resampled data can reduce this instability. Adding more trees helps only when their errors are not perfectly correlated.

This is the core idea behind bagging: repeatedly sampling, fitting, and averaging unstable learners. Random forests further reduce correlation between trees by limiting the set of candidate features at each node, actively lowering the similarity between individual trees.

Learning Objectives

• Understand how bootstrap aggregation reduces variance;
• Explain the randomness in sampling and feature selection within random forests;
• Correctly use out-of-bag (OOB) estimation and recognize scenarios where it fails;
• Distinguish between impurity-based importance and permutation importance;
• Evaluate models beyond accuracy, considering probability calibration, resource costs, and deployment behavior.

1. Training and Prediction in Bagging

When there are $n$ rows of training data, each base learner draws $n$ samples with replacement from these $n$ rows. Different bootstrap samples will omit some rows and repeat others.

For $B$ regression models:

$${\hat{f}}_{bag}(x)=\frac{1}{B}\sum _{b=1}^B{\hat{f}}_b(x).$$

Classification ensembles may use majority voting or average class probabilities. The scikit-learn forest below averages probabilities, preserving scores for later threshold selection and calibration.

2. Why "More" Isn't Enough

If each tree has the same error variance ${\sigma }^2$ at a given input and the pairwise correlation coefficient is approximately $\rho$, then the variance of the average error is:

$$\mathrm{Var}(\overline{e})=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2.$$

As $B$ increases, the second term diminishes, but correlated errors remain. If all trees consistently split on the same batch of samples and the same strong features, the marginal benefit of adding more trees will quickly diminish.

For example, with ${\sigma }^2=1$ and $\rho =0.2$, increasing $B$ from 10 to 100 reduces variance from 0.28 to 0.208, approaching 0.2 rather than zero. This calculation concerns variance; it does not remove a shared systematic bias.

3. How Random Forests Reduce Correlation

Random forests typically combine two sources of randomness:

1. Each tree is trained on a different bootstrap sample;
2. At each node, the algorithm searches for the best split among a randomly selected subset of features.

The smaller max_features is, the less similar the trees tend to be, though individual trees may become weaker. The optimal balance is determined by feature redundancy, sample size, and target loss.

It's important not to conflate several similar models:

• Bagging tree: Uses bootstrap sampling, and at each node considers all available features;
• Random forest: Uses bootstrap sampling and randomly selects a subset of features at each node;
• Extra Trees: Further randomizes the selection of candidate split thresholds, with specific sampling behavior depending on implementation parameters.

4. A Reproducible Training Skeleton

This Python 3 fragment was checked with scikit-learn 1.9.0. Supply separate training and validation arrays with usable numeric features and labels 0/1, with both classes in each set. Rows are assumed approximately IID. For the OOB interpretation below, no data-fitted preprocessing has been applied across all training rows.

from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import log_loss, roc_auc_score

forest = RandomForestClassifier(
    n_estimators=500,
    max_features="sqrt",
    min_samples_leaf=5,
    bootstrap=True,
    oob_score=True,
    n_jobs=1,
    random_state=42,
)
forest.fit(X_train, y_train)

valid_probability = forest.predict_proba(X_valid)[:, 1]
print("validation log loss:", log_loss(y_valid, valid_probability))
print("validation ROC AUC:", roc_auc_score(y_valid, valid_probability))
print("OOB score:", forest.oob_score_)

With oob_score=True, this classifier reports OOB accuracy. For probability metrics, use oob_decision_function_ and verify that each row received sufficient OOB votes. These scores evaluate the forest under its sampling assumptions, not an entire pipeline whose preprocessing saw every training row.

Categorical, missing, or text features still require a preprocessing policy fitted within each training fold. NaN support in one library version does not establish identical behavior in other implementations.

5. Where Does Out-of-Bag Come From?

The probability that a particular row is never selected in a single tree during $ n $ with-replacement samples is:

$${(1-\frac{1}{n})}^n\to e^{-1}\approx 36.8\mathrm{\%}.$$

Thus, we can use the trees that did not include a given row to generate out-of-bag predictions. By aggregating these predictions, we can estimate generalization metrics without having to set aside a separate portion of the data.

However, out-of-bag is not a universal validation set:

• Rows from the same user or device may have already been included in that tree, leading to group leakage;
• Time-series bootstrap can cause future records to inform predictions about past ones;
• If preprocessing steps (such as imputation, encoding, or feature selection) are performed on the full dataset before training, OOB cannot prevent preprocessing leakage;
• Repeatedly tuning hyperparameters by examining OOB results means the OOB data has already been used in model selection, so an independent test set is still required for final evaluation.

When group or temporal structure exists, prefer group/time-aware validation methods.

6. How Key Capacity Parameters Interact

Tree Capacity

max_depth, min_samples_leaf, and max_leaf_nodes determine how finely a single tree can split. A fully expanded tree is not a requirement for a random forest; in cases with high noise or critical probability estimation, larger leaf nodes often provide greater stability.

Number of Trees in the Random Forest

Increasing n_estimators makes the finite forest average more stable. It does not add successive corrections as boosting does, but benefits plateau while training, memory, and inference costs continue growing.

Sample and Feature Sampling

max_samples controls how many rows each tree sees, while max_features governs the pool of candidate columns at each node. Together, they influence tree strength, correlation, and computational cost.

Class/Instance Weights

class_weight or sample_weight alter the splitting objective and leaf probabilities. They can reflect cost-sensitive or sampling designs, but may introduce inaccuracies in the estimated probabilities over the original target distribution, requiring separate calibration.

7. The Limitations of MDI Importance

Many implementations of feature_importances_ aggregate the mean decrease in impurity (MDI) across features. It's computationally cheap and widely used, but it comes with clear limitations:

• It is computed on training data, which may inadvertently reward overfitting splits;
• Features with many candidate splits (such as continuous or high-cardinality features) tend to achieve higher importance scores;
• Correlated features often split importance, either diluting or substituting each other’s contributions;
• MDI measures how a model uses columns, not the causal impact of those columns on the outcome.

Do not simply remove other features based on MDI scores and then claim improved performance on the same validation set.

8. Permutation Importance Also Requires Proper Problem Framing

Randomly shuffle a column on held-out data and observe the drop in model performance:

from sklearn.inspection import permutation_importance

result = permutation_importance(
    forest,
    X_valid,
    y_valid,
    scoring="neg_log_loss",
    n_repeats=20,
    random_state=42,
    n_jobs=1,
)

This estimates "how much performance a trained model loses when that column is disrupted under the current validation distribution." It still does not capture a causal effect. When features are strongly correlated, shuffling one column leaves the other carrying similar signal, so individual feature importance may be artificially low.

Shuffling correlated columns can also create combinations absent from real data, making the measured drop misleading in the opposite direction.

To improve this:

• Perform grouped permutation on sets of correlated features;
• Estimate importance across multiple time slices or groupings to assess stability;
• Use partial dependence, ICE, or ALE to examine response shapes, while clearly stating the distributional assumptions;
• Combine domain knowledge with stability analysis, rather than relying on a single ranking.

9. Probability, Calibration, and Thresholds

Forest probabilities average leaf probabilities. They can be smoother than one tree’s estimates without being calibrated; small leaves, class weights, and distribution changes still matter.

Evaluation should be split into distinct components:

• discrimination: ROC AUC/AUPRC, ranking performance;
• probability quality: log loss, Brier score, reliability curve;
• decision: recall, cost, or net gain under fixed capacity;
• stability: variation across folds, time windows, and random seeds.

Fit a calibrator on predictions for data the forest did not train on, using a held-out set or cross-fitting.

10. Engineering Costs

Trees can parallelize both training and inference, but n_jobs=-1 does not imply resource-free usage:

• Training processes may copy data, increasing peak memory consumption;
• Large, deep trees amplify model size, cold-start times, and tail latency;
• Online concurrency and internal parallelism within a single request can compete for CPU resources;
• Reproducibility requires fixed random seeds, versioned dependencies, and specific thread configurations.

For tabular data, random forests represent a strong baseline worth considering, though they are not universally the first model to choose. Sparse, high-dimensional text, smooth extrapolation, strict latency constraints, or additive interpretability requirements may make linear models, GAMs, or other approaches more suitable.

Common Misconceptions

• Adding more trees eliminates all error: Residual errors and systematic biases still persist.
• OOB equals independent test: Tuning, grouping, temporal leakage, and preprocessing leakage all compromise its validity.
• feature_importances_ is an objective feature value: It's actually a biased statistical summary from model usage.
• Random forests must grow individual trees to maximum depth: Tree capacity needs to be validated empirically.
• Not standardizing means no preprocessing is needed: Categorical variables, missing data, time-based leakage, and data leakage still require proper handling.

Exercise

1. Record validation error and tree-prediction correlation using different values of $B$ and max_features.
2. Compare out-of-bag (OOB) validation with independent validation, and then reproduce data leakage when observing multiple user rows.
3. Introduce a high-cardinality noise column and compare MDI with held-out permutation importance.
4. Measure ensemble size, peak memory, per-request latency, and batch throughput.

Summary

Bagging reduces variance in unstable learners by averaging, while random forests further decrease correlation between trees through random feature selection. Out-of-bag (OOB) estimates, feature importance, and probability outputs are all valuable, but each addresses only a limited question; each must be used within the correct data splitting and evaluation protocol.

Gradient boosting instead adds trees sequentially, with each step adjusting the model in the direction of lower current loss.