0
$\begingroup$

What is the VC dimension of all balanced binary decision tree of depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?

$\endgroup$
  • $\begingroup$ @Aryeh thx alot, How can i proof this formula ? $\endgroup$ – Rhasta Shaman Oct 17 at 8:24
2
$\begingroup$

It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then $$v:=\log_2(H_{d,k})= (2^k-1)(1+\log_2(d))+1 . $$ So $v$ is an upper bound on the VC-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thx alot, How can i proof this formula ? $\endgroup$ – Rhasta Shaman Oct 17 at 8:23
  • 1
    $\begingroup$ Click on the link, the proof is in there. $\endgroup$ – Aryeh Oct 17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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