I posted this question in stack overflow but no one answer it so I moved it to math overflow...

I am learning theory of machine learning and have some confusion about VC dimensions. According to the text book, the VC dimension of 2D axis-aligned rectangles is 4 which means it cannot shatter 5 points.

I found an example here: Cornell Sample

However I still cannot understand this example. What if we use a rectangle like this (the red one)


Then we can classify this point out of them. Why is this incorrect?


1 Answer 1


To "shatter" a 5-point set means to produce all 32 possible subsets (by using a rectangle in each case). In this example, you cannot produce a subset that contains just the four black points without containing the red one.

  • $\begingroup$ Do you mean that shatter doesn't mean simply split positive and negative points but have to contain all positive points in that hypothesis? $\endgroup$
    – zhshr
    Commented Feb 8, 2017 at 20:50
  • $\begingroup$ You are given a set $S$ of 5 points. The points do not have signs. $S$ has 32 different subsets. For each subset $T$ of $S$, you have to find an axis-parallel rectangle that contains all the points of $T$ and doesn't contain any point of $S\setminus T$. But this is impossible $\endgroup$ Commented Feb 8, 2017 at 20:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .