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 ?
  • 2
    (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. – Soren Havelund Welling Oct 5 '15 at 19:56
  • What is a uniform split? – octavian Dec 17 '17 at 15:18
up vote 14 down vote accepted
+50

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"

  • 2
    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? – ramhiser Jan 6 '17 at 19:16
  • 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. – denson May 10 at 2:35

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

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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