Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

Question

Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

C.H.

2021年3月28日 12:01

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 $in$ 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?

Topic vc-theory pac-learning machine-learning

Category Data Science

Ben Reiniger · Accepted Answer · 2020年6月30日 13:38

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$.

Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

About