Relaxing the Realizability Assumption

The Evaluation Problem

A learner must choose a prediction rule h, but choosing a rule is not enough. The learner also needs a way to evaluate how well that rule predicts labels. Two evaluation sources matter: the probability distribution D and the training data S. True error uses labeled points drawn according to D. Empirical risk uses the particular training data S available to the learner.

True Error Under D

The true error, also called the risk, of a prediction rule h asks how likely h is to make an error on labeled points drawn according to the probability distribution D. The prediction rule is evaluated against the labeled examples that D produces, rather than only against the examples that happened to appear in one training sample.

The distribution D matters in two connected ways. It determines which labeled points are relevant to the evaluation, and it determines how those points contribute to the overall assessment through the distribution from which they are drawn. True error therefore describes performance with respect to D, not merely performance on a finite list of observed examples.

Training Data and Empirical Risk

Empirical risk and true error evaluate the same kind of object: a prediction rule h. Their difference is the source used for evaluation. True error uses labeled points associated with the unknown distribution D. Empirical risk uses the observed training data S.

From Observable Risk to Desired Risk

The learner's goal and the learner's information are not the same thing. The learner wants a prediction rule h with low true error because true error describes performance with respect to D. However, the learner cannot directly use D because D is unknown. The learner can inspect S and use empirical risk as an accessible way to evaluate h.

When Perfect Prediction Is Not Required

Relaxing the realizability assumption means that the discussion does not require a prediction rule to classify every possible example associated with D correctly. Some errors may remain part of the evaluation. In that setting, the useful question is not whether h makes no errors everywhere, but how much error h has under D and how much error it has on the observed training data S.

This change does not replace the two evaluation measures. True error still uses D, and empirical risk still uses S. Relaxing the assumption changes how the errors are interpreted: errors are quantities to evaluate and compare rather than evidence that the entire learning setup has failed simply because a perfect rule is unavailable.

Common Misunderstandings

• Treating true error as the error measured only on S.

  True error is evaluated with respect to labeled points drawn according to D, while S is the source for empirical risk.

  Fix: Use true error for the distribution-based evaluation and empirical risk for the training-data evaluation.

• Assuming the learner knows D.

  The learner does not know the data-generating distribution D.

  Fix: Remember that the learner has access to S and can evaluate empirical risk from that training data.

• Assuming that the learner's accessible measure is automatically the learner's final goal.

  The learner wants a prediction rule with low true error, but uses information from S because D is unknown.

  Fix: Keep the goal, low true error, separate from the accessible evaluation, empirical risk.

• Interpreting relaxed realizability as ignoring errors.

  True error and empirical risk still measure the errors made by h; the distinction between D and S remains central.

  Fix: Evaluate the remaining errors using the appropriate source: D for true error and S for empirical risk.

Check Your Understanding

Key Takeaways

1. True error, or risk, evaluates a prediction rule h on labeled points drawn according to the probability distribution D.
2. Empirical risk evaluates the same prediction rule h using the training data S.
3. The learner wants low true error but does not know D.
4. The learner does have access to S, so empirical risk is the directly available evaluation measure.
5. Relaxing the realizability assumption allows the discussion to focus on measuring and comparing errors even when perfect classification is not required.