<p>It is shown <a href="http://www.cs.cmu.edu/%7Eguestrin/Class/10701/slides/learningtheory-bigpicture.pdf" rel="nofollow noreferrer">here</a> (slide 10) that if <span class="math-container">$H_{d,k}$</span> is the number of depth-<span class="math-container">$k$</span> decision trees over <span class="math-container">$d$</span> input bits, then
<span class="math-container">$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$</span>
So <span class="math-container">$v$</span> 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.</p>

CC BY-SA 4.0
2020-10-17T08:23:40.623Z
thx alot, How can i proof this formula ?
Rhasta Shaman
CC BY-SA 4.0
2020-10-17T17:20:45.393Z
Click on the link, the proof is in there.
Aryeh
CC BY-SA 4.0
2020-10-16T12:41:27.863Z
2020-10-16T12:41:27.863Z
Aryeh
<p>What is the VC dimension of all balanced binary decision tree of
depth <span class="math-container">$k$</span> in <span class="math-container">$\{0,1\}^d$</span>? Does it depend on depth <span class="math-container">$k$</span> or dimension <span class="math-container">$d$</span>?</p>

CC BY-SA 4.0
2020-10-17T08:24:56.653Z
@Aryeh thx alot, How can i proof this formula ?
Rhasta Shaman
<machine-learning><vc-dimension>
VC dimension for balanced binary decision trees
Rhasta Shaman
# VC dimension for balanced binary decision trees

(Asked by: username_0 on 2020-10-15)

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$?

**Tags:** machine-learning, vc-dimension
> **Comments:**
> **username_0**: @Aryeh thx alot, How can i proof this formula ?  

---

## 1 answers

### Answer by username_1 on 2020-10-16. Score: 2 | Accepted answer

It is shown [here](http://www.cs.cmu.edu/%7Eguestrin/Class/10701/slides/learningtheory-bigpicture.pdf) (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.

> **Comments:**
> **username_0**: thx alot, How can i proof this formula ?  
> **username_1**: Click on the link, the proof is in there.  

---

