True Risk and Empirical Risk

The Hidden Question Behind Zero Error

A hypothesis with no mistakes on its training set can look successful. But the training set is only the data used to choose the hypothesis. The more important question is how that hypothesis behaves on the true distribution that produces instances. Overfitting occurs when a hypothesis fits the training data too well but performs poorly on the true distribution.

Two Ways to Measure Performance

Empirical risk describes performance computed from the finite training sample: it asks how well the hypothesis handles the instances already observed. True risk describes performance on the true distribution: it asks how well the hypothesis handles the broader world represented by the distribution. These are different questions, even when they are applied to the same hypothesis.

The Papaya Prediction Problem

Consider predicting whether a papaya tastes good using two features: softness and color. In the source's geometric construction, instances are spread uniformly through a gray square. The true labeling rule assigns label 1 to points inside an inner blue square and label 0 to points outside it. The gray square has area 2, while the blue square has area 1.

Why ERM Can Overfit

The empirical risk minimization rule relies on training-set performance. It selects a hypothesis according to how well that hypothesis performs on the observed training data. Therefore, if a memorizing hypothesis has the lowest observed training error, ERM can select it even when another hypothesis captures the underlying labeling pattern and performs better on the true distribution.

Memorizing or Learning the Pattern

A hypothesis that memorizes the observed sample can match the labels of the examples it has already seen without capturing the rule that assigns labels more broadly. A hypothesis that captures the underlying labeling pattern aims to reflect how labels are assigned throughout the true distribution. The distinction matters because training performance examines the observed examples, while true-distribution performance examines behavior beyond those examples.

Mistakes About Training Success

• Treating zero empirical error as proof of low true error.

  The source gives a predictor with zero training error and true error equal to one half.

  Fix: Separate performance on the observed sample from performance on the true distribution.

• Assuming the ERM-selected hypothesis must capture the underlying labeling pattern.

  The ERM rule relies on training-set performance, so it can select an overfitting hypothesis.

  Fix: Recognize that the lowest observed error can belong to a hypothesis that memorizes the sample.

• Using the words training performance and true-distribution performance as if they described the same evaluation.

  The training set is only the data used to choose the hypothesis; the true distribution represents the broader source of instances.

  Fix: Name which set or distribution is being used whenever you discuss error.

Check Your Understanding

Key Takeaways

1. Empirical risk measures how a hypothesis performs on the observed training sample.
2. True risk measures how the hypothesis performs on the true distribution that produces instances.
3. Overfitting occurs when training performance is unusually favorable while performance on the true distribution is poor.
4. Zero empirical error does not guarantee low true error.
5. Because ERM relies on training-set performance, it can select a hypothesis that memorizes the sample instead of capturing the underlying labeling pattern.