Extra Trees: The Chef Who Stopped Tasting the Soup and Somehow Cooked Faster and Better

The One-Line Summary: Extra Trees is a Random Forest that stops searching for the best split point — at every node it draws one random threshold per candidate feature and keeps the best of those few candidates, which pushes tree-to-tree correlation below anything feature subsampling alone can reach, and because nothing ever gets sorted, it trains several times faster while usually scoring the same or better.

---

The Parable of the Copper Ladle

Two posts ago we blindfolded a jury. Yesterday we found a free exam hiding in the leftovers. Today we leave the courthouse and walk into a kitchen.

The Copper Ladle serves exactly one dish. Every evening one hundred cooks each make one pot of it, and at seven o'clock all hundred pots are poured into a single copper cauldron. What comes out of that cauldron is what the city eats. No diner has ever tasted one cook's pot — only the blend.

---

The Era of Careful Tasting

Head chef Fen Okoro trained every cook the same way, and she was proud of it: season in six stages, and at each stage taste properly — forty spoonfuls, amounts side by side — then commit to whichever tastes best right now.

It was rigorous. By August it was also a disaster.

TUESDAY SERVICE AT THE COPPER LADLE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
100 cooks. 100 pots. One cauldron at seven.
The city eats the BLEND, never a single pot.

House rule: 6 seasoning stages. At each stage,
taste 40 spoonfuls, keep the best amount.

  Cook   1  stage 1: tastes 40 -> 9g salt
  Cook   2  stage 1: tastes 40 -> 9g salt
   ...
  Cook 100  stage 1: tastes 40 -> 9g salt

Cauldron tonight:  9.0g salt per bowl
The dish wants:    6.0g salt per bowl

24,000 tastings. One mistake, made 100 times.

Every cook landed on nine grams for the same reason: at stage one the pot is at a rolling boil, and boiling soup hides salt. A hundred tongues were fooled in the same direction, so a hundred cooks overshot by the same three grams.

They were measuring carefully. That was the problem.

WHY THE BLEND DIDN'T SAVE THEM:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Blending only fixes mistakes that point in
DIFFERENT directions.

  100 pots, each +3g too salty
    -> cauldron: +3g too salty

  100 pots: -4, +2, -1, +5, -3, +1, ...
    -> cauldron: +0.2g. Nearly perfect.

Careful tasting did not make the pots good.
It made them IDENTICAL.

Meanwhile the queue reached the tram stop. Twenty-four thousand tastings a night is not cooking; it is auditing.

---

The Dishwasher's Proposal

Teo had washed pots at the Copper Ladle for eleven years. He had watched four thousand services from the sink and had never once been asked his opinion, which is roughly how long it takes to develop a good one.

"What if nobody tastes anything — and every cook seasons on a dice roll?"

Fen asked him to leave. He came back next morning with a written rule: at each stage grab three jars at random, take one blind pinch from each — whatever size your hand closes on, no measuring, no tasting — smell them, keep the most promising, move on. One pinch per jar, no second attempt.

THE DICE RULE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Per stage: 3 random jars, ONE blind pinch each,
keep the best-smelling one. Then move on.

  Cook 1: salt 2g | pepper 4g | thyme 1g
            -> keeps salt 2g
  Cook 2: salt 11g | cumin 3g | bay 2g
            -> keeps cumin 3g
   ...

Salt across the 100 pots: 1g ... 12g. All over.
Average in the cauldron: 6.4g per bowl  ✓

Tastings tonight: 0.
Service ran three times faster.

Fen's objection was the obvious one: you have made every single cook worse. Teo agreed instantly. Not one pot was as good as a carefully tasted pot, and several were frankly bad.

But they were bad in a hundred different directions, and the cauldron does not serve pots. It serves their average.

---

Why the Sloppy Kitchen Won

THE ARITHMETIC OF SLOPPINESS:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
A blend is only as good as two things:

  1. How good each pot is      (competence)
  2. How DIFFERENTLY each is wrong
                               (independence)

Careful tasting maximised #1, destroyed #2.
The dice rule gives up a little #1 to buy an
enormous amount of #2.

  competence per pot:  down     ▼
  independence:        way up   ▲▲▲

And it SAVES time: tasting forty spoonfuls
was the expensive part.

The kitchen called it THE DICE RULE.
Machine learning calls it EXTRA TREES.

The soup got better and the kitchen got faster. Those are not usually the same decision — and everything below is that sentence, written in mathematics and Python.

---

What Is Extra Trees?

