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? 
 A: 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.  
A: 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.
A: 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. 
