I know that the VC dimension for this problem is 3. My concern is about the growth function. The following bound is obtained using the VC dimension: $$m_{\mathcal{H}}(n)\le \sum_{k=0}^3\,{n\choose k}$$ When I simulate this hypothesis set up to $n= 10$, the maximum number of dichotomies I obtain is exactly $\sum_{k=0}^{3}\,{n\choose k}$. Is it by coincidence or is there a way to prove this?
3
-
$\begingroup$ Your question might be more suitable for math.stackexchange.com $\endgroup$– JonathanMar 4, 2020 at 7:39
-
$\begingroup$ Unfortunately your question is not clear! You have inequality and reach the maximum which satisfies it. You can count all possible dichotomies as well. What do you wanna prove here? $\endgroup$– OmGApr 13, 2020 at 13:07
-
$\begingroup$ I reach the maximum for n up to 10, since I can count all possible dichotomies for n up to 10 (I cannot go beyond with my computer). I am asking help for a mathematical proof for all n>0. $\endgroup$– Ali KaraApr 15, 2020 at 10:56
Add a comment
|