2
$\begingroup$

If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ will shatter $A \subset X$ where $|A| \leq d-1$?

$\endgroup$
0
2
$\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 definition, in this case, the $\mathcal{VC}$ dimension of $\mathcal H$ over the domain $X$ is $d=2$. Although $A = \{3\} \subset X$, whose size is smaller than the $\mathcal{VC}$ dimension, i.e $|A|<d=2$, it is not shattered by $\mathcal H$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy