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?
Thanks
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$?