# Extra Trees

> Like a random forest, but split thresholds are drawn at random — even lower variance, and faster to train.

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

**Extra Trees:** (**extremely randomized trees**, Geurts, Ernst & Wehenkel 2006) is an ensemble of fully grown decision trees in which every split is chosen almost at random: at each node, for $K$ randomly chosen features, **one threshold is drawn uniformly** between the feature's minimum and maximum in that node, and the best of those $K$ random splits is kept. Each tree is trained on the **whole** training set (no bootstrap), and the forest averages the trees' class probabilities.

- **Task:** Classification (this article) and regression
- **Input → output:** feature vector $x$ → class probabilities $\hat p(c\mid x)$, the average of every tree's leaf proportions; predicted class $=\arg\max_c \hat p(c\mid x)$
- **Learns:** M independent trees, each a set of axis-aligned random splits and class-proportion leaves
- **Training cost:** about $O(M\,K\,n\log n)$ — no sorting, one pass per candidate split
- **Prediction cost:** $O(M\cdot\text{depth})$; the trees are deeper than a random forest's, so prediction is somewhat slower
- **Key hyperparameters:** `n_estimators` (M), `max_features` (K), `min_samples_split` / `min_samples_leaf`, `max_depth`, `bootstrap` (off by default)
- **Assumes:** nothing about distributions; features on any scale (only order matters); boundaries are built from axis-aligned pieces

## The problem

A single fully grown decision tree has low bias but **high variance**: move one training point and the greedy split search can pick a different root, and everything below it changes. The **random forest** fixes this by averaging many trees and making them *different* — bootstrap rows plus a random subset of features per split — so their errors partly cancel.

But a random forest still runs the full **optimal threshold search** inside each tree: sort the node's values for every candidate feature and scan all $n-1$ cut points. Two things are wrong with that. It is the expensive part of training (sorting at every node), and it is *the* source of the variance we are trying to average away — the best cut point jumps around whenever the sample changes, and on a bootstrap sample it always lands exactly on a midpoint between two training values. The averaged boundary is therefore still made of a few repeated steps.

Extra Trees asks: what if we stop optimizing the threshold altogether? Randomize it, and let averaging do the work.

## The idea

Grow each tree exactly like a CART tree, with one change at every node: instead of *finding* the best threshold for a feature, **draw one threshold at random** in the range of that feature's values in the node. Do this for $K$ random features, score the $K$ random splits by impurity decrease, and keep the best one. Recurse until the leaves are pure (or too small).

Each individual tree is *worse* than a CART tree — its splits are rarely optimal — and slightly more biased. But the trees are now **far less correlated** with each other, because their thresholds land all over the place rather than on the same few midpoints. Averaging many weakly correlated trees removes much more variance, and averaging many *different* thresholds turns the staircase boundary into a smooth ramp. And because nothing is sorted, each split costs one linear pass.

**Vocabulary**

- **Random split:** a pair (feature $j$, threshold $t$) where $j$ is a random feature and $t\sim\mathcal U(\min_S x_j,\ \max_S x_j)$ over the points $S$ in the node
- **K (max_features):** how many random splits are drawn and compared at each node; the only place labels influence the split choice
- **Totally randomized tree:** the extreme $K=1$: the split is chosen without looking at the labels at all (labels only decide when to stop)
- **n_min (min_samples_split):** a node with fewer points becomes a leaf; the paper's defaults are 2 for classification and 5 for regression
- **Score:** the impurity decrease of a split (Gini or entropy for classification); the paper uses a normalized version, scikit-learn the plain decrease
- **Bootstrap:** resampling rows with replacement; Extra Trees does *not* use it by default — every tree sees all n rows

> **Randomness moves from the rows to the thresholds:** A random forest gets diversity from *which data* each tree sees; Extra Trees gets it from *where* each tree cuts. Because every tree sees all the data, no information is thrown away (a bootstrap sample leaves out about 37% of the distinct rows), which partly pays for the bias added by random cuts.

## The math

**The random split.** At a node holding the points $S$, pick $K$ distinct features from the non-constant ones, and for each draw a single cut point:

$$
t_j\sim\mathcal U\!\left(a_j,\,b_j\right),\qquad a_j=\min_{i\in S}x_{ij},\quad b_j=\max_{i\in S}x_{ij}
$$

- $S$: the training points that reached this node
- $x_{ij}$: value of feature $j$ for point $i$
- $a_j,\ b_j$: smallest and largest value of feature $j$ in the node — the draw never leaves a child empty
- $t_j$: the one random threshold tried for feature $j$

**The score.** Each candidate is scored by the same weighted impurity decrease as in **decision trees**, and the best of the $K$ wins:

$$
\Delta G(j,t)=G(S)-\frac{|S_L|}{|S|}G(S_L)-\frac{|S_R|}{|S|}G(S_R),\qquad (j^*,t^*)=\arg\max_{j\in\mathcal F_K}\ \Delta G(j,t_j)
$$

- $G(S)=1-\sum_c p_c^2$: Gini impurity of a node; $p_c$ = fraction of class $c$
- $S_L,\ S_R$: points with $x_{ij}\le t$ and $x_{ij}>t$
- $\mathcal F_K$: the $K$ randomly chosen features at this node

Compare with CART, which computes $\max_{t}\Delta G(j,t)$ over all $n-1$ midpoints of every feature. Extra Trees computes $\Delta G$ at only $K$ points per node. That is why $K$ is the knob between "greedy" and "random": with $K=1$ the split ignores the labels; with large $K$ the best of many random cuts is usually close to a good cut, so each tree is stronger but the trees are more alike.

**The ensemble.** Each leaf stores the class proportions of its training points; the forest averages them:

$$
\hat p(c\mid x)=\frac{1}{M}\sum_{m=1}^{M}\hat p_m(c\mid x),\qquad \hat y(x)=\arg\max_c\ \hat p(c\mid x)
$$

- $M$: number of trees (n_estimators)
- $\hat p_m(c\mid x)$: fraction of class $c$ in the leaf of tree $m$ that $x$ falls into (0 or 1 for a pure leaf)

**Why more randomness means less variance.** Let each tree's output at $x$ have variance $\sigma^2$ over the randomness of the training set and of the tree, and let any two trees have correlation $\rho$. The variance of the average of $M$ trees is

$$
\operatorname{Var}\big[\hat p(x)\big]=\rho\,\sigma^2+\frac{1-\rho}{M}\,\sigma^2
$$

- $\sigma^2$: variance of one tree's prediction
- $\rho$: correlation between two trees' predictions
- $M$: number of trees; the second term vanishes as M grows

More trees only kill the second term. The floor $\rho\sigma^2$ is set by how alike the trees are. Random thresholds lower $\rho$ much more than they raise $\sigma^2$, so the floor drops — at the price of a small increase in bias, since each tree's splits are suboptimal. Whether the trade wins is empirical; the experiment below shows it usually does in more than a couple of dimensions. (The derivation of this formula is in **random forests**.)

**Why the boundary becomes smooth.** Take one feature and two neighbouring training points $a<b$ with different classes, and suppose a tree's cut lands between them. In a random forest the cut sits at the midpoint $\tfrac{a+b}{2}$, so every such tree switches class at the same place — a step. In Extra Trees the cut is uniform on $(a,b)$, so for a query $x$ in the gap

$$
P(x>t\mid a<t<b)=\int_a^{x}\frac{dt}{b-a}=\frac{x-a}{b-a}
$$

- $t$: the random cut, given that it fell in the gap $(a,b)$
- $x$: the query point between the two training points

The fraction of such trees that put $x$ with $b$ rises **linearly** from 0 at $a$ to 1 at $b$. Averaged over many trees, the predicted probability is a piecewise-linear ramp — close to linear interpolation between the training points — rather than a jump. In the limit $K=1$, $M\to\infty$, the forest becomes a smooth, kernel-like function of $x$.

**Why training is faster.** The optimal threshold for one feature needs the node's values sorted: $O(n_s\log n_s)$ for a node with $n_s$ points. A random threshold needs only the min and max and one partition pass: $O(n_s)$. Summed over a balanced tree of depth $\approx\log n$, that is $O(K\,n\log n)$ per tree instead of $O(K\,n\log^2 n)$.

## Worked example: growing one extra tree by hand

