patternMinor
VC Dimension of Origin-Centered Circle
Viewed 0 times
circlecentereddimensionorigin
Problem
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#81733, answer score: 5
Revisions (0)
No revisions yet.