Homogeneous Halfspaces

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.

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.

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.

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.

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.