Fourteen points with two features and two classes, **A** and **B**, split roughly by the diagonal $x_1+x_2\approx 9$. The root has 7 A and 7 B, so $G(\text{root})=1-0.5^2-0.5^2=0.5$. We grow tree 1 of an Extra Trees ensemble with $K=2$ (both features tried at every node) and then classify the new point $q=(4.5,\,5.5)$.

Training data. Highlighted: the three B points with x₁ ≤ 5.58, which end up in the root's left child.

| # | x₁ | x₂ | class |
| --- | --- | --- | --- |
| 1 | 1.0 | 2.0 | A |
| 2 | 2.0 | 1.0 | A |
| 3 | 2.5 | 3.5 | A |
| 4 | 3.5 | 2.0 | A |
| 5 | 4.0 | 4.5 | A |
| 6 | 1.5 | 5.0 | A |
| 7 | 5.5 | 3.0 | A |
| 8 | 6.0 | 5.5 | B |
| 9 | 7.0 | 3.5 | B |
| 10 | 5.0 | 7.0 | B |
| 11 | 8.0 | 6.5 | B |
| 12 | 6.5 | 8.5 | B |
| 13 | 3.5 | 7.5 | B |
| 14 | 3.0 | 6.5 | B |

**Tree 1, node by node**

1. **Root (14 points, $G=0.5$).** Ranges: $x_1\in[1.0,8.0]$, $x_2\in[1.0,8.5]$. The random draws are $t_1=5.58$ and $t_2=8.15$.
2. **Score $x_1\le5.58$.** Left: all 7 A plus B points 10, 13, 14 → 10 points (7 A / 3 B), $G=1-0.7^2-0.3^2=0.42$. Right: 4 B, $G=0$. $\Delta G=0.5-\tfrac{10}{14}(0.42)-\tfrac{4}{14}(0)=0.5-0.30=0.200$.
3. **Score $x_2\le8.15$.** Right: only point 12 (B). Left: 13 points, 7 A / 6 B, $G=1-(\tfrac{7}{13})^2-(\tfrac{6}{13})^2=0.497$. $\Delta G=0.5-\tfrac{13}{14}(0.497)=0.038$. → keep **$x_1\le5.58$**; the right child (4 B) is pure and becomes a leaf.
4. **Left child (10 points: 7 A / 3 B, $G=0.42$).** Ranges now $x_1\in[1.0,5.5]$, $x_2\in[1.0,7.5]$. Draws: $x_1\le4.70$ gives 6 A/2 B vs 1 A/1 B, $\Delta G=0.020$; $x_2\le2.15$ gives 3 A vs 4 A/3 B, $\Delta G=0.077$. → keep **$x_2\le2.15$**; the 3-point A child is a leaf.
5. **Next node (7 points: 4 A / 3 B, $G=0.490$).** Draws: $x_2\le5.31$ sends all 4 A left and all 3 B right, $\Delta G=0.490$ (everything); $x_1\le4.54$ gives only 0.004. → keep **$x_2\le5.31$**. Both children are pure: the tree is finished with 3 splits and 4 leaves.
6. **Classify $q=(4.5,5.5)$.** $4.5\le5.58$ → left; $5.5>2.15$ → right; $5.5>5.31$ → the pure B leaf. Tree 1 votes $\hat p_1(B\mid q)=1$.

> **Not the best root — on purpose:** CART's exhaustive search would split the root at $x_2\le5.25$ with $\Delta G=0.375$. A uniform draw on $x_2\in[1.0,8.5]$ produces that partition only if it lands in $(5.0,5.5)$: probability $0.5/7.5=0.067$. Tree 1 settled for $\Delta G=0.200$, and that is fine — the tree still reaches pure leaves, just along a different path.

Repeating the procedure with fresh random draws gives four more trees. Each one is fully grown, so each votes 0 or 1 at $q$:

The first five trees of the ensemble (K = 2). Root candidates with their Gini decrease; the winner is bold.