Extra Trees — Extremely Randomized Trees, from Geurts, Ernst and Wehenkel (2006) — is a Random Forest with one change at the split-finding step.

An ordinary tree, at every node, sorts each candidate feature's values, walks every cut point between them, scores each and keeps the winner. That is the exhaustive tasting, and it is where nearly all of training time goes. Extra Trees refuses to do it.

At each node	Random Forest	Extra Trees
Candidate features	random subset, size m	random subset, size m
Thresholds per feature	every midpoint	one, drawn uniformly
Split chosen	best of all candidates	best of the m random ones
Rows per tree	bootstrap sample	all rows (bootstrap=False)

Row three is the part people mangle: Extra Trees is not a random tree. It still scores candidates with the same impurity criterion and keeps the best — it just has m candidates instead of thousands. Teo's cooks smelled all three pinches; they never got a second pinch.

The Third Knob

THE THREE KNOBS OF RANDOMNESS:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  KNOB 1  ROWS       bootstrap per tree
                     -> bagging

  KNOB 2  COLUMNS    random feature subset at
                     every split (max_features)
                     -> random forest

  KNOB 3  THRESHOLDS one random cut per feature
                     instead of the best cut
                     -> extra trees

All three do one job: push rho, the tree-to-
tree correlation, down.

Var(avg) = rho*sigma^2 + (1-rho)*sigma^2/N
           └── the floor. More trees never
               touch it. Only diversity does.

For an average of $N$ predictors with variance $\sigma^2$ and correlation $\rho$ :

$$\text{Var}(\bar{f}) = \rho\sigma^2 + \frac{1 - \rho}{N}\sigma^2$$

The second term dies as trees are added; the first does not. Feature subsampling attacks $\rho$ by hiding columns. Random thresholds attack it differently: two trees that pick the same root feature still cut it in different places, because each drew its own threshold from a continuum.

What It Costs: Bias

A greedy split maximises impurity reduction on the node's data; a random one does not, so each Extra Tree fits the signal slightly worse — higher bias. That matters because of an asymmetry people forget:

• Variance averages away. A hundred noisy trees, averaged, are far less noisy.
• Bias does not. The bias of the average is the average of the biases.

So Extra Trees pays permanent per-tree bias to buy variance and correlation reduction that compound over n_estimators. Usually profitable — below we measure where it stops being.

Step by Step

For $b = 1$ to $B$ :

1. Take the whole training set (no bootstrap, by default).
2. Grow a tree. At every node: draw $m$ features at random; for each, draw one threshold $t_f \sim U(\min, \max)$ from that feature's range among this node's samples; score the $m$ candidates with Gini or MSE; keep the best, split, recurse.
3. Stop on the usual rules — pure node, min_samples_leaf, max_depth.

Predict by vote or mean. Because $\min$ and $\max$ are node-local, the threshold distribution narrows automatically as you descend.

---

Measuring the Third Knob

Turn all three knobs on the same data and watch tree quality, correlation, accuracy and wall-clock time move together.

import time
import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier, ExtraTreesClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

def tree_correlation(model, X):
    """Mean pairwise correlation between individual tree predictions."""
    P = np.array([t.predict(X) for t in model.estimators_])
    C = np.corrcoef(P)
    return float(np.nanmean(C[np.triu_indices_from(C, k=1)]))

models = [
    ("1 knob  bagging", RandomForestClassifier(
        n_estimators=200, max_features=None, random_state=42, n_jobs=1)),
    ("2 knobs RF     ", RandomForestClassifier(
        n_estimators=200, max_features="sqrt", random_state=42, n_jobs=1)),
    ("3 knobs ET     ", ExtraTreesClassifier(
        n_estimators=200, max_features="sqrt", random_state=42, n_jobs=1)),
]

print(f"{'model':<16}{'single':>8}{'rho':>7}{'test':>8}"
      f"{'nodes':>7}{'depth':>7}{'fit s':>7}")
for name, m in models:
    t0 = time.perf_counter()
    m.fit(X_tr, y_tr)
    fit_s = time.perf_counter() - t0
    single = np.mean([t.score(X_te, y_te) for t in m.estimators_])
    nodes = np.mean([t.tree_.node_count for t in m.estimators_])
    depth = np.mean([t.get_depth() for t in m.estimators_])
    print(f"{name:<16}{single:>8.4f}{tree_correlation(m, X_te):>7.3f}"
          f"{m.score(X_te, y_te):>8.4f}{nodes:>7.0f}{depth:>7.1f}{fit_s:>7.2f}")

