0
$\begingroup$

The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 otherwise. We want to find the VC dimension of $\mathcal{F}$

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\{(x_1,y_1),\dots,(x_3,y_3)\}$ that all have the label 1, with radius $r_1 = r_2 = 1$, and $r_3 = 0$, it is impossible to shatter them. Is my intuition correct?

$\endgroup$
6
  • 1
    $\begingroup$ Have you tried proving your intuition? $\endgroup$ – Yuval Filmus Apr 29 '20 at 18:09
  • $\begingroup$ It seems you can actually shatter every set of 3 points, but probably no set of 4 points. $\endgroup$ – Yuval Filmus Apr 29 '20 at 18:10
  • $\begingroup$ Also, your point $(x_3,y_3)$ isn't an element of $\mathcal X$. $\endgroup$ – Yuval Filmus Apr 29 '20 at 18:11
  • 1
    $\begingroup$ Make sure you understand the definition of VC dimension. $\endgroup$ – Yuval Filmus Apr 29 '20 at 18:11
  • $\begingroup$ Yuval, you've been super helpful, if theres any comments or upgrade I can do to help your account, feel free to let me know. Back to the question, Ill have to show that some $d$ can be shattered, but not $d+1$. For $d=2$ its clear from above. If $d=3$, can be shattered, then it must be the case that all three points can be classified correctly -- does it mean all three points dont have to be in a single line? Then I can see why three points can be shattered but not four. If this is the case, why isn't it necessary to place the points on the line? Thanks $\endgroup$ – user120261 Apr 29 '20 at 18:18
0
$\begingroup$

In fact, the VC dimension is 3.

To show this, we need to show that there is a set of 3 points which is shattered, and that no set of 4 points is shattered.

All sets of 3 points behave the same, but for definiteness let us choose three points $x,y,z$ which form the corners of an equilateral triangle. By symmetry, there are only 4 cases to consider:

  • $\emptyset$: choose some arc which avoids all points.
  • $\{x,y,z\}$: choose the complement arc.
  • $\{x\}$: choose a small arc around $x$.
  • $\{y,z\}$: choose the complement arc.

This shows that the VC dimension is at least 3.

To show that the VC dimension is at most 3, let us consider some arbitrary set of points $x,y,z,w$, presented in clockwise order starting at an arbitrary point. An arc that contains both $x$ and $z$ must contain either $y$ or $w$, and in particular there is no arc that contains exactly $\{x,z\}$.

$\endgroup$

Your Answer

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