Feature Mappings for Polynomial Classifiers
Compression keeps a smaller representation from which a zero-training-loss predictor can be reconstructed in the realizable case.
The Compression Question
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.
A compression scheme uses an algorithm A to select or create a smaller representation from a training set. A reconstruction function B then turns that representation into a predictor. In the realizable case, the reconstructed predictor must have zero training loss on the original training set.
Extremal Examples and Separation
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.
Counting a Geometric Compression
A linearly separable data set has d dimensions. Apply the extremal-example construction that uses two positive examples per dimension.
Count the contribution of one dimension: The construction retains two positive examples for each dimension.
Multiply by the number of dimensions: Across d dimensions, the total number of retained examples is two times d.
Interpret the result: The retained examples form a compressed representation from which a separating direction can be reconstructed through the geometric argument.
The compression size is k = 2d.
Perceptron Updates as Compression
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.
Reading the Perceptron Bound
A realizable training set is separated with margin γ. What does the Perceptron guarantee tell us about a possible compressed representation?
Use the margin condition: The margin γ supplies the Perceptron update bound.
Bound the number of updates: The Perceptron makes at most 1/γ² updates before finding a separator with no training mistakes.
Use update examples: The examples involved in those updates can be retained as a compressed description.
The compression size can be bounded by k no larger than 1/γ².
Polynomial Features as New Coordinates
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.
Changing the Classification View
A classifier is expressed by a polynomial p(x). Explain how to place it in the halfspace framework.
Construct the representation: Define ψ(x) to contain all monomials of x up to degree r.
Rewrite the polynomial: Express p(x) as the inner product of a weight vector w and the mapped feature vector ψ(x).
Apply halfspace reasoning: Analyze the classifier in the transformed feature space, whose dimension is d′ = O(d^r).
The polynomial classification problem becomes a halfspace classification problem in the feature representation ψ(x).
Choosing the Right Compression View
| Compression route | Retained information | Size bound or count | Geometric or algorithmic basis |
|---|---|---|---|
| Extremal-example construction | Selected positive examples | k = 2d | Convex-hull geometry and a separating direction |
| Perceptron construction | Examples involved in updates | k no larger than 1/γ² | Margin-based update bound |
| Polynomial feature mapping | A halfspace compression representation in ψ(x) | Analyzed in dimension d′ = O(d^r) | Polynomial classification rewritten as halfspace classification |
Treating compression as ordinary data storage
The purpose is to retain a smaller representation from which a predictor can be reconstructed.
Fix:
Focus on whether reconstruction produces zero training loss on the original realizable data.Calling every positive example extremal
The construction uses selected positive examples, with two positive examples per dimension.
Fix:
Track the selected examples that support the convex-hull and separating-direction argument.Using the Perceptron bound as an exact update count
The source gives it as an upper bound on the number of updates.
Fix:
Interpret it as a maximum, and therefore as an upper bound on the compression size obtained from update examples.Saying that a polynomial classifier is linear in the original input space
The halfspace interpretation applies after mapping x to ψ(x).
Fix:
State explicitly that the classifier is a halfspace in the transformed feature space.
Practice and Synthesis
A realizable polynomial classification problem uses monomials up to degree r. Explain, in order, how you would reinterpret it as a halfspace problem, which dimension controls the halfspace analysis, and how a compression result for halfspaces could then be applied.
Hints
- Begin by naming the feature map ψ(x).
- State how p(x) is represented using w and ψ(x).
- Use d′ = O(d^r) for the transformed dimension.
- Conclude by referring to halfspace compression in the transformed space.
Compare the two direct compression constructions for linearly separable data: the extremal-example construction and the Perceptron construction. State what each retains and how its size is bounded.
Hints
- The extremal-example construction uses two positive examples per dimension.
- The Perceptron construction retains examples involved in updates.
- The Perceptron update bound depends on the margin γ.
Key Takeaways
- A compression scheme retains a smaller representation and reconstructs a predictor with zero training loss in the realizable case.
- For linearly separable data, selected extremal positive examples can support reconstruction through convex-hull geometry; the stated construction uses k = 2d examples.
- The Perceptron supplies another compression route: with margin γ, at most 1/γ² updates occur, so update examples give a compression size no larger than 1/γ².
- Mapping x to ψ(x), where ψ(x) contains monomials up to degree r, turns polynomial classification into halfspace classification in dimension d′ = O(d^r).