Random Forest

A random forest is a collection of decision trees whose predictions are combined: for classification the trees vote, for regression their outputs are averaged. Each tree is grown on its own bootstrap sample of the training set, and at every node it searches for the best split among only a few randomly chosen features. A single fully grown tree fits its training data closely and changes a lot when the data change; many such trees, made different from one another on purpose, average out much of that variation. Breiman (§3) lists among the procedure’s properties that it is relatively robust to outliers and noise, simple and easily parallelized, and gives internal estimates of error, strength, correlation and variable importance: an error estimate from the training examples each tree did not see, and a ranking of the inputs by importance. In computer vision, before deep networks, forests served as pixel and patch classifiers and regressors: they predicted local edge masks, regressed facial landmark offsets, labelled pixels in land-cover maps and in cell segmentation tools such as ilastik, and predicted object coordinates for object pose estimation.

This article covers bagging, the random forest procedure in the form Leo Breiman gave it, his analysis of a forest’s error through the strength of its trees and the correlation between them, out-of-bag estimation, variable importance, and how scikit-learn 1.7.2’s RandomForestClassifier differs from Breiman’s description. Breiman’s “Random Forests” is read here in his technical report of January 2001 (the author’s copy on his Berkeley page), not in the Machine Learning journal version; section, equation and theorem numbers below are the report’s. The example uses synthetic image patches whose relevant pixels are known, and measures error against the number of trees, Breiman’s strength and correlation for three settings of the feature subset size, hard votes against averaged probabilities, and two importance maps. Decision Tree already shows how much single trees change between bootstrap resamples; this article builds on that and does not repeat it.

Problem

Given $n$ training examples $(\mathbf{x}_i, y_i)$ with $\mathbf{x}_i \in \mathbb{R}^M$, for example the $M = 256$ pixels of a $16 \times 16$ patch, and a class label $y_i$ (or a real-valued target), learn a predictor for new inputs. A decision tree is a flexible predictor for this, but an unstable one: Murphy (§18.2) calls trees high-variance estimators, because their predictions can change a lot when the training data are perturbed. Breiman’s bagging report names this instability as the vital element: if perturbing the learning set can change the predictor a lot, aggregating many versions can improve accuracy, while for a stable procedure bagging can slightly degrade performance. A random forest is a way to build many trees that are individually accurate but make different mistakes, and to combine them.

Inputs and Outputs

• Input for training: $n$ labelled examples with $M$ numerical features; the number of trees $T$; the number of features $F$ tried at each split (max_features in scikit-learn); and the usual tree-growing settings (Breiman grows trees to maximum size and does not prune them).
• Output of training: $T$ trees, each with the indices of the training examples left out of its bootstrap sample (needed for out-of-bag estimates).
• Input for prediction: a feature vector $\mathbf{x}$.
• Output of prediction: a class (the most popular vote, or in scikit-learn the class with the highest averaged probability), the vote fractions or averaged class probabilities, or for regression the average of the trees’ outputs.
• By-products: an out-of-bag estimate of the generalization error, out-of-bag estimates of strength and correlation, and a per-feature importance.

Intuition

Ask many people to estimate something, and the average of their answers is usually closer than a typical single answer, provided they do not all make the same mistake. Murphy (§18.2) makes this concrete for votes: if each of $T$ binary classifiers is right with probability $\theta$ and their errors are independent, the probability that the majority is right is one minus a binomial tail, which for $\theta = 0.51$ is 0.73 with 1,000 voters and 0.97 with 10,000. The catch is independence. Trees grown on the same data make correlated mistakes, and averaging correlated mistakes helps much less.

A random forest therefore injects two kinds of randomness. Each tree sees a different bootstrap sample of the training set, and at each node it may only choose among a few randomly picked features. Both make the trees less alike. Restricting the features also makes each tree somewhat worse, since the best split is often not among the candidates. Breiman’s analysis turns this into a trade-off between two numbers, the strength of the individual trees and the correlation between them, and his advice is to inject randomness that lowers the correlation while keeping the strength (§3).

Algorithm

Bagging (bootstrap aggregating; Breiman, 1994):

1. For $b = 1, \dots, T$: draw a bootstrap sample of $n$ examples from the training set at random with replacement, and fit a predictor (here, a tree) to it.
2. Predict by a plurality vote of the $T$ predictors for a class, or by their average for a number.

Random forest (Forest-RI, Breiman 2001, §3.1 and §4):

1. For $b = 1, \dots, T$:
   1. Draw a bootstrap sample of the $n$ training examples, with replacement.
   2. Grow a tree on it with the CART procedure, but at each node choose $F$ of the $M$ features at random and search for the best split among those $F$ only.
   3. Grow the tree to maximum size; do not prune.
2. Predict a class by letting the $T$ trees vote and taking the most popular class.

Breiman’s Definition 1.1 says that each tree “casts a unit vote for the most popular class”. In his experiments $F$ was either 1 or, in the report’s words, “the first integer less than $\log_2 M + 1$” (§4), and most forests had 100 trees (§4). A second variant, Forest-RC (§5), splits on random linear combinations: at each node, $L$ randomly chosen inputs are added with coefficients drawn uniformly from $[-1, 1]$, $F$ such combinations are generated, and the best split among them is used; Breiman used $L = 3$ and $F = 2$ or 8.

Out-of-bag (OOB) estimation (§3.1): about a third of the training examples are left out of each bootstrap sample. For each training example, collect the votes only of the trees that did not see it; the error rate of this out-of-bag classifier over the training set estimates the forest’s generalization error without a separate test set.

The bootstrap leaves out a fraction $(1 - 1/n)^n$ of the examples from each sample, which tends to $e^{-1} \approx 0.37$ as $n$ grows (Murphy, §18.3), so each tree is fitted to about 63% of the distinct examples.

Breiman’s report is not consistent about the sampling in bagging. Its introduction (§1.1) describes bagging as a random selection “(without replacement)” from the training set, while §3.1 states that each new training set “is drawn, with replacement”, the bagging report itself uses bootstrap replicates drawn with replacement, and the report’s own Θ for bagging, “the counts in N boxes resulting from N darts thrown at random” (§1.1), is a draw with replacement. The algorithm above follows §3.1.

Mathematical Formulation

Margin and strength. Let $h(\mathbf{x}, \Theta)$ be a tree grown with random vector $\Theta$ (the bootstrap draw and the feature choices). Breiman (§2.2, Definition 2.1) defines the forest’s margin at an example as the probability, over trees, of voting for the true class minus the largest probability of voting for any other class:

$$\operatorname{mr}(\mathbf{X}, Y) = P_\Theta\big(h(\mathbf{X}, \Theta) = Y\big) - \max_{j \neq Y} P_\Theta\big(h(\mathbf{X}, \Theta) = j\big),$$

and the strength as its expectation, $s = E_{\mathbf{X}, Y}\, \operatorname{mr}(\mathbf{X}, Y)$. The generalization error of the infinite forest is $PE^* = P_{\mathbf{X}, Y}(\operatorname{mr} < 0)$. Theorem 1.2 states that as the number of trees grows, the forest’s error converges almost surely to this limit, which Breiman gives as the reason forests “do not overfit as more trees are added” (§2.1). This is a statement about adding trees: the limit itself can still be poor if the trees are poor.

Correlation. With $\hat{j}(\mathbf{X}, Y)$ the strongest wrong class, the raw margin of one tree is $\operatorname{rmg}(\Theta, \mathbf{X}, Y) = I(h = Y) - I(h = \hat{j})$, so $\operatorname{mr}$ is its expectation over $\Theta$. Breiman shows that $\operatorname{var}(\operatorname{mr}) = \bar\rho\, (E_\Theta \operatorname{sd}(\Theta))^2$, where $\operatorname{sd}(\Theta)$ is the standard deviation of a tree’s raw margin over examples and $\bar\rho$ is the mean correlation between the raw margins of two independent trees, weighted by their standard deviations (Eqs. 6–7).

Theorem 2.3. Chebyshev’s inequality and these identities give

$$PE^* \le \frac{\bar\rho\,(1 - s^2)}{s^2},$$

and Breiman (Definition 2.4) calls $\bar\rho / s^2$ the c/s2 ratio, “the smaller it is, the better”. He describes the bound as likely to be loose but suggestive: the error depends on how strong the trees are and how correlated they are. For two classes the margin is $\operatorname{mr} = 2 P_\Theta(h = Y) - 1$, the raw margin is $2I(h = Y) - 1$, and $\bar\rho$ becomes the correlation between two trees’ indicators of being right, averaged over pairs of trees (p. 6).

Out-of-bag estimates of strength and correlation (Appendix II). Let $Q(\mathbf{x}, j)$ be the fraction of out-of-bag votes for class $j$ at a training example. Substituting $Q$ for $P_\Theta$ in the margin and averaging over the training set gives the estimate of $s$; the average of the squared margins minus $s^2$ estimates $\operatorname{var}(\operatorname{mr})$. For each tree $k$, let $p_1$ be the fraction of its out-of-bag examples it classifies correctly and $p_2$ the fraction it assigns to $\hat{j}$. The raw margin takes the values $+1$, $-1$ and $0$ with probabilities $p_1$, $p_2$ and $1 - p_1 - p_2$, so its standard deviation is

$$\operatorname{sd}(\Theta_k) = \sqrt{p_1 + p_2 - (p_1 - p_2)^2}.$$

The report’s Eq. (A2) prints a plus sign before $(p_1 - p_2)^2$, which does not give the standard deviation of a variable with these three values; the example below computes the standard deviation directly and shows that the minus sign matches it. Averaging $\operatorname{sd}(\Theta_k)$ over trees and dividing $\operatorname{var}(\operatorname{mr})$ by its square estimates $\bar\rho$. The report’s Eq. (8), a step towards Theorem 2.3, also prints the square outside $E_{\mathbf{X},Y}$, as $E_\Theta (E_{\mathbf{X},Y} \operatorname{rmg})^2 - s^2$, where the variance of a tree’s raw margin needs the expectation of its square; in our derivation the bound itself is not affected, since a raw margin’s square is at most 1, so the corrected term is still at most $1 - s^2$.

Regression forests (§11). Averaging $T$ regression trees converges to $E_\Theta h(\mathbf{x}, \Theta)$ (Theorem 11.1), and Theorem 11.2, which assumes $EY = E_{\mathbf{X}} h(\mathbf{X}, \Theta)$ for every $\Theta$, bounds the forest’s mean squared error by $\bar\rho$ times the average tree’s, where $\bar\rho$ is now a weighted correlation between the trees’ residuals: the forest reduces the trees’ error by the factor $\bar\rho$. The report’s Appendix I proves this convergence under the heading “Proof of Theorem 9.1”, while the text numbers the theorem 11.1; the report’s outline (§1.2) also numbers sections differently from its headings (it places the out-of-bag review in Section 4 and the two kinds of random features in Sections 5 and 6, where the headings put them in §3.1, §4 and §5).

Bagging reduces variance. Murphy (§18.2) states that an ensemble has similar bias to its base models but lower variance (the decomposition itself is in Bias–Variance Tradeoff). scikit-learn’s user guide (§1.11.2.1) puts the same idea in terms of the two sources of randomness: they decrease the variance of the forest, “sometimes at the cost of a slight increase in bias”.

Parameters

• Number of trees $T$ (n_estimators, default 100 in scikit-learn 1.7.2). As trees are added the error converges to a limit (Theorem 1.2), while time and memory grow. The user guide notes that results stop getting significantly better beyond a critical number of trees. Breiman used 100 trees in most experiments because the out-of-bag estimates use only about a third of them (§4).
• Features per split $F$ (max_features). The main lever on strength and correlation. Breiman tried $F = 1$ and the first integer below $\log_2 M + 1$, and reported that results were “not overly sensitive” to $F$, with an average absolute difference below 1% between the two (§4). scikit-learn defaults to "sqrt" (the square root of the number of features) for RandomForestClassifier and to 1.0 (all features, which is bagged trees) for RandomForestRegressor, and its user guide calls these empirical good defaults that should be cross-validated.
• Bootstrap (bootstrap=True, max_samples). scikit-learn draws $n$ indices with replacement by default (max_samples=None); max_samples draws fewer. Out-of-bag scoring (oob_score=True) raises an error unless bootstrap=True.
• Tree size (max_depth, min_samples_leaf, min_samples_split, max_leaf_nodes). Breiman grows trees fully. The user guide says fully developed trees often give good results but use a lot of memory, and that these parameters reduce model size. As the example shows, they also change what scikit-learn’s probability averaging does.
• Split criterion (criterion, Gini by default), as in a single decision tree.
• random_state fixes both the bootstrap draws and the feature choices; n_jobs sets how many trees are built in parallel.

Complexity

