# Random forest regression

> Average many decorrelated regression trees grown on bootstrap samples; averaging cuts variance without adding bias.

Source: https://www.mlfoundry.in/learn/random-forest-regression  
Section: ML Algorithms › Supervised · Regression  
Level: core · 17 min read · updated 2026-10-07

**Random forest regression:** predicts a number by averaging the outputs of $T$ regression trees. Each tree is grown deep on its own **bootstrap sample** ($n$ rows drawn with replacement), optionally considering only a random subset of features at each split, and each leaf predicts the **mean** target of the training rows that reach it. The forest's prediction is the plain average $\bar f(x)=\tfrac1T\sum_t h_t(x)$.

- **Task:** Regression (numeric target); squared-error loss
- **Input → output:** $x\in\mathbb R^d$ → $\bar f(x)$, the mean of $T$ trees' leaf means
- **Learns:** $T$ deep regression trees: thresholds per internal node, a mean $\bar y$ per leaf
- **Training cost:** about $O(T\cdot m\,n\log n)$ with $m$ features tried per split; trees are independent, so it parallelizes perfectly
- **Prediction cost:** $O(T\cdot\text{depth})$ comparisons, then one average
- **Key hyperparameters:** number of trees `n_estimators`; features per split `max_features`; leaf size `min_samples_leaf`; bootstrap size `max_samples`
- **Assumes:** nothing distributional; the target can be reached as an average of training targets (no extrapolation)

## The problem

A single regression tree (see **Decision tree regression**) is an excellent *low-bias* model: grown deep, it can follow any nonlinear shape and any interaction between features. But it pays for that with **variance**. Its thresholds are chosen greedily from the exact training rows, so moving or removing a handful of points changes the top split, which changes everything underneath. Two trees trained on two samples from the same population can give very different step functions — and at a given $x$, very different numbers.

The usual cure for variance — prune harder, make leaves bigger — trades it straight back for bias: big leaves average over regions where the target is not constant. Linear models have the opposite problem: stable, but blind to thresholds and interactions. We want to keep the deep tree's flexibility and remove its instability.

## The idea

If you had $T$ independent training sets, you could grow a tree on each and average their predictions: the average has the same expected value as one tree but $T$ times less variance. We only have one training set, so we **fake** new ones with the bootstrap — resample $n$ rows with replacement — and grow one deep tree per resample. This is **bagging** (bootstrap aggregating, Breiman 1996).

Bootstrap trees are not independent, though: they share most rows, so they tend to pick the same strong feature at the root and make similar errors. Averaging correlated errors cancels much less. A random forest (Breiman 2001) adds a second source of randomness — at every split, only a random subset of $m$ of the $d$ features is searched — so the trees differ more and their errors cancel more. For regression the averaging is literal: no votes, no probabilities, just the arithmetic mean of numbers.

**Vocabulary**

- **Bootstrap sample:** $n$ row indices drawn uniformly **with replacement** from $\{1,\dots,n\}$; some rows appear 2–3 times, others not at all
- **Bagging:** fitting the same learner on many bootstrap samples and averaging the fits
- **In-bag / out-of-bag (OOB):** for a tree $t$: the rows in its bootstrap sample / the rows it never saw (about 36.8% of them)
- **OOB prediction:** for row $i$: the average over only those trees for which $i$ was out-of-bag — an honest, held-out prediction
- **max_features (mtry):** $m$, the number of features randomly offered to each split; $m=d$ turns the forest back into plain bagging
- **min_samples_leaf (nodesize):** smallest number of training rows a leaf may hold; the forest's main smoothing knob in regression
- **Tree correlation ρ:** the correlation, at a fixed $x$, between the predictions of two trees of the same forest
- **Ambiguity:** the spread of the trees around their own average, $\tfrac1T\sum_t (h_t(x)-\bar f(x))^2$

## The math

**Leaves predict means.** Under squared error, a leaf $\ell$ holding training targets $y_i$ ($i\in\ell$) should predict the constant $c$ that minimizes $\sum_{i\in\ell}(y_i-c)^2$. Setting the derivative $-2\sum_{i\in\ell}(y_i-c)$ to zero gives $c=\bar y_\ell$, the leaf mean, and the leftover loss is the leaf's sum of squared errors (SSE). Each tree splits greedily on the threshold that most reduces total SSE — the same variance-reduction rule as a single regression tree. In a bootstrap sample a row that appears twice simply counts twice in both the mean and the SSE.

