Compression Bounds
A hypothesis class H is a set of functions from X to Y.
From Training Set to Hypothesis
A compression scheme describes how a hypothesis can be reconstructed from only a selected subset of its training data. Instead of using the entire training set directly during reconstruction, the scheme selects training-example indices and then uses the corresponding examples to produce a hypothesis in the hypothesis class.
The central idea is selective reconstruction: A identifies which training examples matter for the compression, and B turns those selected examples into a hypothesis h' in H.
The Compression Scheme
For a hypothesis class H, a compression scheme of size k uses two functions, A and B. Function A selects k indices from the full training set. Function B uses the corresponding selected examples to produce a hypothesis h' in H.
A and B have different jobs. A performs the selection step: it chooses indices in the full training set. Those indices point to the examples that form the compressed information. B performs the reconstruction step: it receives the corresponding selected examples and produces h', a member of H. Thus, A does not itself produce the hypothesis, and B does not select arbitrary examples independently of A's selection.
A Small Compression Example
Consider a generated example with a training set containing five labeled examples. Suppose the compression scheme has size k equal to two. Function A selects the indices of the second and fourth examples. The corresponding two examples are the compressed information passed to B. Function B uses those selected examples to produce h' in H.
Tracing A and B
A compression scheme has size k equal to two. A receives five training examples and selects indices 2 and 4. What does B receive, and what must B produce?
Selection: A selects indices 2 and 4 from the full training set.
Compression set: The examples at indices 2 and 4 become the selected examples used for reconstruction.
Reconstruction: B uses those selected examples to produce a hypothesis h' in H.
B receives the examples at indices 2 and 4 and produces h' in H.
Checking the Original Training Set
Selecting examples and producing h' is not enough by itself. The reconstructed hypothesis must have zero loss on the original training set. In the terms provided for this concept, that means h' must agree with every example in the original training set, including examples that were not selected by A.
The compression set is used to reconstruct h', but the zero-loss condition is checked against the entire original training set. A hypothesis that matches only the selected examples does not satisfy the stated requirement unless it also agrees with all the remaining original examples.
Common Interpretation Errors
Treating A as the function that produces the hypothesis.
The source assigns selection to A and reconstruction to B.
Fix:
Describe A as selecting k indices and B as using the corresponding examples to produce h' in H.Saying that B uses the entire training set directly.
The scheme reconstructs a hypothesis from the selected examples.
Fix:
State that B uses the examples corresponding to the indices selected by A.Checking zero loss only on the selected examples.
The zero-loss requirement applies to the original training set.
Fix:
Check that h' agrees with every example in the original training set.Forgetting that h' must belong to H.
The reconstructed result is required to be a hypothesis h' in H.
Fix:
Include membership in H when describing the output of B.
Practice the Reconstruction Path
A compression scheme of size k receives a full training set. Function A selects k indices, and function B receives the corresponding examples. Explain the roles of A and B, identify the object produced by B, and state which set must be used to verify zero loss.
Hints
- Separate selection from reconstruction.
- The selected indices identify the examples passed to B.
- The zero-loss check uses the original training set, not only the selected examples.
What do you think happens?
If A selects only some training examples, must h' agree with the unselected examples as well?
Reveal answer
Answer: Yes
The reconstructed hypothesis must have zero loss on the original training set, so agreement is required for every original training example.
Summary
- A hypothesis class H is a set of functions from X to Y.
- A compression scheme of size k uses A to select k indices from the full training set.
- The examples corresponding to those indices are used by B to produce h' in H.
- The reconstructed hypothesis must have zero loss on the original training set, meaning it agrees with every original training example.
- Compression changes which examples are used for reconstruction, not the full set used for the zero-loss requirement.
Key Takeaways
- A compression scheme of size k selects k training-example indices and uses the corresponding examples to reconstruct a hypothesis.
- A is the selection function, while B is the reconstruction function.
- B produces a hypothesis h' that belongs to H.
- The zero-loss requirement is evaluated on the entire original training set.