Compression Schemes
A compression scheme replaces a training set with a smaller representation and then reconstructs a predictor from that representation.
Why Retain Only a Few Examples
A compression scheme replaces a training set with a smaller representation and then reconstructs a predictor from that representation. The goal is not to store every original example. In the realizable case, the important requirement is that the reconstructed predictor has zero loss on the training set.
An axis aligned rectangle is a rectangle whose sides are parallel to the coordinate axes. The source describes the class of axis aligned rectangles as uncountable and infinite, while also giving it a simple compression scheme.
The apparent tension is the central lesson: a hypothesis class can be uncountable and infinite while its individual training sets can still be represented compactly. For axis aligned rectangles, the compact representation keeps positive examples that determine the outer limits in each dimension.
Tracing Algorithm A
Algorithm A examines the positive examples dimension by dimension. In every dimension, it selects two positive examples: one with an extremal minimum value and one with an extremal maximum value. These selected examples are the compressed representation.
Selecting extremal examples in two dimensions
Consider positive examples p1 = (1, 4), p2 = (3, 2), and p3 = (5, 6). Apply algorithm A.
- 1First dimension
The minimum first coordinate is 1, supplied by p1. The maximum first coordinate is 5, supplied by p3.
- 2Second dimension
The minimum second coordinate is 2, supplied by p2. The maximum second coordinate is 6, supplied by p3.
- 3Retained representation
The extremal roles identify p1, p2, and p3. The same example, p3, supplies more than one extremal role.
Algorithm A selects at most four extremal roles in two dimensions, but only three distinct examples are needed in this particular data set.
The selection is based on extremal coordinate values, not on retaining an arbitrary sample of positive examples. One example may satisfy several extremal roles, so 2d is an upper bound on the number of distinct retained examples.
Tracing Function B
Function B receives the examples selected by algorithm A and returns their minimal enclosing rectangle. This rectangle is the smallest axis aligned rectangle that encloses the selected examples. In the construction described by the source, the retained extremal examples preserve the outer limits needed to reconstruct the rectangle.
Reconstructing the enclosing rectangle
Use the selected examples p1 = (1, 4), p2 = (3, 2), and p3 = (5, 6). Determine the coordinate limits used by function B.
- 1Lower limits
The smallest first coordinate among the selected examples is 1, and the smallest second coordinate is 2.
- 2Upper limits
The largest first coordinate is 5, and the largest second coordinate is 6.
- 3Rectangle
Function B returns the axis aligned rectangle bounded by first-coordinate values 1 and 5 and second-coordinate values 2 and 6.
The reconstructed rectangle is determined by the lower and upper coordinate limits preserved by the selected examples.
Counting the Compression
- 1There are d dimensions.
- 2Algorithm A selects one minimum and one maximum positive example in each dimension.
- 3That gives two extremal selections per dimension.
- 4Multiplying two selections by d dimensions gives the compression-size bound k = 2d.
The count is a bound on how many examples the scheme needs to retain. It counts the two extremal roles in every dimension. Because one example can supply multiple roles, the number of distinct examples can be smaller than 2d.
| Number of dimensions | Extremal selections per dimension | Compression-size bound |
|---|---|---|
| d | 2 | 2d |
| 2 | 2 | 4 |
| 3 | 2 | 6 |
The bound grows from two extremal selections for each dimension.
What do you think happens?
If one positive example supplies the minimum in one dimension and the maximum in another, must the compressed representation contain two different copies of that example?
Reveal answer
No. The same example can supply multiple extremal roles, so the number of distinct retained examples can be smaller than 2d.
The value 2d counts two selections per dimension as an upper bound. It does not require every role to be supplied by a different example.
The Realizable Zero-Loss Result
In the realizable case, the source gives the result L_S(B(A(S))) = 0. Here A selects the compressed representation from the training set S, and B reconstructs a predictor from that representation.
The equation means that the reconstructed predictor makes zero loss on S. The scheme does not need to preserve every training example individually; it needs to preserve enough information for B to reconstruct a predictor that makes no mistakes on the training set in the realizable situation.
When explaining a compression scheme, always identify both components: the compression algorithm A and the reconstruction function B. Saying only that examples are removed misses the essential question of how the predictor is recovered.
Beyond Rectangles
The extremal-example construction is connected to linearly separable data. The source describes linear separability as the existence of a hyperplane that separates positive and negative examples. In the geometric argument, the convex hull of the relevant positive examples does not contain the origin, and the point in that convex hull closest to the origin is used to obtain a separating direction. This supports reconstruction through the geometry of the data rather than through arbitrary storage.
The Perceptron gives another compression route. 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, so the compression size k is no larger than 1/γ².
Polynomial classification can be treated in the same compression perspective after changing the representation. If ψ(x) contains all monomials of x up to degree r, the polynomial expression p(x) can be written as ⟨w, ψ(x)⟩. This turns the problem into halfspace classification in the transformed feature space, whose dimension is described as d′ = O(dr).
Common Misunderstandings
Common mistake Treating 2d as the number of distinct examples that must always be stored.
What it looks likeIn two dimensions, the bound is 4, but one example may supply multiple extremal roles.
Why it failsThe factor of two counts two extremal selections per dimension, not necessarily different examples.
Do this insteadTreat 2d as an upper bound on the number of retained examples.
Common mistake Confusing algorithm A with function B.
What it looks likeDescribing B as the procedure that selects minimum and maximum examples.
Why it failsA selects the examples, while B constructs the minimal enclosing rectangle from the selected examples.
Do this insteadState the responsibilities separately: A compresses and B reconstructs.
Common mistake Interpreting zero loss as a claim about every possible data set.
What it looks likeClaiming L_S(B(A(S))) = 0 even when the case is not realizable.
Why it failsThe stated zero-loss result is for the realizable case.
Do this insteadAttach the realizability condition whenever you state the result.
Common mistake Assuming polynomial classification is analyzed only in the original coordinates.
What it looks likeIgnoring the transformed feature representation ψ(x).
Why it failsThe source explains polynomial classification as halfspace classification in a higher-dimensional transformed feature space.
Do this insteadAnalyze the linear halfspace after mapping x to ψ(x).
Practice Check
A data set has positive examples in d = 3 dimensions. Explain how algorithm A selects its compressed representation, give the compression-size bound, and state what function B returns.
Hints
- Count the minimum and maximum selections separately for each dimension.
- Remember that the bound counts extremal roles and that distinct examples may overlap across roles.
- Function B returns a minimal enclosing rectangle of the selected examples.
Explain the meaning of L_S(B(A(S))) = 0 in the realizable case. Then compare the rectangle construction with the Perceptron route, whose compression size is no larger than 1/γ² when the training set has margin γ.
Hints
- Describe the loss on the original training set S.
- For the Perceptron route, connect retained examples to update examples.
- Do not confuse the rectangle bound 2d with the margin-dependent bound 1/γ².
- 1Identify the positive examples.
- 2For each dimension, locate the minimum positive coordinate value.
- 3For each dimension, locate the maximum positive coordinate value.
- 4Retain the examples supplying those extremal roles.
- 5Use function B to construct the minimal enclosing rectangle.
- 6Apply the realizability condition when stating the zero-loss result.
Key Takeaways
- 1Axis aligned rectangles have sides parallel to the axes, and the source describes their class as uncountable and infinite.
- 2Algorithm A selects positive examples with minimum and maximum values in every dimension.
- 3Function B reconstructs the minimal enclosing rectangle from the selected examples.
- 4Two extremal selections in each of d dimensions give the compression-size bound k = 2d, although fewer distinct examples may be needed.
- 5In the realizable case, the reconstructed predictor satisfies L_S(B(A(S))) = 0.
- 6Perceptron updates and polynomial feature maps provide related compression perspectives for linearly separable and transformed-feature problems.
At a glance
- A compression scheme retains a smaller representation and reconstructs a predictor from it.
- For axis aligned rectangles, extremal positive examples preserve the outer limits in each dimension.
- Selecting a minimum and maximum example for every dimension gives k = 2d.
- The realizable-case equation L_S(B(A(S))) = 0 means the reconstructed predictor has zero loss on the training set.
- Perceptron update examples and polynomial feature representations extend the compression idea beyond the rectangle construction.