1
$\begingroup$

Today in the lecture the lecturer said something I found peculiar, and I felt very inconvenient when I heard it: He claimed, that if the maximal VCdim of some hypothesis class is $n\in\mathbb N$, then it is possible that there is some $i<n$ such that for every subset C of size i the subset C is not shattered. Is his claim true? I thought that we can take some subset of size $i,\forall i\in [n]$of the set C* which satisfies the condition for the case where $|C|=n$, and they will shatter as well. Am I missing something?

$\endgroup$

1 Answer 1

1
$\begingroup$

I agree, the claim as written is incorrect. If $C^*$ is shattered by $\mathcal{H}$, and $C\subseteq C^*$, then $C$ is also shattered by $\mathcal{H}$; to be possibly over-pedantic:

For each $B\subseteq C$, because then also $B\subseteq C^*$, we have that there is an $H\in\mathcal{H}$ such that $C^*\cap H=B$. Note that this implies $B\subseteq H$. Now, $C\subseteq C^*$ implies that $C\cap H\subseteq C^*\cap H$, so we have $C\cap H\subseteq B$. And having both $B\subseteq C$ and $B\subseteq H$ implies that $B\subseteq C\cap H$. So $B=C\cap H$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.