CODEWITHSUNDEEP
machine-learningtheory
zhshr
zhshr

Reputation: 95

VC Dimension with rectangles with horizontal and vertical edges

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?

Upvotes: 0

Views: 1472

Answers (1)

Raghunath Sarma
Raghunath Sarma

Reputation: 11

We are supposed to draw the rectangle containing +ve examples only for any combination of the given 5 points. Here you see that, for any combination of the given points, a rectangle that corresponds to the points with maximum x-coordinate, minimum x-coordinate, maximum y-coordinate, and minimum y-coordinate will always contain the fifth point also. Hence, the set of 5 points cannot be shattered.

Upvotes: 1

Related Questions