Each tree costs what a CART tree costs on $n$ examples, except that each node examines $F$ features instead of $M$. Breiman (§4) gives the ratio of a Forest-RI tree’s compute time to that of an unpruned tree using all variables as $F \log_2(N) / M$, with $N$ the number of examples; for his zip-code data with $F = 1$ this ratio was 0.025. Trees are independent, so they can be grown in parallel, unlike the trees of boosting (Murphy, §18.4). scikit-learn’s user guide gives the size of a model with default parameters as $O(M N \log N)$, with $M$ the number of trees and $N$ the number of samples (its symbols). Prediction costs one root-to-leaf path per tree.

Implementation

The example uses NumPy 2.3.5, SciPy 1.16.3 and scikit-learn 1.7.2, on one thread. It runs in about a minute (41–44 s in the pilot and two runs of the script shown on the drafting machine; 54 and 70 s in two later runs while other jobs shared the machine).

Data. Each example is a $16 \times 16$ patch. The background is a texture with known statistics: white Gaussian noise on a $24 \times 24$ field, smoothed with a Gaussian filter of $\sigma = 0.6$ px (mode="constant") and cropped to the central $16 \times 16$, then scaled so that every pixel has standard deviation 1. The code builds this as an explicit linear map $L$ from the 576 noise values to the 256 pixels, so the texture’s covariance $\Sigma = L L^\top$ is known exactly. Half the patches on average (labels are drawn with probability ½) also carry a faint Gaussian blob with peak 1.2 and $\sigma = 2$ px, centred at one of four positions near the middle, (7, 7), (7, 8), (8, 7) or (8, 8) in (row, column) pixel coordinates counted from 0 at the top left, chosen at random. The relevant pixels are known: the region $R$ of pixels within 4 px ($2\sigma$) of any of the four centres. Because $\Sigma$ and the blobs are known, the Bayes-optimal classifier is exact: a likelihood ratio between a Gaussian and a mixture of four Gaussians with the same covariance. Its error on the test patches is the floor that any classifier on these data can at best approach, and it shows that the labels can be learned from the pixels but not perfectly. There are 1,000 training and 2,000 test patches; the features are the 256 pixel values, cast to float32 as scikit-learn’s trees do internally.

Forests. Three RandomForestClassifiers with 300 trees each, random_state=0, fully grown (scikit-learn’s defaults), differ only in max_features: 1 (Breiman’s $F = 1$), 16 (the square root of 256, scikit-learn’s default for classifiers) and 256 (every feature, which is bagging). The script reads each tree’s hard predictions and rebuilds each tree’s out-of-bag set itself, by repeating the draw that scikit-learn’s _generate_sample_indices makes from the tree’s own random_state (read in _forest.py, re-implemented in one line), so that Breiman’s vote-based quantities can be computed directly. Hard votes go to class 1 only with more than half the votes; ties go to class 0, which is also what argmax does with tied averaged probabilities.

Measures.

• Checks C1–C5. C1 checks the data: blob energy inside $R$ at least 0.99, unit pixel variance to $10^{-12}$, and the pixel standard deviation of the blob-free training patches within [0.95, 1.05]. C2 checks that the hand-computed out-of-bag vote fractions equal scikit-learn’s oob_decision_function_ to $10^{-12}$ and that every training patch has an out-of-bag vote. C3 checks that the hand count of out-of-bag errors equals the count implied by oob_score_ (an integer comparison). C4 checks that every fully grown tree gives one-hot probabilities on the test patches. C5 compares the standard deviation of each tree’s raw margin, computed directly, with the minus-sign formula above (tolerance $10^{-12}$) and with the sign printed in (A2) (expected to differ by more than $10^{-3}$).
• (1) Error against the number of trees $B$ (the first $B$ of the 300 trees), test error and out-of-bag error, for each forest. H1a: the error at 300 trees is below the error of one tree and not above the error at 10 trees. H1b: the out-of-bag and test errors agree within two standard errors, $2\sqrt{t(1-t)/2000 + o(1-o)/n_{\text{oob}}}$, at $B$ = 100, 200 and 300. H1c: with few trees the out-of-bag error is above the test error (at $B$ = 5 and 10), as Breiman (§3.1) expects because each out-of-bag vote combines only about a third of the trees.
• (2) Strength and correlation from out-of-bag votes (Appendix II, two-class form), with c/s², the Theorem 2.3 bound and the mean out-of-bag error of single trees. H2a: strength rises with max_features (1 < 16 < 256). H2b: correlation rises with max_features. H2c: strength is positive and the bound is above both the test and the out-of-bag error.
• (3) Hard votes against averaged probabilities on the test patches, for the three forests and for a fourth forest with max_features=16 and min_samples_leaf=10. H3a: no disagreement for the fully grown forests. H3b: at least one disagreement for the fourth. H3c: on every disagreement, both the averaged probability and the vote fraction are within 0.1 of ½. H3d: the two rules’ test errors differ by less than 0.01.
• (4) Importance for the max_features=16 forest: scikit-learn’s impurity-based importance (MDI, feature_importances_) and its permutation_importance on the test patches with 3 repeats (negative means set to 0 when computing shares). H4a and H4b: at least half of each importance lies inside $R$, which covers 26.6% of the patch. H4c: at least 15 of the 20 most important pixels lie inside $R$ for each. The maps are printed as shares of 2×2-pixel blocks, in thousandths; the hypotheses are decided at full resolution.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
import numpy as np
from scipy.ndimage import gaussian_filter
from scipy.special import logsumexp
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance

# ---------------- data: 16x16 patches, faint blob over textured noise ----------------
H, PAD, SIG_T, SIG_B, A = 16, 4, 0.6, 2.0, 1.2
CENTRES = [(7.0, 7.0), (7.0, 8.0), (8.0, 7.0), (8.0, 8.0)]
G = H + 2 * PAD
L = np.zeros((H * H, G * G))          # white noise on 24x24 -> Gaussian filter -> crop 16x16
for k in range(G * G):
    e = np.zeros(G * G); e[k] = 1.0
    L[:, k] = gaussian_filter(e.reshape(G, G), SIG_T, mode="constant")[PAD:PAD + H, PAD:PAD + H].ravel()
L /= np.sqrt((L ** 2).sum(axis=1))[:, None]          # unit standard deviation at every pixel
Sigma = L @ L.T
rr, cc = np.mgrid[0:H, 0:H]
BLOBS = np.stack([np.exp(-((rr - r) ** 2 + (cc - c) ** 2) / (2 * SIG_B ** 2)).ravel() for r, c in CENTRES])
R = np.zeros(H * H, bool)                              # known relevant region: within 2*SIG_B of a centre
for r, c in CENTRES:
    R |= (np.hypot(rr - r, cc - c) <= 2 * SIG_B).ravel()

