VC dimension of a rectangle

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?

Answer

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.

Attribution
Source : Link , Question Author : kaz , Answer Author : neutralino

Leave a Comment