# Proof of Calculating VC-Dimensions

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!

• Use the definition of VC dimension. It tells you all you need to know. Oct 6, 2021 at 15:15
• Ok, so I'm thinking that it might be existence? All I gotta do in this particular example is choose points within those positive even unit-lengthed intervals so that I can get two possible labellings, a 1 or 0. If I pick a point $x_0$ lying within these intervals and the adversary labels it with 1, then all I gotta do is pick a classifier in my $\mathcal{H}$ that has threshold $t > x_0$ (thus labelling it correctly). If the adversary labels it with 0, then I pick a classifier with a threshold $t < x_0$ (thus again labelling correctly). So this should mean that the VC-dim is 1, correct? Oct 6, 2021 at 15:26

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