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$
1
  • $\begingroup$ @Aryeh thx alot, How can i proof this formula ? $\endgroup$ Oct 17 '20 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.

$\endgroup$
2
  • $\begingroup$ thx alot, How can i proof this formula ? $\endgroup$ Oct 17 '20 at 8:23
  • 1
    $\begingroup$ Click on the link, the proof is in there. $\endgroup$
    – Aryeh
    Oct 17 '20 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.