Hypothesis Class

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.

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.

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.

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.

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.

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.

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.