Questions: VC Dimension

Question 1

The class of linear classifiers in R^2 (lines dividing the plane into two half-planes) has VC dimension 3. A colleague argues this means any 3 points can be shattered. Is this correct?

• A. Yes — VC dimension d means every set of d points can be shattered
• B. No — VC dimension d means SOME set of d points can be shattered, not that every set can be; three collinear points in R^2 cannot be shattered by lines
• C. No — VC dimension 3 means at most 2 points can be shattered, since the dimension counts from zero
• D. Yes — in R^2, any three points are in general position and can always be shattered by lines

Answer: (B)

VC dimension d requires the existence of at least one set of d points that can be shattered — not that all sets of d points can be. For linear classifiers in R^2, three points in general position (not collinear) can be shattered: for every one of the 8 possible labelings, a line separates the positives from the negatives. But three collinear points cannot be shattered — the labeling +, -, + (middle point different from the outer two) cannot be achieved by a half-plane. The existential quantifier is critical to the definition.

Question 2

Adding more parameters to a model always increases its VC dimension.

• T. True
• F. False

Answer: False

While there is a rough correlation between parameter count and VC dimension, the relationship is not monotonic or guaranteed. The classic counterexample is the hypothesis class h(x) = sign(sin(wx)): this has a single real-valued parameter w but infinite VC dimension, because by choosing w appropriately, the high-frequency sine function can shatter arbitrarily large sets of points on the real line. Conversely, a constrained model with many parameters can have low VC dimension if the constraints limit its expressive power. VC dimension measures the effective complexity of the function class, not its parameterization.

Question 3

Why can't four points in R^2 be shattered by linear classifiers, given that three points in general position can be?

• A. Four points have 16 possible labelings, and there are only 14 distinct orientations of a line in R^2
• B. Radon's theorem guarantees that any 4 points in R^2 can be partitioned into two sets whose convex hulls intersect, making at least one labeling impossible for any half-plane
• C. The number of parameters in a linear classifier in R^2 is 3, and VC dimension always equals the number of parameters
• D. Four points in R^2 always contain three collinear points, which prevents shattering

Answer: (B)

Radon's theorem states that any set of d+2 points in R^d can be partitioned into two sets whose convex hulls intersect. For d=2, any 4 points have a Radon partition — two points whose convex hull (line segment) intersects the convex hull of the other two. A half-plane cannot separate sets with intersecting convex hulls, so at least one labeling is impossible. This geometric argument proves no set of 4 points can be shattered by lines in R^2, establishing that VC dimension is exactly 3. Option C is a common misconception — the 'VC = parameters' rule is a heuristic that fails in general.

Question 4

The VC dimension of the class of all convex polygons in R^2 is finite because convex shapes are relatively simple.

• T. True
• F. False

Answer: False

The class of convex polygon classifiers (point is positive if inside a convex polygon, negative otherwise) has infinite VC dimension. Given any n points arranged on a circle, any subset of them can be enclosed by a convex polygon while excluding the rest — simply draw a convex hull tightly around the positive points. Since this works for any n, the class shatters arbitrarily large sets, giving infinite VC dimension. The intuition that 'convex is simple' is misleading — the class of all convex polygons is extremely rich because there is no limit on the number of vertices.

Question 5

Explain why VC dimension, rather than the number of parameters, is the correct measure of hypothesis class complexity for learning theory.

Model answer: The number of parameters describes how a hypothesis class is parameterized, which is an artifact of representation, not a fundamental property of the function class. Different parameterizations of the same set of functions can have different parameter counts. VC dimension instead measures the intrinsic expressive capacity — the largest number of points the class can classify in all possible ways. This directly governs generalization: a class with VC dimension d requires O(d/epsilon) samples to learn, regardless of how many parameters the representation uses. The sine example (one parameter, infinite VC dimension) and constrained neural networks (many parameters, finite VC dimension) show that parameter count and VC dimension can diverge dramatically. Since sample complexity depends on VC dimension and not parameter count, VC dimension is the theoretically correct measure.

This distinction matters practically too. Modern deep networks have millions of parameters but generalize well — their effective complexity (related to but not equal to VC dimension) is controlled by optimization dynamics, initialization, and implicit regularization, not raw parameter count.