True Error and Generalization

True-error analysis studies how the sample-dependent rule performs on fresh examples under the stated domain, label, distance, sample, and smoothness assumptions.

Programming

From Sample to Prediction

Suppose a classifier receives a training sample and later encounters a new input x. The 1-nearest-neighbor method does not use a single permanently fixed rule independent of the sample. Instead, the particular training sample determines which example is closest to x, and that closest example supplies the prediction. This makes 1-NN a sample-dependent hypothesis, written h_S, where S represents the training sample.

Given a training sample and a new input, how does 1-NN select the closest example and produce h_S(x)?

Worked example

A Sample-Dependent Prediction

A training sample contains labeled examples. A new point x is closer, under Euclidean distance ρ, to one particular training example than to all the others. What determines h_S(x)?

1
Start with S
The training sample S supplies the examples that 1-NN can compare with the new input.
2
Measure closeness
Compare x with the examples in S using Euclidean distance ρ.
3
Select the neighbor
The example with the smallest distance to x becomes the nearest neighbor.
4
Transfer the label
The 1-NN hypothesis h_S assigns x the label associated with that closest example.

Result

The prediction depends on the particular sample S because changing S can change which example is closest to x.

The Analysis Setting

The analysis uses binary classification. Inputs come from the domain X = [0, 1]^d, labels belong to Y = {0, 1}, and closeness is measured with Euclidean distance ρ. Performance is studied with the 0-1 loss, which treats a classification as either correct or incorrect. These choices specify the setting in which the true error of 1-NN is examined.

How do the domain, labels, distance, sample, and conditional probability fit together in the error analysis?

Conditional Probability and Bayes

Definition

The conditional probability function η(x) describes the probability that the label is 1 given the input x: η(x) = P(Y = 1 | X = x). The Bayes rule h* uses η(x) to choose the better of the two binary labels at each input. It predicts 1 when η(x) is at least as large as the probability of label 0, and predicts 0 when label 0 is more likely.

How does η(x) determine whether the Bayes rule predicts 0 or 1 at a particular input?

Worked example

Using η(x) as the Benchmark

At one input x, η(x) indicates that label 1 is more likely than label 0. Which label does the Bayes rule choose?

1
Interpret η(x)
η(x) is the conditional probability of observing label 1 at input x.
2
Compare the two labels
If label 1 is more likely than label 0 at x, label 1 is the better binary decision.
3
Apply h*
The Bayes rule h* predicts label 1 at x.

Result

The Bayes rule is defined by the conditional label probabilities, so it serves as the optimal benchmark for comparing a sample-dependent rule such as h_S.

Smoothness Through Lipschitzness

The c-Lipschitz condition restricts how quickly η can change across the domain. For inputs x and x', the difference between η(x) and η(x') is bounded by c times their Euclidean distance. In practical terms, nearby inputs cannot have arbitrarily different conditional probabilities under this assumption. The constant c controls how strongly distance limits the possible change in label probability.

How does the distance between two inputs limit the difference between η(x) and η(x')?

In the real world

Imagine two inputs that are very close under Euclidean distance. Under the c-Lipschitz assumption, their values of η cannot differ without limit. The closer the inputs are, the tighter the distance-based restriction on the possible change in conditional label probability. This is why the nearest training example can provide useful information about a new point in the analysis.

True Error Beyond the Sample

Once a training sample S has produced the hypothesis h_S, the analysis asks how that hypothesis performs beyond the examples used to construct it. This is the role of true error and generalization: the sample-dependent rule is evaluated on fresh random examples rather than only on the training sample. The result depends on the domain, binary labels, Euclidean distance, training sample, and regularity assumption on η.

How does a fixed training sample become a hypothesis, and how is that hypothesis evaluated on examples beyond the sample?

Comparing h_S with h*

Feature	1-NN rule h_S	Bayes rule h*
What determines it	A particular training sample S	The conditional probability function η(x)
How it predicts	Uses the label of the closest training example	Chooses the more likely binary label at x
Role in analysis	The learned rule whose true error is studied	The optimal benchmark
Dependence on S	Changes when the training sample changes	Defined from η(x), not from a particular sample

The central distinction between the sample-dependent 1-NN hypothesis and the Bayes optimal rule.

Common mistake
Treating h_S as a fixed rule that is independent of the training sample.
What it looks like
Assuming that every possible training sample would make 1-NN produce the same prediction for x.
Why it fails
The closest example can change when S changes, so the resulting hypothesis h_S can also change.
Do this instead
Keep the subscript S in mind: h_S is the rule created by the particular training sample S.
Common mistake
Confusing the nearest neighbor's label with the Bayes decision.
What it looks like
Calling the label copied from the closest training example the Bayes label.
Why it fails
1-NN uses information from the sample, whereas the Bayes rule is defined from η(x).
Do this instead
Use h_S for the sample-dependent nearest-neighbor prediction and h* for the benchmark determined by conditional probabilities.
Common mistake
Ignoring the distance assumption.
What it looks like
Describing two inputs as close without specifying the distance used in the analysis.
Why it fails
The setting specifies Euclidean distance ρ, and the c-Lipschitz condition connects that distance to changes in η.
Do this instead
Interpret closeness using Euclidean distance and connect it to the permitted change in η.
Common mistake
Interpreting generalization as performance only on the training sample.
What it looks like
Concluding that 1-NN generalizes well because it handles the observed examples.
Why it fails
The analysis concerns performance beyond the sample, using fresh random examples and the 0-1 loss.
Do this instead
Ask how h_S behaves on examples not used to create it.

Practice and Recall

MEDIUM

A binary classification problem uses X = [0, 1]^d, labels in Y = {0, 1}, Euclidean distance ρ, and a c-Lipschitz conditional probability function η. Explain, in your own words, the full path from a training sample S to the true-error analysis of 1-NN. Your response should mention h_S, the nearest example, fresh examples, η(x), h*, and the role of the c-Lipschitz condition.

Hints

Begin by explaining what the training sample determines.
Then distinguish the prediction made by h_S from the decision made by h*.
Finish by explaining why the distance and c-Lipschitz assumptions matter when evaluating performance beyond the sample.

Your attempt (not saved)

1
1-NN creates a hypothesis h_S from a particular training sample. For a new input, it uses Euclidean distance to find the closest training example and uses that example's label. The Bayes rule h* is a separate benchmark defined by η(x), the conditional probability of label 1 given x. The c-Lipschitz condition limits how much η can change between inputs as a function of their distance. True-error analysis studies how the sample-dependent rule performs on fresh examples under the stated domain, label, distance, sample, and smoothness assumptions.

Key Takeaways

The 1-NN hypothesis h_S depends on the particular training sample.
For a new input, 1-NN uses Euclidean distance to select the closest labeled example.
The conditional probability η(x) determines the Bayes optimal benchmark h*.
The c-Lipschitz condition limits how quickly η can change between inputs.
True error measures how the sample-dependent rule performs on examples beyond the training sample.

Related concepts

More concepts starting with T