Generalization from Training Data

A Perfect Training Score

A learner can inspect a training sample and choose a predictor that makes the fewest mistakes on those examples. This is a natural strategy, but it has a serious limitation: success on the examples already seen does not guarantee success on new examples from the underlying data distribution. When a predictor fits the training sample well but performs poorly over that broader distribution, the failure is called overfitting.

Tracing the Learning Input

Training data is the learner’s input. It is a finite sequence of labeled examples written as S = ((x₁, y₁), ..., (xₘ, yₘ)). Each pair belongs to X × Y: xᵢ is an input, or domain point, from X, and yᵢ is its label from Y. The individual pairs are training examples, while the complete sequence S is also called the training set.

This labeling step is essential. A collection containing only inputs from X gives the learner domain points, but it does not provide the associated labels from Y. The collection becomes labeled training data when each input is paired with its label.

Restricting ERM with H

Empirical risk minimization, or ERM, chooses a predictor with the lowest possible error over the training data. If ERM may consider every available predictor, it may find one that performs extremely well on the observed sample without performing well over the underlying data distribution.

A hypothesis class is a set of predictors chosen in advance. It is written as H. Each member h of H is a function that maps inputs from X to outputs in Y. After H has been fixed and the training sample S is available, ERM operates inside H: it chooses a member of H with the lowest error on S. The class therefore restricts which candidate predictors ERM is allowed to consider.

Inductive Bias Before Observation

Choosing H before seeing the training data creates inductive bias. The choice expresses a prior structural belief about which predictors are appropriate for the task. ERM remains responsible for selecting among the permitted predictors, while H determines what counts as a permitted choice.

The order matters. If the class is selected before the sample is observed, its restriction is not merely a reaction to the particular examples in S. It is a prior choice about the kinds of predictors the learner will permit. Useful inductive bias should be motivated by prior knowledge about the problem.

A Concrete Labeling Example

Consider a collection of papayas described by color and softness. If the associated tastiness result is recorded for each described papaya, each item is a labeled pair: the description supplies the input and tastiness supplies the label. The resulting collection can serve as training data. If only color and softness are collected, the inputs are present but the labels are missing.

Mistakes About Generalization

• Treating the lowest training error as proof of good performance over the underlying data distribution.

  A predictor can succeed on the examples it has seen while performing poorly over the underlying distribution. That is overfitting.

  Fix: State separately how the predictor performs on the training sample and how it performs over the underlying data distribution.

• Defining a hypothesis class as the predictor selected by ERM.

  H is the set of permitted predictors. ERM selects a member h of H after examining the training sample.

  Fix: Use H for the class and h for an individual predictor that belongs to H.

• Saying that H is chosen after ERM sees the training sample while still calling it prior inductive bias.

  The inductive-bias explanation depends on choosing the hypothesis class before seeing the training data.

  Fix: Describe the order explicitly: choose H, receive S, then apply ERM inside H.

• Calling an unlabeled collection of inputs training data.

  Training data consists of labeled examples, and each example contains an input from X paired with a label from Y.

  Fix: Check that every input has an associated label before calling the collection labeled training data.

Check Your Understanding

The Generalization Picture

1. Training data is a finite sequence S of labeled pairs, and each pair contains an input from X and a label from Y.
2. The individual pairs are training examples, while the complete sequence S is also called the training set.
3. ERM selects a predictor with the lowest training error, but low training error does not guarantee good performance over the underlying data distribution.
4. Overfitting occurs when a predictor succeeds on the observed training examples but performs poorly over the underlying distribution.
5. A hypothesis class H restricts ERM to a chosen set of predictors, and choosing H before seeing the training data creates inductive bias.