From what I understand, the VC dimension of an hypothesis class is given by the maximum number of points in general position (or random) on the domain space that can be arbitrarily labeled by the hypothesis class.
From lecture notes and videos I learned that the hypothesis class of sine functions on the real line has infinite VC dimension. However, the proofs that I see so far always seem to use one example of points to show that the sine can arbitrarily label them, namely the set of points given by {$2^{-m} | m \in \mathbb{N}$}. However, an example does not prove that any set of points in general position on the line can be labeled arbitrarily. So I am confused about the actual definition and the proof. From the regularity of the sine, I would expect that there are set of points that cannot be labeled arbitrarily using the sine function.
Questions:
1) Does anyone have a proof for more general set of points?
2) Where is my misunderstanding of the definition of the VC dimension or of the proof (see Example 3 on p.4 in the link)?
Any comments that point me to the right direction of correct my train of thought are welcome. Thanks!
Best Answer
From your linked notes:
Usually, one considers a set of points in "general position" and shows that they can be shattered. This avoids issues like collinear points for a linear classifier.
But it could be the case that the points need to be arranged in some special way, e.g. $\{ 2^{-m} \mid m \in \mathbb N\}$, for the classifier family to shatter them; that's still okay for the VC dimension, which says "there is a set of size $m$ which can be shattered," not "most sets of size $m$ can be shattered" or "this particular set of size $m$ can be shattered."
I don't know for sure that sine functions shatter points in general position, though I'd expect they do. But an example where $\mathcal H$ has infinite VC dimension but cannot shatter "most" sets would be the set of hypotheses on $\mathbb R^n$ defined as, for $w \in \mathbb R$, $$ h_w(\vec x) = \operatorname{sign}(\sin(w x_1)) .$$ Clearly this does not shatter all or most sets on $\mathbb R^n$: it can't even look at most of the dimensions, so $(0, 0)$ and $(0, 1)$ must get the same label from any such $h$. Still, its VC dimension is infinite, because it can shatter any set of the form $\{ (2^{-m}, 0, \dots, 0) \mid m \in \mathbb N \}$.
The Rademacher complexity is one example of a finer-grained notion of complexity that can account for a function class's complexity on a particular set.