2
$\begingroup$

Is the VC dimension of an origin-centered circle 1 or 2?

It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= r2, r2 will never be able to be labeled 1 without r1 also being labeled 1, so the r1 = 0, r2 = 1 labeling could never be possible.

However, this and this both say that an origin-centered circle has VC dimension of 2.

$\endgroup$
3
$\begingroup$

What you are missing is a definition of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first link) makes it clear that you can choose whether it is the inside or the outside of the circle which gets the value +1, and this shows that any two points whose distance from the origin is not the same can be shattered, and so the VC dimension is at least 2.

$\endgroup$
1
$\begingroup$

Assume that the points on the circle are considered inside. With that if you have 2 points at an equal distance from the origin, you cannot label one + and the other -. Either both are in or both are out. On the contrary for 3 points with varying distance from the origin, you can label them +, -, +. This arrangement cannot be shattered. Hence the VC dimension is 2.

Consider the distance as an attribute and +/- as a label. For the same set of attributes, you cannot have a different label.

$\endgroup$
0
$\begingroup$

Why are you excluding the case where the distance is the same? Take any two points with equal distanced from the origin and they cannot be shatters -> VC is 1

$\endgroup$
  • $\begingroup$ The VC dimension is the maximum number of points that can be arranged such that they are shattered. It is irrelevant that some arrangements of two points cannot be shattered, all that matters is that there is an arrangement that can be shattered. $\endgroup$ – Discrete lizard Feb 5 at 6:51
  • $\begingroup$ With that you can also say that the VC dimension is 3, or 4, or 5.. no? Just put all the points that are closer to the origin than the radius as positives(+) and the others as negatives. $\endgroup$ – user3696468 Feb 5 at 18:18
  • $\begingroup$ No, a circle at the origin cannot shatter 3 or more points. In that case, there is a point that is closer (or equal distance) to the origin than some point and further from the origin than some other point, i.e. there is a point in the "middle". Each origin centered circle that contains the middle point contains a closer point and each circle that does not contain the middle point does not contain a further point. Hence, the middle point cannot be in a different class from both the closer and the further pint. $\endgroup$ – Discrete lizard Feb 5 at 21:37
  • $\begingroup$ I'm still not clear on why you are excluding the case where the 2/3/4 points are at an equal distance from the origin. can you explain that? $\endgroup$ – user3696468 Feb 6 at 20:44
  • $\begingroup$ I am not excluding that case. The argument still works if the points are at equal distance. In fact, an even simpler argument works in that case. I've said quite a bit here, I suggest you have another look at the definition of shattering and VC-dimension and try to work it out on your own. If that doesn't help you, I suggest you ask a question. Be sure to explain in the question what you tried and where you got stuck. $\endgroup$ – Discrete lizard Feb 6 at 21:46

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.