# Random forests

> Average many trees trained on bootstrap samples with random feature subsets, reducing variance.

Source: https://www.mlfoundry.in/learn/random-forests  
Section: ML Algorithms › Supervised · Classification  
Level: core · 18 min read · updated 2026-10-07

**A random forest classifier:** is a collection of $T$ decision trees. Each tree is grown on a **bootstrap sample** of the rows (drawn with replacement). At **every split** it may only look at a random subset of $m$ of the $d$ features. To classify $x$, the forest averages the trees' class-probability estimates and outputs the most probable class. Breiman (2001) called this *soft voting*.

- **Task:** Classification (binary or multi-class). For the regression version see *Random forest regression*.
- **Input → output:** $x\in\mathbb R^d$ → class probabilities $\hat p(c\mid x)=\tfrac1T\sum_t p_t(c\mid x)$ and the label $\arg\max_c \hat p(c\mid x)$
- **Learns:** $T$ deep, unpruned classification trees. Each leaf stores the class proportions of the bootstrap rows that land in it.
- **Training cost:** about $O(T\cdot m\cdot n\log^2 n)$ for balanced trees. The trees are independent, so training runs fully in parallel.
- **Prediction cost:** $O(T\cdot\text{depth})$ comparisons per point
- **Key hyperparameters:** `n_estimators` $T$, `max_features` $m$ (default $\sqrt d$), `max_depth` / `min_samples_leaf`, `max_samples`, `class_weight`
- **Assumptions:** None about distributions. The boundaries are unions of axis-aligned boxes. The model works best when many features each carry some signal.

## The problem

A single fully grown tree (see *Decision trees*) has **low bias and high variance**. It fits the training set exactly. But change a few rows and the root split can change, and the whole tree below it changes too. The tree's probabilities are a second problem. A pure leaf says $P(\text{class})=1$, so a fully grown tree outputs only hard 0/1 confidences. One confident mistake makes the log-loss infinite.

Concretely, on the 569-row breast-cancer dataset (398 rows for training, 171 for testing), one fully grown tree scores **90.6%** test accuracy. A forest of 100 trees with $m=\sqrt{30}\to5$ scores **95.3%**. Test log-loss drops from **3.23** for the single tree to **0.33**. We want to keep the trees' flexibility and remove their instability.

## The idea

Averaging many noisy estimates cancels their noise, but only the part of the noise they do **not** share. If you grew 100 trees on the same data you would get 100 copies of one tree, and averaging would do nothing. So the forest injects two kinds of randomness to make the trees *disagree*:

1. **Bagging (rows).** Each tree sees a bootstrap sample: $n$ rows drawn with replacement. Some rows appear two or three times and about a third are missing. Each tree therefore overfits a different version of the data.
2. **Feature subsampling (columns).** At every split the tree may only choose among $m<d$ randomly drawn features. A dominant feature then cannot sit at the top of every tree. Other features get their turn, and the trees' errors become less correlated.
3. **Vote.** Each tree reports the class proportions in the leaf $x$ falls into. The forest averages these. The average is a smoother, better-calibrated probability than any single tree's 0/1 answer.

**Vocabulary**

- **Bootstrap sample:** $n$ indices drawn uniformly **with replacement** from $\{1,\dots,n\}$. A row's *multiplicity* is how many times it was drawn: 0, 1, 2, …
- **In-bag / out-of-bag (OOB):** For one tree, rows with multiplicity ≥ 1 are in-bag (used to grow it). Rows with multiplicity 0 are out-of-bag: the tree never saw them.
- **OOB estimate:** Score each training row using only the trees for which it was out-of-bag, then measure accuracy. This gives a validation estimate without a held-out split.
- **max_features (m, mtry):** How many features are drawn at random, afresh at **each node**, as split candidates. $m=d$ is plain bagging. The classification default is $\lfloor\sqrt d\rfloor$.
- **Soft vote:** Average the trees' probability vectors and take the argmax. scikit-learn does this.
- **Hard vote:** Each tree casts one vote for its predicted class and the majority wins. This is Breiman's original formulation.
- **Strength s:** How strongly the forest favours the correct class on average: the expected **margin** (below).
- **Correlation ρ̄:** How similar two trees' errors are. Low correlation means averaging cancels more of the error.

## The math

**Leaf probabilities.** Let tree $t$ have bootstrap multiplicities $w_{ti}$. Let $\ell_t(x)$ be the leaf that $x$ lands in. The tree's probability for class $c$ is the weighted share of class $c$ in that leaf:

$$
p_t(c\mid x)=\frac{\sum_{i:\,x_i\in\ell_t(x)} w_{ti}\,\mathbb 1[y_i=c]}{\sum_{i:\,x_i\in\ell_t(x)} w_{ti}}
$$

- $w_{ti}$: number of times row $i$ was drawn into tree $t$'s bootstrap sample (0 = out-of-bag)
- $\ell_t(x)$: the leaf of tree $t$ that $x$ falls into
- $\mathbb 1[y_i=c]$: 1 if row $i$ has class $c$, else 0

Each tree is grown greedily, exactly as in *Decision trees*. The only difference is that the candidate features at each node are restricted to a random subset $\mathcal F\subset\{1..d\}$ with $|\mathcal F|=m$. A node picks the feature $j\in\mathcal F$ and threshold $\tau$ that minimise the weighted Gini impurity $\tfrac{n_L}{n}G(L)+\tfrac{n_R}{n}G(R)$, where $G=1-\sum_c p_c^2$ and every count includes the multiplicities.

$$
\hat p(c\mid x)=\frac1T\sum_{t=1}^{T}p_t(c\mid x),\qquad \hat y(x)=\arg\max_c\ \hat p(c\mid x)
$$

- $\hat p(c\mid x)$: forest probability of class c (soft vote)
- $T$: number of trees
- $\hat y(x)$: predicted label

The hard vote instead counts $V_c(x)=\tfrac1T\sum_t\mathbb 1[\arg\max_k p_t(k\mid x)=c]$. The two rules usually agree. They differ when a minority of trees is *very* sure and the majority is only mildly sure. The worked example below is one such case.

## Why averaging probabilities helps log-loss

For a point with true class $y$, the log-loss of a probability $p$ is $-\log p(y)$. The function $-\log$ is **convex**, so by Jensen's inequality the loss of the average is at most the average loss:

$$
-\log\Big(\frac1T\sum_t p_t(y\mid x)\Big)\ \le\ \frac1T\sum_t\big(-\log p_t(y\mid x)\big)
$$

- $p_t(y\mid x)$: probability tree t gives the true class
- $-\log$: per-example cross-entropy (log-loss)

The inequality is strict whenever the trees disagree. If a single tree is confidently wrong ($p_t(y)=0$), its own loss is infinite. Inside an average it costs only a finite amount, as long as some other tree gives the true class positive probability. This is why a forest's probabilities are usable even though every one of its trees is a 0/1 overfitter.

## Why decorrelation matters more than T

Fix a point $x$ and treat each tree's output $h_t=p_t(c\mid x)$ as a random variable over the bootstrap and feature draws. Each has variance $\sigma^2$, and each pair has correlation $\rho$. The variance of their mean follows by expanding the square:

$$
\operatorname{Var}\Big(\frac1T\sum_t h_t\Big)=\frac1{T^2}\Big(\underbrace{T\sigma^2}_{\text{diagonal}}+\underbrace{T(T-1)\rho\sigma^2}_{\text{off-diagonal}}\Big)=\rho\sigma^2+\frac{1-\rho}{T}\,\sigma^2
$$

- $\sigma^2$: variance of one tree's output at x
- $\rho$: correlation between two trees' outputs

Adding trees shrinks only the second term. The floor $\rho\sigma^2$ can be lowered only by making the trees less alike, and that is the job of `max_features`. The regression article (*Random forest regression*) works through this formula in detail with squared error. For classification, Breiman proved a bound stated in terms of *margins* instead.

$$
\text{mg}(x,y)=P_\Theta\big(h(x,\Theta)=y\big)-\max_{j\ne y}P_\Theta\big(h(x,\Theta)=j\big),\qquad s=\mathbb E_{x,y}\,\text{mg}(x,y)
$$

- $\Theta$: the random draws (bootstrap + feature subsets) that define one tree
- $h(x,\Theta)$: class predicted by a tree built with draws Θ
- $\text{mg}$: margin: share of trees voting for the right class minus share for the best wrong class. mg > 0 means the forest is correct at x.
- $s$: strength: the average margin

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

- $PE^{*}$: generalisation error of the infinite forest (T → ∞)
- $\bar\rho$: mean correlation between the trees' raw margins

The bound says you want **strong** trees (large $s$) that are **uncorrelated** (small $\bar\rho$), and $m$ trades one against the other. A larger $m$ lets each node use its best feature, so each tree is more accurate and $s$ rises. But all trees then pick the same top features, so $\bar\rho$ rises too. With $m=1$ the trees are weak but nearly independent. The table in *Tuning* measures this trade-off on real data.

**Out-of-bag rows.** A given row is missed by one draw with probability $1-\tfrac1n$, so it is missed by all $n$ draws with probability $(1-\tfrac1n)^n\to e^{-1}\approx0.368$. With $n=12$ this is $0.352$, or $4.2$ rows per tree on average. Each row is therefore out-of-bag for roughly a third of the trees, and those trees give an honest vote on it:

$$
\hat p^{\text{oob}}(c\mid x_i)=\frac{1}{|O_i|}\sum_{t\in O_i}p_t(c\mid x_i),\qquad O_i=\{t:\ w_{ti}=0\}
$$

- $O_i$: the trees that never saw row $i$
- $\hat p^{\text{oob}}$: OOB probability; the OOB accuracy is the share of rows where its argmax equals yᵢ

**What each hyperparameter does to the formulas**

- **T (n_estimators):** Shrinks only $(1-\rho)\sigma^2/T$ and the Monte-Carlo noise in $\hat p$. Error falls and then plateaus, and it never rises. More trees cost time, not accuracy.
- **m (max_features):** Raising $m$ increases strength $s$ and correlation $\bar\rho$ together. Smaller $m$ also makes each split cheaper: $O(m\,n\log n)$ instead of $O(d\,n\log n)$.
- **Depth / min_samples_leaf:** Deeper trees have lower bias and higher $\sigma^2$, which the averaging absorbs. Larger leaves give each tree smoother, less extreme $p_t$, at some cost in bias.
- **max_samples:** Smaller bootstrap samples make the trees more different (lower $\rho$) and cheaper to grow, but individually weaker.
- **class_weight:** Multiplies each row's $w_{ti}$ by a class weight inside the Gini counts and leaf proportions. This shifts the leaf probabilities toward rare classes.

## Worked example: will the student pass?

Twelve students, two features: study hours $x_1$ and sleep hours $x_2$. Seven passed. We grow a tiny forest by hand: **T = 3 stumps** (depth-1 trees), each with $m=1$ random feature. Real forests grow deep trees. Stumps keep the hand calculation short, and the figure below lets you switch to full depth. The new student is $q=(5,\ 6.5)$: 5 hours of study and 6.5 hours of sleep.

Training data. Highlighted: rows 6, 7 and 9, which happen to be in-bag for all three trees and so get no OOB vote.

| Row | Study x₁ (h) | Sleep x₂ (h) | Result |
| --- | --- | --- | --- |
| 1 | 1 | 5 | fail |
| 2 | 2 | 7.5 | fail |
| 3 | 3 | 4.5 | fail |
| 4 | 3.5 | 8 | pass |
| 5 | 4 | 6 | pass |
| 6 | 5 | 5 | fail |
| 7 | 5.5 | 7 | pass |
| 8 | 6 | 8.5 | pass |
| 9 | 6.5 | 4.5 | fail |
| 10 | 7 | 6 | pass |
| 11 | 8 | 5.5 | pass |
| 12 | 9 | 7.5 | pass |

The random draws for each tree: 12 row indices with replacement, and the one feature the root may use.

| Tree | Bootstrap rows (12 draws) | Out-of-bag | Feature drawn | Class counts |
| --- | --- | --- | --- | --- |
| 1 | 1, 2, 2, 3, 6, 6, 7, 9, 10, 12, 12, 12 | 4, 5, 8, 11 | sleep x₂ | 7 fail / 5 pass |
| 2 | 2, 2, 2, 4, 5, 5, 6, 7, 8, 8, 9, 11 | 1, 3, 10, 12 | sleep x₂ | 5 fail / 7 pass |
| 3 | 3, 3, 3, 3, 6, 6, 7, 7, 7, 8, 9, 11 | 1, 2, 4, 5, 10, 12 | study x₁ | 7 fail / 5 pass |

**Tree 1, by hand**

1. Parent Gini with multiplicities: 7 fail, 5 pass out of 12, so $G=1-(\tfrac7{12})^2-(\tfrac5{12})^2=0.486$.
2. Distinct in-bag sleep values: 4.5, 5, 6, 7, 7.5. The candidate thresholds are the midpoints 4.75, 5.5, 6.5 and 7.25.
3. $x_2\le5.5$ sends rows 1, 3, 6, 6, 9 left: **5 fail / 0 pass**, a pure node with $G_L=0$. Rows 2, 2, 7, 10, 12, 12, 12 go right: **2 fail / 5 pass**, with $G_R=1-(\tfrac27)^2-(\tfrac57)^2=0.408$.
4. Weighted Gini $=\tfrac5{12}(0)+\tfrac7{12}(0.408)=0.238$. This is the lowest of the four candidates (table below), a decrease of $0.486-0.238=0.248$.
5. Leaves: $P(\text{pass})=0/5=0$ on the left and $5/7=0.714$ on the right. The query has $x_2=6.5>5.5$, so **tree 1 says P(pass) = 0.714**.

Tree 1's candidate thresholds on sleep (counts are fail/pass, including repeats).

| Threshold | Left | Right | G left | G right | Weighted Gini |
| --- | --- | --- | --- | --- | --- |
| x₂ ≤ 4.75 | 2/0 | 5/5 | 0.000 | 0.500 | 0.417 |
| **x₂ ≤ 5.5** | **5/0** | **2/5** | **0.000** | **0.408** | **0.238** |
| x₂ ≤ 6.5 | 5/1 | 2/4 | 0.278 | 0.444 | 0.361 |
| x₂ ≤ 7.25 | 5/2 | 2/3 | 0.408 | 0.480 | 0.438 |

**Trees 2 and 3, the vote, and OOB**

1. **Tree 2** (sleep, parent 5 fail / 7 pass, $G=0.486$). Its best threshold is $x_2\le5.25$: left 2/0, right 3/7, weighted Gini $0.350$. The runner-up $x_2\le7.75$ scores $0.370$. Since $q$ has $x_2=6.5$, it goes right: **P(pass) = 7/10 = 0.700**.
2. **Tree 3** may only use study hours. Its best threshold is $x_1\le5.25$: left **6 fail / 0 pass** (row 3 four times, row 6 twice), right 1/5, weighted Gini $0.139$. Since $q$ has $x_1=5\le5.25$, it goes left: **P(pass) = 0**.
3. **Hard vote:** trees 1 and 2 say pass and tree 3 says fail, so the majority says **pass** (2–1).
4. **Soft vote:** $\hat p(\text{pass}\mid q)=\tfrac13(0.714+0.700+0)=0.471<0.5$, so the forest says **fail**. Tree 3 is certain, the other two are only mildly sure, and certainty outweighs the head-count.
5. **OOB.** Score each row only with the trees that did not see it. Row 4 $(3.5,8)$ is OOB for trees 1 and 3: $\tfrac12(0.714+0)=0.357$, so the prediction is fail, which is wrong. Row 10 $(7,6)$ is OOB for trees 2 and 3: $\tfrac12(0.700+0.833)=0.767$, pass, which is correct. Rows 6, 7 and 9 were in every bag and get no OOB vote. Over the 9 rows that do, **6 are correct: OOB accuracy 6/9 = 67%**. The misses are rows 4, 5 and 11.

Three stumps are not really a forest. The soft vote at $q$ is still swinging from tree to tree. With the same draws continued to **100 stumps**, $\hat p(\text{pass}\mid q)$ settles at **0.723** (pass) and OOB accuracy reaches **11/12**. A scikit-learn forest of 500 fully grown trees on these 12 rows gives **0.868** (see *In code*). The final answer is driven by the many trees, not by any one of them.

## See it work

> Figure: The 12 students from the table; ★ is q = (5, 6.5). It opens on the hand-built forest: 3 stumps, max_features = 1. Two trees vote pass (dots at 0.714 and 0.700) and one votes fail (0), so the mean is 0.471 and the forest says FAIL, with OOB accuracy 6/9. Drag T to 100: the mint curve settles and P(pass) = 0.723, OOB 11/12. Press ▶ to inspect one tree: its split lines, bootstrap repeats (×k) and hollow out-of-bag rows. Switch max_features 1 → 2 (plain bagging) at T = 100 and the mean tree correlation ρ̄ rises from 0.41 to 0.52 for stumps (0.53 → 0.64 at full depth). Drag ★ anywhere, and compare soft and hard voting.

Things to try: set `max_depth` to full and step through trees 1–5. Each tree's regions are jagged and different, while the forest's colouring changes gradually. Then switch to hard voting. The colouring becomes the share of trees voting pass, and at T = 3 the colour at ★ flips to pass.

