Why isn't my decision tree classifier able to solve the XOR problem properly?

I was trying to solve an XOR problem, and the dataset seems like the one in the image. I plotted the tree and got this result: As I understand, the tree should have depth 2 and four leaves. The first comparison is annoying, because it is close to the right x border (0.887). I've tried other parameterizations, but the same result persists.

I used the code below:

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(criterion='gini')
clf = clf.fit(X, y)

fn=['V1','V2']

fig, axes = plt.subplots(nrows = 1,ncols = 1,figsize = (3,3), dpi=300)

tree.plot_tree(clf, feature_names = fn, class_names=['1', '2'], filled = True);

I would be grateful if anyone can help me to clarify this issue.

I can reproduce this problem for an even more easily separable dataset: The ideal tree for it should be as follows: However, when I run DecisionTreeClassifier with the maximal depth = 2 in scikit-learn many times, it splits the dataset randomly and never gets it right.

This is an example of 4 different runs: The problem is that scikit-learn has only two measures of the quality of a split: gini, and entropy. Both of them estimate mutual information between the target and only one predictor.

However, in XOR problem, mutual information of each predictor with the target is zero. You can read more about it here: link from which you can see that this problem exists not only for XOR but for any task where interaction between features is important.

In order to solve it, the tree should be built based neither on the Gini impurity, nor on the information gain but on measures that estimate how the target depends on multiple features, e.g. multivariate mutual information, distance correlation, etc which might solve simple problems like XOR but might fail in the case of real tasks. It is easy to find simple cases when they fail (just try them for a regression for simple non-linear functions of a few variables). There is no such a measure that would estimate the dependence of a target on multiple interacting predictors very well and would work for all problems.

EDIT to answer Asher's comment: I did several runs for max_depth=3. It is better than for max_depth=2 but still misses the correct classification from time to time. Taking max_depth=4 almost always gets XOR correctly with the occasional misses. Below are pictures of some runs for max_depth=3 and max_depth=4.  However, the trees for max_depth=3 and max_depth=4 become ugly. They are ugly not only because they are bigger than the ideal tree shown above but they totally obscure the XOR function. For example, can you decipher an XOR from this tree? It is probably possible with some pruning technique but still, an extra work.

• Even if gini impurity and entropy are ill-suited for finding the optimal tree of depth 2, the classification should be better if we set a depth greater than 2, right? I'm thinking, for instance, depth 3 or 4. Mar 5 '21 at 12:56
• @Asher You are correct. I edited my answer taking your comment into account. However, increasing the depth is not a 100% guarantee for finding a right solution. It also complicates the tree. Mar 6 '21 at 6:13