patternModerate
VC dimension of linear separator in 3D
Viewed 0 times
linearseparatordimension
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#11548, answer score: 11
Revisions (0)
No revisions yet.