> Figure: The same algorithm on 50 noisy two-moon points: each tree sees a bootstrap sample and one random feature per split. Alone the trees are jagged; their vote is smooth — test accuracy 79% for one full tree, 92% for 25.

## The algorithm, step by step

**fit(X, y, T, m)**

1. **For** $t=1\ldots T$ (in parallel): draw $n$ row indices with replacement and record the multiplicities $w_{t\cdot}$. Rows with $w_{ti}=0$ are this tree's OOB set.
2. **Grow** a tree on the weighted rows. At each node, draw $m$ features without replacement. For each, scan the sorted values and pick the threshold with the lowest weighted Gini (or entropy). Split on the best (feature, threshold) pair.
3. **Stop** a node when it is pure or hits `max_depth` / `min_samples_leaf`. The default is to grow until pure, with no pruning. Store the leaf's class proportions.
4. **OOB (optional):** for every row $i$, average $p_t(\cdot\mid x_i)$ over the trees in $O_i$. Compare the argmax with $y_i$ to get the OOB accuracy.
5. **predict_proba(x):** route $x$ down every tree, average the leaf proportions, and take the argmax.

**Complexity**

- **Training:** One node costs $O(m\,n_{\text{node}}\log n_{\text{node}})$ for sorting. Summed over a balanced tree's $\log n$ levels this is $O(m\,n\log^2 n)$ per tree, times $T$. Trees are independent, so the wall-clock time divides by the number of cores.
- **Prediction:** $O(T\cdot\text{depth})$, roughly $O(T\log n)$ for balanced trees
- **Memory:** Fully grown trees have up to $n$ leaves each, so the model size is $O(T\,n)$ nodes. Large forests can take gigabytes on big datasets.

## Tuning and variants

Real data shows the strength–correlation trade-off directly. Below: 500 trees on the breast-cancer data ($d=30$; 398 training rows, 171 test rows). *Tree accuracy* is the mean test accuracy of the individual trees, a proxy for strength. $\bar\rho$ is Breiman's raw-margin correlation, measured on the test set.

Raising max_features makes every tree stronger but the trees more alike. Test accuracy peaks at m = 5 = ⌊√30⌋, the default. All differences here are within a few test rows.

| max_features m | Tree accuracy | Correlation ρ̄ | Strength s | OOB accuracy | Test accuracy |
| --- | --- | --- | --- | --- | --- |
| 1 | 0.885 | 0.306 | 0.771 | 0.965 | 0.936 |
| 2 | 0.901 | 0.359 | 0.803 | 0.965 | 0.942 |
| **5 (√d)** | **0.911** | **0.411** | **0.823** | **0.965** | **0.953** |
| 10 | 0.914 | 0.440 | 0.828 | 0.970 | 0.947 |
| 30 (bagging) | 0.915 | 0.484 | 0.830 | 0.960 | 0.930 |

Same data, max_features = √d, growing T. Accuracy plateaus by about 100 trees; log-loss mostly falls because the probabilities stop being 0/1.

| Trees T | 1 | 5 | 10 | 25 | 100 | 500 |
| --- | --- | --- | --- | --- | --- | --- |
| Test accuracy | 0.889 | 0.942 | 0.936 | 0.936 | 0.953 | 0.953 |
| Test log-loss | 3.84 | 0.73 | 0.52 | 0.32 | 0.33 | 0.32 |

**Practical tuning, in order of importance**

- **n_estimators:** Use as many as you can afford (200–1000). Plot OOB error against T and stop adding trees once it is flat. T is not a regularizer, so there is nothing to cross-validate.
- **max_features:** Try $\{\sqrt d/2,\ \sqrt d,\ 2\sqrt d\}$ or a few fractions. This is the hyperparameter that matters most. With many irrelevant features, raise $m$ so that a useful one is usually among the candidates: a given feature is available at a node with probability $m/d$.
- **min_samples_leaf / max_depth:** The default (grow until pure) is usually fine for accuracy. Raise `min_samples_leaf` (e.g. 3–10) for smoother probabilities, smaller models and noisy labels.
- **class_weight:** Use `"balanced_subsample"` for imbalanced classes. It reweights classes inside each bootstrap sample.
- **max_samples:** Sample a fraction of rows per tree (e.g. 0.3–0.7) on large datasets. This is faster and the trees are more diverse.
- **criterion:** `gini` or `entropy` (log-loss). They rarely differ, as with single trees.

