How important is lookahead search in decision trees?

Question

I am using random forests, and, in my data, I have a lot of situations where $X_1$ is a bad predictor, $X_2$ is a bad predictor, but the joint distribution would make a good predictor.

Say that $X1$, $X2$ and $Y$ are binary variables. We have that $P(X_1|Y)=0.5$ and $P(X_2|Y=y)=0.5$ for any $X_1,X_2,Y\in\{0,1\}$, but $P(X_1=1,X_2=1|Y=1)=1$.

Practical example: I want to predict whether text1 is the same as text2. I have added as a feature difference-in-usage-of-!. But, difference-in-usage-of-! can be zero in two very different cases: when neither text has ! or when both use ! in the same numbers. So, I have added another feature: both-texts-use-!.

The problem now is that the decision tree needs to be forward looking because it is only true that the text is the same if difference-in-usage-of-! is very small and both-texts-use-! is 1.

Now, I probably could and should combine these two features into a single, smarter feature (and suggestions are appreciated). But I have a lot of features such as this one, and I wonder whether the decision trees in my random forest, which are learnt using traditional local search are sub-optimal, relative to lookaheads kind of search.

I read in this thesis that,

As empirically investigated in [Murthy and Salzberg, 1995], such an approach (using lookahead search) is however not only more computationally intensive, it is also not significantly better than greedily induced decision trees.

Comment in parenthesis is added by myself. The work being cited is another thesis, and it indeed says that, for instance,

The counter-intuitive result that lookahead search does not improve over greedy search would stand to reason if the latter itself constructs near-optimal trees.

Both of these works are old and, from what I read, do not delve much into it (but I have not read them fully). I wonder if anyone knows if there are features for which only some kind of lookahead search would work, or whether regular the regular local search algorithm is good even for those cases, and whatever thoughts you have about local vs lookahead searches.

Answer 1

There is no common implementation of decision tree with lookahead search, all common implementations use feature-by-feature greedy search.

Using feature-by-feature greedy search, decision tree can learn conditional relationships. For example, a decision tree can learn patterns you describe. The first split would be either 𝑃(𝑋₁|𝑌)=0.5, 𝑃(𝑋₂|𝑌=𝑦)=0.5, then additional splits would define 𝑃(𝑋₁=1,𝑋₂=1|𝑌=1)=1. This similar to the XOR problem that decision trees can learn.