Data Science Asked by C.H. on October 5, 2021
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 $ninmathbb 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 iin [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?
I agree, the claim as written is incorrect. If $C^*$ is shattered by $mathcal{H}$, and $Csubseteq C^*$, then $C$ is also shattered by $mathcal{H}$; to be possibly over-pedantic:
For each $Bsubseteq C$, because then also $Bsubseteq C^*$, we have that there is an $Hinmathcal{H}$ such that $C^*cap H=B$. Note that this implies $Bsubseteq H$. Now, $Csubseteq C^*$ implies that $Ccap Hsubseteq C^*cap H$, so we have $Ccap Hsubseteq B$. And having both $Bsubseteq C$ and $Bsubseteq H$ implies that $Bsubseteq Ccap H$. So $B=Ccap H$.
Answered by Ben Reiniger on October 5, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP