TransWikia.com

What is the exact definition of VC dimension?

Data Science Asked by Kaushal28 on December 16, 2020

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.

enter image description here

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,

enter image description here

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?

enter image description here

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

2 Answers

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.

Correct answer by Vladislav Gladkikh on December 16, 2020

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

Answered by biddut on December 16, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP