Answers.Body: <p>The algorithm fails because it is greedy. This means that it takes the first split decision immediately, without taking into account what will happen in next steps.</p>
  <p>An alternative would be given by the Viterbi algorithm, that would select the best sequence of splits by backtracking over the best final cumulated information gain.</p>
  <p>In the example given, two different split sequences would achieve maximum separation: first split along <span class="math-container">$V_1$</span> or first split along <span class="math-container">$V_2$</span>.</p>
  <p>For other configurations of the data points, the order may be relevant, so all alternatives should be evaluated.</p>
  <p>Some resources about non-greedy algorithms for decision trees follow.</p>
  <p><a href="https://proceedings.neurips.cc/paper/2015/file/1579779b98ce9edb98dd85606f2c119d-Paper.pdf" rel="nofollow noreferrer">https://proceedings.neurips.cc/paper/2015/file/1579779b98ce9edb98dd85606f2c119d-Paper.pdf</a></p>
  <p><a href="https://medium.com/mlearning-ai/optimal-decision-trees-dbd16dfca427" rel="nofollow noreferrer">https://medium.com/mlearning-ai/optimal-decision-trees-dbd16dfca427</a></p>
  <p><a href="https://faculty.ucmerced.edu/mcarreira-perpinan/papers/ijcnn21a-slides.pdf" rel="nofollow noreferrer">https://faculty.ucmerced.edu/mcarreira-perpinan/papers/ijcnn21a-slides.pdf</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-19T10:52:47.577Z
Answers.LastActivityDate: 2023-01-20T17:14:08.037Z
Answers.LastEditDate: 2023-01-20T17:14:08.037Z
Answers.UserDisplayName: Jaume Oliver Lafont
Answers.Body: <p>I can reproduce this problem for an even more easily separable dataset:</p>
  <p><a href="https://i.sstatic.net/U963rm.png" rel="noreferrer"><img src="https://i.sstatic.net/U963rm.png" alt="enter image description here" /></a></p>
  <p>The ideal tree for it should be as follows:</p>
  <p><a href="https://i.sstatic.net/KG0vTm.png" rel="noreferrer"><img src="https://i.sstatic.net/KG0vTm.png" alt="enter image description here" /></a></p>
  <p>However, when I run <code>DecisionTreeClassifier</code> with the maximal depth = 2 in scikit-learn many times, it splits the dataset randomly and never gets it right.</p>
  <p>This is an example of 4 different runs:</p>
  <p><a href="https://i.sstatic.net/ANA1C.png" rel="noreferrer"><img src="https://i.sstatic.net/ANA1C.png" alt="enter image description here" /></a></p>
  <p>The problem is that scikit-learn has only two measures of the quality of a split: <code>gini</code>, and <code>entropy</code>. Both of them estimate mutual information between the target and <strong>only one</strong> predictor.</p>
  <p>However, in XOR problem, mutual information of each predictor with the target is zero. You can read more about it here: <a href="https://stats.stackexchange.com/questions/277710/how-to-be-absolutely-sure-that-features-do-have-predictive-power-to-predict-the">link</a> from which you can see that this problem exists not only for XOR but for any task where interaction between features is important.</p>
  <p>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. <a href="https://en.wikipedia.org/wiki/Multivariate_mutual_information" rel="noreferrer">multivariate mutual information</a>,  <a href="https://en.wikipedia.org/wiki/Distance_correlation" rel="noreferrer">distance correlation</a>, 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.</p>
  <p>EDIT to answer Asher's comment: I did several runs for <code>max_depth=3</code>. It is better than for <code>max_depth=2</code> but still misses the correct classification from time to time. Taking <code>max_depth=4</code> almost always gets XOR correctly with the occasional misses. Below are pictures of some runs for <code>max_depth=3</code> and <code>max_depth=4</code>.</p>
  <p><a href="https://i.sstatic.net/ZUHRU.png" rel="noreferrer"><img src="https://i.sstatic.net/ZUHRU.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.sstatic.net/gJGnh.png" rel="noreferrer"><img src="https://i.sstatic.net/gJGnh.png" alt="enter image description here" /></a></p>
  <p>However, the trees for <code>max_depth=3</code> and <code>max_depth=4</code> 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?</p>
  <p><a href="https://i.sstatic.net/OdgTa.png" rel="noreferrer"><img src="https://i.sstatic.net/OdgTa.png" alt="enter image description here" /></a></p>
  <p>It is probably possible with some pruning technique but still, an extra work.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-05T12:56:09.177Z