$$
\bar f(x)=\frac1T\sum_{t=1}^{T}h_t(x),\qquad h_t(x)=\frac{1}{|\ell_t(x)|}\sum_{i\in \ell_t(x)} y_i
$$

- $T$: number of trees
- $h_t(x)$: prediction of tree $t$: the mean target in the leaf $x$ falls into
- $\ell_t(x)$: the multiset of tree $t$'s in-bag training rows sharing that leaf (duplicates counted)
- $\bar f(x)$: the forest prediction

**Averaging does not change bias.** Every tree is grown by the same random procedure, so they all have the same expected prediction $\mathbb E[h(x)]$. By linearity of expectation $\mathbb E[\bar f(x)]=\tfrac1T\sum_t\mathbb E[h_t(x)]=\mathbb E[h(x)]$: the forest's bias is exactly the bias of one of its trees. That is why forests use **deep, low-bias trees** — averaging can only remove variance, so the trees should bring as little bias as possible.

**Averaging divides variance — partly.** Let each tree's prediction at $x$ have variance $\sigma^2$, and any two trees correlation $\rho$, so $\operatorname{Cov}(h_s,h_t)=\rho\sigma^2$ for $s\ne t$. The variance of a mean is the sum of all $T^2$ covariances divided by $T^2$: $T$ diagonal terms equal to $\sigma^2$ and $T(T-1)$ off-diagonal terms equal to $\rho\sigma^2$.

$$
\operatorname{Var}\big(\bar f(x)\big)=\frac{1}{T^2}\Big(T\sigma^2+T(T-1)\rho\sigma^2\Big)=\rho\,\sigma^2+\frac{1-\rho}{T}\,\sigma^2
$$

- $\sigma^2$: variance of one tree's prediction at $x$ (over training sets and bootstrap draws)
- $\rho$: correlation between two trees of the same forest
- $\tfrac{1-\rho}{T}\sigma^2$: the part more trees remove; it vanishes as $T\to\infty$
- $\rho\sigma^2$: the floor no number of trees can remove

Putting the pieces into the bias–variance decomposition of the expected squared error at $x$ gives the whole story of the method in one line:

$$
\mathbb E\big[(y-\bar f(x))^2\big]=\underbrace{\sigma_\varepsilon^2}_{\text{noise}}+\underbrace{\big(\mathbb E[h(x)]-f^*(x)\big)^2}_{\text{bias}^2\text{ of one tree}}+\underbrace{\rho\sigma^2+\tfrac{1-\rho}{T}\sigma^2}_{\text{forest variance}}
$$

- $f^*(x)$: the true regression function $\mathbb E[y\mid x]$
- $\sigma_\varepsilon^2$: irreducible noise in y

> **Why more trees never overfit:** $T$ appears only in the term $\tfrac{1-\rho}{T}\sigma^2$, which shrinks monotonically. Adding trees can never raise the expected error — it just converges to the $T=\infty$ forest. The knobs that *can* overfit or underfit are the ones that change $\rho$, $\sigma^2$ and the bias: `max_features`, `min_samples_leaf`, `max_samples`. Pick $T$ for compute and stability, tune the others.

**The ambiguity decomposition.** For squared error there is also an exact identity on any single point, with no expectations at all (Krogh & Vedelsby, 1995). Expand $h_t-y=(h_t-\bar f)+(\bar f-y)$, square, and average over $t$; the cross term vanishes because $\sum_t (h_t-\bar f)=0$:

$$
\big(\bar f(x)-y\big)^2=\underbrace{\frac1T\sum_t\big(h_t(x)-y\big)^2}_{\text{average tree error}}-\underbrace{\frac1T\sum_t\big(h_t(x)-\bar f(x)\big)^2}_{\text{ambiguity}\;\ge 0}
$$

- $y$: the true target at $x$
- $ambiguity$: how much the trees disagree with their own mean

So the forest is **never worse than its average tree**, and it beats it by exactly how much the trees disagree. Diversity is not a side effect; under squared loss it is literally the profit. The catch is that decorrelating trees (smaller $m$, smaller bootstrap samples) also makes each tree worse, so the first term grows too — the tuning question is which effect wins.

**A forest is a weighted nearest-neighbour average.** Substituting the leaf means into $\bar f$ and swapping the sums gives

$$
\bar f(x)=\sum_{i=1}^{n} w_i(x)\,y_i,\qquad w_i(x)=\frac1T\sum_{t=1}^{T}\frac{c_{ti}\,[\,i\in\ell_t(x)\,]}{|\ell_t(x)|}
$$

