4
$\begingroup$

I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions.

In three dimensions, a linear separator would be a plane, and the classification model would be "everything on one side of a plane."

It's apparently proved that the VC dimension of linear separators is d+1, so in 3D, its VC dimension is four. That means it should be able to put any set of 1, 2, 3, or 4 points on one side of a plane.

But, what about this case: four coplanar points on a square with opposite corners same adjacent corners different?

+1    -1

-1    +1

This is the case that a line (2-dimensional linear separator) cannot handle, but the 3-dimensional linear separator is supposed to be able to shatter this. But, I can't see how you could put two corners on "one side of a plane" because all four points are coplanar.

Could someone explain how a 3-d linear separator can shatter the four points I just described?

$\endgroup$
7
$\begingroup$

You have a small (but crucial) misunderstanding of what the VC dimension of a class is.

The VC dimension is the maximal number $d$ such that there exists a set of $d$ points that is shattered by the class. It doesn't mean that every set is shattered.

In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then they can be.

This is similar to the case of 2D: 3 points that are co-linear cannot be shattered by a line, but there exists a set of 3 points that can be shattered.

$\endgroup$
0
$\begingroup$

I will simplify it this way- If we can find at least 1 set of d points in an n-D plane, all of whose possible labellings(consider + and - , i.e 2^n), can be shattered, then its VC dimension >= d. However, if any (atleast 1) of the labellings in that particular set cannot be shattered, then consider another possibility for a set of same number of points d, whose all possible labellings can be shattered,and if found, its VC dimension is at least d and then check for d+1 points, otherwise, its Vc dimension < d. For instance, VC dimension of a 2D space is 3. This is because for any set of 3 non-collinear points, its all possible labelling(2^3) combinations can be perfectly shattered by a line. However, 3 collinear points cannot be shattered in 2-D plane, because there exists combinations like ((+,-,+), (-,+,-)) that cannot be classified by a line, though other labellings like (+,+,-),(+,-,-), etc. can be perfectly classified. Hence, since there is atleast 1 set of 3 points(non-collinear), all of whose combinations can be shattered by a 2D line, its VC dimension is 3. Hope this helps!!

$\endgroup$
  • $\begingroup$ Your post is hard to follow. Maybe some structuring Markdown can help? $\endgroup$ – Raphael Sep 20 '16 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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