# Do more features inevitably lead to better performance in tree-based models?

Assuming that n is large, can the inclusion of a feature cause model performance to ever decrease? Or is the inclusion of a useless feature ignored by the classifier and thus including more features either does not change performance or increases it?

• Counterintuitively, this can happen. When I get more time I'll hunt up an example using C4.5. – zbicyclist Sep 13 '17 at 22:57

Random forest does random selection of a subset of features for each tree.

From wikipedia (Random subspace method):

(...) feature bagging, is an ensemble learning method that attempts to reduce the correlation between estimators in an ensemble by training them on random samples of features instead of the entire feature set.

The idea is to enforce that weak classifiers that get combined forming an ensemble should be different, because if they're too similar combining them wouldn't improve accuracy.

Theoretically you're right, increasing the potential number of factors can't decrease accuracy if the decision tree is optimal for the given set of factors. For proof, the set of all accuracies for all possible trees created on a set of $n$ factors is a subset of the set of all accuracies for all possible trees created on a set of $n+m$ factors. Therefore as you suggest, in the worst case including a useless feature (or even a useful one) can just be ignored by the classifier and at a minimum the performance is equal.

However practically in the real world determining the optimal tree (based on say achieving a minimum Gini) is an NP-hard problem, and real world algorithms which exist and are the ones usually used in practice because they have faster run times (such as those recursive based algorithms) don't strictly produce the optimal tree for a given set of factors.

They instead usually implement some sort of greedy algorithm where they split at each node by the maximum change in Gini at that one split, which almost surely doesn't lead to an optimal tree. Understanding this it's easy to see why adding factors arbitrarily in some circumstances and in practice (not in theory) can decrease performance, there could be cases where there is a forced split at a higher node which isn't part of an optimal tree but does reduce Gini the most at that step.