- $w_i(x)$: weight of training row $i$ in the prediction at $x$; $w_i\ge0$ and $\sum_i w_i=1$
- $c_{ti}$: how many times row $i$ appears in tree $t$'s bootstrap sample

The weights are non-negative and sum to one, so every forest prediction is a **convex combination of training targets**: it always lies between $\min_i y_i$ and $\max_i y_i$. Rows that keep landing in the same leaf as $x$ get large weight — the forest learns its own adaptive neighbourhood, wide along irrelevant features and narrow along important ones. The same weights are what *quantile regression forests* reuse to estimate the whole conditional distribution instead of only its mean.

**Out-of-bag rows.** One bootstrap draw misses row $i$ with probability $1-\tfrac1n$, so all $n$ draws miss it with probability $(1-\tfrac1n)^n\to e^{-1}\approx0.368$ (already 0.349 at $n=10$). Each row is therefore unseen by about a third of the trees, and averaging just those trees gives an honest held-out prediction. The **OOB MSE** $\tfrac1n\sum_i(\hat y_i^{\text{OOB}}-y_i)^2$ estimates test error without a separate validation split.

## How the hyperparameters act on the formula

- **n_estimators T:** shrinks only $\tfrac{1-\rho}{T}\sigma^2$. Error falls fast, then plateaus; bias, $\rho$ and $\sigma^2$ are untouched.
- **max_features m:** smaller $m$ → trees share fewer splits → $\rho$ falls. But each tree is forced to use weaker features at some splits, so its bias and $\sigma^2$ rise. Best $m$ depends on how many features carry signal.
- **min_samples_leaf:** bigger leaves average more targets → $\sigma^2$ falls, but the step function gets coarser → bias rises. In regression this matters much more than in classification, because leaf means of 1–2 noisy targets are very noisy.
- **max_samples:** smaller bootstrap samples → trees see fewer shared rows → $\rho$ falls, each tree is weaker; also faster.
- **max_depth:** a hard cap with the same effect as bigger leaves; usually left unlimited and controlled through leaf size instead.

To see these numbers for real, we simulated the standard **Friedman #1** benchmark ($d=10$ features, only 5 of which matter, noise sd 1): 25 independent training sets of 500 rows, a 200-tree forest on each, scored against the noise-free truth on 1000 test points. Across the 25 forests we measured each tree's variance $\sigma^2$, the tree correlation $\rho$, the bias² and the forest's variance.

Friedman #1, 200 trees, averaged over 25 training sets. Forest MSE = bias² + forest variance (noise excluded). Lower $m$ decorrelates the trees ($\rho$ 0.091 → 0.016) but raises bias, because half the features are noise; here $m=5$ is best and $m=1$ is clearly worst. Bigger leaves cut $\sigma^2$ and raise bias.

| Setting | One tree MSE | Tree variance | Tree correlation | Bias² | Forest variance | Forest MSE |
| --- | --- | --- | --- | --- | --- | --- |
| m = 1 | 26.46 | 18.77 | 0.016 | 7.70 | 0.39 | 8.09 |
| m = 3 (≈ d/3) | 16.38 | 12.45 | 0.032 | 3.93 | 0.45 | 4.39 |
| **m = 5** | 13.12 | 9.83 | 0.053 | 3.29 | 0.56 | **3.86** |
| m = 10 (bagging) | 11.38 | 8.29 | 0.091 | 3.09 | 0.81 | 3.90 |
| m = 10, leaf ≥ 5 | 9.54 | 5.90 | 0.120 | 3.64 | 0.74 | 4.39 |
| m = 10, leaf ≥ 20 | 9.82 | 3.92 | 0.158 | 5.90 | 0.63 | 6.52 |

Read the bagging row: one tree has MSE 11.38 = bias² 3.09 + variance 8.29. The forest keeps the same bias² 3.09 and cuts variance to 0.81 — very close to the floor $\rho\sigma^2=0.091\times8.29\approx0.75$. Ninety percent of a single tree's variance is gone. With one training set the number of trees behaves as the formula promises: test MSE 10.71 with 1 tree, 4.87 with 5, 3.80 with 25, 3.62 with 100, 3.56 with 500.

## Worked example: bike rentals by temperature

Ten days of rentals (in tens of bikes) against the day's temperature. Demand rises with warmth, peaks in the low twenties and falls again on hot days — a hump no straight line can fit. We grow a forest of **3 trees** with `min_samples_leaf = 3` (a leaf must hold at least 3 bootstrap rows, duplicates included) and predict a **21 °C** day.

