Bagging and Random Forests

Bagging fits a high-variance learner on resampled data and averages the results, while random forests add feature randomness so the trees do not all make their first splits from the same dominant predictors.

The aim is not to create one perfect tree. It is to build strong trees whose errors are different enough that averaging reduces variance.

Averaging only pays when the thing being averaged is unstable. Leo Breiman put numbers on that in 1994, in a paper called Bagging Predictors. The method is one “for generating multiple versions of a predictor and using these to get an aggregated predictor”, the versions “formed by making bootstrap replicates of the learning set”. He names the condition under which it works: “The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.”

He tried five regression problems, using 25 bootstrap replications and averaging over 100 random splits. Mean squared test-set error fell from 19.1 to 11.7 on Boston Housing. On the ozone data it fell from 23.1 to 18.0. On Friedman's three simulated problems it fell from 11.4 to 6.2, from 30,800 to 21,700 and from 0.0403 to 0.0249. Those are decreases of 39%, 22%, 46%, 30% and 38%. No new data arrived. The same learner was simply run again on resampled copies of what he already had.

Classification aggregates votes or class probabilities. Regression averages numeric leaf predictions.

The additional randomness changes diversity and correlation.

How much that extra randomness is worth was settled by brute force in 2014. Fernández-Delgado and colleagues ran “179 classifiers arising from 17 families” over “121 data sets, which represent the whole UCI data base (excluding the large-scale problems) and other own real problems”. Their result: “The classifiers most likely to be the bests are the random forest (RF) versions, the best of which (implemented in R and accessed via caret) achieves 94.1% of the maximum accuracy overcoming 90% in the 84.3% of the data sets.” The margin over the runner-up is not the finding. “The difference is not statistically significant with the second best, the SVM with Gaussian kernel implemented in C using LibSVM, which achieves 92.3% of the maximum accuracy”. The family is the finding: “The random forest is clearly the best family of classifiers (3 out of 5 bests classifiers are RF), followed by SVM (4 classifiers in the top-10)”.

Two later benchmarks re-ran the question against the current generation of learners. The first defined 45 datasets for NeurIPS 2022 and released “every point of a 20 000 compute hours hyperparameter search for each learner”, roughly 400 random-search iterations per dataset. Its abstract states the outcome: “Results show that tree-based models remain state-of-the-art on medium-sized data (∼10K samples) even without accounting for their superior speed.”

The second put a rank on it. McElfresh and colleagues ran 19 algorithms over 176 OpenML classification datasets and trained 538,650 models. Over 98 of those datasets, plain RandomForest has mean rank 8.26 (median 7) and mean normalized accuracy 0.76. That is ahead of LightGBM at 8.46 and of six of the ten neural networks listed, and behind CatBoost at 5.50 and XGBoost at 6.87. The single DecisionTree it is assembled from sits at mean rank 11.81 and accuracy 0.59. Averaging the same base learner moves it from rank 11.81 to rank 8.26.

Extremely randomized trees, the fourth family in the comparison, are defined by their own authors rather than by folklore. Two things separate them from a forest: “Its two main differences with other tree-based ensemble methods are that it splits nodes by choosing cut-points fully at random and that it uses the whole learning sample (rather than a bootstrap replica) to grow the trees.” The second departure is deliberate and directional: “The usage of the full original learning sample rather than bootstrap replicas is motivated in order to minimize bias.” Their defaults are K=√n candidate attributes in classification and K=n in regression, nmin=2 for classification and 5 for regression, and M=100 trees. scikit-learn 1.9.0 implements that whole contrast in one flag: bootstrap=True for random forests, bootstrap=False for extra-trees.

If trees make independent zero-mean errors, averaging cancels much of the noise. Real trees are not independent, because they share data, features and target structure.

Breiman turned that dependence into an inequality. His 2001 paper on random forests opens by naming the two quantities that matter: “The generalization error of a forest of tree classifiers depends on the strength of the individual trees in the forest and the correlation between them.” Theorem 2.3 bounds the error as PE* ≤ ρ̄(1−s²)/s², where s is the strength of the individual trees and ρ̄ the mean correlation of their raw margins. The c/s² ratio is defined as ρ̄/s² — “the smaller it is, the better”. One quantity to raise, one to lower. Feature randomness is the lever on the second.

An independent survey by Biau and Scornet picks out the same result as the central one in the field: “The most celebrated theoretical result is that of Breiman (2001), which offers an upper bound on the generalization error of forests in terms of correlation and strength of the individual trees.”

The size of the gap that produces is in his Table 2. The small UCI sets there are run with 100-tree forests, a random 10% held out, and the whole thing repeated 100 times. Across the table, the out-of-bag error of the individual trees inside the forest stands against the forest's own test error: 36.9% against 20.6% on glass, 40.6% against 25.1% on liver, 31.7% against 15.9% on sonar, 25.7% against 4.9% on ringnorm and 19.8% against 3.5% on letters. On ringnorm the trees are wrong 25.7% of the time and the forest they compose is wrong 4.9% of the time.

A forest still inherits biased labels, missing populations, leakage and the limits of axis-aligned partitions. The bound has a term for correlation. It has no term for a wrong problem.

They can combine thresholds and interactions without requiring explicit polynomial design. The same averaging that makes them robust also fixes a hard ceiling on what they can ever predict.

That ceiling is arithmetic, not a rule of thumb. A forest prediction is Ŷ(X₀)=Σ wᵢ(X₀)Yᵢ, with nonnegative weights that sum to one, which gives min Yᵢ ≤ Ŷ(X₀) ≤ max Yᵢ. Three statisticians at Iowa State wrote the consequence out in 2017: “As a consequence, the predictions given by random forests are always within the range of response values in the training dataset, which is problematic if the response values in the target dataset tend to fall outside this range.”

It cost them a real forecast. On county-level Iowa corn yields across 28 growing seasons, “the root mean square error (RMSE) of random forests for predicting 2015 corn yield was slightly more than 10% higher than the RMSE of multivariate linear regression”. Temperature and precipitation had fallen beyond the training ranges, and every forecast was bounded above by the largest yield already in the data. Jeong and ten co-authors reached the same conclusion independently in 2016: “With RF, only the values included in training data are used for splitting regression trees and thus lumping the predictions for the conditions outside the range of training data.”

Tree count is one setting, and two independent studies place it near the bottom of the list.

Tuning a random forest buys less than tuning almost anything else. Probst and colleagues measured it in 2019, benchmarking six algorithms on 38 binary OpenML100 datasets. Random forest scored the lowest overall AUC tunability of the six: 0.010 against package defaults and 0.006 against optimal defaults, against 0.056 for SVM, 0.069 for elastic net and 0.043 for xgboost. Inside the forest the ranking is just as lopsided. mtry is the most tunable parameter at 0.006, while num.trees and min.node.size are worth 0.001 each. The same study reports an optimal default for mtry of p·0.257 rather than the package's √p.

A different method finds the same two knobs. Van Rijn and Hutter applied functional ANOVA to 100 datasets in 2018: “The results reveal that most of the variance could be attributed to a small set of hyperparameters: the minimum samples per leaf and maximal number of features for determining the split were most important.”

Leaf support and the candidate-feature count are therefore where the tuning budget goes. Growing more trees mostly buys stability.

What you are tuning away from is also not one thing. The randomForest package in R, version 4.7-1.2, fixes ntree=500, mtry=max(floor(ncol(x)/3), 1) for regression and floor(sqrt(ncol(x))) for classification, nodesize=5 for regression and 1 for classification, replace=TRUE, and sampsize=ceiling(.632*nrow(x)) when sampling without replacement. scikit-learn 1.9.0's RandomForestClassifier instead arrives with n_estimators=100, max_features='sqrt', min_samples_leaf=1, min_samples_split=2, max_depth=None and bootstrap=True. Its user guide then recommends something different again for regression: “Empirical good default values are max_features=1.0 or equivalently max_features=None (always considering all features instead of a random subset) for regression problems, and max_features="sqrt" (using a random subset of size sqrt(n_features)) for classification tasks (where n_features is the number of features in the data).” The same algorithm, five times fewer trees, and in regression every feature considered at every split.

These outputs can be useful. They are not calibrated risk, and that has been measured rather than suspected.

The measurement ran ten learning algorithms over eight classification problems: Niculescu-Mizil and Caruana, “Predicting Good Probabilities With Supervised Learning”, ICML 2005. Random forests, Niculescu-Mizil and Caruana found, “are less clear cut”: well calibrated on some problems, but “poorly calibrated on LETTER.P2, and not well calibrated on HS, COV TYPE, MEDIS and LETTER.P1”. The reliability plots come out sigmoidal, and the paper names the mechanism: “Methods such as bagging and random forests that average predictions from a base set of models can have difficulty making predictions near 0 and 1 because variance in the underlying base models will bias predictions that should be near zero or one away from these values.”

Deep leaves create extreme local frequencies, and averaging pulls them back from the ends of the scale. That is still visible in current software. The scikit-learn 1.9.0 user guide reports that “RandomForestClassifier shows the opposite behavior: the histograms show peaks at probabilities approximately 0.2 and 0.9, while probabilities close to 0 or 1 are very rare.”

The remedy is a separate fitted step, not a larger forest. Before calibration, Niculescu-Mizil and Caruana found the best models were random forests, bagged trees and neural nets; after Platt scaling or isotonic regression the best were boosted trees, random forests and SVMs. Evaluate calibration separately and choose thresholds using deployment costs.

Trees are independent enough to fit and score in parallel, which makes forests operationally attractive. What that costs has been benchmarked in gigabytes and hours.

Six implementations of the same algorithm were run on one simulated genome-wide association dataset, on a 128 GB node. Peak memory was 39.05 GB for randomForest, 105.77 GB for its multicore variant, 46.82 GB for randomForestSRC, over 128 GB for Rborist, 11.26 GB for ranger and 0.24 GB for ranger in save-memory mode. Runtime at mtry=5,000 ranged from 101.24 hours down to 0.56 hours. On a plainer 100,000-sample, 100-feature problem with 1,000 trees, randomForest used 7.76 GB and 25.88 minutes against ranger's 3.11 GB and 0.69 minutes. The benchmark is ranger's own, and Wright and Ziegler state the conclusion in their abstract: “Finally, we show that ranger is the fastest and most memory efficient implementation of random forests to analyze data on the scale of a genome-wide association study.” One dataset, one algorithm, and a spread from 0.24 GB to over 128 GB and from 0.56 to 101.24 hours depending only on which implementation was loaded.

scikit-learn documents the same pressure from the model side. The size of a fitted model with default parameters is O(M·N·log N) in the number of trees M and samples N, and the guide adds a warning about those defaults: “Bear in mind though that these values are usually not optimal, and might result in models that consume a lot of RAM”. Compression, estimator count, depth, batching, and hardware should be part of model selection.