To calculate VC dimension of axis-aligned rectangles on 2D, according to what I've learned, we should do the following:

i) Prove that there is at least one particular set $S$ of points of cardinality $d$ which can be classified perfectly by $H$ = {Axis aligned rectangles}.

ii) Prove that none of set of $d+1$ points can be shattered.

I have some doubts with that.

First, it is true that there exists a set of 4 points which can be perfectly classified. Thus, dimVC(H) >= 4.

And now, If I want to prove dimVC(H) = 4, I have to prove that none of set with $5$ points can be classified with axis alined rectangles. But the following sets can be classified perfectly:

a) - - - - -

b) + - - - -

c) + + - - -

d) + + + - -

e) + + + + -

f) + + + + +

Suppose that all those points are at the same line which is parallel to $x$ axis of Euclidean plane i.e. the positions of those points $x_i$ for $i = {1,2,3,4,5}$ is given by $(i,1)$. Then, there exists a set of 5 points which can be classified well, thus VC dimension of our H is $\geq 5$.

What's happening here?



1 Answer 1


You've misunderstood what it means to shatter a set. To have VC dimension $\geq 5$, you need to find a set of $5$ points in the plane such that all $32$ subsets of these points can be obtained by intersecting with axis-aligned rectangles, not just the $6$ sets you found.

Explicitly, given $5$ points $\{x_1,x_2,x_3,x_4,x_5\}$ arranged in order along the $x$ axis, you can't realize the subset $\{x_1,x_3,x_5\}$ ($+ - + - +$, in your notation), so this set is not shattered.

To show that the class of axis-aligned rectangles has VC dimension 4, you need to show that no set of $5$ points is shattered. Hint: Given any finite set of points, $P$, you can pick (possibly with repeats) a point with maximum $x$-coordinate, a point with minimum $x$-coordinate, a point with maximum $y$-coordinate, and a point with minimum $y$-coordinate. These choices give you a subset $M\subseteq P$ of size at most $4$. What can you say about any axis-aligned rectangle which contains all the points in $M$?

  • $\begingroup$ Thanks. But I still have some doubts with the definition of VC dimension. If we consider a set of given 4 points, what happens if I have $$\{x_1,x_2,x_3,x_4\} = +,-,+,-$$ aligned in order over the x axis? This is not realizable, thus VC dimension of rectangle is not $\geq 4$. However, its VC dimensino is 4. $\endgroup$ Sep 10, 2017 at 2:38
  • $\begingroup$ I think I'm little bit confused with the definition VCdim. To prove that the vc dimension of a hypothesis class $H$ is $d$, first, I have to show that there exist a set of $d$ points such that we can shatter all $2^d$ combinations of labeling points. Then, I have to prove that there is NO set of $d+1$ points that can be shattered by using previous hypothesis class. In the case of this example of rectangles, I have two possibilities. With 5 points in Euclidean plane, I can have: i) 5 points aligned ii) 4 points forming a convex hull and another one inside that convex hull. $\endgroup$ Sep 10, 2017 at 2:59
  • $\begingroup$ The first case obviously cannot be shattered (we can simply consider your example). For the second case, if I assign $-$ to the point contained in the convex hull, and positives to the vertices of this convex hull, there is no way to classify this set using our hypothesis. Thus, its VC dimension is less than 5. So, we conclude that Its VC dimension must be 4. Is this argument OK? That is what I understood reading your answer. $\endgroup$ Sep 10, 2017 at 3:02
  • $\begingroup$ Your argument is along the right track, but why does every set of $5$ points fit into cases i) or ii)? For example, what about the vertices of a regular pentagon? Here we have $5$ points forming the convex hull. I'll edit my answer with a hint. $\endgroup$ Sep 10, 2017 at 14:34
  • $\begingroup$ Definitely, I have not considered that case. I will read your hint carefully. Thanks. $\endgroup$ Sep 10, 2017 at 21:10

You must log in to answer this question.

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