Random Forests, annotated

How to read this page

• Any dotted word explains itself when you hover it, tab to it, or tap it, and so does every symbol in every equation.
• The diagrams are live: hover or tap a part to read what it does. Several charts respond to you: one lets you watch a vote settle as trees are added, another shows how the paper's error bound moves with strength and correlation.

Each idea climbs the same ladder: an everyday picture, a tiny example you can check by hand, a diagram, the math, and why it matters today. One small example runs through the page: a forest of ten trees voting on whether four emails are spam. The trees and boosting lesson builds a decision tree and a random forest from scratch in NumPy.

Abstract · original

“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.”Breiman (2001), Abstract

Everyday picture

Ask one doctor for a diagnosis and you get one opinion, with that doctor's blind spots. Ask a hundred doctors who each trained at a different hospital and each looked at a different handful of test results, and take the majority: the blind spots rarely line up, so the majority is right more often than almost any single doctor. Two things decide how good the majority is: how good each doctor is (the paper calls it strength) and how often they make the same mistake (correlation). This paper builds that committee out of decision trees.

What the paper claims

• A random forest is any collection of trees, each grown with its own independent dose of randomness, that vote. Adding trees never makes it overfit: its error settles to a limit (Theorem 1.2).
• The forest's error is bounded by the trees' average correlation divided by the square of their strength (Theorem 2.3), so good randomness lowers correlation without costing much strength.
• Choosing a random handful of inputs at every split (and growing each tree on a bootstrap sample) gives accuracy that compares favourably with Adaboost, is more robust to wrong labels, and is faster.
• The rows each tree never saw give free, built-in estimates of the error, the strength, the correlation and the importance of each input.

Why it matters today

Random forests are still the standard first model on a new table of data: they need almost no tuning, cannot be ruined by adding trees, and report their own validation score. The idea of shuffling one column and measuring the damage, introduced in §10, became permutation importance, one of the most used tools for asking what any model relies on.

1 Random forests · original

“After a large number of trees is generated, they vote for the most popular class. We call these procedures random forests.”Breiman (2001), §1.1

Everyday picture

Before this paper, several people had found ways to grow many different trees from one dataset and let them vote. Bagging gives each tree its own resample of the rows. Random split selection picks each split at random from the best few. The random subspace method gives each tree a random subset of the inputs. Breiman notices they share one skeleton: tree number k is grown from the training data plus a fresh random “recipe card” Θ_k, drawn independently of all the other cards and from the same deck. Any procedure of that shape is a random forest.

Tiny example

In bagging, the recipe card is a list of counts: throw N darts at N boxes, one box per training row, and count how many darts land in each box. With N = 5 emails, one card might read (2, 0, 1, 1, 1): email 1 is used twice, email 2 not at all. Tree 1 is grown on that resample. Tree 2 gets a new card, say (0, 2, 1, 0, 2), and so on. Each tree then votes, and the forest answers with the class that gets the most votes.

Reading it: read from the top down. The training set is resampled K times with replacement (the pink boxes), and each resample grows one full-depth, unpruned tree (the blue boxes). Inside every tree, each node (the highlighted circle in tree 1) may only choose its question from F inputs picked at random for that node. Nothing passes between trees, so they can be grown in any order or on different machines. The trees' answers meet at the vote. The dashed wire is the paper's second idea: for each training row, a vote taken only among the trees whose resample left that row out gives an honest score of the forest without a separate test set.

Why it matters

Naming the common skeleton is what made the theory possible. Because the recipe cards are independent and identically distributed, the law of large numbers applies to the vote, which is the next section's first result. The trees and boosting lesson implements the skeleton as RandomForest, which hands each tree its own bootstrap_sample and its own seed for choosing features.

2 Characterizing the accuracy of random forests · original

Everyday picture

For a single email, think of a referendum. What matters is not only whether the right side won, but by how much: winning 90 to 10 is safe, winning 51 to 49 is one bad day from losing. The paper measures every prediction by that winning lead, the margin, and builds all of its theory on it.

