Difference between Random Forest and Extremely Randomized Trees

Question

I understood that Random Forest and Extremely Randomized Trees differ in the sense that the splits of the trees in the Random Forest are deterministic whereas they are random in the case of an Extremely Randomized Trees (to be more accurate, the next split is the best split among random uniform splits in the selected variables for the current tree). But I don't fully understand the impact of this different splits in various situations.

• How do they compare in terms of bias/variance ?
• How do they compare in presence of irrelevant variables ?
• How do they compare in presence of correlated variables ?

Answer 1

The Extra-(Randomized)-Trees (ET) article contains a bias-variance analysis. In Fig. 6 (on page 16), you can see a comparison with multiple methods including RF on six tests (tree classification and three regression).

Both methods are about the same, with the ET being a bit worse when there is a high number of noisy features (in high dimensional data-sets).

That said, provided the (perhaps manual) feature selection is near optimal, the performance is about the same, however, ET's can be computationally faster.

From the article itself:

The analysis of the algorithm and the determination of the optimal value of K on several test problem variants have shown that the value is in principle dependent on problem specifics, in particular the proportion of irrelevant attributes. [...] The bias/variance analysis has shown that Extra-Trees work by decreasing variance while at the same time increasing bias. [...] When the randomization is increased above the optimal level, variance decreases slightly while bias increases often significantly.

No silver bullet as always.

---

Pierre Geurts, Damien Ernst, Louis Wehenkel. "Extremely randomized trees"

Answer 2

ExtraTreesClassifier is like a brother of RandomForest but with 2 important differences.

We are building multiple decision trees. For building multiple trees, we need multiple datasets. Best practice is that we don't train the decision trees on the complete dataset but we train only on fraction of data (around 80%) for each tree. In a random forest, we draw observations with replacement. So we can have repetition of observations in a random forest. In an ExtraTreesClassifier, we are drawing observations without replacement, so we will not have repetition of observations like in random forest.

The split is the process of converting a non-homogeneous parent node into 2 homogeneous child node (best possible). In RandomForest, it select the best split to convert the parent into the two most homogeneous child nodes. In an ExtraTreesClassifier, it selects a random split to divide the parent node into two random child nodes.

Let’s look at some ensemble methods ordered from high to low variance, ending in ExtraTreesClassifier.

1. Decision Tree (High Variance)

A single decision tree is usually overfits the data it is learning from because it learn from only one pathway of decisions. Predictions from a single decision tree usually don’t make accurate predictions on new data.

2. Random Forest (Medium Variance)

Random forest models reduce the risk of overfitting by introducing randomness by:

• building multiple trees (n_estimators)
• drawing observations with replacement (i.e., a bootstrapped sample)
• splitting nodes on the best split among a random subset of the features selected at every node. Split is process to convert non-homogeneous parent node into 2 homogeneous child node(best possible).

3. Extra Trees (Low Variance)

Extra Trees is like a Random Forest, in that it builds multiple trees and splits nodes using random subsets of features, but with two key differences: it does not bootstrap observations (meaning it samples without replacement), and nodes are split on random splits, not best splits. So in summary, ExtraTrees:

• builds multiple trees with bootstrap = False by default, which means it samples without replacement
• nodes are split based on random splits among a random subset of the features selected at every node

In Extra Trees, randomness doesn’t come from bootstrapping the data, but rather comes from the random splits of all observations. ExtraTrees is named for (Extremely Randomized Trees).

Answer 3

Thank you very much for the answers ! As I still had questions, I performed some numerical simulations to have more insights about the behavior of these two methods.

• Extra trees seem to keep a higher performance in presence of noisy features.

The picture below shows the performance (evaluated with cross validation) as random columns irrelevant to the target are added to the dataset. The target being just a linear combination of the first three columns.

• When all the variables are relevant, both methods seem to achieve the same performance,

• Extra trees seem three times faster than the random forest (at least, in scikit learn implementation)

Sources

Link to the full article : random forest vs extra trees.

Answer 4

The answer is that it depends. I suggest you try both random forest and extra trees on your problem. Try large forest (1000 - 3000 trees/estimators, n_estimators in sklearn) and tune the number of features considered at each split (max_features in sklearn) as well as the the minimum samples per split (min_samples_split in sklearn) and the maximum tree depth (max_depth in sklearn). That said, you should keep in mind that over tuning can be a form of overfitting.

Here are two problems I worked on personally where extra trees proved useful with very noisy data:

Decision forests for machine learning classification of large, noisy seafloor feature sets

An efficient distributed protein disorder prediction with pasted samples