Margins and Generalization
A margin γ describes the separation available to the Perceptron analysis.
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?
- 1Identify the rule
The construction uses two positive examples per dimension.
- 2Substitute the dimension
With two dimensions, the count is 2 multiplied by 2.
- 3Interpret 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/γ² |
Two source-grounded ways to obtain a compressed description for linearly separable data.
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 |
The margin connects the geometry of separation to the update and compression bounds.
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(dr).
Changing the Space, Not the Classifier Form
How should a polynomial classifier be analyzed when its expression is not linear in the original coordinates?
- 1Create the representation
Map each input x to ψ(x), which contains all monomials up to degree r.
- 2Rewrite the polynomial
Express the polynomial as p(x) = 〈w, ψ(x)〉.
- 3Apply 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(dr).
Mistakes That Break the Argument
Common mistake Treating compression as arbitrary deletion.
What it looks likeKeeping a few examples without requiring a reconstruction step.
Why it failsA compression scheme must reconstruct a predictor that has zero loss on the full realizable training set.
Do this insteadAlways identify both the compressed representation and the reconstruction function.
Common mistake Assuming the extremal construction stores any 2d positive examples.
What it looks likeChoosing 2d positive examples without considering their geometric role.
Why it failsThe construction is supported by extremal examples and the geometry of the convex hull, not by an arbitrary subset.
Do this insteadConnect the retained examples to the separating direction and the convex-hull argument.
Common mistake Reading 1/γ² as a count of all training examples.
What it looks likeClaiming that the full training set has size 1/γ².
Why it failsThe bound concerns the number of Perceptron updates and therefore the number of update-involved examples used for compression.
Do this insteadState that the compression size is no larger than 1/γ².
Common mistake Analyzing polynomial classification only in the original coordinates.
What it looks likeRejecting halfspace compression because the original boundary is nonlinear.
Why it failsThe polynomial can be represented as a linear inner product after mapping inputs to polynomial features.
Do this insteadMove 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
- 1A compression scheme stores a smaller representation and reconstructs a predictor with zero training loss in the realizable case.
- 2For linearly separable data, two extremal positive examples per dimension give a compression size of k = 2d.
- 3The Perceptron makes at most 1/γ² updates when the training set has margin γ, yielding a compression size no larger than 1/γ².
- 4A polynomial classifier can be rewritten as a halfspace after mapping inputs to polynomial features.
- 5The transformed feature space has dimension d′ = O(dr), so halfspace compression can be analyzed there.
At a glance
- 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.