7
$\begingroup$

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.: enter image description here

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?

$\endgroup$
  • $\begingroup$ Because it is possible to find assignments or colorings that can't be partitioned with a circular classifier. For example, let the points at 1 and 7 o'clock belong to the same class. This model is not flexible enough. $\endgroup$ – Emre Jul 25 '17 at 20:38
2
$\begingroup$

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.

https://en.wikipedia.org/wiki/Cyclic_quadrilateral

| improve this answer | |
$\endgroup$

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.