2

I encounter such an exercise question as below and have no clue so far.

Consider using decision trees/forests to implement Boolean functions, i.e. classifiers from {0,1}n to{0,1}.

1) Give a good upper bound for the VC-dimension of decision trees with l leaves.

2) What is a good upper bound for the VC-dimension of a random forest (thresholded linear combination of decision trees) with k trees where each tree has l leaves?

For question 1), I understand the VC-dimension of a decision tree with l Leaves is at least l, but I cannot come up with the upper bound.

Shaohua Huang
  • 129
  • 3
  • 1
    Welcome to Cross Validated. Before starting to post, it's strongly advised to take the site [tour](http://stats.stackexchange.com/tour). In particular, you should add the `self-study` tag to questions such as yours, related to self-study, and describe what you have attempted so far in order to solve the exercise. We can then give you hints on how to proceed, but we cannot do your homework for you. In this specific case, I would start from the definition of [Vapnik–Chervonenkis dimension](https://en.wikipedia.org/wiki/VC_dimension). Do you have that clear in mind? – DeltaIV Mar 04 '17 at 17:21
  • I agree with DeltaIV. This question requires the self-study tag. – Michael R. Chernick Mar 04 '17 at 20:14
  • @DeltaIV I understand what VC-dimension means. But when it is put into this context, I could not figure out what is the value of the VC-dimension. – Shaohua Huang Mar 05 '17 at 13:35
  • 2
    have you read the question linked by @Sycorax? – DeltaIV Mar 05 '17 at 13:36
  • @DeltaIV I just go through the question linked by Sycorax, I don't think it answers my question. I know that it is not easy to find out the exact VC dimension of a decision tree, therefore here I am asking about whether we can have a good upper bound. – Shaohua Huang Mar 06 '17 at 01:12
  • would it be O(m^l) ? using saur's lemma – mannuscript Mar 08 '17 at 07:23

0 Answers0