True Error and Generalization
1-NN is analyzed as a sample-dependent hypothesis h_S for binary classification.
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.
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)?
Start with S: The training sample S supplies the examples that 1-NN can compare with the new input.
Measure closeness: Compare x with the examples in S using Euclidean distance ρ.
Select the neighbor: The example with the smallest distance to x becomes the nearest neighbor.
Transfer the label: The 1-NN hypothesis h_S assigns x the label associated with that closest example.
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.
Conditional Probability and Bayes
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.
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?
Interpret η(x): η(x) is the conditional probability of observing label 1 at input x.
Compare the two labels: If label 1 is more likely than label 0 at x, label 1 is the better binary decision.
Apply h*: The Bayes rule h* predicts label 1 at x.
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.
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 η.
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 |
Treating h_S as a fixed rule that is independent of the training sample.
The closest example can change when S changes, so the resulting hypothesis h_S can also change.
Fix:
Keep the subscript S in mind: h_S is the rule created by the particular training sample S.Confusing the nearest neighbor's label with the Bayes decision.
1-NN uses information from the sample, whereas the Bayes rule is defined from η(x).
Fix:
Use h_S for the sample-dependent nearest-neighbor prediction and h* for the benchmark determined by conditional probabilities.Ignoring the distance assumption.
The setting specifies Euclidean distance ρ, and the c-Lipschitz condition connects that distance to changes in η.
Fix:
Interpret closeness using Euclidean distance and connect it to the permitted change in η.Interpreting generalization as performance only on the training sample.
The analysis concerns performance beyond the sample, using fresh random examples and the 0-1 loss.
Fix:
Ask how h_S behaves on examples not used to create it.
Practice and Recall
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.
- 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.