14
$\begingroup$

The book "Introduction to Machine learning" by Ethem Alpaydın states that the VC dimension of an axis-aligned rectangle is 4. But how can a rectangle shatter a set of four collinear points with alternate positive and negative points??

Can someone explain and prove the VC dimension of a rectangle?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
25
$\begingroup$

tl;dr: You've got the definition of VC dimension incorrect.

The VC dimension of rectangles is the cardinality of the maximum set of points that can be shattered by a rectangle.

The VC dimension of rectangles is 4 because there exists a set of 4 points that can be shattered by a rectangle and any set of 5 points can not be shattered by a rectangle. So, while it's true that a rectangle cannot shatter a set of four collinear points with alternate positive and negative, the VC-dimension is still 4 because there exists one configuration of 4 points which can be shattered.

Improve this answer
$\endgroup$
0
16
$\begingroup$

The VC dimension of an algorithm is that maximum number of points such that

  • there exists some layout of the points such that

  • for all labelings of those points, the algorithm makes no errors

And indeed, there is a layout of four points (as a diamond) such that a rectangle can divide any set of positive points from the others. That there exists a layout of four points where the rectangle will fail is irrelevant.

Here's a writeup with a diagram.

Improve this answer
$\endgroup$
1
  • $\begingroup$ that's a great answer and the writeup helps a lot, but I'm still curious about the impossibility of 5 points not being able to be shattered? I think there's a layout as well in which you can separate positives from negatives, for instance as star shape where three points are positive and the rest negative or vice-versa. Am I missing something? $\endgroup$
    – Kirk Walla
    Apr 4, 2019 at 9:25
0
$\begingroup$

Consider it like a game between you and an opponent. You choose the location of points and the opponent label them anyway he likes. If he wins by finding a labeling that can not be shattered, then the VC dimension is less than the number of points but if you win the VC dimension is equal or greater than the number of points. In your question, you are not forced to select that arrangement, you can find a better arrangement of points, which let you win.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is all true, but you haven't actually answered the question, which has to do with the VC dimension of an axis-aligned rectangle. Extending your answer to show how it applies to the specific question would be great! $\endgroup$
    – jbowman
    Feb 28, 2018 at 3:32

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.