Bagging, Randomization, and Out-of-Bag Evaluation

A finite training set is only one sample from the process you care about. An unstable learner can react strongly to which rows happened to appear. Bagging makes that instability visible and useful. It creates many bootstrap samples, trains one model on each sample, and aggregates their predictions. A bootstrap sample is drawn with replacement and usually has the same number of rows as the original training set. Some rows appear multiple times. Others are absent. Across many samples, each model sees a slightly different version of the evidence.

Fifty bagged CART trees lowered the average misclassification rate on all seven datasets Leo Breiman tested in 1996. Waveform fell from 29.1% to 19.3%, a 34% decrease. Heart went from 4.9% to 2.8%, a 43% decrease. Breast cancer 5.9% to 3.7% (37%). Ionosphere 11.2% to 7.9% (29%). Glass 30.4% to 23.6% (22%). Soybean 8.6% to 6.8% (21%). Then diabetes: 25.3% to 23.9%, a decrease of 6%. That last pair is the reason bagging is not a generic accuracy switch. The identical procedure that removed a third of the error on waveform removed six percent of it on diabetes.

An independent study over 23 datasets, published in 1999, reached the same qualitative conclusion. The abstract by Opitz and Maclin marks the edges of it: “First, while Bagging is almost always more accurate than a single classifier, it is sometimes much less accurate than Boosting.”

A highly stable learner may produce nearly identical models across bootstrap samples, leaving little variance to remove. The technique is especially natural for deep decision trees and other flexible, high-variance estimators.

The process is simple, but each step changes what you can later measure. Draw bootstrap samples by resampling rows with replacement. Fit one base learner per sample, usually with separate randomness. Predict with every member, producing a score, probability, or class from each. Aggregate by averaging numeric outputs or by combining class probabilities and votes. Then audit stability: compare aggregate performance, variance across seeds, and failure slices.

The second step is where the guarantee is most often lost. Each member has to be fitted independently on its own resample. If a preprocessing stage sees the full dataset first, the members stop being independent fits of one procedure. The aggregate then stops behaving like an average over plausible training worlds.

The fifth step is not optional bookkeeping either. Set the spread of a single member across seeds against the spread of the ensemble. That comparison is the only direct evidence that the aggregation did anything at all.

A row omitted from a member's bootstrap sample can be predicted by that member without direct training exposure. How many such rows there are is fixed by the arithmetic of the bootstrap, and Breiman stated it plainly in 2001: “In each bootstrap training set, about one-third of the instances are left out.” Every out-of-bag prediction is therefore assembled from roughly a third of the forest, never from all of it.

The same mechanic has a quantitative restatement. An out-of-bag prediction uses on average only exp(-1)·T of the T trees grown. So a performance curve measured on independent test data converges faster than the out-of-bag curve by a factor of 2.7, as Probst and Boulesteix put it. That gap is not a defect in the estimate. It is the price of never having spent a row on a test set. It also fixes the direction of the bias: a third of a forest is a smaller forest, and a smaller forest scores worse.

All three aggregate trees, but they inject randomness at different points. Bagged trees randomise the rows and leave the ordinary split search alone. A random forest randomises the rows and, at every split, restricts which features may compete. That restriction is what pulls the trees apart from one another.

Extremely randomized trees drew the third line in 2006. The paper that introduced them states the difference in one sentence: “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.” Its defaults are K=sqrt(n) for classification and K=n for regression, and every ensemble in its experiments was grown to M=100 trees. The saving is measured rather than asserted: an average computing-time ratio of 0.36 against Random Forests over the twelve classification datasets, and about 10x faster than Tree Bagging.

scikit-learn implements exactly this split. The documentation gives bootstrap=True as the default for random forests and bootstrap=False for extra-trees. Read that line carefully before you reach for out-of-bag scores. With the documented default, the third method does not bootstrap at all, so there is no out-of-bag set to score against.

These are empirical clues, not guarantees, and the cleanest way to read them is against a case where every clue is absent. Bagged nearest-neighbour classifiers come back with the rate they started with. Breiman ran 100 bootstrap replicates over 100 iterations on six of the same datasets and got identical rates unbagged and bagged: waveform 26.1/26.1, heart 5.1/5.1, breast cancer 4.4/4.4, ionosphere 36.5/36.5, diabetes 29.3/29.3, glass 30.1/30.1. His explanation is that each bootstrap replicate retains about .632 of the cases, which is not enough perturbation to move a stable rule. His own summary is blunter: “Cycles did not have to be expended to find that bagging nearest neighbors does not change things.” Bühlmann and Yu later formalised why the gain is confined to unstable, hard-decision estimators, in a 2002 analysis. The same protocol that cut tree error by up to 43% left this learner unchanged to the decimal on all six datasets.

The last clue, latency, has been settled in production. Microsoft Kinect classified depth-image pixels into 31 body parts using a forest of just 3 trees of depth 20. The randomisation was pushed into the training data instead: each tree was fitted to a different set of randomly synthesised images, 300k images per tree and 2,000 sampled pixels per image. Training 3 trees to depth 20 from 1 million images took about a day on a 1,000-core cluster. The inference budget is why the ensemble stayed at three. The 2011 paper by Shotton and his co-authors says why: “An optimized implementation of our algorithm runs in under 5ms per frame (200 frames per second) on the Xbox 360 GPU, at least one order of magnitude faster than existing approaches.”

Out-of-bag predictions are convenient, but what they mean depends on how rows relate to one another. The cost of getting that wrong has been measured on one model and one dataset. A random forest was trained on a forest inventory of 11.8 million trees in central Africa. Under standard random 10-fold cross-validation it scored R2 = 0.53 with RMSPE 56.5 Mg/ha. Under a spatial 44-fold cross-validation it scored R2 = 0.14 with RMSPE 77.5 Mg/ha. Same model, same data. Only the resampling changed. Ploton and colleagues published the comparison in Nature Communications in 2020, and their abstract states it flatly: “A standard nonspatial validation method suggests that the model predicts more than half of the forest biomass variation, while spatial validation methods accounting for SAC reveal quasi-null predictive power.” Meyer and colleagues reached the same conclusion independently in 2019, with Random Forest case studies. An ordinary row bootstrap makes exactly the assumption the random 10-fold split made.