def make(n, rng):
    y = rng.integers(0, 2, n)
    X = rng.standard_normal((n, G * G)) @ L.T
    X += (A * y)[:, None] * BLOBS[rng.integers(0, 4, n)]
    return X, y

rng = np.random.default_rng(0)
Xtr64, ytr = make(1000, rng)
Xte64, yte = make(2000, rng)
Xtr, Xte = Xtr64.astype(np.float32), Xte64.astype(np.float32)   # scikit-learn's trees use float32
n, nte = len(ytr), len(yte)

Si = np.linalg.inv(Sigma)
def bayes(X):                                          # exact likelihood ratio, class 1 = 4-centre mixture
    M = A * BLOBS
    q = X @ Si @ M.T - 0.5 * np.einsum("ij,jk,ik->i", M, Si, M)
    return (logsumexp(q, axis=1) - np.log(4) > 0).astype(int)

w = lambda b: "held" if b else "failed"
print("data")
print(f"  train {n} patches ({ytr.sum()} with blob), test {nte} ({yte.sum()} with blob), 256 pixels each")
print(f"  region R: {R.sum()} pixels, area fraction {R.mean():.4f}; blob energy inside R {min((b[R]**2).sum()/(b**2).sum() for b in BLOBS):.4f}")
print(f"  texture: max |diag(Sigma)-1| {np.abs(np.diag(Sigma)-1).max():.1e}; pixel std of blob-free training patches {Xtr64[ytr==0].std():.4f}")
print(f"  Bayes rule (exact likelihood) on the test patches: error {np.mean(bayes(Xte64) != yte):.4f}")
e_in = min((b[R]**2).sum()/(b**2).sum() for b in BLOBS); sd0 = Xtr64[ytr==0].std()
print(f"  C1 energy >= 0.99, |diag-1| <= 1e-12, std in [0.95, 1.05]: "
      f"{w(e_in >= 0.99 and np.abs(np.diag(Sigma)-1).max() <= 1e-12 and 0.95 <= sd0 <= 1.05)}")

def oob_mask(est):                                     # same draw as sklearn's bootstrap for this tree
    idx = np.random.RandomState(est.random_state).randint(0, n, n)
    return np.bincount(idx, minlength=n) == 0

def per_tree(rf):
    htr = np.array([e.predict(Xtr) for e in rf.estimators_]).astype(int)
    hte = np.array([e.predict(Xte) for e in rf.estimators_]).astype(int)
    oob = np.array([oob_mask(e) for e in rf.estimators_])
    nonhot = sum(int(np.sum(e.predict_proba(Xte).max(axis=1) < 1)) for e in rf.estimators_)
    return htr, hte, oob, nonhot

T = 300
CHECK_B = [1, 5, 10, 25, 50, 100, 200, 300]
forests, res = {}, {}
for mf in [1, 16, 256]:
    rf = RandomForestClassifier(n_estimators=T, max_features=mf, bootstrap=True, oob_score=True,
                                random_state=0, n_jobs=1).fit(Xtr, ytr)
    forests[mf] = rf
    res[mf] = per_tree(rf)

# ---------------- checks of the hand out-of-bag computation against scikit-learn ----------------
print("\nchecks (fully grown trees)")
for mf in [1, 16, 256]:
    rf = forests[mf]; htr, hte, oob, nonhot = res[mf]
    cnt = oob.sum(axis=0); Q = (htr * oob).sum(axis=0) / cnt
    dq = np.abs(Q - rf.oob_decision_function_[:, 1]).max()
    my_soft_err = int(np.sum((Q > 0.5).astype(int) != ytr))         # argmax, ties to class 0
    sk_err = int(round((1 - rf.oob_score_) * n))
    print(f"  max_features={mf:3d}: every patch out of bag at least once: {bool((cnt > 0).all())}; "
          f"max|Q - oob_decision_function_| {dq:.1e}; OOB errors hand {my_soft_err} / sklearn {sk_err}; "
          f"non-one-hot leaf probabilities on test {nonhot}")
    print(f"      C2 {w(bool((cnt > 0).all()) and dq <= 1e-12)}; C3 {w(my_soft_err == sk_err)}; C4 {w(nonhot == 0)}")

# ---------------- (1) error against the number of trees ----------------
def votes_err(h, yv, B, mask=None):
    if mask is None:
        v = h[:B].sum(axis=0); c = np.full(len(yv), B)
    else:
        v = (h[:B] * mask[:B]).sum(axis=0); c = mask[:B].sum(axis=0)
    ok = c > 0
    pred = (v > c / 2).astype(int)                     # hard majority vote, ties to class 0
    return np.mean(pred[ok] != yv[ok]), int(ok.sum())

print("\n(1) majority-vote error against number of trees B: test / out-of-bag (patches with an OOB vote)")
print("   B   " + "".join(f"  max_features={mf:<3d}            " for mf in [1, 16, 256]))
curves = {}
for B in CHECK_B:
    row = f"{B:4d}  "
    for mf in [1, 16, 256]:
        htr, hte, oob, _ = res[mf]
        te, _ = votes_err(hte, yte, B); oe, no = votes_err(htr, ytr, B, oob)
        curves[(mf, B)] = (te, oe, no)
        row += f"  {te:.4f} / {oe:.4f} ({no:4d})    "
    print(row)
print("  H1a test(300) < test(1) and test(300) <= test(10); H1b |OOB-test| <= 2 SE at B=100,200,300; H1c OOB > test at B=5,10")
for mf in [1, 16, 256]:
    t = {B: curves[(mf, B)][0] for B in CHECK_B}
    h1a = t[300] < t[1] and t[300] <= t[10]
    parts = []
    h1b = True
    for B in [100, 200, 300]:
        te, oe, no = curves[(mf, B)]
        tol = 2 * np.sqrt(te * (1 - te) / nte + oe * (1 - oe) / no)
        parts.append(f"B={B}: |diff| {abs(oe - te):.4f} tol {tol:.4f}")
        h1b &= abs(oe - te) <= tol
    h1c = all(curves[(mf, B)][1] > curves[(mf, B)][0] for B in [5, 10])
    w = lambda b: "held" if b else "failed"
    print(f"  max_features={mf:3d}: H1a {w(h1a)}; H1b {w(h1b)} ({'; '.join(parts)}); H1c {w(h1c)}")