# the ten trees' votes on email A, whose true class Y is spam
votes = ["spam"] * 7 + ["not"] * 3
Y = "spam"
# av_k I(h_k(X) = j): the share of trees voting for class j
def av(j):
    return sum(1 for h_k in votes if h_k == j) / len(votes)
av(Y)  # → 0.7
# max over the wrong classes j ≠ Y
wrong = max(av(j) for j in ["not"])
wrong  # → 0.3
round(av(Y) - wrong, 2)  # → 0.4

# margins for emails A, B, C, D
mg = [0.4, 0.8, -0.2, 0.6]
# P(mg < 0), estimated by the share of negative margins
sum(1 for m in mg if m < 0) / len(mg)  # → 0.25

# two classes: mr = P_Θ(right) − P_Θ(wrong) = 2P − 1
P = 0.7
round(P - (1 - P), 2)  # → 0.4
# s = E_{X,Y} mr: the average margin over the four emails
mr = [0.4, 0.8, -0.2, 0.6]
s = sum(mr) / len(mr)
round(s, 2)  # → 0.4

mr = [0.4, 0.8, -0.2, 0.6]
s = sum(mr) / len(mr)
# var(mr): the average squared distance from s
var_mr = sum((m - s) ** 2 for m in mr) / len(mr)
round(var_mr, 2)  # → 0.14
# the Chebyshev bound var(mr) / s²
round(var_mr / s ** 2, 3)  # → 0.875

# §9, F = 25: strength and mean correlation
s, rho_bar = 0.28, 0.065
# PE* ≤ ρ̄ (1 − s²) / s²
round(rho_bar * (1 - s ** 2) / s ** 2, 3)  # → 0.764
# the c/s² ratio: ρ̄ / s²
round(rho_bar / s ** 2, 2)  # → 0.83

3 Using random features · original

“To improve accuracy, the randomness injected has to minimize the correlation ρ̄ while maintaining strength.”Breiman (2001), §3

Everyday picture

If every doctor on the committee may look at every test result, they all fixate on the same striking one, and they all make the same mistake when it misleads. Hide most results from each doctor at each step of their reasoning, a different random handful each time, and they are forced to reason along different paths. Each doctor gets slightly worse; the committee gets better.

What the paper proposes

Earlier forests (bagging, random split selection, random outputs) did not match Adaboost, the leading method of the time. The forests in this paper choose, at every node, a random small set of inputs (or random combinations of inputs) and split on the best of those only. The paper lists what it gains: accuracy as good as Adaboost and sometimes better, robustness to outliers and noise, speed, internal estimates of error, strength, correlation and importance, and easy parallel training.

Why it matters

Random feature selection at each node is the ingredient that turned bagged trees into random forests. In the lesson's code it is the max_features setting of DecisionTree, which RandomForest sets to the square root of the number of features by default.

import math
N = 5
# (1 − 1/N)^N: missed by every one of the N draws
round((1 - 1 / N) ** N, 3)  # → 0.328
round((1 - 1 / 1000) ** 1000, 4)  # → 0.3677
round(1 / math.e, 4)  # → 0.3679

4 Random forests using random input selection · original

“It was surprising that using a single randomly chosen input variable to split on at each node could produce good accuracy.”Breiman (2001), §4

Everyday picture

The simplest random forest, which the paper calls Forest-RI (random inputs): at each node, draw F of the M inputs at random, find the best split among just those (with the usual CART search), grow the tree to full size, and do not prune.

Tiny example

The paper tries two group sizes on every dataset: F = 1, a single random input per node, and F = int(log₂ M + 1). The sonar data has M = 60 inputs, so the second choice is 6.

In words: “try about as many inputs per node as it takes binary digits to count the inputs.”

With the numbers: sonar, M = 60: log₂ 60 = 5.9, plus 1 is 6.9, so F = 6. Zip-code digits, M = 256: F = 9. The §9 data with M = 1,000 inputs: F = 10, as the paper states.

