Proof of Calculating VC-Dimensions

Question

I still have some doubts for finding the VC-dimension. Suppose $\mathcal{H}$ has VC-dimension $n$. This is the process of how I think about it: (1) Show that there is a set of $n$ points that can be shattered by $\mathcal{H}$; and (2) No set of $(n+1)$ points is shattered by $\mathcal{H}$. For (2), I just gotta show that for any set of $(n+1)$ points in the $\mathcal{X}$ space I pick, then there would be at least one configuration of labellings by an adversary where none of my classifiers in $\mathcal{H}$ can correctly classify them. For (1), please correct me if I'm wrong somewhere:

1. I choose any set of $n$ points I want in the space.
2. An adversary labels those $n$ points with labels $\mathcal{Y} = \{ 0,1 \}$ it no matter which way he wants.
3. I pick a classifier from $\mathcal{H}$ that correctly labels those points based on the labellings provided by my adversary.
4. If I can find one such classifier from $\mathcal{H}$, then $\mathcal{H}$ can shatter $n$ points and has at least VC-dim of $n$. The next step is to show that it cannot be done with $(n+1)$ points.

So I guess my confusion is in Step 1 here. Do I get to pick any set of points I choose, OR should it be any set of points in the space? The former implies an existence where as long as I can find one (so i.e. I will have to find the best set of points that will work in my favor); while the latter implies universality where I my choice is less flexible.

Here's an example of what I mean. So say we have some hypothesis class $\mathcal{H}$ where $h_t(x) \in \mathcal{H}$. We say that $h_t(x) = 1$ if $x \leq t$ and $x$ lies within a positive even unit-lengthed interval (i.e. $[2,3)$, $[10,11)$, $[100,101)$ are examples of such intervals) and $h_t(x) = 0$ otherwise. Note there that the threshold $t$ is a positive integer and that our domain $\mathcal{X}$ are the real numbers. So say if I want to find its VC-dim, I check first if it can shatter one point. If Step 1 in the above is existential, then I can say that I'll always pick any point that lies within this positive even unit-lengthed interval (because those points can get a chance to be labelled 1 or 0 by the adversary and we can label those accordingly based on the threshold $t$ that we set). All other intervals outside positive even unit-lengthed interval cannot be labelled 1 unfortunately so it doesn't make sense to pick any points within those intervals. However, if we say that Step 1 is a universality, then clearly $\mathcal{H}$ fails to shatter a single point because all points outside the positive even unit-lengthed interval cannot be labelled with 1 by the classifiers whatsoever.

So that's where I'm having doubts with finding the VC-dimension. But in the example, had it been an existence for Step 1, it can shatter one point but not two (just cause I can pick any two points that lie within the positive even unit-lengthed interval and if my adversary labels them with the first point in the left with a 1 and the second point in the right with a 0, then there is no classifier with a threshold $t$ that would be able to classify this correctly). So VC-dim is 1. But if it was a universality for Step 1, then VC-dim is 0.

Any thoughts on this? Thank you!

Answer 1

The VC-dimension of a hypothesis class $\mathcal{H}$ is the maximal size of a set shattered by $\mathcal{H}$, if such a maximal size exists, and $\infty$ otherwise. Therefore to prove that the VC-dimension of $\mathcal{H}$ is $d < \infty$, you need to show that $\mathcal{H}$ shatters some set of size $d$, but no set of size $d+1$.