Extremely Randomized Trees
Extra Trees pushes random forests' randomness one step further by picking split thresholds randomly too, not just which features to consider — trading a bit of per-tree accuracy for faster training and lower variance.
A random forest builds many decision trees, each on a bootstrapped sample of the data, and at each split considers only a random subset of features — but once it picks a feature to split on, it still searches for the single best threshold for that feature, the one that most improves the split's purity.
Extremely Randomized Trees (Extra Trees) takes randomness one notch further: at each candidate feature, instead of searching for the optimal threshold, it picks a threshold at random (within that feature's observed range) and only then compares candidate splits by quality. It also typically skips bootstrapping and trains each tree on the full dataset instead.
Extra Trees deliberately gives up a small amount of per-tree fit quality — random thresholds are rarely the single best split — in exchange for decorrelating the trees in the ensemble even more than bagging alone does, which tends to lower variance and speed up training since no threshold search is needed.
Worked example. Splitting on "income" between two candidate cutoffs, a standard random forest tree evaluates every observed income value as a potential threshold and picks whichever cutoff minimizes impurity, say $52,300. An Extra Trees tree instead draws one threshold at random from the income range — perhaps $48,000 — and uses that split regardless of whether it's locally optimal. Any one such split is a bit worse, but averaged across hundreds of trees each making different random threshold choices, the ensemble's predictions become less correlated tree-to-tree, which is exactly what reduces the ensemble's overall variance and often lets Extra Trees train noticeably faster than an equivalent random forest.
Further reading
- Geurts, Ernst & Wehenkel, 'Extremely Randomized Trees' (2006)