model             single    rho    test  nodes  depth  fit s
1 knob  bagging   0.8342  0.640  0.8967    153   12.8   1.72
2 knobs RF        0.8204  0.571  0.8983    219   14.4   0.45
3 knobs ET        0.8034  0.515  0.9050    696   25.5   0.17

Six columns, one story told six ways:

• Individual trees get worse — 0.8342, 0.8204, 0.8034. Extra Trees builds the weakest tree of the three.
• Correlation drops — 0.640, 0.571, 0.515. The third knob buys another 0.056 on top of subsampling.
• The ensemble gets better anyway — 0.8967, 0.8983, 0.9050. Worst trees, best committee.
• Fit time collapses — 1.72s, 0.45s, 0.17s, single-threaded: 2.6x faster than the forest, 10x faster than bagging.

The last two columns are the ones nobody warns you about: 696 nodes at depth 25.5 versus the forest's 219 at 14.4. A uniform threshold often peels off a handful of samples instead of halving them, so the tree needs far more levels to reach purity.

So Extra Trees is much cheaper to train and modestly more expensive to serve — 8.5 ms (RF) versus 11.0 ms (ET) to predict the 600-row test set, at 3x the nodes in memory. Worth knowing if you train on a schedule and serve under an SLO.

---

The bootstrap=False Default

RandomForestClassifier bootstraps by default. ExtraTreesClassifier does not.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

# The default: every tree sees all 1400 training rows.
et = ExtraTreesClassifier(n_estimators=200, random_state=42, n_jobs=-1)
et.fit(X_tr, y_tr)
print(f"bootstrap=False (default)  train={et.score(X_tr, y_tr):.4f}  "
      f"test={et.score(X_te, y_te):.4f}  oob=n/a")

# Ask for a free validation score anyway, and sklearn stops you.
try:
    ExtraTreesClassifier(n_estimators=200, oob_score=True,
                         random_state=42).fit(X_tr, y_tr)
except ValueError as e:
    print(f"oob_score=True + bootstrap=False ->")
    print(f"    ValueError: {e}")

# Flip the knob and out-of-bag comes back.
et_b = ExtraTreesClassifier(n_estimators=200, bootstrap=True, oob_score=True,
                            random_state=42, n_jobs=-1)
et_b.fit(X_tr, y_tr)
print(f"bootstrap=True             train={et_b.score(X_tr, y_tr):.4f}  "
      f"test={et_b.score(X_te, y_te):.4f}  oob={et_b.oob_score_:.4f}")

bootstrap=False (default)  train=1.0000  test=0.9050  oob=n/a
oob_score=True + bootstrap=False ->
    ValueError: Out of bag estimation only available if bootstrap=True
bootstrap=True             train=1.0000  test=0.8983  oob=0.8957

Why the default is right. Randomness is a budget, not a virtue. A bootstrap sample holds about 63.2% of the distinct rows, so it costs every tree a third of its data — pure bias, paid for diversity. Extra Trees already gets its diversity from the thresholds, so it declines to pay: 0.9050 against 0.8983.

Why train accuracy is 1.0000. No bootstrap, no depth limit, so every tree memorises the training set. A training score on an Extra Trees model tells you nothing.

When to flip it to True. You want oob_score — no bootstrap means no held-out rows, and sklearn raises rather than guess. You want max_samples. Or your labels are noisy, and having each bad row missing from ~37% of trees is free robustness.

---

Where the Speedup Comes From

It is not a micro-optimisation. It is an algorithmic step deleted.

WHERE THE TIME GOES, PER NODE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
n = samples at this node, m = candidate features

RANDOM FOREST
  for each of m features:
      SORT the n values     <- O(n log n)
      scan every midpoint   <- O(n)
  cost: O(m * n log n)

EXTRA TREES
  for each of m features:
      min and max           <- O(n)
      draw ONE threshold    <- O(1)
      score ONE partition   <- O(n)
  cost: O(m * n)

The sort is the whole difference.

In theory that is a factor of $\log n$ . In practice the midpoint scan is the branch-heavy inner loop CPUs hate (helping Extra Trees) while its deeper trees mean more nodes to visit (hurting it), and on tabular data the fight settles at 2–4x in Extra Trees' favour — 2.6x above, wider on wide data. A RandomizedSearchCV therefore gets ~2.5x the configurations per hour, often worth more than the model difference itself.

---

The Noise Sensitivity Trade-Off

