Realizable Compression Schemes

Compression in the unrealizable setting seeks minimum error within H, not necessarily zero error.

Programming

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.

What is retained from a sequence of m examples, and how does it determine the reconstructed hypothesis?

Definition

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.

How does information move from the full training sequence through A and B?

Worked example

Tracing A and B

Suppose a training sequence contains m examples and a size-k compression scheme is applied.

1
Selection
A examines the full sequence and chooses the examples that will be retained. The retained collection contains at most k examples.
2
Transfer
Only the retained collection is passed onward; B does not receive the discarded examples as part of its compression input.
3
Reconstruction
B maps the retained collection to the reconstructed hypothesis h'.
4
Evaluation
The performance of h' is compared on the original m-example sequence, rather than only on the retained collection.

Result

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.

How does an ERM hypothesis turn an unrealizable full sequence into a realizable subset?

The Unrealizable Construction

1
Choose an ERM hypothesis h in H for the full training sequence.
2
Identify the examples on which h is correct.
3
Apply the assumed realizable compression scheme of size k only to that correctly classified subset.
4
Let the realizable scheme return h'.
5
Use h' as the hypothesis reconstructed for the original, possibly unrealizable sequence.

What changes when the realizable compression scheme is applied only to examples consistent with an ERM hypothesis?

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

The unrealizable construction uses a realizable guarantee on the subset where the ERM hypothesis is correct.

Why the Size Stays k

Worked example

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.

1
Partition by h
Separate the sequence into the examples correctly classified by h and the examples on which h errs.
2
Compress the correct part
Apply the realizable compression scheme to the correctly classified part. It retains at most k examples and reconstructs h'.
3
Check retained examples
The realizable guarantee says h' is correct on the retained, realizable part used by the scheme.
4
Locate possible errors
Any remaining error of h' on the original sequence can only be on examples discarded because h was already incorrect.
5
Compare errors
The possible error locations for h' are contained among locations where h errs, so h' has no more error than h.

Result

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

Common mistake
Treating A as the function that reconstructs the hypothesis.
What it looks like
Saying that A receives the training sequence and directly returns h'.
Why it fails
A selects the retained examples. B maps those retained examples to the reconstructed hypothesis.
Do this instead
Trace the roles separately: A selects, then B reconstructs.
Common mistake
Evaluating h' only on the retained subset.
What it looks like
Claiming success because h' is correct on the examples passed to B.
Why it fails
The compression guarantee is evaluated against the original training sequence.
Do this instead
After reconstruction, compare h' with hypotheses in H on the full sequence.
Common mistake
Assuming that the full unrealizable sequence becomes realizable.
What it looks like
Saying that ERM finds a hypothesis that is correct on every original example.
Why it fails
In the unrealizable setting, every hypothesis in H makes at least one mistake.
Do this instead
Use h to identify a correctly classified subset. That subset, not necessarily the full sequence, is realizable.
Common mistake
Adding the ERM-error examples to the compressed representation.
What it looks like
Keeping the selected examples from the realizable subset and also retaining every example where h errs.
Why it fails
The construction relies on the realizable scheme applied to the correct subset, and its size remains k.
Do this instead
Use the realizable compression output of size k and account for the discarded examples through the error comparison.

Check Your Understanding

MEDIUM

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.

Your attempt (not saved)

What do you think happens?

If the assumed realizable compression scheme has size k, does the unrealizable construction require a larger compression size?

Yes, because the ERM errors must also be retained
No, because the realizable scheme is applied to the correctly classified subset
It depends on the number of examples in the original sequence

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

1
A size-k compression scheme retains at most k examples from an m-example training sequence and reconstructs a hypothesis from them.
2
A selects the retained examples; B maps those examples to the reconstructed hypothesis.
3
In an unrealizable problem, an ERM hypothesis h identifies a subset on which h is correct, making that remainder realizable.
4
Applying the realizable compression scheme to that remainder produces h' with no more error than h on the full original sequence.
5
Because the construction uses the original size-k realizable scheme, it yields an unrealizable compression scheme of the same size k.

At a glance

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.

Related concepts

More concepts starting with R