Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
When using VC-dimensions to estimate the capability of a binary classifier, you can find 3 points in R2 that can be shattered, e.g.:
But you can not shatter any 4 points with a circle.
This is stated in these lecture notes. Can anyone give me an intuitive explanation?
Given $4$ points $A,B,C,D$. If they do not lie on the boundary of a convex hull, then it is impossible to shatter the inner point from the boundary.
So assume they lie on the boundary of the hull. So they form a convex quadrilateral. Meaning $\angle A+\angle B +\angle C +\angle D =360^\circ$ Then we can assume w.l.o.g. $\angle A +\angle C \leq 180^\circ$, where $A$ and $C$ are opposite points.
Now the claim is that you cannot have a circle containing $A,C$, but not $B,D$.
Assume that you have such a circle, that contains $A,C$ but not $B,D$. Then we can make the circle smaller if necessary such that $A,C$ lie on the boundary, but $B,D$ is still not contained in the circle.
But now since the the points lie outside the circle $\angle B +\angle D < 180^\circ$. But this is a contradiction thus such a circle does not exist.
This last part has to do with the fact that for a circular quadrilateral opposite angels sum up to $180^\circ$ together with the fact that an angle of a point outside a circle is smaller that on the circle.