Training data. Highlighted: the three days that every one of the three bootstrap samples happens to contain, so they will have no out-of-bag prediction.

| Row | Temp (°C) | Rentals (×10) |
| --- | --- | --- |
| 0 | 4 | 12 |
| 1 | 8 | 18 |
| 2 | 11 | 25 |
| 3 | 14 | 31 |
| 4 | 17 | 38 |
| 5 | 20 | 44 |
| 6 | 23 | 47 |
| 7 | 26 | 45 |
| 8 | 29 | 37 |
| 9 | 33 | 29 |

**Tree 1, by hand**

1. **Bootstrap.** Draw 10 row numbers with replacement (NumPy "default_rng(10)"): rows $\{1, 2, 2, 5, 5, 7, 7, 8, 8, 9\}$. Rows 2, 5, 7, 8 appear twice; rows 0, 3, 4, 6 are **out-of-bag**.
2. **Root node.** The 10 in-bag targets have mean 34.90 and SSE 894.90. With at least 3 rows per side, only three thresholds are legal (midpoints between distinct temperatures): $15.5$, $23$ and $27.5$.
3. **Score them** (table below). $x\le15.5$ leaves SSE $32.67+220.86=253.52$, by far the lowest, so the root asks *temp ≤ 15.5?* — removing 641.38 of the 894.90.
4. **Left child** holds 3 rows (8, 11, 11 °C → 18, 25, 25). Splitting it would leave a side with fewer than 3 rows, so it becomes a leaf predicting $\tfrac{18+25+25}{3}=22.67$.
5. **Right child** holds 7 rows: 20, 20, 26, 26, 29, 29, 33 °C (mean 40.14, SSE 220.86). Only $27.5$ keeps 3+ rows on each side: leaves $\{44,44,45,45\}$ (mean **44.50**, SSE 1.00) and $\{37,37,29\}$ (mean **34.33**, SSE 42.67). SSE drops by 177.19, so split. Neither leaf can split again.
6. **Tree 1** is the step function 22.67 for $x\le15.5$, 44.50 for $15.5<x\le27.5$, 34.33 above. At 21 °C it predicts **44.50**.

Tree 1, root node: every legal threshold scored by total SSE of the two children (in-bag rows, duplicates counted).

| Threshold | Left rows · mean · SSE | Right rows · mean · SSE | Total SSE |
| --- | --- | --- | --- |
| **x ≤ 15.5** | 3 · 22.67 · 32.67 | 7 · 40.14 · 220.86 | **253.52** |
| x ≤ 23 | 5 · 31.20 · 578.80 | 5 · 38.60 · 179.20 | 758.00 |
| x ≤ 27.5 | 7 · 35.14 · 850.86 | 3 · 34.33 · 42.67 | 893.52 |

Trees 2 and 3 are grown the same way on their own bootstrap samples:

The three trees. Each sees a different sample, so each puts its thresholds in a different place.

| Tree | Bootstrap rows | Out-of-bag | Leaves (range → mean, rows) | ŷ(21 °C) |
| --- | --- | --- | --- | --- |
| 1 | 1, 2, 2, 5, 5, 7, 7, 8, 8, 9 | 0, 3, 4, 6 | ≤15.5 → 22.67 (3) · ≤27.5 → 44.50 (4) · >27.5 → 34.33 (3) | 44.50 |
| 2 | 0, 1, 1, 4, 4, 4, 5, 6, 8, 9 | 2, 3, 7 | ≤12.5 → 16.00 (3) · ≤21.5 → 39.50 (4) · >21.5 → 37.67 (3) | 39.50 |
| 3 | 0, 2, 3, 5, 7, 7, 8, 8, 9, 9 | 1, 4, 6 | ≤17 → 22.67 (3) · ≤27.5 → 44.67 (3) · >27.5 → 33.00 (4) | 44.67 |

**The forest**

1. **Predict 21 °C.** $\bar f(21)=\tfrac13(44.50+39.50+44.67)=$ **42.89**. The trees disagree with sd 2.40 — that disagreement is the variance averaging removes. (One tree with the same leaf rule grown on all 10 rows predicts 40.00.)
2. **As neighbour weights.** Tree 1's leaf at 21 °C holds 20 °C ×2 and 26 °C ×2; tree 2's holds 17 °C ×3 and 20 °C ×1; tree 3's holds 20 °C and 26 °C ×2. So $w_{17°}=\tfrac13\cdot\tfrac34=0.25$, $w_{20°}=\tfrac13(\tfrac24+\tfrac14+\tfrac13)=0.361$, $w_{26°}=\tfrac13(\tfrac24+\tfrac23)=0.389$, and $0.25\cdot38+0.361\cdot44+0.389\cdot45=42.89$ — the same number.
3. **OOB predictions.** Row 4 (17 °C, 38) was out-of-bag for trees 1 and 3, which predict 44.50 and 22.67 → OOB prediction 33.58, squared error 19.51. Doing this for every row that has at least one OOB tree (rows 5, 8, 9 have none):
4. **OOB MSE** $=\tfrac17(113.78+21.78+81.00+0.01+19.51+5.84+53.78)=$ **42.24** — an honest error estimate from just 3 trees.
5. **Ambiguity check on the training rows.** The three trees' training MSEs are 29.50, 41.22 and 48.36 (average 39.69). Their average spread around the forest is 21.45, so the forest's training MSE is $39.69-21.45=18.24$ — lower than every one of its trees.

Out-of-bag predictions from the 3-tree forest. Row 0 is the worst: the only tree that never saw it puts it in a leaf with 8–11 °C days.

| Row | Temp | y | OOB trees | OOB prediction | Squared error |
| --- | --- | --- | --- | --- | --- |
| 0 | 4 | 12 | 1 | 22.67 | 113.78 |
| 1 | 8 | 18 | 3 | 22.67 | 21.78 |
| 2 | 11 | 25 | 2 | 16.00 | 81.00 |
| 3 | 14 | 31 | 1, 2 | 31.08 | 0.01 |
| 4 | 17 | 38 | 1, 3 | 33.58 | 19.51 |
| 6 | 23 | 47 | 1, 3 | 44.58 | 5.84 |
| 7 | 26 | 45 | 2 | 37.67 | 53.78 |

## See it work

> Figure: The worked example, live. Thin blue lines are the trees, the bold mint line is their average, and the strip on the right shows every tree's prediction at the dashed query line (drag it). At the start — 3 trees, leaf ≥ 3, query 21 °C — the trees say 44.50, 39.50 and 44.67, and the forest says 42.89 (sd 2.40). Step through trees with ◀ ▶ to see each one's bootstrap counts (×2, ×3) and its out-of-bag days (hollow). Drag T up to 100 and watch the step function smooth out while the OOB curve drops below the dashed one-tree line; switch bootstrap off and every tree becomes identical, so averaging does nothing. On 60 noisy days, test MSE against the true curve falls from 13.33 with one tree to 7.47 with 100 (leaf ≥ 1), and to 4.42 with leaf ≥ 5.

> **What to try in the figure:** On the 10 days, set `min_samples_leaf` to 1: each tree becomes nearly a nearest-neighbour step function, the trees disagree more, and averaging helps more — OOB MSE at 100 trees drops from 59.50 (leaf 3) to 28.63. On 10 rows a leaf of 5 is far too coarse (119.61). On the 60 noisy days the trend reverses: against the true curve, leaf 5 beats leaf 1 (test MSE 4.42 vs 7.47 at 100 trees) because single-row leaves fit noise. Notice that OOB MSE cannot see this (16.47 vs 16.09): it is measured against noisy targets on only 60 rows, so its own noise swamps the difference — on small data, treat OOB as a rough guide.

## The algorithm, step by step

**fit(X, y)**

1. **For** $t=1,\dots,T$ (in parallel):
2. **Bootstrap.** Draw $n$ (or "max_samples") row indices with replacement; remember which rows are out-of-bag.
3. **Grow** a regression tree on the sample. At each node: draw `max_features` candidate features at random; for each, sort the node's values and scan all midpoints, computing left/right SSE from running sums; keep the split with the lowest total SSE.
4. **Stop** a node when it cannot be split into two children with at least `min_samples_leaf` rows each (or hits `max_depth`, or no split reduces SSE). The leaf stores the mean target of its rows.
5. **OOB.** For each out-of-bag row of tree $t$, add $h_t(x_i)$ to that row's running sum and count.
6. **Predict** $x$: drop it down all $T$ trees and average the $T$ leaf means. OOB MSE $=\text{mean}_i(\text{OOB sum}_i/\text{count}_i-y_i)^2$.

**Complexity.** Sorting dominates: a balanced tree costs about $O(m\,n\log^2 n)$ with per-node sorting, or $O(m\,n\log n)$ with pre-sorting or histogram binning; the forest is $T$ times that, divided by the number of cores. Deep regression trees have roughly $n/\text{min\_samples\_leaf}$ leaves, so memory is $O(T\,n/\text{leaf})$ nodes — a 500-tree forest on a million rows with leaf size 1 can take gigabytes. Prediction is $O(T\log n)$ per row.

## Variants and practical tuning

Where to start. Library defaults differ, so check them: in scikit-learn the regressor's max_features defaults to 1.0 — all features, i.e. plain bagging.

| Hyperparameter | scikit-learn default | Breiman / R randomForest (regression) | Tune how |
| --- | --- | --- | --- |
| n_estimators | 100 | 500 | Increase until OOB error flattens; more is never worse, only slower |
| max_features | 1.0 (all d) | d/3 | Try {d/3, d/2, 1.0} and √d; fewer when many features are correlated copies of each other |
| min_samples_leaf | 1 | 5 (nodesize) | Try 1, 3, 5, 10, 20; larger for noisy targets |
| max_samples | n (full bootstrap) | n | 0.5–0.8 to decorrelate and speed up large data |
| bootstrap / oob_score | True / False | — | Set oob_score=True for a free validation estimate |

**Relatives**

- **Bagged trees:** $m=d$. Only bootstrap randomness; best when few features matter or features are all informative.
- **Extra Trees:** split thresholds drawn at random too, no bootstrap by default — even lower correlation, a bit more bias, faster to train (see **Extra Trees**).
- **Quantile regression forest:** keep all leaf targets, not just the mean; use the weights $w_i(x)$ to estimate conditional quantiles and give prediction intervals.
- **Honest / causal forests:** use one half of each sample to choose splits and the other to fill leaf means; this gives valid confidence intervals and heterogeneous treatment effects.
- **Gradient boosting:** the other way to combine trees: grow shallow trees *sequentially* to fix the current residuals. Boosting attacks bias, forests attack variance (see **Gradient boosting regression** and **AdaBoost regression**).

> **Feature importance comes for free — carefully:** Mean decrease in impurity sums, for each feature, the SSE reduction of every split that used it, averaged over trees. It is cheap but biased toward continuous and high-cardinality features. Permutation importance on OOB or held-out rows (shuffle one column, measure how much MSE rises) is the honest version.

## In code

```python
import numpy as np

def grow(X, y, min_leaf=3, max_features=None, rng=None):
    """Regression tree: split on the threshold with the lowest total SSE; leaves store the mean."""
    n, d = X.shape
    best = None                                            # (sse, feature, threshold)
    feats = range(d) if max_features is None else rng.choice(d, max_features, replace=False)
    for j in feats:
        order = np.argsort(X[:, j], kind="stable")
        xs, ys = X[order, j], y[order]
        cs, cq = np.cumsum(ys), np.cumsum(ys ** 2)          # prefix sums -> SSE of every split in O(n)
        for k in range(min_leaf, n - min_leaf + 1):          # k rows go left
            if xs[k - 1] == xs[k]:
                continue
            sl, ql, sr, qr = cs[k - 1], cq[k - 1], cs[-1] - cs[k - 1], cq[-1] - cq[k - 1]
            sse = ql - sl ** 2 / k + qr - sr ** 2 / (n - k)
            if best is None or sse < best[0] - 1e-9:
                best = (sse, j, (xs[k - 1] + xs[k]) / 2)
    if best is None:
        return {"value": y.mean(), "n": n}
    _, j, t = best
    left = X[:, j] <= t
    return {"feature": j, "threshold": t,
            "left": grow(X[left], y[left], min_leaf, max_features, rng),
            "right": grow(X[~left], y[~left], min_leaf, max_features, rng)}

def predict_tree(node, x):
    while "value" not in node:
        node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
    return node["value"]

class RandomForestRegressor:
    def __init__(self, n_trees=100, min_leaf=5, max_features=None, seed=0):
        self.T, self.min_leaf, self.mf, self.seed = n_trees, min_leaf, max_features, seed

    def fit(self, X, y):
        n = len(y)
        rng = np.random.default_rng(self.seed)
        self.trees, self.samples = [], []
        for _ in range(self.T):
            idx = rng.integers(0, n, n)                       # bootstrap: n draws with replacement
            self.samples.append(idx)
            self.trees.append(grow(X[idx], y[idx], self.min_leaf, self.mf, rng))
        # out-of-bag: average only the trees that never saw row i
        s, c = np.zeros(n), np.zeros(n)
        for tree, idx in zip(self.trees, self.samples):
            oob = np.setdiff1d(np.arange(n), idx)
            s[oob] += [predict_tree(tree, X[i]) for i in oob]
            c[oob] += 1
        ok = c > 0
        self.oob_pred_ = np.where(ok, s / np.maximum(c, 1), np.nan)
        self.oob_mse_ = np.mean((self.oob_pred_[ok] - y[ok]) ** 2)
        return self

    def tree_predictions(self, X):
        return np.array([[predict_tree(t, x) for x in X] for t in self.trees])

    def predict(self, X):
        return self.tree_predictions(X).mean(axis=0)          # the forest = plain average

# Worked example: temperature (°C) -> bike rentals (x10)
X = np.array([[4], [8], [11], [14], [17], [20], [23], [26], [29], [33]], dtype=float)
y = np.array([12, 18, 25, 31, 38, 44, 47, 45, 37, 29], dtype=float)

rf = RandomForestRegressor(n_trees=3, min_leaf=3, seed=10).fit(X, y)
for k, idx in enumerate(rf.samples, 1):
    print(f"tree {k} bootstrap rows:", sorted(idx.tolist()))
P = rf.tree_predictions(np.array([[21.0]]))[:, 0]
print("tree predictions at 21°C:", P.round(2))         # [44.5  39.5  44.67]
print("forest prediction:", round(P.mean(), 2), " spread (sd):", round(P.std(), 2))  # 42.89, 2.4
print("OOB predictions:", np.round(rf.oob_pred_, 2))
print("OOB MSE:", round(rf.oob_mse_, 2))                # 42.24
```

