26
$\begingroup$

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

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ Then in this case we can get at least one pattern of any number of points which can be classified by straight line. For example think about 4 points. Two red points in left side and two blue points in right side would make it possible to classify, and VC dimension would be 4. So why not this considered? $\endgroup$
    – Kaushal28
    Jun 3, 2018 at 9:31
  • 1
    $\begingroup$ Classified - yes. Shattered - no $\endgroup$
    – Vladislav Gladkikh
    Jun 3, 2018 at 9:33
  • 1
    $\begingroup$ So what is the meaning of shattering an arrangement of points? I'm really confused here. Thanks $\endgroup$
    – Kaushal28
    Jun 3, 2018 at 10:05
  • $\begingroup$ An arrangement of points can be shattered if any subset of this arrangement can be isolated and put into one class. Say, you want to test if a certain arrangement (not all possible arrangements but only one particular arrangement) of n points can be shattered by a certain type of classifiers. Then you first test if any single point can be isolated. Then, if any 2 points can be isolated, then if any 3 points, etc, till any n-1 points of that particular arrangement. See here en.wikipedia.org/wiki/Shattered_set $\endgroup$
    – Vladislav Gladkikh
    Jun 3, 2018 at 10:23
  • 1
    $\begingroup$ Figure with 8 subplots is a very good illustration of what is shattering. Here you have 3 points, 2 classes, so 2^3=8 possible labelings of these 3 points. All 8 labelings can be done and isolated with a line therefore this set can be shattered by a line. The figure with 4 points: it has some labelings that can be isolated with a line (say, two left are red, two right are blue) but also has a labeling that cannot be isolated with a line (like in the Figure: upper and lower blue; left and right are left). As it has a labeling that cannot be isolated with a line, this set is not shattered. $\endgroup$
    – Vladislav Gladkikh
    Jun 4, 2018 at 1:33
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.