10

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?

Brian Spiering
  • 21,136
  • 2
  • 26
  • 109
  • 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. – Emre Jul 25 '17 at 20:38

1 Answers1

4

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

Kaladin
  • 141
  • 2