6.2 Bagging, Random Forests, and OOB: Averaging Can Only Eliminate Incompletely Similar Errors

The Developer Workshop trained several deep trees. They made almost no errors on the training data, but with each new sample, they chose different features at the root node. Instead of asking for "the single correct tree," the intelligence officer instructed multiple trees to make independent predictions, then aggregated their probabilities.

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). $$

In classification, the predicted class probabilities from each tree are averaged, and a decision is made either by thresholding or by selecting the class with the highest probability, rather than simply counting majority votes. Averaging probabilities preserves more information and enables subsequent 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:

$$ \operatorname{Var}(\bar 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.

Thus, the key to Bagging is not just the number of models, but that each individual model carries meaningful signal, while the errors remain not fully correlated.

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.

max_features The smaller this value, 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

Assume X_train/X_valid has already passed through the same leak-free pipeline, and that the rows can be approximated as independent and identically distributed (iid):

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_)

The default metric used by oob_score_ depends on the estimator or API parameters, printing a single value is not sufficient for a complete evaluation. If you need out-of-bag (OOB) probabilities, check oob_decision_function_ and verify that each row received sufficient OOB predictions.

Preprocessing for categorical columns, missing values, and text features should still be encapsulated within the training fold's pipeline. The fact that a particular library version supports NaN does not imply that all forest implementations use the same missing value handling strategy.

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:

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

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.

Forest Size

Increasing n_estimators typically makes the average performance of a finite forest more stable, though it does not equate to the boosting-style iterative noise reduction. However, gains tend to plateau, while training, memory, and inference costs continue to rise.

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.

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 probability is the average of many leaf probabilities. It may be smoother than individual tree outputs, but it does not automatically calibrate. Factors such as small leaf sizes, class weighting, and distribution shifts can all affect the resulting probability estimates.

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.

Calibrators must be trained on data not seen during the forest training phase, or via cross-validation.

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 forest size, peak memory usage, single-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.

The next lesson moves beyond parallel averaging of independent trees and instead introduces sequential tree addition, where each step adjusts the model in the direction of minimizing current loss.