Do CART trees capture interactions among predictors?

Question

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 book by Hastie Elements of Statistical Learning).

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

References:

Paper 1: Lee, Sun-Mi, and Patricia A. Abbott. "Bayesian networks for knowledge discovery in large datasets: basics for nurse researchers." Journal of biomedical informatics 36.4-5 (2003): 389-399.

Paper 2: Elith, Jane, John R. Leathwick, and Trevor Hastie. "A working guide to boosted regression trees." Journal of Animal Ecology 77.4 (2008): 802-813.

Answer 1

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:

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.

Answer 2

Short answer

CARTs need help with capturing interactions.

Long answer

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

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):

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"):