| Tree | Root candidates (ΔGini) | Leaves | Vote at q |
| --- | --- | --- | --- |
| 1 | **x₁ ≤ 5.58 (0.200)** · x₂ ≤ 8.15 (0.038) | 4 | B |
| 2 | **x₂ ≤ 5.17 (0.375)** · x₁ ≤ 4.22 (0.167) | 3 | B |
| 3 | **x₁ ≤ 4.02 (0.167)** · x₂ ≤ 7.41 (0.083) | 5 | B |
| 4 | **x₂ ≤ 2.48 (0.136)** · x₁ ≤ 1.86 (0.083) | 6 | A |
| 5 | **x₂ ≤ 4.22 (0.167)** · x₁ ≤ 5.36 (0.100) | 9 | A |

Five different roots — tree 2 happened to draw a cut in the optimal gap. The forest's estimate is $\hat p(B\mid q)=\tfrac{1+1+1+0+0}{5}=0.60$, so $q$ is classified **B**. With 50 trees the same procedure gives $\hat p(B\mid q)=0.68$: $q$ sits close to the diagonal boundary, and the probability says so instead of pretending to certainty.

> Figure: The worked example, live. The shading is the ensemble's P(B); orange lines are one tree's splits (drawn root-first; dashed = the losing root candidate), and the ticks on the axes are the root thresholds of all trees. It opens on tree 1 of the hand calculation: root candidates x₁ ≤ 5.58 (Gini gain 0.200) and x₂ ≤ 8.15 (0.038), 4 leaves, and the five votes B B B A A → P(B | ◆) = 0.60. Step through trees with ◀ ▶ or click a vote square; drag the ◆. Slide to 50 trees: P(B | ◆) = 0.68, the 50 root thresholds take 49 distinct values, and the 25×25 map shows 48 distinct probability levels. Switch to random forest (bootstrap + best midpoint): the root ticks collapse onto 14 distinct values, the map onto 40 levels, P(B | ◆) = 0.66 — and point sizes show each tree's bootstrap counts (hollow = out of bag). K = 1 gives totally randomized trees: 8.04 leaves per tree on average instead of 5.90.

## The algorithm, step by step

**ExtraTrees.fit(X, y)**

1. **For** m = 1 … M: grow one tree on the **full** training set (no bootstrap) with `BuildNode(all rows)`. The trees are independent, so this loop is trivially parallel (`n_jobs`).
2. **BuildNode(S) — stop?** If $S$ is pure, has fewer than $n_{\min}$ points, or every feature is constant in $S$, return a leaf that stores the class proportions of $S$.
3. **Draw.** Choose $K$ distinct features among the non-constant ones. For each, compute $a_j=\min_S x_j$, $b_j=\max_S x_j$ and draw $t_j\sim\mathcal U(a_j,b_j)$.
4. **Score.** For each of the $K$ candidates, partition $S$ in one pass and compute the Gini (or entropy) decrease.
5. **Split** on the best candidate and call BuildNode on the two children.
6. **Predict:** drop $x$ down every tree, average the leaf proportions, and return the class with the largest average probability.

**Complexity**

- **One node:** $O(K\,n_s)$ — min/max plus one partition per candidate; a random forest node costs $O(K\,n_s\log n_s)$ for sorting
- **One tree:** about $O(K\,n\log n)$ for a balanced tree of depth $\approx\log n$
- **Forest:** $O(M\,K\,n\log n)$, parallel over trees
- **Memory / prediction:** fully grown trees on all n rows have more leaves than bootstrap trees; prediction walks deeper trees

Measured with scikit-learn on 20,000 rows × 40 features, 200 trees, one core: a random forest took 24.69 s to fit and an Extra Trees ensemble **5.02 s** — about 5× faster. The price shows up in the trees' size: 10,292 nodes and depth 40.1 per tree on average for Extra Trees, versus 3,211 nodes and depth 25.6 for the random forest. 5-fold cross-validated accuracy with 300 trees: 0.9479 for Extra Trees, 0.9438 for the random forest.

## Does it really reduce variance?

Take 30 independent training sets of 300 rows each from one synthetic 20-feature problem (6 informative, 5% label noise), fit each model on each, and score on the same 5,000 test rows. "Variance" is the variance of the predicted probability across the 30 fits, averaged over test points; "bias²" is the squared gap between the average prediction and the label (the Brier-score decomposition).