So far Extra Trees looks free. It is not — and the surprise is which mess breaks it. It handles one kind of noise better than Random Forest, and the other kind worse.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier, ExtraTreesClassifier
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=2000, n_features=10, n_informative=4,
                           n_redundant=0, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)
rf  = lambda: RandomForestClassifier(n_estimators=100, random_state=42, n_jobs=-1)
et  = lambda: ExtraTreesClassifier(n_estimators=100, random_state=42, n_jobs=-1)
etl = lambda: ExtraTreesClassifier(n_estimators=100, min_samples_leaf=5,
                                   random_state=42, n_jobs=-1)
etm = lambda: ExtraTreesClassifier(n_estimators=100, max_features=0.5,
                                   random_state=42, n_jobs=-1)

print("JUNK COLUMNS BOLTED ON  (mean of 2 noise draws)")
print(f"{'junk':>6}{'RF':>9}{'ET':>9}{'ET-RF':>9}{'ETmf.5':>9}")
for extra in [0, 25, 100, 200]:
    a, b, c = [], [], []
    for s in range(2):
        g = np.random.default_rng(200 + s)
        Ztr = np.hstack([X_tr, g.normal(size=(len(X_tr), extra))]) if extra else X_tr
        Zte = np.hstack([X_te, g.normal(size=(len(X_te), extra))]) if extra else X_te
        a.append(rf().fit(Ztr, y_tr).score(Zte, y_te))
        b.append(et().fit(Ztr, y_tr).score(Zte, y_te))
        c.append(etm().fit(Ztr, y_tr).score(Zte, y_te))
    print(f"{extra:>6}{np.mean(a):>9.4f}{np.mean(b):>9.4f}"
          f"{np.mean(b)-np.mean(a):>+9.4f}{np.mean(c):>9.4f}")

print("FLIPPED TRAINING LABELS  (mean of 3 noise draws)")
print(f"{'flip%':>6}{'RF':>9}{'ET':>9}{'ET-RF':>9}{'ETleaf5':>9}")
for frac in [0.0, 0.15, 0.30]:
    a, b, c = [], [], []
    for s in range(3):
        g = np.random.default_rng(300 + s)
        yn = y_tr.copy()
        k = int(frac * len(yn))
        if k:
            yn[g.choice(len(yn), k, replace=False)] ^= 1
        a.append(rf().fit(X_tr, yn).score(X_te, y_te))
        b.append(et().fit(X_tr, yn).score(X_te, y_te))
        c.append(etl().fit(X_tr, yn).score(X_te, y_te))
    print(f"{frac*100:>5.0f}%{np.mean(a):>9.4f}{np.mean(b):>9.4f}"
          f"{np.mean(b)-np.mean(a):>+9.4f}{np.mean(c):>9.4f}")

JUNK COLUMNS BOLTED ON  (mean of 2 noise draws)
  junk       RF       ET    ET-RF   ETmf.5
     0   0.8733   0.8700  -0.0033   0.8900
    25   0.8283   0.7875  -0.0408   0.8817
   100   0.7458   0.7267  -0.0192   0.8658
   200   0.7250   0.6825  -0.0425   0.8475
FLIPPED TRAINING LABELS  (mean of 3 noise draws)
 flip%       RF       ET    ET-RF  ETleaf5
    0%   0.8733   0.8700  -0.0033   0.8567
   15%   0.8278   0.8389  +0.0111   0.8328
   30%   0.7606   0.7700  +0.0094   0.7900

Noise in the features hurts Extra Trees more. Bolt 200 columns of Gaussian garbage onto a 10-feature problem and default Extra Trees falls to 0.6825 while the forest holds 0.7250. A random cut on a genuinely informative feature often produces a mediocre gain, and a mediocre gain does not stand out against the lucky gains junk columns throw up by chance. Exhaustive search gives real signal its best shot.

Noise in the labels hurts it less. Flip 30% of training labels and Extra Trees edges ahead — same mechanism, opposite sign: a random cut cannot chase an individual mislabelled point the way a greedy one can.

TWO KINDS OF NOISE, TWO ANSWERS:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
NOISY FEATURES (junk columns)
  ET loses to RF        ✗
  FIX: raise max_features
       0.6825 -> 0.8475 at 200 junk columns

NOISY LABELS (flipped y)
  ET beats RF           ✓
  FIX: raise min_samples_leaf
       0.7700 -> 0.7900 at 30% flipped

Random thresholds are bad at finding signal
AND bad at memorising noise.

