Linear Classifiers in Binary Classification

Capacity Through Shattering

A binary classifier is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity. It is the largest number of points that a classification class can shatter, where shattering means that every possible binary labeling of those points can be produced by some classifier in the class.

Two Halfspace Classes

For halfspaces, the VC dimension depends on whether the separating boundary must pass through the origin. A homogeneous halfspace uses a weight vector and has no bias term. A non-homogeneous halfspace includes a bias term, so its boundary is not required to pass through the origin. The difference changes the largest number of points that can be shattered in R^d.

Homogeneous Lower Bound

To prove that the VC dimension of homogeneous halfspaces in R^d is at least d, use the d standard basis vectors e1 through ed. Each basis vector has a 1 in one coordinate and 0 in every other coordinate.

Homogeneous Upper Bound

The lower bound alone is not enough. It shows that d points can be shattered, but an exact VC dimension also requires proving that d+1 points cannot be shattered.

Take any d+1 vectors in R^d. They are linearly dependent, so there are real coefficients a1 through a(d+1), not all zero, whose weighted combination of the vectors equals the zero vector. Separate the indices with positive coefficients from those with negative coefficients. If both groups are nonempty, shattering would require a weight vector whose dot products are positive on one group and negative on the other. Applying that weight vector to the dependence relation creates incompatible sign conditions. If one group is empty, the corresponding side becomes an equality, and the contradiction still follows.

The Bias Adds One Point

For non-homogeneous halfspaces, the lower-bound construction uses the zero vector together with the d standard basis vectors. This set contains d+1 points. The source proof states that this set is shattered by non-homogeneous halfspaces, paralleling the homogeneous construction for the basis vectors.

The distinction is the bias term. In the homogeneous construction, the weight vector supplies the coordinates used to control the labels of the standard basis vectors. In the non-homogeneous construction, the bias supplies the additional affine degree that makes it possible to include the zero vector as one more point in the shattered set.

Augmented-Space Reduction

The non-homogeneous upper bound uses a standard reduction. If d+2 vectors in R^d could be shattered by non-homogeneous halfspaces, the situation could be converted into d+2 vectors in R^(d+1) shattered by homogeneous halfspaces. But homogeneous halfspaces in R^(d+1) have VC dimension d+1, so they cannot shatter d+2 vectors. Therefore, non-homogeneous halfspaces in R^d cannot shatter d+2 points.

A Complete Proof Map

The weight vector and bias should therefore be tracked separately. The weight vector is central to the homogeneous lower-bound construction because its coordinates are chosen to match the desired labels of the standard basis vectors. The bias changes the non-homogeneous class enough to support the additional zero vector in the lower-bound construction, and it is represented by the extra dimension in the upper-bound reduction.

Common Proof Mistakes

• Treating a lower bound as the complete VC-dimension proof.

  Shattering d points proves only that the VC dimension is at least d. An upper bound is also required.

  Fix: Also show that no set of d+1 points can be shattered.

• Using the homogeneous argument for the non-homogeneous class without modification.

  The non-homogeneous lower-bound construction includes the zero vector as well as the d standard basis vectors.

  Fix: Use the zero vector plus the d standard basis vectors for the lower bound.

• Ignoring linear dependence in the homogeneous upper bound.

  Any d+1 vectors in R^d are linearly dependent, and the resulting sign constraints prevent at least one labeling from being realized.

  Fix: Use the dependence relation and separate its positive and negative coefficients.

• Confusing the original dimension with the augmented dimension.

  The standard reduction converts the problem into homogeneous classification in R^(d+1).

  Fix: Apply the homogeneous VC-dimension result in the augmented space.

Apply the Proof Pattern

Key Takeaways

1. VC dimension measures classification capacity through shattering.
2. Homogeneous halfspaces in R^d shatter the d standard basis vectors.
3. Linear dependence among any d+1 vectors in R^d prevents homogeneous halfspaces from shattering d+1 points.
4. Non-homogeneous halfspaces can shatter the zero vector together with the d standard basis vectors.
5. The augmented-space reduction gives the non-homogeneous upper bound, so its VC dimension is d+1.
6. The weight vector controls the homogeneous basis-vector construction, while the bias enables the additional affine degree represented in the non-homogeneous argument.