2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Welcome to Cross Validated. Before starting to post, it's strongly advised to take the site 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. Do you have that clear in mind? $\endgroup$
    – DeltaIV
    Commented Mar 4, 2017 at 17:21
  • $\begingroup$ I agree with DeltaIV. This question requires the self-study tag. $\endgroup$
    – Michael R. Chernick
    Commented Mar 4, 2017 at 20:14
  • $\begingroup$ @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. $\endgroup$
    – Shaohua Huang
    Commented Mar 5, 2017 at 13:35
  • 2
    $\begingroup$ have you read the question linked by @Sycorax? $\endgroup$
    – DeltaIV
    Commented Mar 5, 2017 at 13:36
  • $\begingroup$ @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. $\endgroup$
    – Shaohua Huang
    Commented Mar 6, 2017 at 1:12

0

Reset to default