Now look at the ETmf.5 column, the most useful number here: 0.8475 with 200 junk columns, against 0.7250 for the forest and 0.6825 for default Extra Trees. The 'sqrt' default was starving it — with 210 columns it draws 14 candidates, and 14 single random thresholds cannot find a good split. Give it more draws per node and it recovers, then wins outright, still as the faster model. In a Random Forest max_features mostly controls decorrelation; in Extra Trees it also controls how much search happens at all, so its sensible range sits higher.

---

Extra Trees for Regression

The trade lands differently here. Piecewise-constant regressors have visible steps, and averaging many differently placed steps smooths the surface — random thresholds place them in far more distinct positions than greedy splits.

import time
import numpy as np
from sklearn.datasets import make_friedman1
from sklearn.ensemble import RandomForestRegressor, ExtraTreesRegressor
from sklearn.model_selection import train_test_split

def rho_of(model, X):
    P = np.array([t.predict(X) for t in model.estimators_])
    C = np.corrcoef(P)
    return float(np.nanmean(C[np.triu_indices_from(C, k=1)]))

for noise in [1.0, 5.0]:
    X, y = make_friedman1(n_samples=2000, n_features=10, noise=noise,
                          random_state=42)
    X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3,
                                              random_state=42)
    print(f"--- friedman1, target noise sigma={noise} ---")
    print(f"{'model':<15}{'single R2':>11}{'rho':>7}{'ens R2':>9}{'fit s':>7}")
    for name, m in [
        ("RF mf=1.0 (def)", RandomForestRegressor(
            n_estimators=150, random_state=42, n_jobs=1)),
        ("RF mf=0.3      ", RandomForestRegressor(
            n_estimators=150, max_features=0.3, random_state=42, n_jobs=1)),
        ("ET mf=1.0 (def)", ExtraTreesRegressor(
            n_estimators=150, random_state=42, n_jobs=1)),
        ("ET mf=0.3      ", ExtraTreesRegressor(
            n_estimators=150, max_features=0.3, random_state=42, n_jobs=1)),
    ]:
        t0 = time.perf_counter()
        m.fit(X_tr, y_tr)
        fit_s = time.perf_counter() - t0
        single = np.mean([t.score(X_te, y_te) for t in m.estimators_])
        print(f"{name:<15}{single:>11.4f}{rho_of(m, X_te):>7.3f}"
              f"{m.score(X_te, y_te):>9.4f}{fit_s:>7.2f}")

--- friedman1, target noise sigma=1.0 ---
model            single R2    rho   ens R2  fit s
RF mf=1.0 (def)     0.6273  0.751   0.8590   0.77
RF mf=0.3           0.4725  0.602   0.8412   0.31
ET mf=1.0 (def)     0.6075  0.721   0.8745   0.34
ET mf=0.3           0.3484  0.498   0.8372   0.17
--- friedman1, target noise sigma=5.0 ---
model            single R2    rho   ens R2  fit s
RF mf=1.0 (def)    -0.1515  0.406   0.4103   0.80
RF mf=0.3          -0.2160  0.328   0.4122   0.32
ET mf=1.0 (def)    -0.1884  0.368   0.4179   0.33
ET mf=0.3          -0.3094  0.252   0.4025   0.16

At low target noise Extra Trees wins on both axes: R² 0.8745 against 0.8590, in 0.34s against 0.77s. At high noise the ensembles converge (0.4179 against 0.4103) while the speed gap holds.

The row that should stop you is ET mf=1.0 at sigma 5.0: single-tree R² is -0.1884. Every tree is worse than predicting the mean, and the ensemble of them explains 42% of the variance. That is the whole series in one line — averaging does not need good members, only members whose errors point in different directions.

Note what max_features=0.3 did: the lowest $\rho$ in the table (0.498) and a worse ensemble. Diversity is not the objective; accuracy is. And a nuance for anyone who read the max_features post — 1.0 is the notorious bad default for RandomForestRegressor, but for ExtraTreesRegressor it is defensible, since the thresholds already supply the decorrelation subsampling would have to. The one regression default worth leaving alone.

---

Extra Trees from Scratch

Now the part that makes "stopped tasting the soup" concrete: two split-finders in NumPy, run on the same node with the same candidate features, printing what each chose and what it cost.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split

def gini(y):
    if len(y) == 0: return 0.0
    p = np.bincount(y, minlength=2) / len(y)
    return 1.0 - (p ** 2).sum()

def gain(y, mask):
    """Impurity drop from splitting y into mask / ~mask."""
    n, nl = len(y), int(mask.sum())
    if nl == 0 or nl == n: return 0.0
    return gini(y) - (nl/n)*gini(y[mask]) - ((n-nl)/n)*gini(y[~mask])

def best_threshold_split(X, y, feats):
    """RANDOM FOREST style: taste every midpoint of every candidate feature."""
    best, tried = (-1.0, None, None), 0
    for f in feats:
        col = X[:, f]
        vals = np.unique(col)
        for thr in (vals[:-1] + vals[1:]) / 2.0:
            tried += 1
            g = gain(y, col <= thr)
            if g > best[0]: best = (g, f, thr)
    return best, tried

def random_threshold_split(X, y, feats, rng):
    """EXTRA TREES style: ONE uniform draw per candidate feature. No tasting."""
    best, tried = (-1.0, None, None), 0
    for f in feats:
        col = X[:, f]
        thr = rng.uniform(col.min(), col.max())   # <- the entire difference
        tried += 1
        g = gain(y, col <= thr)
        if g > best[0]: best = (g, f, thr)
    return best, tried

X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, _, y_tr, _ = train_test_split(X, y, test_size=0.3, random_state=42)
feats = np.array([1, 4, 7, 12, 15])       # the 5 candidate features at this node

(gb, fb, tb), nb = best_threshold_split(X_tr, y_tr, feats)
(gr, fr, tr), nr = random_threshold_split(X_tr, y_tr, feats,
                                          np.random.default_rng(42))
print(f"node: {len(y_tr)} samples, gini={gini(y_tr):.4f}, "
      f"candidates={feats.tolist()}")
print(f"BEST  : feature {fb:>2}  thr={tb:+.4f}  gain={gb:.4f}  "
      f"({nb} splits tried)")
print(f"RANDOM: feature {fr:>2}  thr={tr:+.4f}  gain={gr:.4f}  "
      f"({nr} splits tried)")
print(f"        random keeps {gr/gb:.1%} of the gain "
      f"for {nr/nb:.3%} of the work")

g, chosen = [], []
for s in range(100):
    (gg, ff, _), _ = random_threshold_split(X_tr, y_tr, feats,
                                            np.random.default_rng(s))
    g.append(gg); chosen.append(int(ff))
g = np.array(g)
print(f"100 seeds: mean gain={g.mean():.4f} ({g.mean()/gb:.0%} of best), "
      f"worst={g.min():.4f}, best={g.max():.4f}")
print(f"           root feature chosen: {sorted(set(chosen))} "
      f"-> {len(set(chosen))} different roots")

node: 1400 samples, gini=0.4999, candidates=[1, 4, 7, 12, 15]
BEST  : feature  7  thr=+0.3604  gain=0.1281  (6995 splits tried)
RANDOM: feature  1  thr=+1.9664  gain=0.0197  (5 splits tried)
        random keeps 15.4% of the gain for 0.071% of the work
100 seeds: mean gain=0.0697 (54% of best), worst=0.0022, best=0.1243
           root feature chosen: [1, 7, 15] -> 3 different roots

This is the article in one output block.

The greedy finder tried 6,995 candidate splits to land on feature 7 at +0.3604, gain 0.1281. The random finder tried five, and with random_state=42 it drew badly: gain 0.0197, fifteen percent of what was available. That split is terrible — and that is not a flaw in the demo, that is the algorithm. One Extra Tree is permitted to be terrible.

Then read the last two lines. Across 100 seeds the random finder averages 54% of the best available gain, and the winning feature itself moves: three different features take the root, where the greedy finder returns feature 7 every time, in every tree, forever. Feature subsampling can only vary the root by hiding feature 7; random thresholds make the winner vary even when every tree sees everything.

Here is the same idea grown into an ensemble — pure NumPy, no bootstrap — checked against sklearn.

import time
import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.model_selection import train_test_split

def gini(y):
    p = np.bincount(y, minlength=2) / len(y)
    return 1.0 - (p ** 2).sum()

