Realizable Compression Schemes
Compression in the unrealizable setting seeks minimum error within H, not necessarily zero error.
From Full Sequence to Small Representation
A compression scheme replaces a training sequence with a much smaller retained collection of examples and then reconstructs a hypothesis from that collection. For a scheme of size k, the original sequence may contain m examples, but the selection step keeps only k of them. The reconstructed hypothesis is judged on the original sequence, not only on the retained examples.
A compression scheme of size k limits the number of examples that survive the selection step to k. Function A selects the retained examples, and function B maps those retained examples to a reconstructed hypothesis h'. The quality guarantee is evaluated against the full original training sequence.
The Two Functions
The selection and reconstruction functions have different responsibilities. A decides what information is preserved from the training sequence. B receives only that preserved information and decides which hypothesis to reconstruct. A does not itself produce the final hypothesis, and B does not receive every example from the original sequence.
Tracing A and B
Suppose a training sequence contains m examples and a size-k compression scheme is applied.
Selection: A examines the full sequence and chooses the examples that will be retained. The retained collection contains at most k examples.
Transfer: Only the retained collection is passed onward; B does not receive the discarded examples as part of its compression input.
Reconstruction: B maps the retained collection to the reconstructed hypothesis h'.
Evaluation: The performance of h' is compared on the original m-example sequence, rather than only on the retained collection.
A controls which examples survive, while B controls how those examples become a hypothesis.
Making the Remainder Realizable
In the realizable setting, some hypothesis in H labels every training example correctly. In the unrealizable setting, every hypothesis in H makes at least one mistake. The bridge between these settings is an empirical risk minimization hypothesis, written h. An ERM hypothesis minimizes training error within H. The examples on which h is correct form a retained remainder that is realizable by h, even when the full sequence is not realizable.
The Unrealizable Construction
- Choose an ERM hypothesis h in H for the full training sequence.
- Identify the examples on which h is correct.
- Apply the assumed realizable compression scheme of size k only to that correctly classified subset.
- Let the realizable scheme return h'.
- Use h' as the hypothesis reconstructed for the original, possibly unrealizable sequence.
On every example retained from the correct subset, h is correct and the realizable compression guarantee makes h' correct as well. Therefore, any errors made by h' on the original sequence can occur only among the examples discarded because h was already wrong. Since h was chosen by ERM, h has minimum training error within H. Thus h' cannot have more training error than h and also has minimum training error within H.
| Setting | Condition on the sequence | Role of the guarantee |
|---|---|---|
| Realizable | Some hypothesis in H is correct on every training example | The reconstructed hypothesis is correct on the realizable training data |
| Unrealizable | Every hypothesis in H makes at least one training error | The reconstructed hypothesis has no more training error than an ERM hypothesis |
Why the Size Stays k
A Symbolic Error Trace
Consider an arbitrary sequence containing examples on which an ERM hypothesis h is correct and examples on which h makes errors.
Partition by h: Separate the sequence into the examples correctly classified by h and the examples on which h errs.
Compress the correct part: Apply the realizable compression scheme to the correctly classified part. It retains at most k examples and reconstructs h'.
Check retained examples: The realizable guarantee says h' is correct on the retained, realizable part used by the scheme.
Locate possible errors: Any remaining error of h' on the original sequence can only be on examples discarded because h was already incorrect.
Compare errors: The possible error locations for h' are contained among locations where h errs, so h' has no more error than h.
The construction keeps the same size k because it uses the assumed size-k realizable scheme and does not add extra retained examples for the unrealizable part.
The key comparison is about error locations, not about whether the retained examples reproduce every detail of the original sequence. The realizable scheme protects the examples on which h was correct. The only uncovered examples are precisely those on which h already errs. This is why the final hypothesis is no worse than h on the full sequence.
Common Reasoning Errors
Treating A as the function that reconstructs the hypothesis.
A selects the retained examples. B maps those retained examples to the reconstructed hypothesis.
Fix:
Trace the roles separately: A selects, then B reconstructs.Evaluating h' only on the retained subset.
The compression guarantee is evaluated against the original training sequence.
Fix:
After reconstruction, compare h' with hypotheses in H on the full sequence.Assuming that the full unrealizable sequence becomes realizable.
In the unrealizable setting, every hypothesis in H makes at least one mistake.
Fix:
Use h to identify a correctly classified subset. That subset, not necessarily the full sequence, is realizable.Adding the ERM-error examples to the compressed representation.
The construction relies on the realizable scheme applied to the correct subset, and its size remains k.
Fix:
Use the realizable compression output of size k and account for the discarded examples through the error comparison.
Check Your Understanding
An ERM hypothesis h is correct on part of a training sequence and incorrect on the rest. Describe the complete compression construction that uses a realizable compression scheme of size k. Identify what A receives, what A retains, what B receives, and why the final hypothesis has no more error than h on the original sequence.
Hints
- First separate the examples where h is correct from the examples where h errs.
- Apply the realizable scheme only to the correctly classified subset.
- The possible errors of the reconstructed hypothesis outside that subset must be compared with the examples where h already errs.
- Remember that the reconstructed hypothesis is evaluated on the full original sequence.
What do you think happens?
If the assumed realizable compression scheme has size k, does the unrealizable construction require a larger compression size?
Reveal answer
Answer: No, because the realizable scheme is applied to the correctly classified subset.
The construction uses the assumed size-k scheme on the realizable remainder, so the resulting scheme preserves size k.
Essential Takeaways
- A size-k compression scheme retains at most k examples from an m-example training sequence and reconstructs a hypothesis from them.
- A selects the retained examples; B maps those examples to the reconstructed hypothesis.
- In an unrealizable problem, an ERM hypothesis h identifies a subset on which h is correct, making that remainder realizable.
- Applying the realizable compression scheme to that remainder produces h' with no more error than h on the full original sequence.
- Because the construction uses the original size-k realizable scheme, it yields an unrealizable compression scheme of the same size k.
Key Takeaways
- Compression keeps a small retained subset but evaluates the reconstructed hypothesis on the full training sequence.
- A selects examples, while B reconstructs the hypothesis.
- An ERM hypothesis makes the correctly classified remainder realizable.
- The realizable compression guarantee protects that remainder, leaving possible errors only where the ERM already errs.
- Therefore, a realizable compression scheme of size k yields an unrealizable compression scheme of size k.