VC Dimension with rectangles with horizontal and vertical edges

3.5k Views Asked by At

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)

Another

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

1

There are 1 best solutions below

2
On BEST ANSWER

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.