Feature Mappings for Polynomial Classifiers

Suppose a training set is realizable: some classifier can label every training example correctly. A compression scheme asks whether we can keep only a smaller representation of that training set and still reconstruct a predictor that makes zero mistakes on the original examples. The important issue is therefore not whether every example is stored. It is whether the retained representation contains enough information for reconstruction without training errors.

For linearly separable data, a geometric compression construction can retain selected positive examples that support a separating direction. The construction uses two positive examples per dimension, so its compression size is k = 2d. These examples are useful because the separating classifier is determined through the geometry of the relevant positive examples rather than by storing the entire training set.

The geometric argument uses the convex hull of the relevant positive examples. When that convex hull does not contain the origin, the point in the convex hull closest to the origin provides a route to a separating direction. Reconstruction therefore depends on the geometry represented by the selected examples. The compressed examples are not arbitrary storage; they support the separation argument.

The Perceptron gives a second route to compression. It searches for a separating hyperplane and updates when an example is not correctly handled by the current separator. If the training set is separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.

The examples involved in those updates can serve as a compressed description. Because there are no more than 1/γ² updates, the resulting compression size k is no larger than 1/γ². This connects an algorithmic progress bound directly to the amount of information needed for reconstruction.

A polynomial classifier may look nonlinear in the original input coordinates. The feature-mapping view changes the representation instead of changing the halfspace idea. Let ψ(x) contain all monomials of x up to degree r. Then the polynomial expression p(x) can be written as the inner product of a weight vector w with ψ(x). In the transformed feature space, polynomial classification is therefore a halfspace classification problem.

The transformed feature space has dimension d′ = O(d^{^r}). Consequently, compression can be analyzed as a halfspace compression problem in that higher-dimensional space. The key shift is to analyze the classifier using ψ(x), not directly using the original coordinates x.