Mean over 30 training sets, 200 trees each. Extra Trees has the lowest variance at both settings of max_features, and slightly higher bias at sqrt.

| Model | max_features | Accuracy | Log-loss | Bias² | Variance |
| --- | --- | --- | --- | --- | --- |
| Single tree | sqrt | 0.743 | 1.777 | 0.1035 | 0.1536 |
| Random forest | sqrt | 0.868 | 0.380 | 0.1073 | 0.0060 |
| **Extra Trees** | sqrt | **0.871** | 0.394 | 0.1125 | **0.0047** |
| Random forest | all (20) | 0.864 | 0.360 | 0.0934 | 0.0134 |
| **Extra Trees** | all (20) | **0.880** | **0.331** | **0.0898** | **0.0070** |

With all features as candidates, a random forest is nearly a bagged CART and its trees are strongly correlated (variance 0.0134); Extra Trees halves that (0.0070) and wins on every column. The effect is not universal: on the 2-D two-moons problem (200 rows, 30% noise) the random forest's variance was lower, 0.0135 vs 0.0158, and its accuracy 0.887 vs 0.882 — with only two features there are few ways to cut, and random cuts mostly add bias.

## Hyperparameters and tuning

scikit-learn ExtraTreesClassifier names and defaults.

| Parameter | Default | Effect |
| --- | --- | --- |
| n_estimators (M) | 100 | More trees only lower the (1−ρ)σ²/M term; never hurts accuracy, costs time. Random cuts make single trees noisier, so ET benefits from more trees than a forest — 300–1000 is common. |
| max_features (K) | "sqrt" | K = 1: totally random, lowest correlation, highest bias. Larger K: stronger, more similar trees. Tune over {sqrt, log2, 0.5, 1.0}; large K suits problems with many irrelevant features. |
| min_samples_split / min_samples_leaf | 2 / 1 | Larger values smooth the probabilities and help with label noise; the paper recommends n_min = 5 for regression. |
| max_depth | None | Usually left unlimited; limit it to cap memory and prediction time. |
| bootstrap | False | Turning it on adds row randomness (and enables oob_score) but throws away data; rarely helps. |
| criterion | "gini" | "entropy" / "log_loss" give nearly the same trees. |
| class_weight | None | "balanced" reweights classes inside the impurity for imbalanced data. |

**Variants and relatives**

- **Totally randomized trees:** $K=1$: the structure is independent of the labels; useful for theory and as a fast, smooth baseline
- **Random forest:** bootstrap rows + optimal threshold among a random feature subset; see **random forests**
- **ExtraTreesRegressor:** the same randomization with variance reduction as the score and leaf means as predictions
- **Isolation forest:** fully random cuts (no score at all) used to measure how easily a point is isolated — see **isolation forest**
- **Totally random trees embedding:** scikit-learn's RandomTreesEmbedding: unsupervised random trees whose leaf indices become sparse features
- **Boosting:** the opposite philosophy — shallow trees fitted sequentially to reduce bias; see **AdaBoost** and **gradient boosting**

> **Irrelevant features hurt more than in a random forest:** With small K, a random split on a pure-noise feature is accepted whenever it happens to beat the other random candidates. If most features are noise, increase `max_features` (or select features first) — the best of more random cuts filters the noise back out.

> **Do not cross-validate on the training probabilities:** With default settings every leaf is pure and every tree saw every row, so training accuracy is 100% and training probabilities are 0 or 1 — and, unlike a random forest, there is no out-of-bag estimate unless you set `bootstrap=True`. Always evaluate on held-out data or with cross-validation.

## In code

