1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Use the definition of VC dimension. It tells you all you need to know. $\endgroup$ Oct 6 '21 at 15:15
  • $\begingroup$ 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? $\endgroup$
    – M. Fire
    Oct 6 '21 at 15:26
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.