class MyExtraTree:
    """One Extra Tree: at each node, ONE random threshold per candidate feature."""

    def __init__(self, k=5, min_leaf=3, rng=None):
        self.k, self.min_leaf, self.rng = k, min_leaf, rng

    def fit(self, X, y):
        self.root = self._grow(X, y)
        return self

    def _leaf(self, y):
        return np.bincount(y, minlength=2) / len(y)

    def _grow(self, X, y):
        if len(y) < 2 * self.min_leaf or len(np.unique(y)) == 1:
            return self._leaf(y)
        best = None
        for f in self.rng.choice(X.shape[1], self.k, replace=False):
            col = X[:, f]
            lo, hi = col.min(), col.max()
            if hi <= lo:
                continue
            thr = self.rng.uniform(lo, hi)          # no search, one draw
            mask = col <= thr
            nl = int(mask.sum())
            if nl < self.min_leaf or len(y) - nl < self.min_leaf:
                continue
            g = (gini(y) - (nl/len(y))*gini(y[mask])
                 - ((len(y)-nl)/len(y))*gini(y[~mask]))
            if best is None or g > best[0]:
                best = (g, f, thr, mask)            # best of the random draws
        if best is None:
            return self._leaf(y)
        _, f, thr, mask = best
        return (f, thr, self._grow(X[mask], y[mask]),
                self._grow(X[~mask], y[~mask]))

    def predict_proba(self, X):
        out = np.zeros((len(X), 2))
        stack = [(self.root, np.arange(len(X)))]
        while stack:
            node, idx = stack.pop()
            if not isinstance(node, tuple):
                out[idx] = node
                continue
            f, thr, left, right = node
            m = X[idx, f] <= thr
            stack.append((left, idx[m]))
            stack.append((right, idx[~m]))
        return out