From scratch with NumPy: SSE splits with prefix sums, bootstrap, feature subsampling, OOB. Running it reproduces the worked example exactly.

```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
from sklearn.ensemble import RandomForestRegressor
from sklearn.metrics import mean_squared_error

X = np.array([[4], [8], [11], [14], [17], [20], [23], [26], [29], [33]], dtype=float)
y = np.array([12, 18, 25, 31, 38, 44, 47, 45, 37, 29], dtype=float)

# 1) The three hand-built trees: same bootstrap rows, same leaf rule
rng = np.random.default_rng(10)
preds = []
for k in range(3):
    idx = rng.integers(0, 10, 10)
    tree = DecisionTreeRegressor(min_samples_leaf=3).fit(X[idx], y[idx])
    preds.append(tree.predict([[21.0]])[0])
print("hand forest at 21°C:", np.round(preds, 2), "->", round(np.mean(preds), 2))
# hand forest at 21°C: [44.5  39.5  44.67] -> 42.89

# 2) The library forest (its own random bootstraps)
rf = RandomForestRegressor(n_estimators=500, min_samples_leaf=1, oob_score=True,
                           random_state=0).fit(X, y)
print("sklearn forest at 21°C:", rf.predict([[21.0]]).round(2))          # [44.2]
print("OOB R^2:", round(rf.oob_score_, 3),                               # 0.769
      " OOB MSE:", round(mean_squared_error(y, rf.oob_prediction_), 2))  # 28.92
spread = np.array([t.predict([[21.0]])[0] for t in rf.estimators_])
print("tree spread at 21°C: sd =", round(spread.std(), 2),               # 2.26
      " 10th-90th pct:", np.percentile(spread, [10, 90]).round(1))       # [44. 47.]
```

scikit-learn: first the three hand-built trees (same bootstrap rows), then a real 500-tree forest on the same 10 days.

> **scikit-learn counts leaf size differently:** Inside `RandomForestRegressor` the bootstrap is implemented as *sample weights* (a row drawn twice gets weight 2), and `min_samples_leaf` counts **distinct** rows, not weighted ones. A leaf holding one row drawn three times is legal there but not in the hand-built version above. That is why the worked example builds its trees with `DecisionTreeRegressor` on explicitly duplicated rows; if you need the weighted rule in a forest, use `min_weight_fraction_leaf`.

**Strengths**

- You want a strong nonlinear regressor with almost no tuning: defaults are rarely bad.
- Features are mixed in scale and type, with interactions and thresholds; no scaling or transformation needed.
- You want a free validation estimate (OOB MSE) and robust permutation importances.
- Training must parallelize, or you need a reliable baseline before trying boosting.

**Limitations**

- Targets will go beyond the training range (trends, growth, time series) — the forest flattens out.
- The signal is smooth and close to linear in a few features: a linear or spline model is smaller and more accurate.
- You need the last few percent of accuracy on tabular data: tuned gradient boosting usually wins.
- Memory or latency is tight: hundreds of deep trees are large and slow to evaluate.

