52
$\begingroup$

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 ?
$\endgroup$
  • 2
    $\begingroup$ (a) ERT can sometimes be more biased due to less optimal splits / ERT will sometimes reduce variance because of further decorrelation of trees; (b) I guess the same, not sure; (c) I guess the same, not sure. Extra: I would not call the splitting of RF deterministic due to random variable sampling, and the trees are of course neither due to bootstrapping. $\endgroup$ – Soren Havelund Welling Oct 5 '15 at 19:56
  • $\begingroup$ What is a uniform split? $\endgroup$ – octavian Dec 17 '17 at 15:18
36
+50
$\begingroup$

The Extra-(Randomized)-Trees (ET) article contains a bias-variance analysis. 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 Wehenke. "Extremely randomized trees"

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Any references (either empirical or theory) regarding ET being a bit worse when there is a high number of noisy features? Or is this based on experience? $\endgroup$ – ramhiser Jan 6 '17 at 19:16
  • 1
    $\begingroup$ In my experience the opposite is true: Extra-Trees does better with many noisy features. With the caveat that you have to have a large forest (many estimators, n_estimators in sklearn) and tune the number of features considered at each split (max_features in sklearn) for this to work. A single Extra-Tree will overfit more than a single random forest tree but if you have many Extra-Trees they will tend to overfit in different ways and not overfit. I often get substantial improvement up to 3000 estimators. $\endgroup$ – denson May 10 '18 at 2:35
  • $\begingroup$ As @ramhiser pointed out, ET seem to keep a higher performance in presence of noisy features. Can you add some references to your answer? $\endgroup$ – Gonçalo Peres 龚燿禄 Nov 20 '19 at 9:36
  • $\begingroup$ Is trees in Extra Trees always a 'stump' (just one split)?? Reading other articles give such an impression. $\endgroup$ – Regi Mathew Oct 20 at 3:58
15
$\begingroup$

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

enter image description here

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).

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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. random forest vs extra trees in presence of irrelevant variables

  • 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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ From your linked article: "In blue are presented the results from the random forest and red for the extra trees." $\endgroup$ – tomsv Nov 19 '19 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.