Margins and Generalization
Compression keeps a smaller representation from which a zero-training-loss predictor can be reconstructed in the realizable case.
From Training Set to Compressed Model
A compression scheme replaces a training set with a smaller representation and then reconstructs a predictor from that representation. In the realizable case, the essential requirement is not that every original example be stored. The requirement is that the reconstructed predictor make zero mistakes on the entire training set.
A compression scheme uses an algorithm A to select or create a compressed representation and a reconstruction function B to produce a predictor. For a realizable sample S, the reconstructed predictor must satisfy L_S(B(A(S))) = 0.
Extremal Points and Separating Directions
For linearly separable data, some positive examples can carry the geometric information needed to reconstruct a separator. The construction uses two extremal positive examples per dimension, so the compression size is k = 2d. These examples are not chosen merely because they are convenient members of the training set. Their role comes from the geometry of linear separability.
The geometric argument considers 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 can be used to obtain a separating direction. The reconstructed classifier is therefore supported by the arrangement of the data, rather than by storing arbitrary examples.
A Two-Dimensional Compression Count
Suppose the data is linearly separable and has d = 2 dimensions. How many positive examples does the extremal-example construction retain?
Identify the rule: The construction uses two positive examples per dimension.
Substitute the dimension: With two dimensions, the count is 2 multiplied by 2.
Interpret the result: The retained examples form a compressed geometric description from which a separating classifier can be reconstructed.
The compression size is k = 2d = 4.
Perceptron Updates as Compression
The Perceptron gives a second route to compression. It searches for a separating hyperplane. When the training set is separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution that makes no mistakes on the entire training set.
The examples involved in those updates can serve as a compressed description. Consequently, the compression size k is no larger than 1/γ². The update bound is therefore more than a statement about how quickly the Perceptron finds a separator: it also limits how many training examples need to be retained for this compression route.
| Compression route | Retained information | Size bound |
|---|---|---|
| Extremal-example construction | Two positive examples per dimension | k = 2d |
| Perceptron construction | Examples involved in updates | k no larger than 1/γ² |
Why Margin Matters
A margin γ describes the separation available to the Perceptron analysis. The source result connects a larger margin with a smaller update bound through 1/γ². Because the examples involved in updates can form the compressed description, the margin also controls the resulting compression-size bound.
| Geometric situation | Perceptron consequence | Compression consequence |
|---|---|---|
| Training set separated with margin γ | At most 1/γ² updates | Compression size k no larger than 1/γ² |
| Linearly separable training set | A separating hyperplane can be searched for | A predictor can be reconstructed with zero training loss in the realizable case |
Polynomial Features and Halfspaces
Polynomial classification can be converted into halfspace classification in a higher-dimensional feature space. Let ψ(x) contain all monomials of x up to degree r. A polynomial expression p(x) can then be written as the inner product of a weight vector w and the transformed feature vector ψ(x): p(x) = 〈w, ψ(x)〉.
This transformation changes the representation used for analysis. A boundary that is nonlinear when viewed in the original input coordinates can be treated as a linear hyperplane in the transformed feature space. The compression problem consequently becomes a halfspace compression problem in a space whose dimension is d′ = O(d^r).
Changing the Space, Not the Classifier Form
How should a polynomial classifier be analyzed when its expression is not linear in the original coordinates?
Create the representation: Map each input x to ψ(x), which contains all monomials up to degree r.
Rewrite the polynomial: Express the polynomial as p(x) = 〈w, ψ(x)〉.
Apply halfspace reasoning: Analyze the classifier as a halfspace in the transformed feature space rather than directly in the original coordinates.
Polynomial classification becomes a halfspace problem in dimension d′ = O(d^r).
Mistakes That Break the Argument
Treating compression as arbitrary deletion.
A compression scheme must reconstruct a predictor that has zero loss on the full realizable training set.
Fix:
Always identify both the compressed representation and the reconstruction function.Assuming the extremal construction stores any 2d positive examples.
The construction is supported by extremal examples and the geometry of the convex hull, not by an arbitrary subset.
Fix:
Connect the retained examples to the separating direction and the convex-hull argument.Reading 1/γ² as a count of all training examples.
The bound concerns the number of Perceptron updates and therefore the number of update-involved examples used for compression.
Fix:
State that the compression size is no larger than 1/γ².Analyzing polynomial classification only in the original coordinates.
The polynomial can be represented as a linear inner product after mapping inputs to polynomial features.
Fix:
Move the analysis to the transformed feature space ψ(x).
Check Your Understanding
A realizable, linearly separable sample is in a d-dimensional space, and its Perceptron analysis has margin γ. Explain two different compression-size bounds that may arise from the source constructions. Then explain how the analysis changes if the classifier is polynomial of degree at most r.
Hints
- For the extremal-example construction, count two positive examples per dimension.
- For the Perceptron construction, use the update bound.
- For a polynomial classifier, describe the feature map ψ(x) and the transformed dimension.
Key Takeaways
- A compression scheme stores a smaller representation and reconstructs a predictor with zero training loss in the realizable case.
- For linearly separable data, two extremal positive examples per dimension give a compression size of k = 2d.
- The Perceptron makes at most 1/γ² updates when the training set has margin γ, yielding a compression size no larger than 1/γ².
- A polynomial classifier can be rewritten as a halfspace after mapping inputs to polynomial features.
- The transformed feature space has dimension d′ = O(d^r), so halfspace compression can be analyzed there.
Key Takeaways
- Compression replaces a full training set with a smaller representation from which a zero-training-loss predictor can be reconstructed in the realizable case.
- Extremal positive examples provide a geometric compression of size k = 2d for linearly separable data.
- The Perceptron update bound gives another compression size, no larger than 1/γ².
- Polynomial classification can be transformed into halfspace classification in a higher-dimensional feature space.