VC dimension of linear separator in 3D

Question

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?

Answer 1

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.

Answer 2

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!!