Just as almost all the lecture said, VC Dimension is defined as the cardinality of the largest set of points that the algorithm can shatter.
Here, I summarize some VC dimension:
(1) VC of a 2-D linear classifier: 3
VC of a p-D linear classifier: p+1
This is easy to understand:
Someone may say if three points are colinear, they cannot be shattered. Yes, but the definition is the largest set of points that can be shattered. When three points are not colinear, it is easy to find a set of three points that can be classified correctly no matter how they are labeled:
But for four points,
Above is totally the XOR, which is nonlinear separable.
That means, after examining all the cases of 4 points, none cases can be shattered given all the possible scene of labels.
(2) VC dimension of a rectangle with horizontal and vertical edges is 4:
As figure 1 shows:
(figure 1)
Some one may say the following case, They can't be shattered:
Ok, it only needs to satisfy one possible position of four points. So even though this kind of position can't be shattered using this kind of labels, figure 1 can no matter what the labels of four points are.
Why can't it shatter 5 points?:
For all the possible position of five points, they can't be shattered.
(3) VC dimension of a rotatable rectangle is 7:
(4) VC of interval=2
(5) VC of threshhold on the real line=1
(6) Union of k intervals on the real line: VC=2k
(7)VC of convex polygons on the plane=infinite
points inside the convex polygon are positive and outside are negative
there is no bound on the number of edges
(8)VC of circle, which is a little confusing.
a. f(x;theta)=sign(xx-theta), VC =1
b. just circle which centers at the origin: VC=2
in case someone may argue the VC is 1, the explanation is symmetry. Because you have no limit on which side is positive which side is negative, which also is the main difference compared to a.
c.
proof:
(9)triangle: VC=7
(10) sphere centers at origin: VC=2. The same reason with (8)b
Just as almost all the lecture said, VC Dimension is defined as the cardinality of the largest set of points that the algorithm can shatter.
Here, I summarize some VC dimension: (1) VC of a 2-D linear classifier: 3 VC of a p-D linear classifier: p+1 This is easy to understand:
Someone may say if three points are colinear, they cannot be shattered. Yes, but the definition is the largest set of points that can be shattered. When three points are not colinear, it is easy to find a set of three points that can be classified correctly no matter how they are labeled:
But for four points,
Above is totally the XOR, which is nonlinear separable.
That means, after examining all the cases of 4 points, none cases can be shattered given all the possible scene of labels. (2) VC dimension of a rectangle with horizontal and vertical edges is 4: As figure 1 shows:
(figure 1)
Some one may say the following case, They can't be shattered:
Ok, it only needs to satisfy one possible position of four points. So even though this kind of position can't be shattered using this kind of labels, figure 1 can no matter what the labels of four points are.
Why can't it shatter 5 points?:
For all the possible position of five points, they can't be shattered.
(3) VC dimension of a rotatable rectangle is 7:
(4) VC of interval=2
(5) VC of threshhold on the real line=1
(6) Union of k intervals on the real line: VC=2k
(7)VC of convex polygons on the plane=infinite points inside the convex polygon are positive and outside are negative there is no bound on the number of edges
(8)VC of circle, which is a little confusing. a. f(x;theta)=sign(xx-theta), VC =1
b. just circle which centers at the origin: VC=2
in case someone may argue the VC is 1, the explanation is symmetry. Because you have no limit on which side is positive which side is negative, which also is the main difference compared to a.
c.
proof:
(9)triangle: VC=7
(10) sphere centers at origin: VC=2. The same reason with (8)b
(11)square: VC=3: