New answers tagged vc-dimension
5
For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to estimate a distribution over $d$ in $\ell_1$ is equivalent to agnostically PAC-learning the concept class $2^{[d]}$).
For discrete distributions with infinite ...
2
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.
Top 50 recent answers are included
