Linear Classifiers in Binary Classification

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.

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}.

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.

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.

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.

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.

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.