1
$\begingroup$

Take the 𝐶𝐴𝑅𝑇 binary splitting tree, for example, the practical implementation is a greedy splitting procedure.

With some fixed depth ℎ, one can fit an optimal decision tree (by trying every possible split).

The two different training procedures would hopefully result in different trees.

My question is whether the VC dimension of both trees/models are the same?

From my school memory, the VC dimension is independent of learning algorithm, can we treat greedy and optimal decision tree are only different in learning algorithms?

Improve this question
$\endgroup$
4
  • $\begingroup$ There are many (many many) breeds of optimal; one of them is greedy. Did you have a particular alternative? Did you see this? link? $\endgroup$
    – EngrStudent
    Nov 22, 2020 at 4:06
  • $\begingroup$ so I'm interested in an optimal CART. try out every binary split with different orders. and thanks for the link, I do read those before, and yet, my interest isn't really in the absolute VC dimension, as greedy is different from the optimal, whether if their VC dimension is the same is the thing I'm interested in $\endgroup$
    – yupbank
    Nov 22, 2020 at 4:10
  • $\begingroup$ Optimal isn't singular. There are billions of breeds, possibly infinite families, of optimal. Optimal means you found a balance point between two competing criteria that, according to a mathematical cost formula, was the best that you could find. There are many many potential cost-formulae that you could use. Sparsity, Vastness, any of the thousands of variants of weighted error to some power "p". Energy, Force, Time. CPU heat. Whether the clock has contiguous subsequences that can be found in the first 10k digits of pi. Which optimal do you mean? $\endgroup$
    – EngrStudent
    Nov 23, 2020 at 14:46
  • $\begingroup$ ok, so let me be strict, my goal is to compare greedy and "optimal" CART, their cost function would be the same, e.g. entropy impurity. since greedy CART would fix one binary split at a time, the "optimal" would try out different binary split combinations every time. I'm really trying to control variable here, instead of comparing two completely different model $\endgroup$
    – yupbank
    Nov 23, 2020 at 14:50

1 Answer 1

Reset to default
1
$\begingroup$

As you have already said, the VC dimension does not depend on the algorithm used: the VC dimension simply characterizes the hypothesis class, i.e. the set of classifiers considered by a learning algorithm. Then, if both algorithms consider the same set of trees, the VC dimension must be the same. In your case, if you impose to CART and to your optimal tree learning algorithm that they learn trees with depth at most h, then the set of trees considered are the same, regardless of the algorithm chosen.

There is a distinction to be made for the VC dimension of the individual returned tree. Indeed, each decision tree class (i.e. the set of functions that can be realized using a fixed tree structure letting the internal nodes and the leaf labeling free) has its own VC dimension. If the two algorithms return different trees, then they likely won't have the same VC dimension, and one can expect that the individual VC dimension of the CART tree will be greater than the other, since it is not optimal. This fact can be leverage in practice, but it is not in CART. For more information on this subject, you might be interested in this paper. (Disclaimer: I am one of the author.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.