9
$\begingroup$

This paper claims that in CART, because a binary split is performed on a single covariate at each step, all splits are orthogonal and therefore interactions among covariates are not considered.

However, a lot of very serious references claim, on the contrary, that the hierarchical structure of a tree guarantees that interactions between predictors are automatically modeled (e.g., this paper, and of course the Hastie).

Who's right? Do CART-grown trees capture interactions among input variables?

$\endgroup$
  • $\begingroup$ The flaw in the argument is that splits are made on subsets of covariates defined by splits done previously. $\endgroup$ – user88 Apr 21 '15 at 23:50
  • $\begingroup$ @mbq so the new splits are conditional with respect to the preceding splits... I see... I guess I was having trouble understanding that "conditioned by a previous split made on a given predictor" was equivalent to "interacting with this predictor"... $\endgroup$ – Antoine Apr 22 '15 at 7:01
10
$\begingroup$

CART can capture interaction effects. An interaction effect between $X_1$ and $X_2$ occurs when the effect of explanatory variable $X_1$ on response variable $Y$ depends on the level of $X_2$. This happens in the following example:

enter image description here

The effect of poor economic conditions (call this $X_1$) depends on what type of building is being purchased ($X_2$). When investing in an office building, poor economic conditions decrease the predicted value of the investment by 140,000 dollars. But when investing in an apartment building, the predicted value of the investment decreases by 20,000 dollars. The effect of poor economic conditions on the predicted value of your investment depends on the type of property being bought. This is an interaction effect.

$\endgroup$
2
$\begingroup$

Short answer

CARTs need help with capturing interactions.

Long answer

Take the exact greedy algorithm (Chen and Guestrin, 2016):

The exact greedy algorithm

The mean on the leaf will be a conditional expectation, but every split on the way to the leaf is independent of the other. If Feature A does not matter by itself but it matters in interaction with Feature B, the algorithm will not split on Feature A. Without this split, the algorithm cannot foresee the split on Feature B, necessary to generate the interaction.

Trees can pick interactions in the simplest scenarios. If you have a dataset with two features $x_1, x_2$ and target $y = XOR(x_1, x_2)$, the algorithm have nothing to split on but $x_1$ and $x_2$, therefore, you will get four leaves with $XOR$ estimated properly.

With many features, regularization, and the hard limit on the number of splits, the same algorithm can omit interactions.

Workarounds

Explicit interactions as new features

An example from Zhang ("Winning Data Science Competitions", 2015):

Zhang on interactions

Non-greedy tree algorithms

In the other question, Simone suggests lookahead-based algorithms and oblique decision trees.

A different learning approach

Some learning methods handle interactions better.

Here's a table from The Elements of Statistical Learning (line "Ability to extract linear combinations of features"):

Comparison of learning methods

$\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.