1
$\begingroup$

Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC dimension?

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?

Or can I construct the sample points to my liking (to get the maximum VC dim) so that only the positive labels will be on the rim (have some combination of $x_i^2 + y_i^2 = 1$), and have 0 labels to not lie on the rim, therefore have infinite VC dimension?

Improve this question
$\endgroup$
8
  • $\begingroup$ The VC dimension is a feature of a class of functions. If the VC dimension is $d$, then the class of functions has to contain at least $2^d$ different functions. You are describing a class of functions consisting of a single function. Hence its VC dimension is zero. $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 at 7:31
  • $\begingroup$ Sorry I don't quite get why it is zero. If we have $d = 2$, then we can always place the two samples $S = {(x_1,y_1),(x_2,y_2)}$ either on the arc or not on the arc without misclassifying any other sample... Doesn't this show that it contains at least $2^2$ functions, thus VC is at least 2? Could you also elaborate more about "You are describing a class of functions consisting of a single function"? $\endgroup$
    – user120261
    Apr 29, 2020 at 14:33
  • $\begingroup$ In your post you are describing a single function $\mathbb{R}^2 \to \{0,1\}$, which is $1$ on input $(x,y)$ iff $x^2 + y^2 = 1$. As far as I know, this is the only function in your class. If not, you'll have to specify your class of functions explicitly. I can't read your mind! $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 at 14:35
  • $\begingroup$ No, you are correct, this is the only function from $\mathbb{R}^2$ to $\{0,1\}$. So proceeding from here, if I have 2 samples, wouldn't it be possible to place the $1$ label on the arc, the $0$ label outside of the arc, shattering $d=2$? On the contrary, If I have three labels all on the x-axis, then it is impossible to label all 1's (only two can be labeled 1 at (-1,0) and (1,0))? Please advise. Thanks for the time! $\endgroup$
    – user120261
    Apr 29, 2020 at 15:20
  • $\begingroup$ I suspect that you are understanding the question wrong. (You also seem to be misunderstanding the definition of VC dimension.) $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 at 15:33

1 Answer 1

Reset to default
1
$\begingroup$

Let us prove the following general result:

Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\{0,1\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$.

Indeed, if $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \{0,1\}$ we can find a function $f_\phi \in \mathcal{F}$ that agrees with $\phi$ on $S$. Note that if $\phi \neq \psi$ then $f_\phi \neq f_\psi$. Since there are $2^d$ different functions from $S$ to $\{0,1\}$, we conclude that $\mathcal F$ must contain at least $2^d$ functions. $\square$

In particular, the VC dimension of a class of functions containing a single function is zero.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This point is also made on Wikipedia (the very first example). $\endgroup$
    – Yuval Filmus
    Apr 29, 2020 at 15:33

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.