Answers.Text: 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.
Answers.UserDisplayName: Asher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-06T06:13:37.557Z
Answers.Text: @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.
Answers.UserDisplayName: Vladislav Gladkikh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-19T11:00:38.047Z
Answers.Text: I don't think the problem is in the impurity measure as much as in the greediness of the standard algorithm.
Answers.UserDisplayName: Jaume Oliver Lafont
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-20T12:56:14.643Z
Answers.Text: @JaumeOliverLafont Do you know any non-greedy decision tree algorithms? I would like to read about them.
Answers.UserDisplayName: Vladislav Gladkikh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-20T17:14:53.677Z
Answers.Text: @VladislavGladkikh Not yet, but I did a quick search and added a selection of links to my answer. I'll study with you :)
Answers.UserDisplayName: Jaume Oliver Lafont
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-05T04:34:30.630Z
Answers.LastActivityDate: 2021-03-06T06:10:18.033Z
Answers.LastEditDate: 2021-03-06T06:10:18.033Z
Answers.UserDisplayName: Vladislav Gladkikh
Body: <p>I was trying to solve an XOR problem, and the dataset seems like the one in the image.</p>
  
  <p><a href="https://i.sstatic.net/qVEHH.png" rel="noreferrer"><img src="https://i.sstatic.net/qVEHH.png" alt="dataset"></a></p>
  
  <p>I plotted the tree and got this result:</p>
  
  <p><a href="https://i.sstatic.net/iFopL.png" rel="noreferrer"><img src="https://i.sstatic.net/iFopL.png" alt="enter image description here"></a></p>
  
  <p>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.</p>
  
  <p>I used the code below:</p>
  
  <pre><code>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);
  </code></pre>
  
  <p>I would be grateful if anyone can help me to clarify this issue. </p>
  
Tags: <machine-learning><python><decision-trees><scikit-learn>
Title: Why isn't my decision tree classifier able to solve the XOR problem properly?
UserDisplayName: Pedro Paiva
ThreadText: # Why isn't my decision tree classifier able to solve the XOR problem properly?
  
  (Asked by: username_0 on 2020-06-12)
  
  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.
  
  **Tags:** machine-learning, python, decision-trees, scikit-learn
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-03-05. Score: 5 | Accepted answer
  
  I can reproduce this problem for an even more easily separable dataset:
  
  [![enter image description here](https://i.sstatic.net/U963rm.png)](https://i.sstatic.net/U963rm.png)
  
  The ideal tree for it should be as follows:
  
  [![enter image description here](https://i.sstatic.net/KG0vTm.png)](https://i.sstatic.net/KG0vTm.png)
  
  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:
  
  [![enter image description here](https://i.sstatic.net/ANA1C.png)](https://i.sstatic.net/ANA1C.png)
  
  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](https://stats.stackexchange.com/questions/277710/how-to-be-absolutely-sure-that-features-do-have-predictive-power-to-predict-the) 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](https://en.wikipedia.org/wiki/Multivariate_mutual_information), [distance correlation](https://en.wikipedia.org/wiki/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`.
  
  [![enter image description here](https://i.sstatic.net/ZUHRU.png)](https://i.sstatic.net/ZUHRU.png)
  
  [![enter image description here](https://i.sstatic.net/gJGnh.png)](https://i.sstatic.net/gJGnh.png)
  
  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?
  
  [![enter image description here](https://i.sstatic.net/OdgTa.png)](https://i.sstatic.net/OdgTa.png)
  
  It is probably possible with some pruning technique but still, an extra work.
  
  > **Comments:**
  > **username_3**: 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.  
  > **username_2**: @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.  
  > **username_1**: I don't think the problem is in the impurity measure as much as in the greediness of the standard algorithm.  
  > **username_2**: @JaumeOliverLafont Do you know any non-greedy decision tree algorithms? I would like to read about them.  
  > **username_1**: @VladislavGladkikh Not yet, but I did a quick search and added a selection of links to my answer. I'll study with you :)  
  
  ---
  
  ### Answer by username_1 on 2023-01-19. Score: 2
  
  The algorithm fails because it is greedy. This means that it takes the first split decision immediately, without taking into account what will happen in next steps.
  
  An alternative would be given by the Viterbi algorithm, that would select the best sequence of splits by backtracking over the best final cumulated information gain.
  
  In the example given, two different split sequences would achieve maximum separation: first split along $V\_1$ or first split along $V\_2$.
  
  For other configurations of the data points, the order may be relevant, so all alternatives should be evaluated.
  
  Some resources about non-greedy algorithms for decision trees follow.
  
  <https://proceedings.neurips.cc/paper/2015/file/1579779b98ce9edb98dd85606f2c119d-Paper.pdf>
  
  <https://medium.com/mlearning-ai/optimal-decision-trees-dbd16dfca427>
  
  <https://faculty.ucmerced.edu/mcarreira-perpinan/papers/ijcnn21a-slides.pdf>
  
  
  ---
  
  