# ---------------- (2) Breiman's strength and correlation from out-of-bag votes ----------------
print("\n(2) out-of-bag strength s, correlation rho, bound rho(1-s^2)/s^2 (Breiman 2001 TR, Sec. 2.2, App. II)")
print("  max_features      s     var(mr)  E sd   rho     c/s^2   bound   OOB err  test err  mean tree OOB err")
S2 = {}
for mf in [1, 16, 256]:
    htr, hte, oob, _ = res[mf]
    cnt = oob.sum(axis=0); Q1 = (htr * oob).sum(axis=0) / cnt
    Qy = np.where(ytr == 1, Q1, 1 - Q1)
    mr = 2 * Qy - 1                                    # two classes: Q(x,y) - Q(x, other)
    s = mr.mean(); var_mr = np.mean(mr ** 2) - s ** 2
    sd_f, dev_minus, dev_plus, p1s = [], 0.0, 0.0, []
    for k in range(T):
        o = oob[k]; corr = (htr[k, o] == ytr[o])
        p1 = corr.mean(); p2 = 1 - p1                  # j-hat is the other class
        rmg = np.where(corr, 1.0, -1.0)
        direct = rmg.std()
        fm = np.sqrt(p1 + p2 - (p1 - p2) ** 2); fp = np.sqrt(p1 + p2 + (p1 - p2) ** 2)
        dev_minus = max(dev_minus, abs(direct - fm)); dev_plus = max(dev_plus, abs(direct - fp))
        sd_f.append(fm); p1s.append(p1)
    Esd = np.mean(sd_f); rho = var_mr / Esd ** 2
    bound = rho * (1 - s ** 2) / s ** 2
    te = curves[(mf, 300)][0]; oe = curves[(mf, 300)][1]
    S2[mf] = (s, rho, bound, te, oe)
    print(f"  {mf:5d}        {s:.4f}  {var_mr:.4f}  {Esd:.4f}  {rho:.4f}  {rho/s**2:.4f}  {bound:.4f}  {oe:.4f}   {te:.4f}    {1-np.mean(p1s):.4f}")
    print(f"        sd check: max|direct sd - sqrt(p1+p2-(p1-p2)^2)| {dev_minus:.1e}; "
          f"max|direct sd - sqrt(p1+p2+(p1-p2)^2)| (sign as printed in (A2)) {dev_plus:.4f}; "
          f"C5 {w(dev_minus <= 1e-12 and dev_plus > 1e-3)}")
print(f"  H2a s(1) < s(16) < s(256): {w(S2[1][0] < S2[16][0] < S2[256][0])}")
print(f"  H2b rho(1) < rho(16) < rho(256): {w(S2[1][1] < S2[16][1] < S2[256][1])}")
for mf in [1, 16, 256]:
    s, rho, bound, te, oe = S2[mf]
    print(f"  H2c max_features={mf:3d}: s > 0 and bound >= test and OOB error: {w(s > 0 and bound >= te and bound >= oe)}")

# ---------------- (3) Breiman's hard vote against scikit-learn's averaged probabilities ----------------
print("\n(3) hard majority vote against averaged probabilities (predict), 300 trees, test patches")
rfD = RandomForestClassifier(n_estimators=T, max_features=16, min_samples_leaf=10, bootstrap=True,
                             random_state=0, n_jobs=1).fit(Xtr, ytr)
hD = np.array([e.predict(Xte) for e in rfD.estimators_]).astype(int)
nonhotD = sum(int(np.sum(e.predict_proba(Xte).max(axis=1) < 1)) for e in rfD.estimators_)
for name, rf, h in [("max_features=  1, fully grown", forests[1], res[1][1]),
                    ("max_features= 16, fully grown", forests[16], res[16][1]),
                    ("max_features=256, fully grown", forests[256], res[256][1]),
                    ("max_features= 16, min_samples_leaf=10", rfD, hD)]:
    vote = h.mean(axis=0); hard = (vote > 0.5).astype(int)
    p = rf.predict_proba(Xte)[:, 1]; soft = rf.predict(Xte)
    dis = hard != soft
    line = (f"  {name:38s} disagree {int(dis.sum()):3d}/{nte}; error hard {np.mean(hard != yte):.4f} "
            f"soft {np.mean(soft != yte):.4f}")
    if dis.any():
        line += (f"; on disagreements max|p-0.5| {np.abs(p[dis]-0.5).max():.4f}, "
                 f"max|vote-0.5| {np.abs(vote[dis]-0.5).max():.4f}")
    print(line)
    if rf is rfD:
        h3c = bool(dis.any()) and np.abs(p[dis]-0.5).max() < 0.1 and np.abs(vote[dis]-0.5).max() < 0.1
        print(f"      H3b {w(dis.sum() >= 1)}; H3c {w(h3c)}; "
              f"H3d {w(abs(np.mean(hard != yte) - np.mean(soft != yte)) < 0.01)}")
    else:
        print(f"      H3a {w(dis.sum() == 0)}")
print(f"  min_samples_leaf=10 forest: non-one-hot leaf probabilities on test {nonhotD}")

# ---------------- (4) importance maps: MDI and permutation importance ----------------
print("\n(4) importance, max_features=16 forest: share of importance inside R (area fraction "
      f"{R.mean():.4f}) and top-20 pixels inside R")
rf = forests[16]
mdi = rf.feature_importances_
pi = permutation_importance(rf, Xte, yte, n_repeats=3, random_state=0, n_jobs=1).importances_mean
pip = np.clip(pi, 0, None)
for name, imp in [("MDI", mdi), ("permutation (test, 3 repeats)", pip)]:
    share = imp[R].sum() / imp.sum(); top = int(R[np.argsort(imp)[::-1][:20]].sum())
    print(f"  {name:30s} share in R {share:.4f}; top-20 in R {top:2d}; "
          f"H4 share >= 0.5 {w(share >= 0.5)}, top-20 >= 15 {w(top >= 15)}")
print(f"  permutation importances below zero: {int((pi < 0).sum())} pixels")
for name, imp in [("MDI", mdi), ("permutation", pip)]:
    m = imp.reshape(H, H) / imp.sum()
    blk = m.reshape(8, 2, 8, 2).sum(axis=(1, 3))
    print(f"  {name} share per 2x2 block, x1000:")
    for row in blk:
        print("    " + " ".join(f"{int(round(1000*v)):3d}" for v in row))

Output:

