VC Dimension and Shattering

Why Capacity Matters

A classification class is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity through shattering: it is the largest number of points for which the class can produce every possible binary labeling.

Homogeneous Halfspaces

For homogeneous halfspaces, the separating boundary is required to pass through the origin. The classification decision is controlled by the weight vector through dot products with the input vectors. The VC dimension of homogeneous halfspaces in R^d is d.

The basis-vector construction works because each basis vector isolates one coordinate of the weight vector. Selecting the coordinates of w to match the desired labels lets the classifier independently realize the labeling on those d points.

The upper bound uses a different idea. Any d+1 vectors in R^d are linearly dependent, so there are real coefficients, not all zero, whose weighted combination of the vectors equals the zero vector. If a weight vector produced positive dot products on the vectors with positive coefficients and negative dot products on those with negative coefficients, applying that weight vector to the dependence relation would create incompatible sign conditions. Therefore, some labeling cannot be realized.

Adding a Bias

Non-homogeneous halfspaces include a bias term, so the separating boundary is not required to pass through the origin. This additional parameter increases the VC dimension in R^d from d to d+1.

The upper bound follows by reducing the non-homogeneous problem in R^d to a homogeneous problem in R^(d+1). If d+2 vectors in R^d could be shattered by non-homogeneous halfspaces, the reduction would produce d+2 vectors in R^(d+1) shattered by homogeneous halfspaces. That contradicts the homogeneous result, because homogeneous halfspaces in R^(d+1) have VC dimension d+1 and cannot shatter d+2 vectors.

Common Reasoning Errors

• Treating a successful construction on d points as a complete proof that the homogeneous VC dimension is d.

  It establishes only the lower bound. A larger set might still be shatterable unless an upper bound is proved.

  Fix: Add the linear-dependence argument showing that no d+1 vectors in R^d can be shattered.

• Applying the homogeneous result directly to non-homogeneous halfspaces in the same dimension.

  The bias term changes the shattering argument by allowing a boundary that is not required to pass through the origin.

  Fix: Use the zero vector together with the d basis vectors for the lower bound and the reduction to homogeneous halfspaces in R^(d+1) for the upper bound.

• Ignoring the sign structure in the linear-dependence proof.

  The contradiction depends on requiring opposite dot-product signs for the groups determined by the coefficients.

  Fix: Separate indices with positive coefficients from those with negative coefficients and apply the proposed weight vector to the dependence relation.

Capacity Check

Final Takeaways

1. VC dimension is the largest number of points that a classification class can shatter.
2. Shattering means realizing every possible binary labeling of a selected set of points.
3. Homogeneous halfspaces in R^d have VC dimension d: the standard basis gives the lower bound, and linear dependence gives the upper bound.
4. Non-homogeneous halfspaces in R^d have VC dimension d+1: the zero vector plus the basis vectors gives the lower bound, and reduction to homogeneous halfspaces in R^(d+1) gives the upper bound.
5. The weight vector controls the dot-product signs used in the shattering construction, while the bias term removes the requirement that the boundary pass through the origin.