Homogeneous Halfspaces

A Separator with No Bias

A homogeneous halfspace classifies a vector x by the sign of its dot product with a weight vector w. The resulting decision rule uses the sign of w dot x. The boundary consists of points whose dot product with w is zero, so the separating hyperplane passes through the origin. The central question in this article is how a classifier that seems to depend on an entire training sample can instead be represented using only a small subset of that sample.

Finding the Special Vector

The compression construction begins with the convex hull of the training sample. Among all points in that convex hull, choose the point w with the smallest Euclidean norm. Geometrically, w is the point in the convex hull closest to the origin. Equivalently, it is the Euclidean projection of the origin onto the convex hull.

Why does this closest point define a separator? Suppose a training point xi had a nonpositive dot product with w. Moving a suitable amount from w toward xi would remain inside the same convex hull while producing a point closer to the origin. That contradicts the choice of w as the minimum-norm point. Therefore, the minimum-norm construction gives a vector whose dot product has the separating sign on the training points.

Compressing the Training Sample

The classifier is determined by w, but the compressed object is not w itself. The compressed object is a subset of training points from which w can be reconstructed. This distinction matters: the selected points are not merely examples that happen to be classified correctly. They form a compact geometric recipe for rebuilding the chosen separator.

Because w lies in the convex hull of the training sample, it can be written as a convex combination of sample points. Carathéodory's theorem gives a representation using at most d + 1 points in d-dimensional space. The construction has additional structure: the minimum-norm point lies on a face of the convex hull. The face property reduces the required representation to a convex combination of d sample points.

Capacity Through Shattering

For homogeneous halfspaces in R^d, the VC dimension is d. The lower bound comes from the d standard basis vectors. For any desired binary labeling, use those labels as the coordinates of w. Taking the dot product with a basis vector selects the corresponding coordinate of w, so every labeling can be realized.

The upper bound uses linear dependence. Any d + 1 vectors in R^d are linearly dependent, so there are coefficients, not all zero, whose weighted combination is the zero vector. Split the indices according to the signs of those coefficients. If the d + 1 vectors could be shattered, one weight vector would have to produce positive dot products on one group and negative dot products on the other. Applying that weight vector to the dependence relation creates incompatible sign conditions. If one coefficient-sign group is empty, the corresponding equality still yields the contradiction. Therefore, d + 1 points cannot always be shattered.

Adding a Bias Term

A non-homogeneous halfspace includes a bias term, so its separating boundary is not required to pass through the origin. That extra parameter changes the shattering argument. In R^d, non-homogeneous halfspaces have VC dimension d + 1 rather than d.

For the lower bound, consider the zero vector together with the d standard basis vectors. The source construction states that non-homogeneous halfspaces can shatter these d + 1 points. For the upper bound, if d + 2 vectors in R^d could be shattered by non-homogeneous halfspaces, the standard reduction would convert that situation into d + 2 vectors in R^(d+1) shattered by homogeneous halfspaces. That contradicts the homogeneous result in dimension d + 1, whose VC dimension is d + 1.

Practice and Common Errors

• Calling the weight vector w the compressed object.

  The construction compresses the training data into selected sample points that can be used to recover w.

  Fix: Treat the selected subset as the compressed description and w as the reconstructed classifier parameter.

• Stopping at the d + 1 bound from Carathéodory's theorem.

  The minimum-norm point lies on a face, and that additional property reduces the representation to d points in this construction.

  Fix: Distinguish the general Carathéodory bound from the stronger bound obtained using the face property.

• Using the homogeneous VC dimension for classifiers with a bias term.

  Adding a bias term changes the shattering argument and raises the stated dimension to d + 1.

  Fix: Check whether the boundary is required to pass through the origin before selecting the VC-dimension result.

• Proving only the lower bound when claiming an exact VC dimension.

  That establishes only that the VC dimension is at least d.

  Fix: Also use linear dependence to show that d + 1 vectors cannot always be shattered by homogeneous halfspaces.

Key Takeaways

1. A homogeneous halfspace classifies x using the sign of w dot x, and its boundary passes through the origin.
2. The compression construction chooses the minimum-norm point of the training sample's convex hull.
3. That point separates the training data because moving toward a point with a nonpositive dot product would contradict its minimum norm.
4. Carathéodory's theorem gives d + 1 points in general, while the face property reduces the construction to d selected points.
5. The selected points are the compressed description; reconstruction uses them to recover w and the classifier.
6. Homogeneous halfspaces in R^d have VC dimension d, while non-homogeneous halfspaces have VC dimension d + 1.