In Python:

import math
# F = int(log2 M + 1) for sonar, zip-code and the §9 data
[int(math.log2(M) + 1) for M in (60, 256, 1000)]  # → [6, 9, 10]

For each of 13 smaller datasets, the paper sets aside a random 10%, grows 100 trees with each F, keeps the F with the lower out-of-bag error, and scores it on the held-out 10%; it repeats this 100 times and averages. Adaboost gets 50 trees on the same splits.

Reading it: in the bars, grey is Adaboost, blue is Forest-RI and the striped bars are a single tree from the same forest; shorter is better. On most rows the forest and Adaboost are within a point of each other, the forest winning some (vowel, ringnorm) and losing some (German credit). The striking column is the last: each tree alone is far worse (30.4% on vowel against 3.4% for the forest). The forest is not a collection of good trees; it is a good committee of mediocre ones. The paper notes that the average gap between F = 1 and the larger F is under one point: the method is not sensitive to F.

It is also fast

Searching F inputs instead of all M makes each node cheaper. The paper gives the ratio of compute time against growing unpruned trees on all inputs:

In words: “a random-input tree costs roughly F times the log of the number of rows, compared with M for a tree that searches every input.”

With the numbers: zip-code with F = 1: N = 7,291 training rows and M = 256 inputs give log₂ 7291 / 256 = 12.8 / 256 = 0.050, a 20-fold saving. The paper prints the ratio as .025 and “40 times faster”, twice what its own formula gives for these numbers, so one of the two has slipped. Its measured run is in the same range: 4.0 minutes for 100 Forest-RI trees on a 250 MHz Macintosh, against almost three hours for Adaboost (which combined 100 trees on zip-code).

In Python:

import math
F, N, M = 1, 7291, 256
# F log2 N / M
ratio = F * math.log2(N) / M
round(ratio, 3)  # → 0.05
# how many times faster
round(1 / ratio, 1)  # → 20.0

Why it matters

“One random input per node already works” is the result that showed how much of a forest's power comes from decorrelation rather than from clever splits. Modern defaults sit between the paper's two choices; the lesson's RandomForest uses the square root of the number of features.

5 Random forests using linear combinations of inputs · original

Everyday picture

With only a handful of inputs, drawing F of them at random does not decorrelate much: the trees keep drawing the same few. Forest-RC (random combinations) invents new inputs instead. At each node it mixes L randomly chosen inputs with random weights, makes F such mixtures, and splits on the best one. There are so many possible mixtures that trees rarely repeat each other.

Tiny example

Take L = 3 inputs, already rescaled to comparable units: age 0.5, income −1.2 and number of links 2.0. Draw three weights uniformly between −1 and 1, say 0.3, −0.8 and 0.5. The new feature for this row is 0.3 × 0.5 + (−0.8) × (−1.2) + 0.5 × 2.0 = 0.15 + 0.96 + 1.0 = 2.11. The node then searches for the best threshold on that feature, exactly as it would on a real column.

In words: “a random feature is a weighted sum of L randomly chosen inputs, with each weight drawn evenly from −1 to 1.” (The paper describes this in prose; the formula is ours.)

With the numbers: 0.3 × 0.5 + (−0.8) × (−1.2) + 0.5 × 2.0 = 2.11.

In Python:

# a_l: the random weights; x_{m_l}: the chosen inputs (age, income, links)
a = [0.3, -0.8, 0.5]
x = [0.5, -1.2, 2.0]
# v = Σ a_l x_{m_l}
round(sum(a_l * x_ml for a_l, x_ml in zip(a, x)), 2)  # → 2.11

