Compression Bounds
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.
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?
- 1Selection
A selects indices 2 and 4 from the full training set.
- 2Compression set
The examples at indices 2 and 4 become the selected examples used for reconstruction.
- 3Reconstruction
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
Common mistake Treating A as the function that produces the hypothesis.
What it looks likeA selects indices, and the explanation stops there.
Why it failsThe source assigns selection to A and reconstruction to B.
Do this insteadDescribe A as selecting k indices and B as using the corresponding examples to produce h' in H.
Common mistake Saying that B uses the entire training set directly.
What it looks likeB receives all training examples even after compression.
Why it failsThe scheme reconstructs a hypothesis from the selected examples.
Do this insteadState that B uses the examples corresponding to the indices selected by A.
Common mistake Checking zero loss only on the selected examples.
What it looks likeThe selected examples agree with h', so the scheme is declared valid.
Why it failsThe zero-loss requirement applies to the original training set.
Do this insteadCheck that h' agrees with every example in the original training set.
Common mistake Forgetting that h' must belong to H.
What it looks likeB produces an arbitrary function without relating it to the hypothesis class.
Why it failsThe reconstructed result is required to be a hypothesis h' in H.
Do this insteadInclude 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
Yes
The reconstructed hypothesis must have zero loss on the original training set, so agreement is required for every original training example.
Summary
- 1A hypothesis class H is a set of functions from X to Y.
- 2A compression scheme of size k uses A to select k indices from the full training set.
- 3The examples corresponding to those indices are used by B to produce h' in H.
- 4The reconstructed hypothesis must have zero loss on the original training set, meaning it agrees with every original training example.
- 5Compression changes which examples are used for reconstruction, not the full set used for the zero-loss requirement.
At a glance
- 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.