**Relatives**

- **Plain bagging:** $m=d$: only the bootstrap provides randomness. It is the max_features = 2 setting in the figure.
- **Extra Trees:** Also draws the split *thresholds* at random and usually skips the bootstrap, which makes it even less correlated and faster. See *Extra Trees*.
- **Balanced random forest:** Each tree draws a bootstrap sample with equal class counts (imbalanced-learn's `BalancedRandomForestClassifier`).
- **Boosting:** Builds trees *sequentially*, each one fitting the current errors. It reduces bias where forests reduce variance. See *Gradient boosting* and *AdaBoost*.
- **Isolation forest:** Uses random trees for anomaly detection instead: anomalies are isolated in fewer splits.

> **The OOB estimate is a free validation set:** Each tree never saw about 37% of the rows, so every training row receives honest votes from roughly a third of the forest. The OOB accuracy is close to a cross-validation estimate at no extra training cost. It is slightly pessimistic, because each row is scored by only about T/3 trees. Use it to choose `max_features` and `min_samples_leaf` without a separate split.

> **Soft voting is what makes the probabilities useful:** The worked example showed one certain tree outweighing two mildly sure ones: 0.471 overall versus a 2–1 head-count. Averaging probabilities is also what gives the log-loss guarantee from Jensen's inequality. Hard votes throw away each tree's confidence.

## In code

```python
import numpy as np

def gini(counts):
    n = counts.sum()
    return 0.0 if n == 0 else 1.0 - ((counts / n) ** 2).sum()

def best_split(X, y, w, features):
    """Lowest weighted Gini over the given features; w = bootstrap multiplicities."""
    best = (np.inf, None, None)
    for j in features:
        v = np.unique(X[w > 0, j])
        for t in (v[:-1] + v[1:]) / 2:
            L = X[:, j] <= t
            cl = np.bincount(y, w * L, minlength=2)
            cr = np.bincount(y, w * ~L, minlength=2)
            score = cl.sum() * gini(cl) + cr.sum() * gini(cr)
            if score < best[0] - 1e-12:
                best = (score, j, t)
    return best

def grow(X, y, w, max_features, rng, max_depth=None, depth=0, features=None):
    counts = np.bincount(y, w, minlength=2)
    leaf = {"p": counts[1] / counts.sum()}                 # leaf stores P(class 1)
    if counts.min() == 0 or depth == max_depth:
        return leaf
    if features is None:                                   # fresh random subset at every node
        usable = [j for j in rng.permutation(X.shape[1]) if np.unique(X[w > 0, j]).size > 1]
        features = usable[:max_features]
    _, j, t = best_split(X, y, w, features)
    if j is None:
        return leaf
    L = X[:, j] <= t
    return {"j": j, "t": t,
            "L": grow(X, y, w * L, max_features, rng, max_depth, depth + 1),
            "R": grow(X, y, w * ~L, max_features, rng, max_depth, depth + 1)}

def proba(node, x):
    while "j" in node:
        node = node["L"] if x[node["j"]] <= node["t"] else node["R"]
    return node["p"]

def fit_forest(X, y, T=100, max_features=1, max_depth=None, seed=0):
    rng, n = np.random.default_rng(seed), len(y)
    forest = []
    for _ in range(T):
        w = np.bincount(rng.integers(0, n, n), minlength=n).astype(float)   # bootstrap
        forest.append((grow(X, y, w, max_features, rng, max_depth), w))
    return forest

def predict_proba(forest, x):                              # soft vote
    return np.mean([proba(tree, x) for tree, _ in forest])

def oob_accuracy(forest, X, y):
    right = seen = 0
    for i in range(len(y)):
        ps = [proba(tree, X[i]) for tree, w in forest if w[i] == 0]
        if ps:
            seen += 1
            right += (np.mean(ps) > 0.5) == y[i]
    return right / seen

# ---- the worked example ----------------------------------------------------
X = np.array([[1, 5], [2, 7.5], [3, 4.5], [3.5, 8], [4, 6], [5, 5],
              [5.5, 7], [6, 8.5], [6.5, 4.5], [7, 6], [8, 5.5], [9, 7.5]])
y = np.array([0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1])        # 1 = pass
q = np.array([5, 6.5])

# Replay the article's three bootstrap draws and feature draws (stumps).
boots = [[1, 2, 1, 0, 0, 2, 1, 0, 1, 1, 0, 3],
         [0, 3, 0, 1, 2, 1, 1, 2, 1, 0, 1, 0],
         [0, 0, 4, 0, 0, 2, 3, 1, 1, 0, 1, 0]]
feats = [[1], [1], [0]]                                    # sleep, sleep, study
three = [(grow(X, y, np.array(b, float), 1, None, max_depth=1, features=f), np.array(b))
         for b, f in zip(boots, feats)]
for k, (tree, _) in enumerate(three, 1):
    print(f"tree {k}: x{tree['j'] + 1} <= {tree['t']}   P(pass | q) = {proba(tree, q):.3f}")
print("soft vote P(pass | q) =", round(predict_proba(three, q), 3))
print("hard vote: passes =", sum(proba(t, q) > 0.5 for t, _ in three), "of 3")
print("OOB accuracy (3 stumps) =", round(oob_accuracy(three, X, y), 3))

# A real forest: 200 fully grown trees, one random feature per split.
rf = fit_forest(X, y, T=200, max_features=1, seed=0)
print("200 trees: P(pass | q) =", round(predict_proba(rf, q), 3),
      " OOB accuracy =", round(oob_accuracy(rf, X, y), 3))
```

From scratch in NumPy: weighted Gini trees with a fresh random feature subset at every node, soft voting, OOB accuracy. The demo replays the article's three draws, then grows a real forest. Prints: 0.714 / 0.700 / 0.000, soft 0.471, 2 of 3 hard votes, OOB 0.667; then 200 trees: P(pass | q) = 0.84, OOB 0.75.

```python
import numpy as np
from sklearn.ensemble import RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier

X = np.array([[1, 5], [2, 7.5], [3, 4.5], [3.5, 8], [4, 6], [5, 5],
              [5.5, 7], [6, 8.5], [6.5, 4.5], [7, 6], [8, 5.5], [9, 7.5]])
y = np.array([0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1])
q = np.array([[5, 6.5]])

# 1) The three hand-built stumps: bootstrap = sample weights, feature = one column.
boots = [[1, 2, 1, 0, 0, 2, 1, 0, 1, 1, 0, 3],
         [0, 3, 0, 1, 2, 1, 1, 2, 1, 0, 1, 0],
         [0, 0, 4, 0, 0, 2, 3, 1, 1, 0, 1, 0]]
ps = []
for w, j in zip(boots, [1, 1, 0]):
    stump = DecisionTreeClassifier(max_depth=1).fit(X[:, [j]], y, sample_weight=w)
    ps.append(stump.predict_proba(q[:, [j]])[0, 1])
    print(f"x{j + 1} <= {stump.tree_.threshold[0]}  P(pass|q) = {ps[-1]:.3f}")
print("soft vote:", round(np.mean(ps), 3))

# 2) The library forest.
rf = RandomForestClassifier(n_estimators=500, max_features=1, oob_score=True,
                            random_state=0).fit(X, y)
print("P(fail, pass | q) =", rf.predict_proba(q).round(3))
print("OOB accuracy =", round(rf.oob_score_, 3))
print("impurity importances (study, sleep) =", rf.feature_importances_.round(3))
```

scikit-learn. Part 1 reproduces the hand-built stumps, with the bootstrap passed as sample weights: thresholds 5.5, 5.25 and 5.25, soft vote 0.471. Part 2 is the library forest (500 full trees, max_features = 1): P(pass | q) = 0.868, OOB accuracy 0.75, importances 0.431 (study) and 0.569 (sleep).

> **Why the numbers differ between implementations:** The scratch forest uses NumPy's random generator and scikit-learn uses its own, so the bootstrap samples differ. On 12 rows, each OOB row is a large share of the score. Both forests agree that q passes (0.84 and 0.868), and both reach OOB 9/12. The per-tree replay matches exactly.

**Strengths**

- Tabular classification where you want a strong model with almost no tuning. The defaults are usually within a point or two of the best.
- You want a built-in validation estimate (OOB), robustness to outliers and monotone transforms, and no feature scaling.
- Many weak or noisy features, including more features than rows (genomics).
- Training must parallelize, or you need a dependable baseline before trying boosting.

**Limitations**

- You need the last percent of accuracy on tabular data: tuned gradient boosting (XGBoost, LightGBM, CatBoost) usually wins.
- Tight latency or memory budgets: hundreds of deep trees are large and slow to evaluate.
- You need calibrated probabilities out of the box: forest probabilities are pulled away from 0 and 1, so calibrate them (isotonic or Platt) first.
- Very high-dimensional sparse data such as text, where linear models are faster and often better. Or a smooth or diagonal boundary that a linear model captures directly.

- **Remote sensing:** Land-cover classification of satellite pixels from spectral bands. Random forests are a standard method here, valued for robustness and OOB error.
- **Genomics & medicine:** Disease classification from thousands of gene-expression or SNP features with few patients, where the many-weak-features setting suits feature subsampling.
- **Fraud & credit risk:** A strong first model on mixed tabular data, with `class_weight` for the rare positive class.
- **Bioacoustics & ecology:** Species identification from audio or habitat features, plus permutation importances to see which variables drive the predictions.

> **Impurity importances mislead:** `feature_importances_` sums each feature's Gini decreases on the training bags. It favours continuous and high-cardinality features, even pure noise like an ID column. Correlated features also split the credit between them, so each looks weak. Use `permutation_importance` on held-out data (or SHAP) before drawing conclusions.

> **Training accuracy tells you nothing:** Fully grown trees memorise their bags, so the forest scores close to 100% on the training rows almost by construction. Judge it by OOB or held-out accuracy, never by the training score.

> **Leakage through duplicates and groups:** OOB and random splits assume the rows are independent. If the same patient, user or near-duplicate image appears in several rows, its copies leak information between in-bag and OOB rows, and both estimates come out optimistic. Use group-aware cross-validation instead.

**Question:** Three trees give $P(\text{pass}\mid x) = 0.9,\ 0.4,\ 0.4$. What do soft and hard voting predict?

- A. Both pass
- B. Both fail
- C. Soft: pass (0.567); hard: fail (1–2)
- D. Soft: fail; hard: pass

**Answer:** C. Soft: pass (0.567); hard: fail (1–2) — Soft: $(0.9+0.4+0.4)/3=0.567>0.5$, so pass. Hard: only one tree has $p>0.5$, so fail wins 2–1. This is the mirror image of the worked example.

**Question:** Tree outputs have pairwise correlation $\rho=0.3$ and variance $\sigma^2=1$. What is the variance of a 10-tree average, and the best any number of trees can do?

- A. 0.1 and 0
- B. 0.37 and 0.3
- C. 0.3 and 0.03
- D. 0.37 and 0

**Answer:** B. 0.37 and 0.3 — $\rho\sigma^2+(1-\rho)\sigma^2/T=0.3+0.7/10=0.37$. As $T\to\infty$ the second term vanishes, leaving $\rho\sigma^2=0.3$. Only lowering $\rho$ gets below it.

**Question:** Going from max_features = √d to max_features = d (plain bagging) typically…

- A. makes each tree weaker and the trees less correlated
- B. makes each tree stronger and the trees more correlated
- C. changes only the training speed
- D. removes the need for bootstrap samples

**Answer:** B. makes each tree stronger and the trees more correlated — Every node can now use its best feature, so trees are individually more accurate, but they all choose the same dominant splits. On the breast-cancer data tree accuracy went 0.911 → 0.915 while ρ̄ went 0.411 → 0.484 and test accuracy fell 0.953 → 0.930.

**Question:** With n = 12 rows, what is the probability that a given row is out-of-bag for one tree?

- A. 1/12 ≈ 0.083
- B. ≈ 0.352
- C. ≈ 0.5
- D. ≈ 0.648

**Answer:** B. ≈ 0.352 — $(1-\tfrac1{12})^{12}=(\tfrac{11}{12})^{12}=0.352$, already close to the large-$n$ limit $e^{-1}=0.368$. A tree has about $12\times0.352=4.2$ OOB rows; the worked example's trees had 4, 4 and 6.

**Key points**

- A random forest grows deep trees on bootstrap samples, with a fresh random subset of max_features candidates at every split.
- It predicts by averaging leaf class proportions (soft vote). By Jensen's inequality, averaged probabilities never have a higher log-loss than the trees' average log-loss.
- Variance falls to $\rho\sigma^2+(1-\rho)\sigma^2/T$. More trees never overfit, but only decorrelation (smaller $m$) lowers the floor.
- Breiman's bound $PE^*\le\bar\rho(1-s^2)/s^2$: max_features trades tree strength against tree correlation, and $\sqrt d$ is a good default.
- About $e^{-1}\approx37\%$ of rows are out-of-bag for each tree, which gives a free validation estimate. Judge the forest by that or held-out data, never by training accuracy.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
