9 From single trees to random forests: Leo Breiman and the logic of ensemble learning

Bagging with decision trees. Bootstrap sampling creates multiple training sets by drawing observations with replacement, so each sample contains duplicated and omitted observations. A separate decision tree is trained on each sample using the same procedure. The trees’ predictions are then combined by majority vote for classification or averaging for regression, producing a more stable final prediction.

Feature subsampling in a random forest. The simplified example represents two trees trained to evaluate the same type of loan application. To isolate feature-level randomness, both trees are shown using the same training data. At the illustrated split, the first tree is permitted to consider only Age and Income, while the second can consider only Balance and Tenure. After evaluating the candidates available to it, the first tree selects Age ≤ 45 and the second selects Balance > X, where X represents the threshold that best satisfies the splitting criterion. These different initial decisions send applicants into different branches and influence every split that follows. In a complete random forest, each tree also receives a different bootstrap sample, and a new random subset of features is selected at every node. The trees and candidate sets shown here are deliberately simplified to isolate how feature selection creates structural diversity.

Permutation importance using out-of-bag observations. The forest first establishes baseline predictions and error using observations that were omitted from the bootstrap samples of the trees evaluating them. The values of feature X are then randomly shuffled among those observations, disrupting the relationships carried by that feature while leaving the other feature columns unchanged. Without retraining the forest, the same trees recalculate their predictions from the modified data. The increase from baseline error to permuted error measures how much predictive performance depended on feature X. In Breiman’s original procedure, the error increase is calculated within each tree’s out-of-bag observations and then averaged across the forest.

• A decision tree learns through greedy recursive splitting. At each node, it selects the feature and splitting rule that produce the greatest immediate improvement, continuing until predictions are assigned at its leaves. Trees support classification and regression, capture nonlinear relationships and interactions, accommodate different variable types, and provide a decision structure that can be inspected directly.
• The flexibility of a single tree also makes it unstable. Small changes in the training data can alter an early split and propagate throughout the remaining structure. Increasing depth allows the tree to capture more signal but also more noise, producing high variance and overfitting. Pruning can reduce these effects, but the resulting tree still depends on one training sample.
• Breiman’s 1996 bagging method addressed instability through bootstrap sampling and aggregation. Each tree is trained on a sample created by drawing observations with replacement from the original data. Classification predictions are combined by voting, while regression predictions are averaged. Bagging reduces variance without requiring the individual trees to surrender their expressive power.
• Breiman’s 2001 random forests retained bagging and added randomness to the features considered at each split. Each constituent tree otherwise follows the ordinary decision-tree process, but it receives its own bootstrap sample and a new random subset of candidate features at every node. Predictions from the resulting trees are then aggregated into one forest prediction.
• Feature randomness prevents dominant predictors from shaping every tree in the same way. Temporarily withholding those predictors forces some trees to use other informative features, producing different early splits and structures. Considering fewer features can weaken an individual tree, but the resulting reduction in correlation can strengthen the forest by making aggregation more effective.
• Generalization depends on balancing the predictive strength of the trees against the correlation among their behavior. For classification forests, margins measure the voting advantage of the known class over its strongest incorrect competitor, and average margin defines forest strength. Strong trees with highly correlated errors provide limited gains, while diverse but weak trees provide too little reliable information.
• Adding trees to a forest differs from increasing the depth of one tree. Additional independently randomized trees stabilize class-vote proportions or averaged regression predictions, causing the forest to approach a limiting result. More trees cannot correct data leakage, poor features, unsuitable settings, or weak and highly correlated learners; they cause the forest to converge more precisely toward the result implied by its design.
• Out-of-bag observations provide an internal means of evaluating predictive performance. Each observation is predicted using only trees whose bootstrap samples omitted it. Comparing these predictions with known outcomes produces classification or regression error estimates without requiring a separate validation procedure, although an independent test set remains valuable after model selection and tuning.
• Variable importance recovers a measure of the interpretation lost when one visible tree becomes a forest. Permutation importance measures how much out-of-bag error increases when a feature is disrupted, while impurity-based importance accumulates its contributions to improved splits. Both require caution because correlated predictors, splitting opportunities, and proxy relationships can distort scores, and predictive importance does not establish causality.
• Support vector machines and random forests offered two enduring answers to the generalization problem. Vapnik controlled variability within one model through geometry, margin, and constraint. Breiman reduced variability across many models through sampling, feature randomness, and aggregation. Random forests demonstrate that reliable learning can emerge not only by restricting complexity, but also by organizing it into a stable and understandable system.

FAQ