Generalization

A Perfect Training Score

A hypothesis that makes no mistakes on its training set can look successful. But the training set contains only the instances used to choose the hypothesis. Generalization asks a broader question: how does the hypothesis perform on the true distribution that produces instances? Overfitting occurs when a hypothesis fits the training data too well but performs poorly on that true distribution.

The Papaya Illustration

The source illustrates the distinction with a papaya prediction problem. The input has two features: softness and color. Instances are distributed 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

Empirical risk minimization, or ERM, relies on performance on the training set. It therefore prefers a hypothesis with low training error. That preference can select an overfitting hypothesis when a hypothesis fits the observed sample exceptionally well but performs poorly on the true distribution. ERM is using the evidence supplied by the sample; the problem is that sample performance does not guarantee distribution performance.

The 1-NN Hypothesis

The 1-nearest-neighbor rule classifies a new point using the closest example in a training sample. In the binary-classification setting described by the source, labels belong to the set containing 0 and 1, the loss is the 0-1 loss, the domain is the unit cube in d dimensions, and closeness is measured with Euclidean distance. Because its prediction depends on the particular training sample, the rule is described as a sample-dependent hypothesis h_S.

The subscript S matters: changing the training sample can change which observed point is nearest and therefore can change the resulting hypothesis. This makes h_S different in kind from a rule defined directly from the underlying distribution.

Bayes as the Distribution Benchmark

This gives two different sources of a classification rule. The 1-NN hypothesis h_S uses the closest observed example in a particular sample. The Bayes optimal rule h* is defined from the conditional probability function associated with the underlying distribution. One is sample-dependent; the other is distribution-defined.

Smoothness Through Lipschitzness

The c-Lipschitz condition connects distance between inputs with change in their conditional label probabilities. Its role is to restrict how quickly η(x) can change: inputs that are close under Euclidean distance cannot have an unrestricted difference in their conditional probabilities. This smoothness assumption helps the analysis relate a new point to a nearby training example.

The condition is important for 1-NN analysis because 1-NN transfers the label information of a nearby observed example to a new input. A smooth conditional probability function provides a restriction on how different the label probabilities can be at those two nearby locations.

Assumptions Behind the Analysis

• Domain: inputs lie in X = [0, 1]^d.
• Labels: the classification problem is binary, with labels in the set containing 0 and 1.
• Loss: mistakes are measured with the 0-1 loss.
• Distance: Euclidean distance ρ is used to identify the nearest example.
• Sample dependence: the 1-NN hypothesis is written h_S because it depends on the training sample S.
• Conditional probability: η(x) supplies the distribution-based quantity from which the Bayes rule h* is defined.
• Smoothness: the c-Lipschitz condition restricts how quickly η(x) can change.

These assumptions work together rather than independently. The domain and distance describe where inputs are and what nearby means. The binary labels and 0-1 loss describe the prediction task and its mistakes. The sample defines the sample-dependent 1-NN rule. The conditional probability function and its smoothness condition provide the distributional structure used to compare that rule with the Bayes benchmark.

Common Reasoning Errors

• Treating zero training error as proof of generalization.

  The true distribution includes instances beyond the observed sample, and the source gives an example with zero training error but true error equal to one half.

  Fix: Evaluate training performance and true-distribution performance as separate questions.

• Assuming ERM directly optimizes true-distribution performance.

  ERM relies on training-set performance, so it can select a hypothesis that overfits.

  Fix: Remember that ERM can prefer a sample-fitting hypothesis whose broader performance is poor.

• Describing 1-NN as a fixed rule independent of the data.

  The 1-NN rule is sample-dependent and is denoted h_S.

  Fix: Track the training sample when describing a 1-NN hypothesis.

• Confusing the Bayes rule with the nearest-neighbor rule.

  The Bayes rule is defined from η(x), while 1-NN uses the closest example in a training sample.

  Fix: Identify whether a prediction rule comes from the sample or from the underlying distribution.

Practice the Distinction

Key Takeaways

1. Overfitting means fitting the training data too well while performing poorly on the true distribution.
2. Zero empirical error does not guarantee low true error.
3. ERM can select an overfitting hypothesis because it relies on training-set performance.
4. A 1-NN hypothesis h_S depends on the training sample and predicts from the closest observed example.
5. The Bayes rule h* is defined from η(x) and serves as the optimal distribution-based benchmark.
6. The c-Lipschitz condition restricts how quickly η(x) can change as inputs vary, supporting the analysis of nearby examples.