How to calculate VC-dimension?

Question

Im studying machine learning, and I would like to know how to calculate VC-dimension.

For example:

$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases} $, with parameters $(a,b) ∈ R^2$.

What is the VC-dimension of it?

Answer 1

The VC dimension is an estimate for the capability of a binary classifier. If you can find a set of $n$ points, so that it can be shattered by the classifier (i.e. classify all possible $2^n$ labelings correctly) and you cannot find any set of $n+1$ points that can be shattered (i.e. for any set of $n+1$ points there is at least one labeling order so that the classifier can not seperate all points correctly), then the VC dimension is $n$.

In your case, first consider two points $x_1$ and $x_2$, such that $x_1 < x_2$. Then there are are $2^2=4$ possible labelings

1. $x_1:1$, $x_2:1$
2. $x_1:0$, $x_2:0$
3. $x_1:1$, $x_2:0$
4. $x_1:0$, $x_2:1$

All labelings can be achieved through the classifier $h$ by setting the parameters $a<b \in R$ such that

1. $a<x_1<x_2<b$
2. $x_1<x_2<a<b$
3. $a<x_1<b<x_2$
4. $x_1<a<x_2<b$

respectively. (Actually, $x_1 < x_2$ can be assumed w.l.o.g. but it is enough to find one set that can be shattered.)

Now, consider three arbitrary(!) points $x_1$, $x_2$, $x_3$ and w.l.o.g. assume $x_1<x_2<x_3$, then you can't achieve the labeling (1,0,1). As in case 3 above, the labels $x_1$:1 and $x_2$:0 imply $a<x_1<b<x_2$. Which implies $x_3$ > b and therefore the label of $x_3$ has to be 0. Thus, the classifier cannot shatter any set of three points and therefore the VC dimension is 2.

-

Maybe it becomes clearer with a more useful classifier. Let's consider hyperplanes (i.e. lines in 2D).

It is easy to find a set of three points that can be classified correctly no matter how they are labeled:

For all $2^3=8$ possible labelings we can find a hyperplane that separates them perfectly.

However, we cannot find any set of 4 points so that we could classify all $2^4=16$ possible labelings correctly. Instead of a formal proof, I try to present a visual argument:

Assume for now, that the 4 points form a figure with 4 sides. Then it is impossible to find a hyperplane that can separate the points correctly if we label the opposite corners with the same label:

If they don't form a figure with 4 sides, there are two "boundary cases": The "outer" points must either form a triangle or all form a straight line. In the case of the triangle, it is easy to see that the labeling where the "inner" point (or the point between two corners) is labeled different from the others can't be achieved:

In the case of a line segment, the same idea applies. If the end points are labeled differently than one of the other points, they cannot be separated by a hyperplane.

Since we covered all possible formations of 4 points in 2D, we can conclude that there are no 4 points that can be shattered. Hence, the VC dimension must be 3.

Answer 2

The VC dimension of a classifier is determined the following way:

VC = 1
found = False
while True:
    for point_distribution in all possible point distributions of VC+1 points:
        allcorrect = True
        for classdist in every way the classes could be assigned to the classes:
            adjust classifier
            if classifier can't classify everything correct:
                allcorrect = False
                break
        if allcorrect:
            VC += 1
            continue
    break

So there has only to be one way to place three points such that all possible class distributions among this point-placement can be classified the correct way.

If you don't place the three points on a line, the perception gets it right. But there is no way to get the perception classify all possible class distributions of 4 points, no matter how you place the points

Your example

Your features are in $\mathbb{R}$. Every classifier has at least dimension 1.

VC-Dimension 2: It can classify all four situations correctly.

1. Points: 0 and 42
2. Distributions:
   • class(0) = False, class(42) = False => $a = 1337, b=3141$ classifies this correctly
   • class(0) = False, class(42) = True => $a = 40, b = 1337$ classifies this correctly
   • class(0) = True, class(42) = False => $a = -1, b = 1$ classifies this correctly
   • class(0) = True, class(42) = True => $a = -1, b = 1337$ classifies this correctly.

VC-Dimension 3: No, that doesn't work. Imagine the classes true and false being ordered like True False True. Your classifier can't deal with that. Hence it has a VC-Dimension of 2.

Proof

Obviously, the points $x_1, x_2, x_3 \in \mathbb{R}$ can only be distinguished if they have different values. Without loss of generality, we can assume that $x_1 < x_2 < x_3$. Hence the classifier has to be able to classify

class($x_1$) = True, class($x_2$) = False, class($x_3$) = True

correctly to have VC dimension 3. For $x_1$ to be classified as True, $$a \leq x_1 \leq b$$ is required. For $x_2$ to be False, $$x_2 < a \qquad\text{ or }\qquad b < x_2$$ is required. As $a \leq x_1$ and $x_1 < x_2$, it has to be $b < x_2$. So the situation is currently: $$a \leq x_1 \leq b < x_2 < x_3$$ For $x_3$ to be classified as True, $$a \leq x_3 \leq b$$ is required. But the other constraints already required $b < x_3$. Hence it is not possible to classify all class distributions of any 3 points correctly with this classifier. Hence it does not have VC dimension 3.