```python
import numpy as np

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

def grow(X, y, K, rng, min_split=2):
    p = np.bincount(y, minlength=2) / len(y)
    live = [j for j in range(X.shape[1]) if X[:, j].max() > X[:, j].min()]
    if len(y) < min_split or p.max() == 1 or not live:
        return {"p": p}                                     # leaf: class proportions
    best = None
    for j in rng.choice(live, size=min(K, len(live)), replace=False):
        lo, hi = X[:, j].min(), X[:, j].max()
        t = rng.uniform(lo, hi)                             # ONE random threshold
        L = X[:, j] <= t
        score = gini(y) - L.mean() * gini(y[L]) - (~L).mean() * gini(y[~L])
        if best is None or score > best[0]:
            best = (score, j, t, L)
    _, j, t, L = best
    return {"j": j, "t": t,
            "left": grow(X[L], y[L], K, rng, min_split),
            "right": grow(X[~L], y[~L], K, rng, min_split)}

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

class ExtraTrees:
    def __init__(self, n_trees=100, K=None, min_split=2, seed=0):
        self.n_trees, self.K, self.min_split = n_trees, K, min_split
        self.rng = np.random.default_rng(seed)

    def fit(self, X, y):                                    # no bootstrap: every tree sees all rows
        K = self.K or max(1, int(np.sqrt(X.shape[1])))
        self.trees = [grow(X, y, K, self.rng, self.min_split) for _ in range(self.n_trees)]
        return self

    def predict_proba(self, X):
        return np.array([np.mean([proba(t, x) for t in self.trees], axis=0) for x in X])

X = np.array([[1.0, 2.0], [2.0, 1.0], [2.5, 3.5], [3.5, 2.0], [4.0, 4.5], [1.5, 5.0], [5.5, 3.0],
              [6.0, 5.5], [7.0, 3.5], [5.0, 7.0], [8.0, 6.5], [6.5, 8.5], [3.5, 7.5], [3.0, 6.5]])
y = np.array([0] * 7 + [1] * 7)
et = ExtraTrees(n_trees=500, K=2, seed=0).fit(X, y)
print("train acc:", (et.predict_proba(X).argmax(1) == y).mean())
print("P(B | x=(4.5, 5.5)):", et.predict_proba(np.array([[4.5, 5.5]]))[0, 1].round(3))
```

From scratch: random thresholds, best of K, no bootstrap, averaged leaf proportions. Prints train acc: 1.0 and P(B | x=(4.5, 5.5)): 0.642.

```python
import numpy as np
from sklearn.ensemble import ExtraTreesClassifier, RandomForestClassifier

X = np.array([[1.0, 2.0], [2.0, 1.0], [2.5, 3.5], [3.5, 2.0], [4.0, 4.5], [1.5, 5.0], [5.5, 3.0],
              [6.0, 5.5], [7.0, 3.5], [5.0, 7.0], [8.0, 6.5], [6.5, 8.5], [3.5, 7.5], [3.0, 6.5]])
y = np.array([0] * 7 + [1] * 7)          # 0 = A, 1 = B
q = np.array([[4.5, 5.5]])

et = ExtraTreesClassifier(n_estimators=500, max_features=None, random_state=0).fit(X, y)
rf = RandomForestClassifier(n_estimators=500, max_features=None, random_state=0).fit(X, y)
print("ET  P(B | q) =", et.predict_proba(q)[0, 1].round(3), " train acc", et.score(X, y))
print("RF  P(B | q) =", rf.predict_proba(q)[0, 1].round(3), " train acc", rf.score(X, y))

# How many distinct probability levels does each ensemble produce on a 100x100 grid?
g = np.stack(np.meshgrid(np.linspace(0, 10, 100), np.linspace(0, 10, 100)), -1).reshape(-1, 2)
for name, m in [("ET", et), ("RF", rf)]:
    print(name, "distinct P(B) values on grid:", len(np.unique(m.predict_proba(g)[:, 1].round(4))))
print("ET root thresholds of first 5 trees:",
      [(int(t.tree_.feature[0]), round(float(t.tree_.threshold[0]), 2)) for t in et.estimators_[:5]])
```

scikit-learn on the worked example, next to a random forest. Prints ET P(B | q) = 0.626, RF P(B | q) = 0.59 (both train acc 1.0), 489 vs 163 distinct probability values on a 100×100 grid, and ET root splits [(1, 6.34), (1, 5.53), (1, 5.25), (0, 2.57), (1, 4.89)].

> **Why the numbers differ from the hand calculation:** Every implementation draws different random thresholds, so tree-by-tree results differ: the figure's first five trees give 0.60, the NumPy version with 500 trees 0.642, scikit-learn 0.626. All agree that q leans B but sits near the boundary — the stable quantity is the averaged probability, not any one tree.

**Strengths**

