Bayes Optimal Classification
1-NN is analyzed as a sample-dependent hypothesis h_S for binary classification.
From a Sample to a Prediction
Suppose a new point must be assigned one of two labels, 0 or 1. The 1-nearest-neighbor rule uses the training sample to make that decision: it finds the sampled point closest to the new point and assigns the new point the closest point's label. Because the selected neighbor depends on the particular sample, this classifier is represented as a sample-dependent hypothesis h_S.
Following One Query Through 1-NN
A query point x is evaluated using a training sample S. One sampled point is the closest point to x, and that point has label 1. What does the 1-NN hypothesis h_S assign to x?
Search the sample: Compare the query point with the sampled points using the distance ρ.
Select the neighbor: Choose the sampled point with the smallest distance from x.
Transfer the label: The 1-NN rule assigns x the label carried by that closest sampled point.
The sample-dependent hypothesis h_S assigns x the label 1.
The Bayes Benchmark
The sample-dependent rule h_S is not the only rule considered. The analysis also defines a Bayes rule h*. It is built from the conditional probability function η(x), which describes the conditional probability of a label at input x. In binary classification, the Bayes rule uses the label with the larger conditional probability at x. Thus h* is determined by the underlying distribution rather than by which particular training point happens to be closest. It serves as the optimal benchmark for evaluating the true error of 1-NN.
Comparing Two Decisions
For a particular input x, suppose the closest sampled point has label 0. At the same input, suppose the conditional probability of label 1 is larger than the conditional probability of label 0. What do h_S and h* predict?
Apply 1-NN: The sample-dependent rule follows the closest sampled point, so h_S predicts label 0.
Apply the Bayes rule: The Bayes rule follows η(x) and chooses the label with the larger conditional probability, so h* predicts label 1.
Interpret the difference: The two rules use different information: h_S uses the realized training sample, while h* uses the conditional label probabilities of the underlying distribution.
The two rules can make different decisions for the same input: h_S(x) = 0 while h*(x) = 1.
Reading η(x)
The function η(x) is the conditional probability function for the label at input x. It summarizes how likely the possible binary labels are at that location. The Bayes optimal rule h* examines these conditional probabilities and selects the label with the larger probability.
The important distinction is between evidence from a finite sample and information from the conditional distribution. A nearby sampled point provides the evidence used by h_S. The function η(x) provides the probability-based description used by h*. The analysis asks how reliably the first rule approaches the performance of the second when evaluated beyond the training sample.
Smoothness Through Distance
The c-Lipschitz condition places a smoothness restriction on η. For two domain points x and x', the change in their conditional label probabilities is bounded by a constant c multiplied by their Euclidean distance ρ(x, x'). In notation, the condition is written as |η(x) − η(x')| ≤ cρ(x, x'). Its interpretation is more important than the symbols: points that are close in the domain cannot have arbitrarily different conditional label probabilities, while points farther apart are allowed a larger difference.
Interpreting the Lipschitz Bound
Compare two pairs of points. Pair A contains very close points, while Pair B contains points that are farther apart. How does the c-Lipschitz condition constrain changes in η?
Pair A: Because the Euclidean distance is small, the bound cρ(x, x') is small. The conditional probabilities cannot differ by more than that small bound.
Pair B: Because the Euclidean distance is larger, cρ(x, x') is larger. The condition permits a larger difference between the conditional probabilities.
Main interpretation: The condition does not say that η is constant. It limits how quickly η can change as points move through the domain.
Euclidean closeness implies a tighter limit on the change in conditional label probability.
Assumptions Behind the Error Analysis
The analysis fixes a setting in which the behavior of 1-NN can be studied precisely. The domain is X = [0, 1]^d, the labels are binary with Y = {0, 1}, the loss is the 0-1 loss, and distance is measured with the Euclidean distance ρ. A training sample supplies the examples used by h_S. The conditional probability function η and its c-Lipschitz restriction describe how labels behave across the domain. Together, these assumptions connect the geometry of the sample to the probability of labels and support an analysis of the true error of 1-NN.
Common Reasoning Errors
Treating h_S and h* as the same classifier.
h_S depends on the particular training sample, while h* is defined from the conditional probability function and serves as the optimal benchmark.
Fix:
Ask which information is being used: the closest observed example for h_S, or the larger conditional label probability for h*.Interpreting c-Lipschitz smoothness as constant η.
The condition limits the difference in η between two points according to their distance; it does not require η to be constant.
Fix:
Read the condition as a bound on how quickly η can change.Ignoring the distance function.
The analysis uses Euclidean distance ρ to identify the closest sampled point.
Fix:
Include the distance assumption when explaining how h_S selects its neighbor.Evaluating 1-NN only on the training sample.
The purpose is to study how well the rule performs beyond the sample, through its true error.
Fix:
Distinguish the sample used to form h_S from the broader error analysis.
Check Your Understanding
Explain, in your own words, why a 1-NN prediction can differ from the Bayes optimal prediction at the same input. In your answer, identify the information used by h_S, the information used by h*, and the role of η(x).
Hints
- Start with how h_S selects a sampled point.
- Then describe how h* uses the conditional label probabilities.
- Remember that the two rules are based on different sources of information.
A pair of points becomes farther apart while the constant c stays fixed. According to the c-Lipschitz condition, what happens to the maximum allowed difference between their conditional label probabilities? Explain why.
Hints
- Look at the distance term ρ(x, x').
- The allowed difference is bounded by c multiplied by that distance.
- The condition restricts change; it does not force equality.
Key Takeaways
- The 1-NN hypothesis h_S is sample-dependent: it finds the closest sampled point under Euclidean distance and inherits that point's binary label.
- The conditional probability function η(x) describes the conditional label behavior at x and defines the Bayes rule h* by selecting the label with the larger conditional probability.
- The Bayes rule is the optimal benchmark, while h_S is the rule whose true error is being analyzed.
- The c-Lipschitz condition limits how quickly η can change as the Euclidean distance between inputs changes.
- The domain, binary labels, 0-1 loss, Euclidean distance, training sample, and smoothness assumption work together to support the 1-NN error analysis.
Key Takeaways
- 1-NN uses the closest example in a training sample, so its hypothesis h_S depends on the sample.
- The Bayes rule h* uses η(x), the conditional probability function, and chooses the label with the larger conditional probability.
- The c-Lipschitz condition says that η cannot change too rapidly relative to Euclidean distance.
- The analysis of 1-NN error depends jointly on the domain, binary labels, 0-1 loss, distance, sample, and smoothness assumptions.
- h_S and h* may make different predictions because they use different information.