What does the depth of a decision tree depend on?

Question

In these notes, 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, 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?

Answer 1

As stated in the other answer, 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, 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 2

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 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...