- **Real-estate valuation:** Predicting sale price from size, location, age and amenities, where effects interact and thresholds (e.g. a school-district boundary) matter.
- **Demand forecasting:** Store- or station-level demand from weather, calendar and price features — as long as the future stays inside the range of the past.
- **Remote sensing & ecology:** Biomass, canopy height or species abundance from satellite bands; OOB error and importances are standard in this literature.
- **Chemistry & materials (QSAR):** Predicting a molecule's solubility or binding affinity from hundreds of descriptors, a classic random-forest benchmark.

> **Forests cannot extrapolate:** Every prediction is a weighted average of training targets, so it can never leave $[\min y,\max y]$. Fit $y=2x$ on 50 evenly spaced points in $x\in[0,10]$ (targets up to 20) and a 200-tree forest predicts 19.75 at $x=15$, where the truth is 30. For trending targets, model the trend separately (or predict differences/ratios) and let the forest model what is left.

> **Tree spread is not a prediction interval:** The disagreement between trees measures *model* uncertainty only, and bootstrap trees share most of their data, so it is far too narrow for new observations: on the 10 days the 500 trees' predictions at 21 °C span only 44 to 47 (10th–90th percentile), while the neighbouring days (17–26 °C) range from 38 to 47. Use quantile regression forests or conformal prediction for intervals on y.

> **Train error tells you nothing:** With leaf size 1 every tree nearly interpolates its bootstrap sample, so training MSE is close to zero whatever the true quality. Judge the forest by OOB MSE or a held-out set — and if rows are grouped in time or by entity, OOB rows are not truly unseen; use a grouped or time-based split.

**Question:** Each tree's prediction at x has variance 10 and pairwise correlation 0.2. What is the variance of a 10-tree forest's prediction there?

- A. 1.0
- B. 2.0
- C. 2.8
- D. 10

**Answer:** C. 2.8 — $\rho\sigma^2+\tfrac{1-\rho}{T}\sigma^2=0.2\cdot10+\tfrac{0.8}{10}\cdot10=2+0.8=2.8$. Even with infinitely many trees it would only fall to $\rho\sigma^2=2$.

**Question:** Three trees predict 30, 36 and 42 for a point whose true value is 40. What is the forest's squared error?

- A. 40
- B. 24
- C. 16
- D. 4

**Answer:** C. 16 — The forest predicts 36, so $(36-40)^2=16$. Check with the ambiguity decomposition: the average tree error is $\tfrac13(100+16+4)=40$, the spread around 36 is $\tfrac13(36+0+36)=24$, and $40-24=16$.

**Question:** A forest is trained on house prices between $80k and $900k. What can it predict for a mansion far larger than anything in the data?

- A. Any value, depending on its features
- B. At most $900k
- C. Exactly the mean price
- D. It refuses to predict

**Answer:** B. At most $900k — Every forest prediction is $\sum_i w_i(x)y_i$ with non-negative weights summing to 1 — a convex combination of training prices — so it can never exceed the largest training target.

**Question:** You switch scikit-learn's RandomForestRegressor from max_features=1.0 to max_features=1/3. What happens to the trees?

- A. They become identical
- B. Correlation between trees falls, but each tree gets somewhat worse
- C. Bias of the forest falls to zero
- D. Nothing; regression ignores max_features

**Answer:** B. Correlation between trees falls, but each tree gets somewhat worse — Each split sees a third of the features, so trees share fewer splits (lower ρ) but are sometimes forced onto weaker features (higher bias and σ²). On Friedman #1 this moved ρ from 0.091 to 0.032 and the forest MSE from 3.90 to 4.39 — whether it helps depends on the data.

**Key points**

- Random forest regression averages deep regression trees grown on bootstrap samples, with a random feature subset tried at each split; each leaf predicts a mean.
- Averaging keeps the bias of one tree and shrinks variance to $\rho\sigma^2+\tfrac{1-\rho}{T}\sigma^2$: more trees remove the second term, decorrelation lowers the first.
- Under squared error the forest's error equals the average tree error minus the trees' disagreement (ambiguity), so it is never worse than its average tree.
- A forest is a weighted nearest-neighbour average of training targets: smooth-ish, robust, but unable to extrapolate beyond the training range.
- Each row is out-of-bag for about 36.8% of trees; OOB MSE is a free test-error estimate. Tune max_features and min_samples_leaf; T only needs to be large enough.

---

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