Can decision trees look multiple levels deep when selecting features to maximize information gain?

Question

Suppose we have two features $f_1$ and $f_2$ that, when examined individually, yield very low or zero information gain relative to competing features. But further suppose that if we were to first split on $f_1$, then $f_2$ would yield high information gain. How can we ensure that the decision tree discovers this split that requires looking two levels deep to realize any information gain?

My concern is that I would not expect the tree to split on $f_1$ or $f_2$ given many competing features with higher individual information gain, and therefore it would fail to discover the optimal $f_1-f_2$ combined split (without overfitting by setting its depth and other parameters suboptimally).

When building a regression model based on decision trees (RandomForestRegressor or GradientBoostingRegressor, for example), does one need to explicitly create derived features out of $f_1$ and $f_2$ to ensure that this information is captured?

Answer 1

Depending on which tree algorithm you're using, usually there is a regularization parameter that defines the cost of splitting: a chosen feature is split if the gain in accuracy exceeds the parameter. By playing with this parameter, you can allow for more splits, and therefore exploring more depth (but still keeping depth constrained). Keep in mind that good tree algorithms will also have a pruning step at the end which will again check whether or not to keep certain branches.

As well, most split choices are done in a pseudorandom way because in general it would be prohibitively expensive to test all possible splits. Alternatively a multi-tree model would quite possibly capture the extra splits you mentioned in a handful of trees if indeed they do increase the accuracy enough, given their current structure.

Answer 2

In practice, random forests overcome this problem with randomization.

Regarding a single tree, it is possible that features which are good in combination but not individually do not get selected. In the decision trees literature, there exist non-greedy approaches called lookahead: the best possible combination of features is tried up to a certain level of depth. E.g. in Lookahead-based algorithms for anytime induction of decision trees or in MurTree: Optimal Decision Trees via Dynamic Programming and Search. Other approaches that explicitly use combination of features at each node are the oblique decision trees.

In general, if you have domain knowledge and you know how some features should be combined you might want to add an additional feature to combine $f_1$ and $f_2$. E.g. if you have weight and height you might want to try computing the BMI feature. Then, you can choose whether to keep it or not in the model if it improves accuracy or interpretability. You might also want to try to remove the original features if this simplifies the model.

Answer 3

Trees are grown by a "top down, greedy approach that is know as recursive binary splitting" (An Introduction to Statistical Learning by Tibshirani, Hastie and Friedman).

For each splitting variable, the determination of the split point s can be done very quickly and hence by scanning through all of the inputs, determination of the best pair (variable j, split s) is feasible. Having found the best split, we partition the data into the two resulting regions and repeat the splitting process on each of the two regions. Then this process is repeated on all of the resulting regions. Elements of statistical Learning

So I do think you have to do feature engineering before, all the more if you know ex ante how the interaction of several variables can influence the outcome.

Answer 4

When splitting, tree-based methods do not compute feature interactions. Searching for a split is always done along a single feature at a time. So generating interactions unfortunately has to be done manually.