Hypothesis Classes and Training Error

When Perfect Fit Is Impossible

Compression is easiest to picture in the realizable setting: some hypothesis in the class H labels every training example correctly. The more difficult setting is unrealizable. In that setting, every hypothesis in H makes at least one mistake on the training sequence. The goal is no longer zero training error. Instead, the goal is to reconstruct a hypothesis whose training error is no worse than that of any competing hypothesis in H.

The Compression Pipeline

Consider an arbitrary training sequence containing m examples. A compression scheme of size k keeps only the examples selected by A, with no more than k examples surviving the selection step. The reconstruction function B then receives those retained examples and produces a hypothesis h'. The number m may be larger than k, but B does not receive all m examples. The compression guarantee is evaluated on the original training sequence, not only on the retained subset.

Selection and Reconstruction

The functions A and B have different responsibilities. A chooses what information to preserve from the training sequence. It may select examples or encode the selected positions, but its role is selection. B takes the retained information and turns it into a hypothesis. Its role is reconstruction. Confusing these roles makes the compression guarantee difficult to follow: A controls what survives, while B controls how that surviving information becomes h'.

The ERM Retention Step

Start with an ERM hypothesis h: a hypothesis in H chosen to minimize training error on the original sequence. If the problem is unrealizable, h may still make mistakes. Discard the examples on which h errs and retain the examples on which h is correct. On this retained subset, h is perfectly consistent. The original unrealizable problem has therefore been converted into a realizable problem on the retained examples.

Why the Error Guarantee Transfers

The reconstructed hypothesis h′ is guaranteed to be correct on every retained example because the realizable compression scheme is applied to a subset that h labels perfectly. Therefore, any error h′ makes on the original sequence must lie among the discarded examples. Those discarded examples are precisely examples on which h already errs. This shows that h′ cannot have more training error than h.

Because h was chosen to minimize training error within H, no hypothesis in H has fewer errors than h on the original sequence. Since h′ has no more errors than h, h′ also has minimum training error within H. The construction therefore extends a realizable compression scheme of size k to the unrealizable setting without increasing the compression size.

Common Reasoning Mistakes

• Assuming that compression requires zero training error on the original sequence.

  In the unrealizable setting, the target is minimum training error within H, not necessarily zero error.

  Fix: Choose an ERM hypothesis and compare the reconstructed hypothesis with that minimum-error benchmark.

• Treating A and B as the same operation.

  A selects the retained examples, while B maps the retained information to the reconstructed hypothesis.

  Fix: Describe A as the selection step and B as the reconstruction step.

• Evaluating h′ only on the retained subset.

  The training-error comparison is made on the full original sequence.

  Fix: Use the retained subset to establish correctness there, then examine the discarded examples to compare full-sequence error.

• Claiming that h′ must be correct on every discarded example.

  The guarantee only forces h′ to be correct on the retained examples. Errors may remain among the discarded examples.

  Fix: Show instead that discarded examples are exactly where h already errs, so h′ cannot have more error than h.

• Increasing the compression size when moving to the unrealizable setting.

  The construction applies the existing realizable scheme only to the examples correctly classified by h, and the stated result preserves size k.

  Fix: Keep the same size bound k for the realizable compression step.

Practice the Construction

1. A size-k compression scheme keeps at most k examples from an arbitrary training sequence and reconstructs a hypothesis from them. A selects the retained information; B reconstructs the hypothesis. In the unrealizable setting, first choose an ERM hypothesis h. Retain only examples that h classifies correctly, creating a realizable subset. Apply the realizable compression scheme to that subset to obtain h′. Since h′ is correct on the retained examples, any errors it makes on the original sequence can occur only where h already errs. Therefore h′ is no worse than h, and because h is an ERM in H, h′ also achieves minimum training error within H. The compression size remains k.