The paper uses L = 3 and picks F = 2 or F = 8 by out-of-bag error, rescaling inputs to mean 0 and spread 1 first when their units differ. The results (its Table 3) compare with Adaboost even more favourably than Forest-RI: 13.6% against 15.6% on sonar, 23.0% against 26.6% on diabetes, 3.8% against 4.9% on twonorm. A later experiment with F = 100 combinations reached 8.5% on the satellite images and 3.0% on the letters, and Forest-RI with F = 25 reached 5.8% on zip-code, which the paper calls the lowest test set errors so far achieved on these three datasets by tree ensembles.

5.1 Categorical variables

A categorical input with I values (a region code with I = 6 regions, say) is handled by drawing a random subset of its categories each time it is chosen, and turning it into a yes/no feature: “is the region in this subset?”. Since such an input carries as much as I − 1 yes/no columns would, it is made I − 1 times as likely to be picked; the region code is 5 times as likely as a numeric input. With many categorical inputs, the paper finds F must rise to two or three times int(log₂ M + 1) to keep enough strength. This also sidesteps the costly search for the best subset of categories, which for more than two classes grows like 2^I−1.

Why it matters

Random combinations produce splits that are not parallel to the axes, so the forest can follow a diagonal boundary with fewer steps. The price is that each question mixes several inputs and is harder to read; the lesson's forest, like Forest-RI, asks about one real input per split.

6 Empirical results on strength and correlation · original

“Past about F=4 the strength remains constant; adding more inputs does not help. But the correlation continues to increase.”Breiman (2001), §6

Everyday picture

Let each doctor see more test results and two things happen: each becomes a little better, and they start agreeing more, mistakes included. Past some point the first effect stops and only the second continues.

The experiment

On the sonar data (60 inputs, 208 examples) the paper grows Forest-RI with every F from 1 to 50, 100 trees each, repeated 80 times on random 10% test splits: 400,000 trees in all. It records the out-of-bag strength and correlation for each F.

Reading it: the horizontal axis is F, the number of random inputs each node may choose from. The solid line (strength) climbs quickly up to F of about 4 and then stays almost flat near 0.4. The dashed line (correlation) starts lower and keeps climbing all the way to about 0.5. The second chart is their ratio ρ̄/s², the quantity Theorem 2.3 says to keep small (note its axis starts at 2.5): it falls to its lowest around F = 5 or 6, then climbs steadily as extra correlation buys no extra strength. The paper's error curves (the bottom panel of its Figure 1) behave the same way: a small drop out to F of about 4 to 8, then a slow rise.

Other datasets

On the breast cancer data with random combinations (Figure 2), strength is flat from the start and correlation creeps up, so the best F is 1. On the larger satellite data (Figure 3), both keep rising slowly and the error falls slightly as F grows; the paper conjectures that on larger, more complex data the strength keeps improving for longer before it plateaus.

Why it matters

This is the evidence behind the rule “use few random inputs per node”. It also explains why forests are so forgiving to tune: the ratio is shallow over a wide range of F, so almost any sensible choice lands near the best.

7 Conjecture: Adaboost is a random forest · original

“… my belief is that in its later stages Adaboost is emulating a random forest.”Breiman (2001), §1.2

Everyday picture

A pseudo-random number generator is completely deterministic, yet its output looks random. Adaboost is also deterministic: it reweights the training examples after each tree, raising the weight of the ones just misclassified. Breiman's hunch is that, after a while, this sequence of weightings wanders like a random draw from some fixed distribution, which would make Adaboost a random forest in disguise.

Tiny example

Adaboost gives each tree a vote weight that grows with its accuracy on the weighted data. A tree with 10% weighted error gets log(0.9/0.1) = 2.197; one with 40% error gets log(0.6/0.4) = 0.405; one no better than a coin flip (50%) gets 0.

In words: “a tree's say in the vote is the logarithm of its odds of being right on the weighted training set.”

With the numbers: taking log as the natural logarithm, error 0.1: log 9 = 2.197; error 0.25: log 3 = 1.099; error 0.4: log 1.5 = 0.405; error 0.5: log 1 = 0.

In Python:

