True Error

The Learner's Information Problem

A learner wants a prediction rule that makes few errors on the labeled points it may encounter. The difficulty is that the learner does not directly know the entire probability distribution D that produces examples, and it does not directly inspect the unknown target function that supplies their labels. Instead, the learning algorithm receives a training set S. That sample is the evidence available for comparing prediction rules.

Two Sources for Measuring Error

The same prediction rule h can be evaluated in two related ways. True error, also called risk, asks how likely h is to make an error on labeled points drawn according to the probability distribution D. Empirical risk evaluates h using the training data S. The prediction rule is the object being evaluated; D and S are the different sources used for that evaluation.

Why Training Data Becomes the Substitute

The learner cannot directly minimize true error because D is unknown. It does, however, have access to S and can inspect how a prediction rule performs on the training examples. Empirical risk is therefore the training-data measure used to compare prediction rules. This does not change the learner's goal: the desired outcome remains a prediction rule with low true error.

ERM Selection on One Sample

Labels and Prediction Rules

A training set is sampled from an unknown distribution and labeled by an unknown target function. A prediction rule h makes predictions for the examples. Its error is determined by comparing those predictions with the labels carried by the examples. The learner can use these observed comparisons on S, but it cannot directly inspect the complete target function or the complete source distribution.

Common Confusions

• Treating training error as true error

  Training error is observable on S, whereas true error is defined with respect to labeled points drawn according to the unknown distribution D.

  Fix: Call the training-data measure empirical risk and reserve true error, or risk, for evaluation with respect to D.

• Saying that ERM directly inspects D

  The learner does not know D and cannot directly use knowledge of it.

  Fix: Explain that ERM uses the accessible training set S to compare predictors.

• Confusing the target function with the learned predictor

  The source distinguishes the unknown target function that labels the sample from the predictor produced by the learning algorithm.

  Fix: Keep the roles separate: the target function supplies labels, while h is the prediction rule being evaluated.

• Claiming that every learning algorithm performs the same candidate search

  The ERM criterion concerns which measured error is favored; it does not claim that every algorithm follows one identical search procedure.

  Fix: State the criterion without adding a specific search mechanism: predictors are judged by their error on the training sample, and ERM favors the minimum.

Check Your Understanding

Key Takeaways

1. True error, or risk, evaluates a prediction rule h with respect to labeled points drawn according to the probability distribution D.
2. Empirical risk evaluates the same kind of prediction rule using the available training data S.
3. The learner wants low true error but cannot directly inspect the unknown distribution D or target function.
4. ERM uses the training set as evidence, compares candidate predictors by their measured errors on S, and favors the predictor with the minimum empirical risk.
5. Training error and true error are related measures, but they must not be treated as the same quantity.