0
$\begingroup$

I was reading an article about how "it might be possible to improve the common decision trees (e.g. CART) using evolutionary heuristics such as the genetic algorithm"

(https://www.researchgate.net/publication/239807856_evtree_Evolutionary_Learning_of_Globally_Optimal_Classification_and_Regression_Trees_in_R).

"Commonly used classification and regression tree methods like the CART algorithm are recursive partitioning methods that build the model in a forward stepwise search. Although this approach is known to be an efficient heuristic, the results of recursive tree methods are only locally optimal, as splits are chosen to maximize homogeneity at the next step only. "

I understand the basic logic in this argument : A decision tree that uses the genetic algorithm has the advantage of considering a much larger search space than the standard decision tree.

However, I was just wondering why in this article, regular decision trees are repeatedly described as "suboptimal"?

My Question: Does anyone know of any references which theoretically establish the weaknesses of standard decision trees with regards to the fact that they inherently will produce a suboptimal model?

Thanks

$\endgroup$

1 Answer 1

1
$\begingroup$

This is just an obvious consequence of creating splits in the tree based on what improves the fit the most (when you look at the data before the split). E.g. let's say you have 3 categories and thee are mean outcomes for the different combinaton f category levels:

Variables
Variable 1 X X X X Y Y Y Y
Variable 2 A A B B A A B B
Variable 3 1 2 1 2 1 2 1 2
Mean outcome 0 10 10 0 0.1 10.1 10.1 0.1

When you greedily build a try, you'd split by Variable 1 on X vs. Y to create groups separated by 0.1 in their predictions (assuming that's a big enough lift to be meaningful to you/based on the hyperparameters you set). Then you would stop, because you cannot find another split that improves predictions. Obviously, there's ways of building trees that will split in other ways / on other variables that modern tree based algorithms use, and once you've split on either Variable 2 or 3, splitting on the other one will be obvious.

If you create the tree in "holistic" way, you might really want to split on Variable 2 and 3 first (creates groups that are 10 apart in their predictions) and only then on Variable 1 (small additional improvement).

You can think of more sophisticated versions of this, but that's one basic challenge with trees. See also e.g. random forest, where you build lots of trees, each of which may not be all that good, but in combination they are pretty good.

$\endgroup$

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.