import math
# Q(w_k) = log[(1 − error(k)) / error(k)], natural log
[round(math.log((1 - err) / err), 3) for err in (0.1, 0.25, 0.4, 0.5)]  # → [2.197, 1.099, 0.405, 0.0]

The experiment

The paper runs Adaboost 75 times, discards the first 25 weightings, and treats the remaining 50 as a deck of cards, each drawn with probability proportional to its Q. A random forest that grows each tree on a randomly drawn card from this deck matched Adaboost closely: on the Wisconsin breast cancer data, 2.91% error for Adaboost against 2.94% for the forest. If the conjecture holds (the paper states it precisely as an ergodicity condition on the reweighting map), it would also explain why Adaboost does not overfit as trees are added, which was a puzzle at the time.

Why it matters

The conjecture was never settled in this paper, and later work showed that boosting can overfit when run long enough on noisy data, which is why modern boosting uses early stopping. The lasting lesson is the contrast in how the two families work: boosting changes the training set as it goes, forests never do.

8 The effects of output noise · original

“Then, Adaboost will concentrate increasing weight on these noisy instances and become warped.”Breiman (2001), §8

Everyday picture

A tutor who spends each lesson on the questions you got wrong last time is excellent, until the answer key has typos. Then the tutor keeps drilling the questions whose “correct” answers are wrong, and the whole course bends around them. A committee that never reweights anything just outvotes the typos.

Tiny example

The paper flips 5% of the training labels (about one in twenty) to a different class at random, and measures how much the test error rises. On the breast cancer data, Adaboost's error rises by 43.2%; Forest-RI's by 1.8%.

Reading it: each pair of bars is one dataset from the paper's Table 4, selected rows reproduced with attribution (Breiman, 2001): the percent increase in test error when 5% of the training labels are wrong. Grey bars are Adaboost and the striped blue bars are Forest-RI; a negative value (sonar) means the noisy run happened to score slightly better. Adaboost's damage is large and uneven, from a few percent to almost 50%, while the forest's stays in single digits. The reason is in the quote above: mislabelled examples keep being misclassified, so boosting keeps raising their weight.

Why it matters

Real labels are noisy. Robustness to wrong labels is one of the practical reasons forests remain a safe default, and why boosting libraries added shrinkage, subsampling and early stopping (see the trees and boosting lesson).

9 Data with many weak inputs · original

“Forests seem to have the ability to work with very weak classifiers as long as their correlation is low.”Breiman (2001), §9

Everyday picture

Some problems have no single tell-tale clue: a diagnosis from hundreds of lab values, each only slightly informative. One tree, which asks about one input at a time, barely beats guessing. But a crowd of barely-better-than-guessing trees, if their mistakes are independent, can add up to an expert.

Tiny example: the paper's run

The paper simulates 10 classes and 1,000 yes/no inputs, 1,000 training and 4,000 test examples. The best possible error (the Bayes rate) is 1.0%, and a naive Bayes classifier gets 6.2%.

