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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Have you tried proving your intuition? $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 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, 2020 at 18:10
  • $\begingroup$ Also, your point $(x_3,y_3)$ isn't an element of $\mathcal X$. $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 at 18:11
  • 1
    $\begingroup$ Make sure you understand the definition of VC dimension. $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 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, 2020 at 18:18

1 Answer 1

Reset to default
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\}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.