Bayes Optimal Classification
1-NN is analyzed as a sample-dependent hypothesis h_S for binary classification.
Try it: Conditional Probability and Bayes' Rule
Conditional probability with natural frequencies: a population is split by the prior P(A) and by P(B | A), P(B | not A); the joint table gives P(B) and Bayes' rule P(A | B) = P(B | A)·P(A) / P(B). The Bayes-optimal classifier predicts the label with the larger conditional probability, and its error is the smallest any rule of the observation can reach.
How it works
- Split 10,000 people by the prior: 10,000·P(A) are in A.
- Split each group by B: P(B | A) of A and P(B | not A) of not A have B — four exact joint counts.
- Total probability: P(B) = P(B | A)·P(A) + P(B | not A)·P(not A).
- Bayes' rule: P(A | B) = (count of A and B) / (count of B); likewise P(A | not B).
- Bayes-optimal classifier h*(x): for x = B and x = not B predict A when η(x) = P(A | x) ≥ 1/2, else not A; count its mistakes and compare with other rules.
Default run (10 steps): A population of 10,000 people. P(A) = 0.05, P(B | A) = 0.9, P(B | not A) = 0.1. … Error of h*: it is wrong on 500 of 10000 people = 1/20 (0.05). "Predict A exactly when B" errs on 1000 (0.1); ignoring x and always predicting the majority label errs on 500. No rule that only sees x does better than h*.
Simplified: Probabilities are whole percentages so every natural-frequency count out of 10,000 is exact; one binary event B plays the role of the observed feature x.
Loading the simulation…
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?
- 1Search the sample
Compare the query point with the sampled points using the distance ρ.
- 2Select the neighbor
Choose the sampled point with the smallest distance from x.
- 3Transfer 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?
- 1Apply 1-NN
The sample-dependent rule follows the closest sampled point, so h_S predicts label 0.
- 2Apply the Bayes rule
The Bayes rule follows η(x) and chooses the label with the larger conditional probability, so h* predicts label 1.
- 3Interpret 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 η?
- 1Pair 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.
- 2Pair B
Because the Euclidean distance is larger, cρ(x, x') is larger. The condition permits a larger difference between the conditional probabilities.
- 3Main 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
Common mistake Treating h_S and h* as the same classifier.
What it looks likeAssuming that the nearest sampled label must always equal the label selected from η(x).
Why it failsh_S depends on the particular training sample, while h* is defined from the conditional probability function and serves as the optimal benchmark.
Do this insteadAsk which information is being used: the closest observed example for h_S, or the larger conditional label probability for h*.
Common mistake Interpreting c-Lipschitz smoothness as constant η.
What it looks likeConcluding that η(x) must have the same value everywhere.
Why it failsThe condition limits the difference in η between two points according to their distance; it does not require η to be constant.
Do this insteadRead the condition as a bound on how quickly η can change.
Common mistake Ignoring the distance function.
What it looks likeCalling a point the nearest neighbor without specifying the distance used to compare points.
Why it failsThe analysis uses Euclidean distance ρ to identify the closest sampled point.
Do this insteadInclude the distance assumption when explaining how h_S selects its neighbor.
Common mistake Evaluating 1-NN only on the training sample.
What it looks likeConcluding that the analysis is complete after describing how h_S labels sampled examples.
Why it failsThe purpose is to study how well the rule performs beyond the sample, through its true error.
Do this insteadDistinguish 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
- 1The 1-NN hypothesis h_S is sample-dependent: it finds the closest sampled point under Euclidean distance and inherits that point's binary label.
- 2The 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.
- 3The Bayes rule is the optimal benchmark, while h_S is the rule whose true error is being analyzed.
- 4The c-Lipschitz condition limits how quickly η can change as the Euclidean distance between inputs changes.
- 5The domain, binary labels, 0-1 loss, Euclidean distance, training sample, and smoothness assumption work together to support the 1-NN error analysis.
At a glance
- 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.