- You want random-forest accuracy with less training time — no sorting, about 5× faster in the benchmark above.
- There are many features and you want smoother probability estimates and lower variance than a random forest.
- You need a strong, low-tuning baseline that handles mixed scales and nonlinear interactions.
- Data is small to moderate: every tree uses all rows, so nothing is lost to bootstrapping.

**Limitations**

- Most features are irrelevant and you cannot raise max_features — random cuts on noise features cost accuracy.
- Memory or prediction latency is tight: fully grown random trees are larger and deeper.
- You need an out-of-bag estimate for free, or interpretable individual trees.
- There are only one or two features: random cuts mostly add bias (see the moons result).
- You need the last bit of accuracy on tabular data — gradient boosting usually wins.

- **Genomics and bioinformatics:** Thousands of gene-expression features, few samples: Extra Trees is fast and its feature importances are used for gene selection (e.g. GENIE3 for gene-network inference builds on tree ensembles including Extra Trees).
- **Image and signal classification:** Pixel- and patch-based classifiers in the original paper's experiments, and fast random-tree feature extraction for vision pipelines.
- **Feature selection:** `SelectFromModel(ExtraTreesClassifier())` is a common first pass to rank and prune features before a heavier model.
- **AutoML and stacking:** A standard diverse member of ensembles in AutoML systems: its errors are less correlated with random forests and boosting than they are with each other.

**Question:** At the root of the worked example, x₂ ranges over [1.0, 8.5] and the optimal cut x₂ ≤ 5.25 is reproduced by any threshold in (5.0, 5.5). What is the probability that one random x₂ threshold produces that optimal partition?

- A. 0.033
- B. 0.067
- C. 0.25
- D. 0.5

**Answer:** B. 0.067 — The threshold is uniform on an interval of length $8.5-1.0=7.5$; the good gap has length $0.5$. $0.5/7.5=0.067$.

**Question:** Two training points on one feature: class A at x = 2 and class B at x = 4, and a totally randomized tree's cut falls between them. Averaged over many such trees, what is P(B) at x = 3.5?

- A. 0
- B. 0.5
- C. 0.75
- D. 1

**Answer:** C. 0.75 — With $t\sim\mathcal U(2,4)$, $x=3.5$ goes with B when $t<3.5$: probability $(3.5-2)/(4-2)=0.75$. A random forest would put the cut at the midpoint 3 and give exactly 1.

**Question:** Why does scikit-learn's ExtraTreesClassifier default to bootstrap=False?

- A. Bootstrap samples cannot be used with random thresholds
- B. The random thresholds already decorrelate the trees, so using all rows lowers bias at little cost in variance
- C. Bootstrapping would make training slower than a random forest
- D. Without bootstrap the trees are identical, which is desirable

**Answer:** B. The random thresholds already decorrelate the trees, so using all rows lowers bias at little cost in variance — Diversity comes from the random cuts, so the trees differ even on identical data. Keeping every row avoids discarding about a third of the distinct samples per tree, which reduces bias.

**Question:** In Var = ρσ² + (1 − ρ)σ²/M, which term does Extra Trees mainly reduce compared with a random forest?

- A. σ², by making each tree more accurate
- B. ρσ², by making the trees less correlated
- C. (1 − ρ)σ²/M, by using more trees
- D. None; it reduces bias instead

**Answer:** B. ρσ², by making the trees less correlated — Random thresholds make individual trees slightly *noisier* ($\sigma^2$ goes up a little) but much less alike, so the floor $\rho\sigma^2$ that no number of trees can remove drops.

**Key points**

- At each node Extra Trees draws one uniform threshold for each of $K$ random features and keeps the best by impurity decrease — no threshold search, no sorting.
- Every tree is grown fully on the whole training set (no bootstrap); the forest averages leaf class proportions.
- Random cuts raise bias a little but cut tree correlation $\rho$, lowering the variance floor $\rho\sigma^2$; averaging many random cuts turns step boundaries into smooth probability ramps.
- $K$ is the dial: $K=1$ is totally random, large $K$ approaches a random forest without bootstrap. Raise it when many features are noise.
- Training is several times faster than a random forest, but the trees are larger and deeper; evaluate on held-out data since there is no OOB score by default.

---

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