2
$\begingroup$

I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \subset X$ where $|A| \leq d-1$.

$\endgroup$
  • $\begingroup$ What's the formal definition of the VC dimension? If the VC dimension of $H$ is $d$, does it mean that $H$ shatters all subsets of size $d$ or at least one subset of size $d$? $\endgroup$ – nbro Mar 28 at 22:06
  • $\begingroup$ @nbro at least one subset of size $d$ and no subset of size $d+1$ $\endgroup$ – DuttaA Mar 28 at 22:09
  • $\begingroup$ You said that "if a certain hypothesis class $H$ has a VC dimension d over domain $X$". So, it doesn't mean that $X$ is shattered by $H$. Right? In other words, You say $X$‌ as a domain, not as a set that is shattered by $H$. Right? $\endgroup$ – OmG Mar 29 at 0:17
  • $\begingroup$ @OmG yes. Probably should have added $|X| > d$. $\endgroup$ – DuttaA Mar 29 at 0:24
1
$\begingroup$

We can show that it is not true by a counterexample. For example, $X = \{1,2,3\}$ and $\mathcal H = \{\{\},\{1\},\{2\},\{1,2\}\}$ is the finite set hypothesis class. By the definition, $\mathcal V \mathcal C$ dimension of $\mathcal H$ over domain $X$ is $d=2$. Although, $A = \{3\} \subset X$, whose size is smaller than the $\mathcal V \mathcal C$ dimenion i.e $|A|<d=2$ it is not shattered by $\mathcal H$.

| improve this answer | |
$\endgroup$

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.