Definition
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 randomly chosen features, one threshold is drawn uniformly between the feature's minimum and maximum in that node, and the best of those random splits is kept. Each tree is trained on the whole training set (no bootstrap), and the forest averages the trees' class probabilities.
At a glance
- Task
- Classification (this article) and regression
- Input → output
- feature vector → class probabilities , the average of every tree's leaf proportions; predicted class
- Learns
- M independent trees, each a set of axis-aligned random splits and class-proportion leaves
- Training cost
- about — no sorting, one pass per candidate split
- Prediction cost
- ; 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 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 random features, score the 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 , threshold ) where is a random feature and over the points 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 : 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
The math
The random split. At a node holding the points , pick distinct features from the non-constant ones, and for each draw a single cut point:
- the training points that reached this node
- value of feature for point
- smallest and largest value of feature in the node — the draw never leaves a child empty
- the one random threshold tried for feature
The score. Each candidate is scored by the same weighted impurity decrease as in decision trees, and the best of the wins:
- Gini impurity of a node; = fraction of class
- points with and
- the randomly chosen features at this node
Compare with CART, which computes over all midpoints of every feature. Extra Trees computes at only points per node. That is why is the knob between "greedy" and "random": with the split ignores the labels; with large 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:
- number of trees (n_estimators)
- fraction of class in the leaf of tree that falls into (0 or 1 for a pure leaf)
Why more randomness means less variance. Let each tree's output at have variance over the randomness of the training set and of the tree, and let any two trees have correlation . The variance of the average of trees is
- variance of one tree's prediction
- correlation between two trees' predictions
- number of trees; the second term vanishes as M grows
More trees only kill the second term. The floor is set by how alike the trees are. Random thresholds lower much more than they raise , 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 with different classes, and suppose a tree's cut lands between them. In a random forest the cut sits at the midpoint , so every such tree switches class at the same place — a step. In Extra Trees the cut is uniform on , so for a query in the gap
- the random cut, given that it fell in the gap
- the query point between the two training points
The fraction of such trees that put with rises linearly from 0 at to 1 at . 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 , , the forest becomes a smooth, kernel-like function of .
Why training is faster. The optimal threshold for one feature needs the node's values sorted: for a node with points. A random threshold needs only the min and max and one partition pass: . Summed over a balanced tree of depth , that is per tree instead of .
Worked example: growing one extra tree by hand
Fourteen points with two features and two classes, A and B, split roughly by the diagonal . The root has 7 A and 7 B, so . We grow tree 1 of an Extra Trees ensemble with (both features tried at every node) and then classify the new point .
| # | 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
- 1Root (14 points, ). Ranges: , . The random draws are and .
- 2Score . Left: all 7 A plus B points 10, 13, 14 → 10 points (7 A / 3 B), . Right: 4 B, . .
- 3Score . Right: only point 12 (B). Left: 13 points, 7 A / 6 B, . . → keep ; the right child (4 B) is pure and becomes a leaf.
- 4Left child (10 points: 7 A / 3 B, ). Ranges now , . Draws: gives 6 A/2 B vs 1 A/1 B, ; gives 3 A vs 4 A/3 B, . → keep ; the 3-point A child is a leaf.
- 5Next node (7 points: 4 A / 3 B, ). Draws: sends all 4 A left and all 3 B right, (everything); gives only 0.004. → keep . Both children are pure: the tree is finished with 3 splits and 4 leaves.
- 6Classify . → left; → right; → the pure B leaf. Tree 1 votes .
Repeating the procedure with fresh random draws gives four more trees. Each one is fully grown, so each votes 0 or 1 at :
| 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 , so is classified B. With 50 trees the same procedure gives : sits close to the diagonal boundary, and the probability says so instead of pretending to certainty.
The algorithm, step by step
ExtraTrees.fit(X, y)
- 1For 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). - 2BuildNode(S) — stop? If is pure, has fewer than points, or every feature is constant in , return a leaf that stores the class proportions of .
- 3Draw. Choose distinct features among the non-constant ones. For each, compute , and draw .
- 4Score. For each of the candidates, partition in one pass and compute the Gini (or entropy) decrease.
- 5Split on the best candidate and call BuildNode on the two children.
- 6Predict: drop down every tree, average the leaf proportions, and return the class with the largest average probability.
Complexity
- One node
- — min/max plus one partition per candidate; a random forest node costs for sorting
- One tree
- about for a balanced tree of depth
- Forest
- , 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).
| 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
| 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
- : 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
In code
1import numpy as np23def gini(y):4 p = np.bincount(y, minlength=2) / len(y)5 return 1 - (p ** 2).sum()67def grow(X, y, K, rng, min_split=2):8 p = np.bincount(y, minlength=2) / len(y)9 live = [j for j in range(X.shape[1]) if X[:, j].max() > X[:, j].min()]10 if len(y) < min_split or p.max() == 1 or not live:11 return {"p": p} # leaf: class proportions12 best = None13 for j in rng.choice(live, size=min(K, len(live)), replace=False):14 lo, hi = X[:, j].min(), X[:, j].max()15 t = rng.uniform(lo, hi) # ONE random threshold16 L = X[:, j] <= t17 score = gini(y) - L.mean() * gini(y[L]) - (~L).mean() * gini(y[~L])18 if best is None or score > best[0]:19 best = (score, j, t, L)20 _, j, t, L = best21 return {"j": j, "t": t,22 "left": grow(X[L], y[L], K, rng, min_split),23 "right": grow(X[~L], y[~L], K, rng, min_split)}2425def proba(node, x):26 while "p" not in node:27 node = node["left"] if x[node["j"]] <= node["t"] else node["right"]28 return node["p"]2930class ExtraTrees:31 def __init__(self, n_trees=100, K=None, min_split=2, seed=0):32 self.n_trees, self.K, self.min_split = n_trees, K, min_split33 self.rng = np.random.default_rng(seed)3435 def fit(self, X, y): # no bootstrap: every tree sees all rows36 K = self.K or max(1, int(np.sqrt(X.shape[1])))37 self.trees = [grow(X, y, K, self.rng, self.min_split) for _ in range(self.n_trees)]38 return self3940 def predict_proba(self, X):41 return np.array([np.mean([proba(t, x) for t in self.trees], axis=0) for x in X])4243X = 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],44 [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]])45y = np.array([0] * 7 + [1] * 7)46et = ExtraTrees(n_trees=500, K=2, seed=0).fit(X, y)47print("train acc:", (et.predict_proba(X).argmax(1) == y).mean())48print("P(B | x=(4.5, 5.5)):", et.predict_proba(np.array([[4.5, 5.5]]))[0, 1].round(3))1import numpy as np2from sklearn.ensemble import ExtraTreesClassifier, RandomForestClassifier34X = 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],5 [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]])6y = np.array([0] * 7 + [1] * 7) # 0 = A, 1 = B7q = np.array([[4.5, 5.5]])89et = ExtraTreesClassifier(n_estimators=500, max_features=None, random_state=0).fit(X, y)10rf = RandomForestClassifier(n_estimators=500, max_features=None, random_state=0).fit(X, y)11print("ET P(B | q) =", et.predict_proba(q)[0, 1].round(3), " train acc", et.score(X, y))12print("RF P(B | q) =", rf.predict_proba(q)[0, 1].round(3), " train acc", rf.score(X, y))1314# How many distinct probability levels does each ensemble produce on a 100x100 grid?15g = np.stack(np.meshgrid(np.linspace(0, 10, 100), np.linspace(0, 10, 100)), -1).reshape(-1, 2)16for name, m in [("ET", et), ("RF", rf)]:17 print(name, "distinct P(B) values on grid:", len(np.unique(m.predict_proba(g)[:, 1].round(4))))18print("ET root thresholds of first 5 trees:",19 [(int(t.tree_.feature[0]), round(float(t.tree_.threshold[0]), 2)) for t in et.estimators_[:5]])Use when
- +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.
Avoid when
- −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.
Where it's used
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.
Check yourself
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?
Check yourself
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?
Check yourself
Why does scikit-learn's ExtraTreesClassifier default to bootstrap=False?
Check yourself
In Var = ρσ² + (1 − ρ)σ²/M, which term does Extra Trees mainly reduce compared with a random forest?
Remember
- ✓At each node Extra Trees draws one uniform threshold for each of 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 , lowering the variance floor ; averaging many random cuts turns step boundaries into smooth probability ramps.
- ✓ is the dial: is totally random, large 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.