VC dimension of half spaces over the real line

Question

I'm studying VC dimension and I'm having a little difficulty understanding it. I read lots of explanations, but when I come across this simple exercise I did not get a good intuition. The problem is this:

Find the VC dimension for the following case,

$h (x) = \mathbb{1}_{{a < x}}$, with parameter $a, X \in R$.

The resolution is as follows:

VC-dimension = 1.

(a) It can shatter point $0$, by choosing a to be $2$ and $-2$.

(b) It can not shatter any two points ${x1, x2}, x1 < x2$, because the labeling $x1 = 1$ and $x2=0$ can not be realized.

My doubts are:

1) In item (a) what is parameter $a$? I looked for similar exercises, but there was no concrete explanation about this parameter, what is its function? In this item it takes as equals $2$ and $-2$, with $-2 < 0$ ok, but $2 < 0$, I did not understand, from this conclusion, why it is correct.

2) In item (b) I did not understand the inequality, as he came to the conclusion that $x1 < x2$ can not be realized, why is the inequality $x1 > x2$ not valid?

Answer 1

First you need to understand how to calculate the VC-dimension. There are two conditions for the VC-dimension to be $n$ (here $n=1$):

1. You need to find one set of $n$ points that can be shattered (i.e. classify all possible $|\{0,1\}|^n=2^n$ labelings correctly) and
2. It must be impossible to find any set of $n+1$ points that can be shattered.

Now to your questions:

1) $a$ defines the family of possible decision functions in your classification problem. In your case, $a$ defines all possible half spaces along the real axis. That means all points greater than $a$ a classified as $1$ and all points less than $a$ are classified as $0$.

First they show that one point can be shattered. And they choose that point to be $x=0$. They could choose another point but it is enough to show it for $x=0$.

To shatter $x=0$ you need to find an $a$ so that $h(0)=0$ and an $a$ such that $h(0)=1$. (Those are the $2^1=2$ possible labels.)

If the label is $0$ you can choose any $a>0$ to label $x$ correctly. $2$ is one example. With $a=2$ all $h(x)$ will return $0$ for all points less than $2$ (which includes $x=0$).

If the label is $1$ you can similarly choose any $a<0$. $-2$ is one example, but you could also choose $-0.01$ or $-1232132158932$. In the case $a=-2$, $h(x)$ will return 1 for all $x>-2$ (which again includes $x=0$).

So you fulfilled the first condition.

2) Now they show the second condition. But maybe they left out some of the details. Let me try to fill them in.

To show the second condition, you need to pick any two points and show that it is impossible to find $a$ to classify all possible labels correctly. Let's call the two points $x1$ and $x2$. The $2^2=4$ possible labels are: $\{0,0\},\{0,1\},\{1,0\},\{1,1\}$.

Clearly, if $x1=x2$ it follows that $h(x1)=h(x2)$ and therefore the labels must be the same and and only $\{0,0\}$ and $\{1,1\}$ are possible but not $\{0,1\},\{1,0\}$.

Therefore, we can move on to the case where $x1 \neq x2$. Since the naming of $x1$ and $x2$ is arbitrary we can assume that $x1 < x2$ ("without loss of generality" because if $x1 > x2$ we can just rename $x2$ as $x1$ and $x1$ as $x2$ and we would have $x1 <x2$ again).

Now, in this case it is also impossible to achieve all four possible labeling combinations. In particular they show that the labeling $\{1,0\}$ is impossible. If the label of $x1$ is $1$ then it follows (similarly to 1) with $x=0$) that $a$ must be less than $x1$. But then $a < x1 < x2$ and therefore $h(x2)$ must also be $1$ and can't be $0$.

(You could now move on to the case $x1 > x2$ but as I tried to explain above that's basically the same idea, but now with the labeling $\{0,1\}$).

See this question for a very similar example with intervals instead of half lines.