# How to calculate Vapnik-Chervonenkis dimension

it's my first post here, so I apologize if I broke a rule!

I'm reading Introduction to Machine Learning and got stuck on VC dimension. Here's a quote from the book:

"...we see that an axis-aligned rectangle can shatter four points in two dimensions. Then VC(H), when H is the hypothesis class of axis-aligned rectangles in two dimensions, is four. In calculating the VC dimension, it is enough that we find four points that can be shattered; it is not necessary that we be able to shatter any four points..."

And I don't understand that. If it's enough to find some separable combinations, why can't we just choose a "rectangle with positive examples" from the image above, put another $n$ positive ones therein, and then say $VC(H)$ increased by $n$? And if all cases must be separable then why we don't consider 4 points placed on a line - which is in general not possible to shatter by a rectangle?

The same with the linear classifier example on wikipedia VC article - on their image four points are impossible to shatter, but we can come up with a layout where it is possible. And conversely, we can put 3 points (as "+", "-", "+") on a line and it won't be possible to separate the positives from the negatives by a linear classifier.

Can anyone explain where's my mistake?

-
VC dimension works like this: You choose the points, then the adversary chooses the labeling. Finally you should be able to produce a hypothesis that correctly classifies that labeling of those points. If you are able to succeed for all labelings of the adversary, we say that the VC dimension is at least the number of points you were able to choose. – Srivatsan Jan 5 '12 at 14:23
@Srivatsan, your comment should definitely be posted as an answer :) – Serhiy Dec 31 '14 at 10:18

## 3 Answers

I think you just need to think carefully about how your examples relate to the definition. The VC dimension of H is the maximum h such that there exists a set of cardinality h shattered by H. To show that VC(H)=4 you must show:

• There is a set of cardinality 4 shattered by H, and
• Any set of cardinality greater than 4 is not shattered by H

In the picture, they are doing the first thing - giving a lower bound on the VC dimension by giving an example of a set that is shattered. To show VC(H)<5 they should also show that no set of five points is shattered.

There will in general be lots of sets of various sizes that are not shattered, but that doesn't matter, essentially because VC dimension is a maximum over sets that are shattered. Your example of $n$ points on a line does not imply anything about the VC dimension. I hope this helps.

-
So finding a 3 point layout which is not possible to shatter with a line, or finding a 100 point layout which is possible to shatter with a rectangle - they're exceptional cases and don't matter because we consider "all possible" sets for a given N and identify how many of those sets are shattered - is that correct? Also, see Srivatsan's comment with "You choose the points, then the adversary chooses the labeling" - I find it very appealing, seems to solve my problem as well as your explanation. – andreister Jan 5 '12 at 14:43
Yes that's correct in the sense that for each size, either there are no sets shattered or there is at least one set shattered. For VC dimension you want to find the highest size with at least one set shattered. – Colin McQuillan Jan 5 '12 at 14:59
Hmmm. This "you want to find the highest size with at least one set shattered" is exactly what confused me in the first place. A rectangle hypothesis can shatter 5000 "specially placed" points but somehow we ignore this and say VC(H)=4. Why? Srivatsan's "You choose the points and the adversary selects the labels" rule sounds spot on, because then I won't be able to shatter "much". You seem to be explaining it more rigorously but so far it's been close to what they say in the book, and I feel like I'm not satisfied with their answer... – andreister Jan 5 '12 at 15:25
It is not correct that 'A rectangle hypothesis can shatter 5000 "specially placed" points'. The set of axis-aligned rectangles does not shatter any set of order five or more. – Colin McQuillan Jan 5 '12 at 17:03
Well, if VC dimension is about finding the size with at least one set shattered, then imagine 2500 "+" examples located inside a rectangle and 2500 "-" ones located outside. I don't see why we cannot do that, how exactly VC theory prevents us from choosing that one? – andreister Jan 9 '12 at 19:58

@Srivatsan's explanation makes sense to me. I had this same problem when I started learning this. You have to allow any possible point dichotomy, and then prove that you can shatter that. Hence, if you find one combination of classes for a number of points that you can't shatter, that machine must have a VC dimension smaller than that number of points. Hence, the fact that a linear classifier can't shatter XOR means that you can't handle anything larger than 3 points, which is an illustration of Burges' n(-dimension)+1 rule for linear classifier VC dimension.

-

@andreister, just adding some color:

The confusion arises because the definition of VC dimension involves BOTH an existential qualifier ("there exists"), and a universal qualifier ("for all"):

Note that, if the VC dimension is h, then there exists at least one set of h points that can be shattered, but it in general it will not be true that every set of h points can be shattered Burgess (1998)

Thus, one such set of points has to exist, but their shattering == for all labelings == a universal assertion.

-