Hypothesis Class

From Candidates to One Predictor

A learner does not always choose from every possible predictor. Instead, it may be restricted to a hypothesis class H, a set of functions from X to Y. Each function is a candidate rule for mapping inputs to predictions. Learning then becomes a controlled selection problem: examine the candidates, measure their performance on the training sample, and choose one.

This restriction matters because a finite class contains a finite number of candidates. A class can still represent a broad modeling idea while being finite. For example, predictors implementable by a C++ program using at most 10^9 bits of code form one example described in the source. Axis-aligned rectangles also become a finite class when their real-valued parameters are represented using a 64-bit floating-point representation.

Compressing Training Information

A compression scheme of size k describes how to reconstruct a hypothesis using only k selected labeled examples from the full training set. It uses two functions. Function A selects k indices from the complete training set. Function B receives the corresponding selected examples and produces a reconstructed hypothesis h' in H.

The key point is that A does not directly return the final hypothesis. A identifies which training examples are retained. B then uses those retained examples to construct a hypothesis in the class. The rest of the training set is not used as input to B for the reconstruction step.

Checking the Original Sample

Reconstruction is not complete merely because B returns a hypothesis in H. The reconstructed hypothesis must also have zero loss on the original training set. The check therefore compares h' with every example in the full training set, not only with the k examples selected by A.

This requirement separates two roles for the data. The selected examples are sufficient inputs for reconstruction, while the complete original sample is used to verify the zero-loss condition. A hypothesis that fits only the retained examples has not yet met the compression-scheme requirement.

ERM Within a Finite Class

Empirical risk minimization, or ERM, examines how each candidate in a fixed collection performs on the training sample and chooses a hypothesis with minimum empirical risk. When the hypothesis class is finite, the learner is choosing from a finite number of candidates rather than from an unrestricted collection.

Restricting the learner to a finite class can limit overfitting because the learner has fewer candidate hypotheses available for selection. The class may still be large, so finiteness does not mean that the modeling idea is extremely narrow. The learning question remains whether the training-based choice will also perform well beyond the observed sample.

Realizability and Its Consequence

Because h* has zero true risk, it has empirical risk zero on the random training sample with probability 1. Thus ERM has an available candidate that makes no errors on the observed sample. Since ERM chooses a hypothesis with minimum empirical risk, every ERM result hS also has empirical risk zero in this setting.

Sample Fit Versus Distribution Performance

Empirical risk describes a hypothesis's performance on the observed training sample. True risk describes its performance under the data distribution. Therefore, zero empirical risk means that the hypothesis makes no errors on the available sample, while low true risk means that it performs well beyond that sample under the distribution.

Why Class Size Affects Data Needs

For a finite hypothesis class, the relationship between training-based selection and performance beyond the sample is tied to two conditions: the size of the class and the amount of training data. As the number of candidate hypotheses grows, the required amount of training data grows in relation to the size of the class.

The reason to track class size is that ERM is selecting among all available candidates. A finite class gives a controlled candidate set, but a larger finite set still gives the learner more candidates to compare. The sample-size requirement therefore cannot be discussed independently of how many hypotheses the class contains.

Mistakes in Reasoning

• Treating A as the function that directly constructs the hypothesis.

  In the compression scheme, A performs selection, while B uses the selected labeled examples to produce h' in H.

  Fix: Remember the division of labor: A selects; B reconstructs.

• Checking zero loss only on the selected examples.

  The zero-loss requirement applies to the original training set, not just the compressed subset.

  Fix: Evaluate the reconstructed hypothesis against every example in the original training set.

• Concluding that zero empirical risk means zero true risk.

  Empirical risk concerns the sample, whereas true risk concerns the data distribution.

  Fix: State separately what was established on the sample and what remains to be established under the distribution.

• Assuming realizability guarantees that every hypothesis in H has zero empirical risk.

  Realizability guarantees an available zero-risk target hypothesis, and therefore a zero-empirical-risk benchmark on the sample. It does not say that every candidate has zero risk.

  Fix: Use h* to explain why the ERM minimum is zero under the stated setting.

• Ignoring the size of the hypothesis class when discussing training data.

  The required amount of training data grows in relation to the size of the class.

  Fix: Always identify both the candidate-class size and the available training amount.

Practice the Selection Logic

Key Takeaways

1. A hypothesis class H is a set of functions from X to Y.
2. A size-k compression scheme uses A to select k training-example indices and B to reconstruct a hypothesis in H from the corresponding labeled examples.
3. The reconstructed hypothesis must have zero loss on the entire original training set.
4. ERM chooses a minimum-empirical-risk hypothesis from a finite class; under realizability, every ERM result has zero empirical risk on the random sample with probability 1.
5. Zero empirical risk is a statement about the observed sample, not the same as low true risk under the data distribution.
6. The required training amount grows in relation to the size of the finite hypothesis class.