What is the exact definition of VC dimension?

I'm studying machine learning from Andrew Ng Stanford lectures and just came across the theory of VC dimensions. According to the lectures and what I understood, the definition of VC dimension can be given as,

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$ labeling 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 separate all points correctly), then the VC dimension is $n$.

Also Professor took an example and explained this nicely. Which is:

Let,

$H=\{{set\ of\ linear\ classifiers\ in\ 2\ Dimensions \}}$

Then any 3 points can be classified by $H$ correctly with separating hyper plane as shown in the following figure.

And that's why the VC dimension of $H$ is 3. Because for any 4 points in 2D plane, a linear classifier can not shatter all the combinations of the points. For example,

For this set of points, there is no separating hyper plane can be drawn to classify this set. So the VC dimension is 3.

I get the idea till here. But what if we've following type of pattern?

Or the pattern where a three points coincides on each other, Here also we can not draw separating hyper plane between 3 points. But still this pattern is not considered in the definition of the VC dimension. Why? The same point is also discussed the lectures I'm watching Here at 16:24 but professor does not mention the exact reason behind this.

Any intuitive example of explanation will be appreciated. Thanks

Topic vc-theory classification machine-learning

Category Data Science


So based on the definition we need to find $2^n$ arrangements that can be shattered by a linear boundary, which you have shown in the figure. Therefore, it does not matter if there are other arrangements that cannot be shattered.

For $n = 4$ we cannot find $2^n = 16$ arrangements that can be shattered by a linear boundary hence we say we cannot shatter $4$ points with a linear boundary in a 2D plane.


The points should fulfil points in general condition before consider for VC dimension. enter image description here


The definition of VC dimension is: if there exists a set of n points that can be shattered by the classifier and there is no set of n+1 points that can be shattered by the classifier, then the VC dimension of the classifier is n.

The definition does not say: if any set of n points can be shattered by the classifier...

If a classifier's VC dimension is 3, it does not have to shatter all possible arrangements of 3 points.

If of all arrangements of 3 points you can find at least one such arrangement that can be shattered by the classifier, and cannot find 4 points that can be shattered, then VC dimension is 3.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.