Answers.Body: <p>As stated in <a href="https://ai.stackexchange.com/a/25176/2444">the other answer</a>, in general, the depth of the decision tree depends on the decision tree algorithm, i.e. the algorithm that builds the decision tree (for regression or classification).</p>
  <p>To address your notes more directly and why that statement may not be always true, let's take a look at <a href="https://en.wikipedia.org/wiki/ID3_algorithm" rel="nofollow noreferrer">the ID3 algorithm</a>, for instance. Here's the initial part of its pseudocode.</p>
  <pre><code>ID3 (Examples, Target_Attribute, Attributes)
      Create a root node for the tree
      If all examples are positive, Return the single-node tree Root, with label = +.
  ...
  </code></pre>
  <p>So, in general, the depth of the tree may not depend on the number of features, but it may just depend on the labels or training examples (which is a degenerate case), although, in most cases, it will also depend on the number of features, because each node represents a split of the training examples based on some condition that needs to be true for some feature (e.g. the height of the people must be less than 150cm).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-14T21:55:32.183Z
Answers.LastActivityDate: 2020-12-14T21:55:32.183Z
Answers.UserDisplayName: nbro
Answers.Body: <p>While this sounds obvious, the depth of the tree depends on how your algorithm builds the tree. For a fixed dataset <span class="math-container">$\mathcal{D}$</span>, there're many algorithms, such as ID3, C4.5, CART, etc. (and their variants) to build your tree. For the most part, these algorithms recursively partition the dataset, so it's never possible to get a tree larger than <span class="math-container">$|\mathcal{D}|$</span>. Large/deep trees are also prone to overfitting and are computationally expensive, so these algorithms typically prune the tree so it's much smaller than <span class="math-container">$|\mathcal{D}|$</span>.</p>
  <p>In fact,
  <a href="https://www.cis.upenn.edu/%7Emkearns/papers/topdown.pdf" rel="nofollow noreferrer">Kearns and Mansour showed</a> that under the weak learning assumption (i.e. at each node, there's a split that classifies the data at this node better than a random classifier, by <span class="math-container">$\gamma$</span>) to achieve <span class="math-container">$\epsilon$</span> training error, it suffices to make <span class="math-container">$(1/\epsilon)^{\mathcal{O}(\log(1/\epsilon)/\gamma^2)}$</span> splits (and thus depth is upper bounded by this).</p>
  <p>But of course, you can always cook up trees of arbitrary depth...</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-15T10:42:27.120Z
Answers.Text: @Sara Imagine the tree was deeper than the amount of of examples. Then, when you assign all examples to the leaves of the tree, there will be some leaves that are empty. The parent of these leaves makes a distinction that doesn't improve the accuracy on the training set (if you removed that distinction, you would get the same result), so while there could be an algorithm that creates such a tree, it would have to be based on assumptions about unseen data.
Answers.UserDisplayName: kutschkem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-13T22:02:24.597Z
Answers.LastActivityDate: 2020-12-13T22:02:24.597Z
Answers.UserDisplayName: kaiwenw
Body: <p>In <a href="https://www.cs.cmu.edu/%7Eaarti/Class/10701/exams/midterm2010f_sol.pdf#page=3" rel="nofollow noreferrer">these notes</a>, we have the following statement</p>
  <blockquote>
  <p>The depth of a learned decision tree can be larger than the number of training examples used to create the tree</p>
  </blockquote>
  <p>This statement is false, according to the same <a href="https://www.cs.cmu.edu/%7Eaarti/Class/10701/exams/midterm2010f_sol.pdf#page=3" rel="nofollow noreferrer">notes</a>, where it is written</p>
  <blockquote>
  <p><strong>False</strong>: Each split of the tree must correspond to at least one training example, therefore, if there are <span class="math-container">$n$</span> training examples, a path in the tree can have length at most <span class="math-container">$n$</span></p>
  <p><strong>Note</strong>: There is a pathological situation in which the depth of a learned decision tree can be larger than number of training examples <span class="math-container">$n$</span> - if the number of features is larger than <span class="math-container">$n$</span> and there exist training examples which have same feature values but different labels.</p>
  </blockquote>
  <p>I had written on my notes that the depth of a decision tree only depends on the number of features of the training set and not on the number of training samples. So, what does the depth of the decision tree depend on?</p>
  
Tags: <machine-learning><classification><decision-trees><features>
Title: What does the depth of a decision tree depend on?
UserDisplayName: S. Christin
ThreadText: # What does the depth of a decision tree depend on?
  
  (Asked by: username_0 on 2020-12-13)
  
  In [these notes](https://www.cs.cmu.edu/%7Eaarti/Class/10701/exams/midterm2010f_sol.pdf#page=3), we have the following statement
  
  > The depth of a learned decision tree can be larger than the number of training examples used to create the tree
  
  This statement is false, according to the same [notes](https://www.cs.cmu.edu/%7Eaarti/Class/10701/exams/midterm2010f_sol.pdf#page=3), where it is written
  
  > **False**: Each split of the tree must correspond to at least one training example, therefore, if there are $n$ training examples, a path in the tree can have length at most $n$
  >
  > **Note**: There is a pathological situation in which the depth of a learned decision tree can be larger than number of training examples $n$ - if the number of features is larger than $n$ and there exist training examples which have same feature values but different labels.
  
  I had written on my notes that the depth of a decision tree only depends on the number of features of the training set and not on the number of training samples. So, what does the depth of the decision tree depend on?
  
  **Tags:** machine-learning, classification, decision-trees, features
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-12-14. Score: 0 | Accepted answer
  
  As stated in [the other answer](https://ai.stackexchange.com/a/25176/2444), in general, the depth of the decision tree depends on the decision tree algorithm, i.e. the algorithm that builds the decision tree (for regression or classification).
  
  To address your notes more directly and why that statement may not be always true, let's take a look at [the ID3 algorithm](https://en.wikipedia.org/wiki/ID3_algorithm), for instance. Here's the initial part of its pseudocode.
  
  ```
  ID3 (Examples, Target_Attribute, Attributes)
      Create a root node for the tree
      If all examples are positive, Return the single-node tree Root, with label = +.
  ...
  
  ```
  
  So, in general, the depth of the tree may not depend on the number of features, but it may just depend on the labels or training examples (which is a degenerate case), although, in most cases, it will also depend on the number of features, because each node represents a split of the training examples based on some condition that needs to be true for some feature (e.g. the height of the people must be less than 150cm).
  
  
  ---
  
  ### Answer by username_2 on 2020-12-13. Score: 0
  
  While this sounds obvious, the depth of the tree depends on how your algorithm builds the tree. For a fixed dataset $\mathcal{D}$, there're many algorithms, such as ID3, C4.5, CART, etc. (and their variants) to build your tree. For the most part, these algorithms recursively partition the dataset, so it's never possible to get a tree larger than $|\mathcal{D}|$. Large/deep trees are also prone to overfitting and are computationally expensive, so these algorithms typically prune the tree so it's much smaller than $|\mathcal{D}|$.
  
  In fact,
  [Kearns and Mansour showed](https://www.cis.upenn.edu/%7Emkearns/papers/topdown.pdf) that under the weak learning assumption (i.e. at each node, there's a split that classifies the data at this node better than a random classifier, by $\gamma$) to achieve $\epsilon$ training error, it suffices to make $(1/\epsilon)^{\mathcal{O}(\log(1/\epsilon)/\gamma^2)}$ splits (and thus depth is upper bounded by this).
  
  But of course, you can always cook up trees of arbitrary depth...
  
  > **Comments:**
  > **username_3**: @Sara Imagine the tree was deeper than the amount of of examples. Then, when you assign all examples to the leaves of the tree, there will be some leaves that are empty. The parent of these leaves makes a distinction that doesn't improve the accuracy on the training set (if you removed that distinction, you would get the same result), so while there could be an algorithm that creates such a tree, it would have to be based on assumptions about unseen data.  
  
  ---
  
  