Each tree is wrong 60% to 80% of the time, yet the forest with F = 25 gets 2.8%, not far above the 1.0% floor and well below naive Bayes. With F = 1 the correlation is almost zero but the strength is too low, and the forest had still not converged after 2,500 trees. Raising F bought strength at a small price in correlation, and the ratio fell from 2.5 to 0.83, tracking the error. (The paper's 0.91 for F = 10 differs from the 0.93 recomputed here only because its strength is printed rounded to 0.22.) The paper could not get Adaboost to run on this data at all, because the individual trees are too weak.

In Python:

# (s, ρ̄) for F = 1, 10, 25, as printed in §9
runs = [(0.069, 0.012), (0.22, 0.045), (0.28, 0.065)]
# c/s² = ρ̄ / s²
[round(rho_bar / s ** 2, 2) for s, rho_bar in runs]  # → [2.52, 0.93, 0.83]

Why it matters

The same principle, many weak but independent voters, is behind every ensemble method, including the averaging of many randomly thinned networks that dropout approximates inside one neural network.

10 Exploring the random forest mechanism · original

“A forest of trees is impenetrable as far as simple interpretations of its mechanism go.”Breiman (2001), §10

Everyday picture

To learn which player a football team depends on, bench each one for a real match and see how much the score suffers. The paper does this to the inputs of a forest: scramble one input's values in the out-of-bag rows, so it no longer lines up with anything, and measure how much worse the out-of-bag vote gets.

Tiny example

A forest has an out-of-bag error of 20%. Shuffle input m among the out-of-bag rows, run them down the trees again, and the out-of-bag error becomes 26%. The paper reports the percent increase: (26 − 20) / 20 = 30%.

In words: “an input's importance is how much, in percent, the out-of-bag error grows when that input is scrambled.” (The paper describes this in prose; the formula is ours.)

With the numbers: 100 × (0.26 − 0.20) / 0.20 = 30.

In Python:

# out-of-bag error intact, and with input m scrambled
e, e_m = 0.20, 0.26
round(100 * (e_m - e) / e, 1)  # → 30.0

Reading it: each bar is one of the eight inputs of the diabetes data, and its length is the percent rise in out-of-bag error when that input is scrambled (a forest of 1,000 trees, F = 1). Input 2 dominates at about 34%, followed by input 8 (about 14%) and input 6 (about 10%). The paper then checks by refitting on subsets: input 2 alone gives 29.7% test error against 23.1% with everything; adding input 6 brings it to 26.4%, but adding input 8 only to 29.4%. Input 8 looked important because it carries much of the same information as input 2: scrambling either one hurts, but once one is in, the other adds little.

On the congressional voting data (435 members, 16 yes/no votes), one vote stands out: scrambling it triples the error, and a forest using that single vote scores 4.3%, about the same as one using all sixteen.

Why it matters

This procedure grew into permutation importance, now standard for any model. The trees and boosting lesson implements it on held-out validation data as permutation_importance, and shows the cheaper impurity-based importance (RandomForest.feature_importances) crediting a pure-noise column. The paper's diabetes finding is the caveat the lesson repeats: correlated inputs share the credit, and importance is not cause.

11 Random forests for regression · original

“The randomization employed needs to aim at low correlation.”Breiman (2001), §11

Everyday picture

For numbers instead of labels, the trees no longer vote; they average. Ask a hundred people to guess the weight of an ox and average the guesses: individual errors cancel, but only to the extent that people do not all err in the same direction.

Tiny example

The paper's Table 7 reports, for the Boston housing data, that a single tree's mean squared error averages 26.3, and that two trees' residuals (true value minus prediction) have a weighted correlation of 0.45. Theorem 11.2 promises the forest's error is at most 0.45 × 26.3 = 11.8. The forest's out-of-bag error is 11.6 and its test error 10.2.

In words: “averaging the trees divides their typical squared error by at least the mean correlation of their residuals.”

With the numbers: Boston: 0.45 × 26.3 = 11.8 (out-of-bag 11.6); ozone: 0.55 × 32.5 = 17.9 (out-of-bag 17.6); abalone: 0.56 × 8.3 = 4.6 (out-of-bag 4.6).

In Python:

# (ρ̄, PE*(tree)) from Table 7 for Boston, ozone and abalone
rows = [(0.45, 26.3), (0.55, 32.5), (0.56, 8.3)]
# the bound ρ̄ · PE*(tree)
[round(rho_bar * pe_tree, 1) for rho_bar, pe_tree in rows]  # → [11.8, 17.9, 4.6]

The theorem assumes each tree is unbiased on average (its average prediction equals the average target). Its proof is the same move as §2.2: the forest's squared error is an average, over pairs of trees, of the covariance of their residuals, which is correlation times spreads. Theorem 11.1, the regression version of Theorem 1.2, says the average over trees converges as trees are added, so again more trees cannot overfit.

Why it matters

With B → ∞ this is exactly the lesson's formula ρσ² + (1 − ρ)σ²/B with the second term gone: the floor is ρσ². The lesson plots it with averaged_variance and forest_curve.

12 Empirical results in regression · original

What the paper finds

Regression forests here use bagging plus 25 random features per node, each a random combination of two inputs, 100 trees, and no split of a node with fewer than 5 examples. Against plain bagging and Breiman's earlier adaptive bagging:

The forest always beats bagging. Where adaptive bagging (which, like boosting, changes the training data as it goes) helps a lot, the forest helps less; where it helps nothing, the forest still helps. One difference from classification: correlation rises only slowly as more features are allowed per node, so regression forests need more features per node to drive down each tree's error.

The paper also swaps bagging for random output noise (Gaussian noise with the same spread as the targets added to every training target) and gets its lowest errors yet on the first two datasets. Its Table 8 lists Boston at 10.2 with bagging and 9.1 with noise. One entry there does not match the earlier tables: Table 8 gives ozone's with-bagging error as 17.8, which is bagging's entry in Table 6, while the forest's is 16.3 in Tables 6 and 7, the same value Table 8 gives for the noise version.

Why it matters

The out-of-bag estimates track the test errors, usually a little high, as §3.1 predicted. And the result that different kinds of injected randomness work better on different problems is the paper's standing invitation to experiment with the recipe.

13 Remarks and conclusions · original

“Because of the Law of Large Numbers they do not overfit.”Breiman (2001), §13

What the paper leaves open

• Why forests reduce bias. Boosting is known to reduce bias as well as variance by reweighting the data. Forests never change the data, yet match boosting's accuracy, so they must reduce bias too, and the paper admits the mechanism is not obvious.
• Other randomness. Bagging and random features are only two choices; a referee suggested random Boolean combinations of features.
• Random features plus boosting. Combining the two gave errors as low as 5.1% on zip-code, 2.2% on letters and 7.9% on the satellite data in some runs: better than either alone on the larger datasets.

Why it matters

The last open question was answered in practice: XGBoost, for one, samples a random subset of columns for every tree, borrowing the forest's decorrelation trick to make boosting less prone to overfitting (see the XGBoost companion, §2.3).

Appendix II: out-of-bag estimates for strength and correlation · original

Everyday picture

Strength and correlation are defined through the probabilities that an imaginary random tree votes each way. The appendix replaces each imaginary probability with a real count: the share of out-of-bag trees that voted that way.

Tiny example

In the out-of-bag table above, email 2 is spam and is out of bag for trees 1 and 3. If both vote spam, its out-of-bag vote share for spam is 2/2 = 1. Email 1 is out of bag only for tree 2; if tree 2 votes not spam, email 1's share for spam is 0/1 = 0.

In words: “among the trees that never saw this example, the share that voted for class j.”

With the numbers: email 2: trees 1 and 3 are out of bag and both vote spam, so Q(email 2, spam) = 2/2 = 1.0. Replace the probabilities in the margin by these shares, average over the training set, and you have the out-of-bag strength; the spread of those margins gives the correlation through equation (7).

In Python:

# for email 2: which trees saw it, and how each tree votes on it
in_bag = {1: False, 2: True, 3: False, 4: True}
vote = {1: "spam", 2: "not", 3: "spam", 4: "spam"}
oob_trees = [k for k in in_bag if not in_bag[k]]
oob_trees  # → [1, 3]
# Q(x, spam): the out-of-bag share of votes for spam
sum(1 for k in oob_trees if vote[k] == "spam") / len(oob_trees)  # → 1.0

Why it matters

This is what makes the theory usable: strength and correlation are not just symbols in a bound, they are numbers the forest reports about itself on every run, as §6 and §9 show.

What changed since 2001

The algorithm most people run today is the paper's Forest-RI with bagging, almost unchanged. What moved is around it:

Glossary

Every term with hover guidance on this page, in one place.