data
  train 1000 patches (537 with blob), test 2000 (1020 with blob), 256 pixels each
  region R: 68 pixels, area fraction 0.2656; blob energy inside R 0.9919
  texture: max |diag(Sigma)-1| 3.3e-16; pixel std of blob-free training patches 0.9974
  Bayes rule (exact likelihood) on the test patches: error 0.1485
  C1 energy >= 0.99, |diag-1| <= 1e-12, std in [0.95, 1.05]: held

checks (fully grown trees)
  max_features=  1: every patch out of bag at least once: True; max|Q - oob_decision_function_| 0.0e+00; OOB errors hand 215 / sklearn 215; non-one-hot leaf probabilities on test 0
      C2 held; C3 held; C4 held
  max_features= 16: every patch out of bag at least once: True; max|Q - oob_decision_function_| 0.0e+00; OOB errors hand 162 / sklearn 162; non-one-hot leaf probabilities on test 0
      C2 held; C3 held; C4 held
  max_features=256: every patch out of bag at least once: True; max|Q - oob_decision_function_| 0.0e+00; OOB errors hand 180 / sklearn 180; non-one-hot leaf probabilities on test 0
      C2 held; C3 held; C4 held

(1) majority-vote error against number of trees B: test / out-of-bag (patches with an OOB vote)
   B     max_features=1                max_features=16               max_features=256            
   1    0.4720 / 0.4533 ( 364)      0.3155 / 0.2967 ( 364)      0.3005 / 0.3022 ( 364)    
   5    0.4245 / 0.4583 ( 888)      0.2470 / 0.2804 ( 888)      0.2265 / 0.3007 ( 888)    
  10    0.3745 / 0.4229 ( 986)      0.2335 / 0.2809 ( 986)      0.2260 / 0.2688 ( 986)    
  25    0.3295 / 0.4050 (1000)      0.1910 / 0.2250 (1000)      0.1960 / 0.2020 (1000)    
  50    0.2540 / 0.3480 (1000)      0.1770 / 0.1940 (1000)      0.1850 / 0.1830 (1000)    
 100    0.2270 / 0.2770 (1000)      0.1655 / 0.1650 (1000)      0.1835 / 0.1790 (1000)    
 200    0.2090 / 0.2300 (1000)      0.1570 / 0.1600 (1000)      0.1830 / 0.1760 (1000)    
 300    0.2010 / 0.2150 (1000)      0.1595 / 0.1620 (1000)      0.1800 / 0.1800 (1000)    
  H1a test(300) < test(1) and test(300) <= test(10); H1b |OOB-test| <= 2 SE at B=100,200,300; H1c OOB > test at B=5,10
  max_features=  1: H1a held; H1b failed (B=100: |diff| 0.0500 tol 0.0339; B=200: |diff| 0.0210 tol 0.0322; B=300: |diff| 0.0140 tol 0.0316); H1c held
  max_features= 16: H1a held; H1b held (B=100: |diff| 0.0005 tol 0.0288; B=200: |diff| 0.0030 tol 0.0283; B=300: |diff| 0.0025 tol 0.0285); H1c held
  max_features=256: H1a held; H1b held (B=100: |diff| 0.0045 tol 0.0298; B=200: |diff| 0.0070 tol 0.0296; B=300: |diff| 0.0000 tol 0.0298); H1c held

(2) out-of-bag strength s, correlation rho, bound rho(1-s^2)/s^2 (Breiman 2001 TR, Sec. 2.2, App. II)
  max_features      s     var(mr)  E sd   rho     c/s^2   bound   OOB err  test err  mean tree OOB err
      1        0.1201  0.0231  0.9901  0.0236  1.6374  1.6137  0.2150   0.2010    0.4398
        sd check: max|direct sd - sqrt(p1+p2-(p1-p2)^2)| 3.3e-16; max|direct sd - sqrt(p1+p2+(p1-p2)^2)| (sign as printed in (A2)) 0.0961; C5 held
     16        0.3200  0.0942  0.9452  0.1054  1.0297  0.9242  0.1620   0.1595    0.3396
        sd check: max|direct sd - sqrt(p1+p2-(p1-p2)^2)| 3.3e-16; max|direct sd - sqrt(p1+p2+(p1-p2)^2)| (sign as printed in (A2)) 0.2250; C5 held
    256        0.3860  0.1627  0.9204  0.1921  1.2895  1.0974  0.1800   0.1800    0.3065
        sd check: max|direct sd - sqrt(p1+p2-(p1-p2)^2)| 3.3e-16; max|direct sd - sqrt(p1+p2+(p1-p2)^2)| (sign as printed in (A2)) 0.2759; C5 held
  H2a s(1) < s(16) < s(256): held
  H2b rho(1) < rho(16) < rho(256): held
  H2c max_features=  1: s > 0 and bound >= test and OOB error: held
  H2c max_features= 16: s > 0 and bound >= test and OOB error: held
  H2c max_features=256: s > 0 and bound >= test and OOB error: held

(3) hard majority vote against averaged probabilities (predict), 300 trees, test patches
  max_features=  1, fully grown          disagree   0/2000; error hard 0.2010 soft 0.2010
      H3a held
  max_features= 16, fully grown          disagree   0/2000; error hard 0.1595 soft 0.1595
      H3a held
  max_features=256, fully grown          disagree   0/2000; error hard 0.1800 soft 0.1800
      H3a held
  max_features= 16, min_samples_leaf=10  disagree  35/2000; error hard 0.1605 soft 0.1620; on disagreements max|p-0.5| 0.0411, max|vote-0.5| 0.0267
      H3b held; H3c held; H3d held
  min_samples_leaf=10 forest: non-one-hot leaf probabilities on test 365132

(4) importance, max_features=16 forest: share of importance inside R (area fraction 0.2656) and top-20 pixels inside R
  MDI                            share in R 0.6096; top-20 in R 20; H4 share >= 0.5 held, top-20 >= 15 held
  permutation (test, 3 repeats)  share in R 0.7025; top-20 in R 20; H4 share >= 0.5 held, top-20 >= 15 held
  permutation importances below zero: 106 pixels
  MDI share per 2x2 block, x1000:
      8   8   7   8   8   8   8   9
      7   8   8  10   9   8   8   8
      8   9  10  13  21  12   7   8
      9   7  22 113  88  18   9   8
      9   8  20 108  95  17   8   8
     10   8  11  21  19  12  10   8
      8   9   9   9   7   8   7   9
      9   9   9   8   8   8   9  10
  permutation share per 2x2 block, x1000:
      2   4   4   2   3  20  10   0
      0  17  12  12   0  23   2   1
      9   3   3   5  40  25  11   0
      2  10  45 118  40  33   2   2
      0   6  49 128  74  35   0   4
      9   1  18  37  42   2  10  21
      1   6   4   2   2   0   5   2
     11  15  10   6   1   2  21  12

