Hypothesis

A Prediction Is Tested on Random Data

A classifier is not evaluated by looking at only one prediction. Instead, imagine selecting a data point according to an underlying distribution D. The correct labeling function f supplies the correct label for that point, while a hypothesis or classifier h supplies its prediction. The classifier error is the probability that h gives a different label from f.

The Three Roles in Error

The distribution D determines which data points can be selected and how likely they are. The function f represents the correct labeling rule. The hypothesis h is the classifier being evaluated. An error occurs precisely when h(x) does not equal f(x). Therefore, classifier error depends on both the distribution D and the correct labeling function f, as well as on the behavior of h on the possible points.

Adding Probabilities of Mistakes

To calculate error for a small, discrete set of possible data points, inspect each point and find where h and f disagree. Then add the probabilities assigned by D to those incorrect points. The result is the probability that a randomly selected point is misclassified.

ERM Searches a Finite Class

A learner may be restricted to a fixed collection of predictors called a hypothesis class. When this class is finite, it contains a finite number of candidate hypotheses, even if the collection is still large. Empirical risk minimization, or ERM, examines how every candidate performs on the training sample and chooses a hypothesis with minimum empirical risk.

Restricting the learner to a finite class gives it a controlled candidate set. The class size matters because a larger collection gives the learner more hypotheses to compare and more opportunities to find a candidate that fits the observed sample unusually well. The amount of training data required therefore grows in relation to the size of the hypothesis class.

Realizability Creates a Perfect Candidate

Because h* has zero true risk, a random sample drawn from D and labeled by f has empirical risk zero for h* with probability 1. Thus ERM has at least one zero-error candidate on the observed sample. Since ERM chooses a hypothesis with minimum empirical risk, every ERM result hS also has empirical risk zero under realizability.

Training Error Versus True Error

Empirical risk describes how a hypothesis performs on the particular training sample S. True risk, also called generalization error or true error, describes how it performs on randomly drawn data points from D. A hypothesis can make no mistakes on S while still disagreeing with f on points that were not represented in S. Therefore, zero empirical risk is not the same statement as low true risk.

Class Size and Sample Requirements

For a finite hypothesis class, the learner compares a fixed number of candidates. The class size is central to the question of whether a hypothesis selected using the training sample will also perform well beyond that sample. As the number of available hypotheses grows, the learner has a larger candidate set and more opportunity to find a hypothesis that fits the observed sample. The required amount of training data grows in relation to the size of the class.

Mistakes in Risk Reasoning

• Treating one incorrect prediction as the classifier error.

  Classifier error is a probability over randomly selected data points from D, not the result of one observation.

  Fix: Consider all possible points and add the probabilities of the points where h(x) differs from f(x).

• Ignoring D or f when discussing error.

  The measurement depends on both D and f.

  Fix: State which points D can select and which labels f assigns before evaluating h.

• Equating zero empirical risk with zero true risk.

  The hypothesis may disagree with f on points not represented in S.

  Fix: Separate the sample-based result from the true risk under D.

• Assuming realizability means every hypothesis is perfect.

  Realizability places at least one zero-true-risk hypothesis h* inside H; it does not make every candidate perfect.

  Fix: Use h* as the guaranteed perfect candidate and remember that ERM chooses among all candidates by empirical risk.

• Assuming a finite hypothesis class automatically removes all overfitting.

  Finiteness provides a controlled candidate set, but the relationship between class size and training-data amount still matters.

  Fix: Consider both the size of H and the amount of training data.

Check Your Understanding

The Complete Reasoning Chain

1. D selects a random data point, and f supplies its correct label.
2. A classifier h makes an error exactly when h(x) differs from f(x).
3. The classifier error is the probability of selecting a point where those labels differ.
4. Generalization error, risk, and true error name this same distribution-level quantity in this setting.
5. ERM evaluates each candidate in a finite hypothesis class on the training sample and selects one with minimum empirical risk.
6. Under realizability, a zero-true-risk hypothesis h* belongs to the class, so h* has zero empirical risk on the random sample with probability 1 and ERM also achieves zero empirical risk.
7. Zero empirical risk is still a statement about the sample; true risk concerns performance on points drawn from D.
8. The larger the hypothesis class, the more the required training-data amount matters for controlling the gap between sample performance and performance under D.