Answers.Body: <p>Decision tree for classification is essentially Boolean function approximator which is usually equivalent to a MLP neural network. Thus the usual Gini index, entropy based uncertainty reduction methods to select and order test attributes is akin to optimize MLP parameters based on the same training set. If the size of your training set is relatively small compared to your future test set, they both face the same common overfitting issue. But nonetheless you can always convert to its equivalent MLP form for “optimality”.</p>
  <p>If you stick with decision tree method there’s no rigorous mathematical proof for your hoped &quot;globally optimal&quot; tree if your training set is relatively small or incomplete w.r.t your test set, and usually Gini index metric is more efficient to compute in most cases unless in some highly unbalanced data sets where one of the classification category is relatively unlikely and entropy formula can amplify attributes of such rare category. You may further read this 2004 <a href="https://www.unine.ch/files/live/sites/imi/files/shared/documents/papers/Gini_index_fulltext.pdf" rel="nofollow noreferrer">paper</a> summarizing theoretical optimality comparison between Gini index and Information Gain metrics for decision tree induction with the conclusion:</p>
  <blockquote>
  <p>Based on these characterizations we were able to
  analyze the frequency of agreement/disagreement of the Gini Index function and the Information Gain function. We found that they disagree only in 2% of all cases, which explains why most previously published empirical results concluded that it is not possible to decide which one of the two tests performs better... Based on the gained deeper insights on the split process we are currently working on a system, which will select the optimal criterion based on a user defined optimality criterion. Preliminary results can be found in [20].</p>
  </blockquote>
  <p>And in the mentioned reference therein about their proposed family of split functions the authors also confirmed:</p>
  <blockquote>
  <p>The tests have shown that the two popular functions are very sensitive to the variation of the training set sizes and therefore the quality of the inferred trees is highly dependent on the training set size. At the same time however, we were able to show that the simplest members of the introduced family of split functions behave in a very predictable way and, furthermore, the created trees were superior to the trees inferred using the Gini Index or the Information Gain based on our evaluation criteria.</p>
  </blockquote>
  <p>One common approach in such case is using the idea of cross validating your existing training set, to divide it into multiple equal-sized subsets. Then for each subset to train your tree based on your chosen metric using the remaining sets and calculate some error rate using the said subset as test set. Finally to average all the error rates and you can get some idea of the degree of your “global optimality” for your specific candidate tree. Of course if you have several similarly performed trees which are all more or less uncorrelated, you can always use ensemble idea to do voting such as random forest.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-01T08:48:44.903Z
Answers.LastActivityDate: 2022-12-03T00:48:58.607Z
Answers.LastEditDate: 2022-12-03T00:48:58.607Z
Answers.UserDisplayName: cinch
Body: <p><strong>BACKGROUND:</strong>  When constructing decision trees, the features are selected at various nodes based on whether it optimally splits the samples at that level (i.e., locally) using some user-chosen metric to judge &quot;optimalness&quot; (e.g., Gini index, Information gain, Entropy).  My understanding is that this is what is called a <strong>greedy algorithm</strong>, meaning that it optimizes locally but not necessarily globally.  As a consequence, the algorithm does not guarantee that the final tree is going to be the <em>best</em> tree.  Nonetheless, it would be desirable to derive the best tree or, at the very least, know if we have derived the best tree (even if we have no procedure for deriving the best tree).</p>
  <p><strong>QUESTION:</strong>  How to determine if a decision tree is the (globally) optimal tree?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-03T18:07:54.763Z
Comments.Text: There are statistical learning guarantees for some decision tree learning methods https://link.springer.com/content/pdf/10.1023/A:1013685603443.pdf
Comments.UserDisplayName: Franco Marchesoni
Tags: <optimization><algorithm><decision-trees>
Title: How to determine if a decision tree is the (globally) optimal tree?
UserDisplayName: Snehal Patel
ThreadText: # How to determine if a decision tree is the (globally) optimal tree?
  
  (Asked by: username_0 on 2022-11-29)
  
  **BACKGROUND:** When constructing decision trees, the features are selected at various nodes based on whether it optimally splits the samples at that level (i.e., locally) using some user-chosen metric to judge "optimalness" (e.g., Gini index, Information gain, Entropy). My understanding is that this is what is called a **greedy algorithm**, meaning that it optimizes locally but not necessarily globally. As a consequence, the algorithm does not guarantee that the final tree is going to be the *best* tree. Nonetheless, it would be desirable to derive the best tree or, at the very least, know if we have derived the best tree (even if we have no procedure for deriving the best tree).
  
  **QUESTION:** How to determine if a decision tree is the (globally) optimal tree?
  
  **Tags:** optimization, algorithm, decision-trees
  > **Comments:**
  > **username_1**: There are statistical learning guarantees for some decision tree learning methods https://link.springer.com/content/pdf/10.1023/A:1013685603443.pdf  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-12-01. Score: 1
  
  Decision tree for classification is essentially Boolean function approximator which is usually equivalent to a MLP neural network. Thus the usual Gini index, entropy based uncertainty reduction methods to select and order test attributes is akin to optimize MLP parameters based on the same training set. If the size of your training set is relatively small compared to your future test set, they both face the same common overfitting issue. But nonetheless you can always convert to its equivalent MLP form for “optimality”.
  
  If you stick with decision tree method there’s no rigorous mathematical proof for your hoped "globally optimal" tree if your training set is relatively small or incomplete w.r.t your test set, and usually Gini index metric is more efficient to compute in most cases unless in some highly unbalanced data sets where one of the classification category is relatively unlikely and entropy formula can amplify attributes of such rare category. You may further read this 2004 [paper](https://www.unine.ch/files/live/sites/imi/files/shared/documents/papers/Gini_index_fulltext.pdf) summarizing theoretical optimality comparison between Gini index and Information Gain metrics for decision tree induction with the conclusion:
  
  > Based on these characterizations we were able to
  > analyze the frequency of agreement/disagreement of the Gini Index function and the Information Gain function. We found that they disagree only in 2% of all cases, which explains why most previously published empirical results concluded that it is not possible to decide which one of the two tests performs better... Based on the gained deeper insights on the split process we are currently working on a system, which will select the optimal criterion based on a user defined optimality criterion. Preliminary results can be found in [20].
  
  And in the mentioned reference therein about their proposed family of split functions the authors also confirmed:
  
  > The tests have shown that the two popular functions are very sensitive to the variation of the training set sizes and therefore the quality of the inferred trees is highly dependent on the training set size. At the same time however, we were able to show that the simplest members of the introduced family of split functions behave in a very predictable way and, furthermore, the created trees were superior to the trees inferred using the Gini Index or the Information Gain based on our evaluation criteria.
  
  One common approach in such case is using the idea of cross validating your existing training set, to divide it into multiple equal-sized subsets. Then for each subset to train your tree based on your chosen metric using the remaining sets and calculate some error rate using the said subset as test set. Finally to average all the error rates and you can get some idea of the degree of your “global optimality” for your specific candidate tree. Of course if you have several similarly performed trees which are all more or less uncorrelated, you can always use ensemble idea to do voting such as random forest.
  
  
  ---
  
  