Checks. C1 held: the blob’s energy lies 99.19% inside $R$, the texture has unit variance to rounding, and the blob-free patches have pixel standard deviation 0.9974. The Bayes-optimal rule errs on 14.85% of the test patches. C2, C3 and C4 held for all three forests: the hand out-of-bag vote fractions equal scikit-learn’s exactly, the error counts agree (215, 162 and 180 of 1,000), and no fully grown tree gives anything but one-hot probabilities. C5 held for all three forests: the minus-sign formula reproduces each tree’s standard deviation to $3 \times 10^{-16}$, while the sign printed in (A2) is off by up to 0.0961, 0.2250 and 0.2759. With two classes, $p_1 + p_2 = 1$, so the correct form is $\sqrt{1 - m^2}$ with $m = 2p_1 - 1$, and the printed one is $\sqrt{1 + m^2}$; the gap grows with $|m|$, and the forests whose trees are more accurate on average (see (2)) show the larger maximum gaps.

(1) Number of trees. H1a held for all three forests: test error falls from 0.4720 with one tree to 0.2010 with 300 for max_features=1, from 0.3155 to 0.1595 for 16, and from 0.3005 to 0.1800 for 256. The curve flattens: for 16 and 256 features the error changes by less than 0.01 between 100 and 300 trees, while the one-feature forest is still improving between 100 and 300 (0.2270 to 0.2010). H1c held for all three: at 5 and 10 trees the out-of-bag error is above the test error (for example 0.2804 against 0.2470 at five trees with 16 features). Breiman’s reason is that each out-of-bag vote combines only the trees that left that example out, about a third of them; the B = 1 row shows the fraction, 364 of the 1,000 training patches having an out-of-bag vote from the first tree. H1b held for 16 and 256 features, where the two estimates differ by at most 0.0070 at 100, 200 and 300 trees, and failed for max_features=1: at 100 trees the out-of-bag error is 0.2770 and the test error 0.2270, a difference of 0.0500 against a tolerance of 0.0339. At 200 and 300 trees the differences (0.0210 and 0.0140) are within tolerance. The out-of-bag error is above the test error at every printed number of trees from 5 on for this forest, in the direction Breiman expects, but the output does not show why the gap at 100 trees is larger than for the other two forests.

(2) Strength and correlation. H2a and H2b held: strength rises from 0.1201 to 0.3200 to 0.3860 as the number of features tried at each split goes from 1 to 16 to 256, and correlation rises from 0.0236 to 0.1054 to 0.1921. The single trees improve in the same order (mean out-of-bag error 0.4398, 0.3396, 0.3065). With one feature per split the trees are barely better than chance and almost uncorrelated; with all features they are better but nearly twice as correlated as with 16. The ratio c/s² is lowest for 16 features (1.0297, against 1.2895 for 256 and 1.6374 for 1), and so is the test error (0.1595, against 0.1800 and 0.2010): here the ordering of c/s² matches the ordering of test error, the role Breiman gives the ratio. H2c held: the bound (1.6137, 0.9242 and 1.0974) is above every forest’s errors, but it says little, since two of the three bounds exceed 1. This is the looseness Breiman expected of it. On Breiman’s sonar data strength stopped rising past about four features while correlation kept rising (§6); on these patches strength is still rising between 16 and 256 features, and the forest with all features is nevertheless worse than the one with 16, as its larger c/s² ratio indicates.

(3) Votes. H3a held: the three fully grown forests never disagree with their own predict. This follows from C4: with scikit-learn’s defaults a tree splits until each leaf is pure or cannot be split, and C4 shows that every leaf a test patch reaches is pure, so each tree’s probability vector is one-hot, and averaging one-hot vectors is counting votes. The fourth forest, whose leaves hold at least 10 training patches, gives non-one-hot probabilities and disagrees on 35 of the 2,000 test patches; H3b held. H3c held: on every disagreement the averaged probability is within 0.0411 of ½ and the vote fraction within 0.0267, so the two rules differ only on near-ties. H3d held: the hard vote errs on 0.1605 of the test patches and the averaged probabilities on 0.1620.

(4) Importance. H4a, H4b and H4c held: 61% of the MDI importance and 70% of the permutation importance lie in $R$, which covers 27% of the patch, and all 20 of the most important pixels by either measure lie in $R$. The two maps differ outside $R$. MDI gives every block wholly outside $R$ a nearly constant share of 7 to 10 thousandths; in our reading, these are the splits that fully grown trees make deep in the tree on whatever pixel separates the last few training patches, which MDI credits because it is computed on the training data. Permutation importance is measured on the test patches; in the blocks wholly outside $R$ it is irregular, from 0 to 23 thousandths per block, and 106 pixels have a negative mean importance, meaning that shuffling them made the test accuracy slightly better on average over the three repeats. What the two maps share is the concentration inside $R$.

How this example was planned and changed. The plan for this example, its hypotheses and its criteria were written before any forest was fitted. Before writing it, on 12 November 2026, planning scripts that fit no forest computed, for candidate textures and blobs, the Bayes error and the error of the best single-pixel threshold. Candidate set-ups were rejected there: a coarser texture at weaker and stronger blob peaks (two scripts), where one pixel near the centre carried almost all of the information, and the finer texture with two blob widths at weaker peaks, where the Bayes error was too high; a last script chose the peak 1.2 among four peaks for the texture and blob width used here, and one invocation failed to parse its arguments and printed nothing. No value from these scripts is used in this article. The plan listed eight departures from the batch plan’s outline of this example: (1) the fourth forest with min_samples_leaf=10, added because with fully grown trees averaged probabilities and votes cannot differ, as H3a states; (2) importance printed as 2×2-block shares instead of full 16×16 maps; (3) scikit-learn’s test-set permutation importance in place of Breiman’s out-of-bag noising (described under Properties and Behavior); (4) hard-vote ties to class 0; (5) 300 trees instead of Breiman’s usual 100; (6) the added Bayes error, mean tree error, c/s², bound and (A2) check; (7) a single data seed and forest seed, so no range over seeds is claimed; (8) “concentrates on the blob region” made measurable as the H4 thresholds. A pilot of the planned script ran once. It printed every value shown here; the only change before the run shown was approved as a print-only repair: the words “held” and “failed” were added for C1–C5 and H3a–H3d, which the pilot had printed as values only. No measure, setting or seed changed. The run shown was repeated with byte-identical output.

Properties and Behavior

• Convergence instead of overfitting with more trees. Adding trees moves the forest’s error towards a limit (Theorem 1.2); in the example, the test error at 300 trees is the lowest or close to the lowest for every setting. More trees do not fix trees that are too weak or too correlated. The general diagnosis of overfitting is in Overfitting and Underfitting.
• Strength against correlation. Fewer features per split lower both the correlation and the strength. In Breiman’s experiments error was fairly flat over a range of $F$, with $F = 1$ sometimes best (§4, §6); on data with many weak inputs, such as his simulated 1,000-input problem, more features per split were needed to build up strength while correlation stayed low (§9, where $F = 1$ gave 10.7% test error and $F = 25$ 2.8%, with individual trees erring on 60–80% of cases). The example’s patches, whose faint blob is spread over many pixels, behave in that direction: 16 features beat 1.
• Out-of-bag estimates. Breiman (§3.1) cites his own earlier study as showing the out-of-bag estimate to be as accurate as a test set of the same size as the training set, and notes that it overestimates the current error while the error is still falling, so the forest should be run past the point where the test error converges. In the example, the one-feature forest’s out-of-bag error lies above its test error from 5 trees on, the direction Breiman describes, and H1b failed for it at 100 trees; the output does not show whether his mechanism is the cause. The estimate is only as honest as the independence of the training examples: patches cut from the same image, or pixels from the same field, are not independent, and Land-Cover Classification shows what random splits do with spatially correlated samples.
• Robustness to label noise. With 5% of the training labels flipped, Breiman’s forests generally changed their error much less than AdaBoost did on the same data sets (§8, Table 4; on ecoli the increases were similar), which he attributes to AdaBoost concentrating weight on the mislabelled examples.
• Variable importance. Breiman (§10) measures importance by permuting one input’s values in each tree’s out-of-bag examples, running them down the tree, and reporting the percent increase in the out-of-bag error. He also notes how correlated inputs share importance: of two identical informative inputs, each looks important when noised alone, but once one is used the other adds nothing. scikit-learn’s feature_importances_ is instead the mean decrease in impurity (MDI; the user guide refers to Louppe, 2014, for more), and its user guide warns that MDI is computed on training statistics, so it need not reflect what helps on held-out data, and that it favours features with many unique values; it recommends permutation importance (sklearn.inspection.permutation_importance, which shuffles a feature in a given data set) as an alternative. In the example all 256 pixels are continuous, so cardinality plays no role, and the difference between the two maps outside $R$ comes from where and how each is measured.
• Votes against probabilities. scikit-learn’s user guide states that, “in contrast to the original publication”, the implementation averages the trees’ probabilistic predictions instead of letting each tree vote; the source confirms it (predict takes the argmax of predict_proba, which divides the summed tree probabilities by the number of trees). The same user-guide page elsewhere says that random forests “use a majority vote” (in its comparison with histogram gradient boosting), which contradicts this; the source code is the authority. For fully grown trees the two rules coincide, as the example shows; they differ only when leaves are impure, and then only on near-ties. scikit-learn’s out-of-bag decision function averages probabilities in the same way.

Limitations

• Little interpretability. Breiman calls a forest “impenetrable” to simple interpretation (§10); importance scores rank inputs but do not show how they interact, and correlated inputs share or hide each other’s importance.
• Memory and prediction cost. Fully grown trees are large, and a forest stores hundreds of them; prediction traverses every tree. The user guide’s parameters for limiting size are the cost of a smaller model.
• Axis-aligned splits. Each tree inherits the decision tree’s staircase boundaries. On raw pixels, a boundary that depends on sums of many pixels, like the blob detector the Bayes rule uses here, needs many splits; in our reading, averaging smooths the staircase but does not remove the need for many splits. Forest-RC’s splits on linear combinations of inputs are not axis-aligned.
• Hand-made features. On images, forests work on the features they are given: pixel values, pixel differences or filter responses. They do not learn the features themselves; networks that learn features from pixels are the subject of Deep Learning.
• No extrapolation in regression. Each leaf of a regression tree predicts an average of training targets (the form Breiman’s Appendix I uses), so an average of such trees stays within the range of the training targets.

Variants

• Bagging, pasting, random subspaces and random patches. scikit-learn’s user guide names these variants by how each predictor’s training set is drawn: random subsets of samples (pasting), samples with replacement (bagging), random subsets of features (random subspaces, after Ho, 1998), or both (random patches). Its BaggingClassifier wraps any estimator. Random subspaces choose features per tree, where a random forest chooses them per node; Breiman (§1.1) lists Ho’s method among the earlier randomized ensembles.
• Forest-RC (Breiman, §5): splits on random linear combinations of a few inputs, which Breiman found compared more favourably with AdaBoost than Forest-RI.
• Extremely randomized trees (Geurts, Ernst and Wehenkel, 2006). As scikit-learn’s user guide describes them, they draw thresholds at random for each candidate feature and pick the best of these random thresholds, which usually reduces variance a bit more at the cost of a slightly greater increase in bias; scikit-learn’s ExtraTreesClassifier uses the whole training set by default (bootstrap=False). Dollár and Zitnick (2013, §2.2) describe the randomness of decision forests in the same terms: diversity comes from subsampling the data for each tree or the features and splits at each node, injecting it at the nodes tends to produce more accurate models, and individual trees’ accuracy is sacrificed for a diverse ensemble.
• Randomized trees for shape recognition. Breiman (§1.1, §3) credits Amit and Geman (1997), who searched over a random selection of many geometric features at each node for handwritten character recognition, as the start of his ideas.
• Structured and regression forests in vision. Dollár and Zitnick’s structured forests store a whole edge mask at each leaf and average edge maps across trees (Edge Detection); local binary features regress each facial landmark’s offset with a forest (Facial Landmark Detection); regression forests predicted cell-centre proximity maps (Cell Detection); and forests predicted object coordinates from RGB-D input (Object Pose Estimation). These are different from the randomized k-d trees of approximate nearest neighbor search, which are also called forests but index points rather than predict labels, and from the boosted decision forests of pedestrian detection, which are built by boosting.
• Boosting. Boosting also combines trees, but fits them one after another to reweighted data. Breiman (§7) conjectured that AdaBoost in its later stages behaves like a random forest. Murphy (§18.4) shows boosting beating random forests on a spam data set, at the cost of fitting trees sequentially.