X, y = make_classification(n_samples=2000, n_features=20, n_informative=5,
                           n_redundant=5, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

t0 = time.perf_counter()
rng = np.random.default_rng(42)
forest = [MyExtraTree(k=5, min_leaf=3, rng=rng).fit(X_tr, y_tr)   # no bootstrap
          for _ in range(50)]
proba = np.mean([t.predict_proba(X_te) for t in forest], axis=0)
mine = float((proba.argmax(axis=1) == y_te).mean())
print(f"MyExtraTree x50 (pure NumPy) : {mine:.4f}   "
      f"built in {time.perf_counter() - t0:.2f}s")

sk = ExtraTreesClassifier(n_estimators=50, max_features=5, min_samples_leaf=3,
                          random_state=42, n_jobs=-1).fit(X_tr, y_tr)
print(f"sklearn ExtraTreesClassifier : {sk.score(X_te, y_te):.4f}")

MyExtraTree x50 (pure NumPy) : 0.8933   built in 0.63s
sklearn ExtraTreesClassifier : 0.8917

Within noise of the library, with no sorting anywhere in it — fifty fully grown trees over 1,400 rows in 0.63 seconds of interpreted Python. That is how little work remains once you delete the threshold search.

---

When Extra Trees Wins, and When It Doesn't

Situation	Pick	Why
Training time matters	Extra Trees	2–4x faster fit, no sort per node
Smooth regression target	Extra Trees	Random cut positions average smoother
Noisy or mislabelled y	Extra Trees	Random cuts can't chase bad labels
Many pure-junk features	RF, or ET with high max_features	Greedy search defends real signal
Signal at a sharp exact threshold	Random Forest	A uniform draw rarely lands on it
Skewed features, extreme outliers	Random Forest	Uniform draws land in empty space
oob_score out of the box	Random Forest	ET needs bootstrap=True first
Tight serving latency or memory	Random Forest	ET trees: 3x nodes, 1.8x depth

The APIs are identical and the two disagree by a point or two in unpredictable directions, so when in doubt, fit both and keep the winner. It is one import and, for Extra Trees, a third of the time.

---

Extra Trees Hyperparameters

Parameter	What it does	Sensible range	Notes
n_estimators	Trees	300–1000	Not a regularizer. ET is cheap — be generous
max_features	Candidates per split	'sqrt'–0.5 (clf), 1.0 (reg)	Tune first. Higher than RF: one shot per feature
bootstrap	Sample rows	False (default)	True for oob_score, max_samples, noisy labels
min_samples_leaf	Min per leaf	1 (clf), 5–20 (reg)	The real regularizer, and your label-noise defence
max_depth	Depth cap	None, or 20–40	ET runs deep (25.5 vs 14.4 here). Cap if size matters
criterion	Impurity	'gini' / 'squared_error'	Still used — ET scores its random candidates
n_jobs	Parallelism	-1	Free, always

One anti-pattern: copying your Random Forest's max_features straight into Extra Trees. Related parameters, different jobs, and we measured the bill — 0.6825 versus 0.8475 on the junk-column test.

---

Quick Reference Card

EXTRA TREES: CHEAT SHEET
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

WHAT IT IS:
  Random Forest, but each split threshold is DRAWN AT
  RANDOM (one per candidate feature) instead of searched.
  Best of the m random candidates still wins.

THE THREE KNOBS:
  rows       -> bootstrap        (bagging)
  columns    -> max_features     (random forest)
  thresholds -> random cuts      (extra trees)  <- new

THE TRADE:
  bias per tree     ▲ slightly (bias does NOT average away)
  correlation rho   ▼▼  measured 0.571 -> 0.515
  fit time          ▼▼▼ measured 2.6x faster
  model size        ▲▲  696 nodes vs 219

DEFAULTS TO KNOW:
  bootstrap    = False   (whole dataset per tree!)
  oob_score    -> ValueError unless bootstrap=True
  train score  -> always 1.0000, tells you nothing
  max_features = 'sqrt' (clf) / 1.0 (reg, and fine here)

WHEN IT WINS:
  ✓ Fit time matters / big hyperparameter search
  ✓ Smooth regression targets
  ✓ Noisy or mislabelled y
WHEN IT LOSES:
  ✗ Many pure-junk features (raise max_features!)
  ✗ Signal at a sharp exact threshold
  ✗ Tight serving latency or memory

SKLEARN:
  from sklearn.ensemble import (
      ExtraTreesClassifier, ExtraTreesRegressor)

---

Key Takeaways

1. One change: the threshold is drawn, not searched. One uniform draw per candidate feature, inside that node's range, and the best of those few wins.

2. It is not a random tree. The impurity criterion still picks the winner — Teo's cooks smelled all three pinches, they just never got a second pinch.

3. This is the third knob: rows, columns, thresholds. We measured the ladder: $\rho$ = 0.640, 0.571, 0.515.

4. Weaker trees, stronger ensemble — again. Single-tree accuracy fell to 0.8034, worst of the three, while the ensemble rose to 0.9050, best of the three.

5. You pay in bias, and bias does not average away. Variance reduction compounds over trees; per-tree bias is permanent. That is why the trade has limits.

6. bootstrap=False is the default and it is right. The thresholds already supply diversity, so no tree gives up a third of its rows. Flip it for oob_score, max_samples, or noisy labels.

7. The speedup is structural: no search means no sort per node, $O(mn)$ instead of $O(mn\log n)$ — 2.6x here, and ~2.5x the hyperparameter search per hour.

8. The noise trade-off cuts both ways. ET lost under junk features (0.6825 vs 0.7250), won under flipped labels (0.7700 vs 0.7606), and raising max_features fixed the first case outright, to 0.8475.

---

The One-Sentence Summary

Extra Trees is Teo's dice rule written in NumPy: stop tasting forty spoonfuls at every stage, take one blind pinch from each of a few random jars and keep the best-smelling one, and you get a hundred sloppier pots whose mistakes point in a hundred different directions — which is exactly why the blend beats a hundred identically over-salted pots, and why deleting the most expensive step in tree building makes the model faster and, far more often than anyone expects, more accurate.

---

What's Next?

Every model in this series has been fighting variance — bagging, feature subsampling, random thresholds, all of it averaging noise away. Tomorrow the strategy inverts.

1. AdaBoost — the pivot from variance reduction to bias reduction: not independent trees averaged in parallel, but a sequence of deliberately weak stumps, each built to fix what the last got wrong. Everything you learned about decorrelation stops applying.
2. Gradient Boosting — that insight generalised: each tree fits the gradient of the loss, turning boosting into gradient descent in function space.
3. XGBoost — the engineering that made boosting win competitions: second-order gradients, regularised leaf weights, sparsity-aware splits, and histogram binning (another way of refusing to sort).
4. The Boosting series — LightGBM, CatBoost, early stopping, learning rates, and an honest answer to "boosting or forests?" on tabular data.

Follow me for the next article in the Random Forests Deep Dive series!

---

Let's Connect!

If the Copper Ladle made Extra Trees click, drop a heart!

Questions? Ask in the comments — I read and respond to every one.

Do you actually fit both RandomForest and ExtraTrees before choosing? I do, every time, and Extra Trees wins more often than its reputation suggests — usually while I am still waiting for the forest to finish. 🥄

---

There is a version of engineering discipline that is really just expensive habit. The Copper Ladle tasted forty spoonfuls a stage because tasting felt like rigour, and it took a dishwasher to notice that all that rigour was producing one hundred copies of the same mistake, slowly. The best optimisation I ever shipped was not a faster algorithm — it was deleting a step everybody assumed had to be there.

---

Share this with the teammate still waiting for a Random Forest to finish training. Tell them to try the one that stopped tasting.