VC dimension of perpendicular lines classifier

Question

I was learning about VC dimension, and I saw an example in the "Introduction to Machine learning" that the VC dimension of a rectangle is 4. I'm just curious about VC-dimension of two perpendicular lines. I try to shatter some points but I'm not sure about it. I think It should be 2,3 or 4. But could find the exact n.

Answer 1

For the VC dimension of a classifier to be at least $n$, we just need to give a single example of a set of points that it can shatter. This is an example of a set of 4 points that the perpendicular lines classifier can shatter:

$$\{ (0,1), (1,0), (0,-1), (-1,0) \}$$

For each possible assignment of labels, I give a pair of perpendicular lines that correctly classifies all points:

• YYYY/NNNN: $y=2$, $x=2$
• YNNN/NYYY: $y=0.5$, $x=2$
• NYNN/YNYY: $y=2$, $x=0.5$
• NNYN/YYNY: $y=-0.5$, $x=2$
• NNNY/YYYN: $y=2$, $x=-0.5$
• YYNN/NNYY: $y=-x$, $y=x-2$
• NYYN/YNNY: $y=x$, $y=x-2$
• YNYN/NYNY: $y=x$, $y=-x$

Thus, its VC dimension must be at least 4.

Answer 2

Your drawing and inavda's answer already show that the VC dimension of your family of classifiers (hypothesis space) is at least $4$.

Showing that the VC dimension is strictly less than $5$ is also pretty straightforward by doing a drawing, but here is a more formal proof : fix $5$ points $\{x_1,x_2,x_3,x_4,x_5\} $ in the Euclidean plane $\mathbb R^2$, and let $C$ be any classifier in your hypothesis space.

By definition of the hypothesis space, there is a partition of $\mathbb R^2$ into four quadrants $A_1,A_2,A_3,A_4\subseteq \mathbb R^2$ (the regions delimited by the two perpendicular lines) such that $C$ assigns the same class to all $x$ belonging in the same quadrant. More formally, for all $1\le i\le 4$ : $$x\in A_i \implies C(x) = \varepsilon_i \tag1$$ Where $\varepsilon_i\in\{-1,+1\}$ is fixed (it depends on $C$ only).

Now we have $5$ points in the plane $x_1,\ldots,x_5$, and the plane is partitioned in $4$ disjoint subsets $A_1,\ldots,A_4$, so (by the pigeonhole principle) there exists an index $i_0 \in [\!|1,4|\!]$ such that $x_i$ and $x_j$ belong in $A_{i_0}$ for some $i,j \in [\!|1,5|\!]$ $i\ne j$ (in other words, one of the quadrant must contain at least two distinct $x_i$'s, very clear with a drawing).

Now simply assign to $x_i$ the class $-1$ and to $x_j$ the class $+1$, and you see from equation $(1)$ that $C$ can't properly classify these two points.
Because $C$ was taken arbitrarily, it follows that no classfier in this hypothesis space can shatter this set of $5$ points, and because the set of points was also arbitrary we conclude that no set of $5$ points can be shattered by this family of classifiers, hence the hypothesis space has VC dimension strictly less than 5.

Conclusion : The VC dimension of the hypothesis space is strictly less than $5$ and at least $4$, so it is equal to $4$.