Conditional Probability in Classification
1-NN is analyzed as a sample-dependent hypothesis h_S for binary classification.
A New Point Meets a Sample
Suppose a classifier receives a new input x and a labeled training sample S. The 1-nearest-neighbor rule does not make its prediction independently of S. It searches S for the closest observed example, using Euclidean distance, and transfers that example's label to x. Because the prediction depends on which sample S was observed, the rule is written as the sample-dependent hypothesis h_S.
The subscript S matters: h_S is not one fixed prediction rule detached from data. It records that the observed training sample determines which neighbor will be used.
Tracing the 1-NN Decision
A Sample-Dependent Prediction
Consider a binary classification problem with labels 0 and 1. A new point x is evaluated against a labeled sample S. The closest observed point in S has label 1.
Locate the neighbor: Use the Euclidean distance ρ to compare x with the points in S.
Select the closest point: The point in S with the smallest distance from x is the 1-nearest neighbor.
Transfer its label: Because the selected neighbor has label 1, the sample-dependent rule assigns h_S(x) = 1.
The 1-NN prediction is determined by the closest labeled example in S. If S changed, the closest example and therefore h_S(x) could also change.
This example illustrates why 1-NN analysis must account for the sample. The classifier is evaluated on a new point, but its decision comes from the relationship between that point and the particular labeled sample that was observed.
The Conditional Probability η(x)
The conditional probability function is η(x) = P(Y = 1 | X = x). It describes the probability that the label is 1 when the input is x. In this setting, labels are binary: Y belongs to {0, 1}.
η(x) describes the label behavior at x rather than the label of one particular observed neighbor. The Bayes rule h* is defined from η(x) and serves as the optimal benchmark for the binary classification problem under 0-1 loss. It chooses the label that is more probable at x: label 1 when η(x) is greater than 1/2, and label 0 when η(x) is less than 1/2. The tie case is not needed for the present comparison.
A Probability-Based Benchmark
At one input x, suppose η(x) is greater than 1/2. What label does the Bayes rule select?
Interpret η(x): η(x) is the conditional probability of label 1 at x.
Compare the alternatives: Because η(x) is greater than 1/2, label 1 is more probable than label 0 at x.
Apply the Bayes rule: The Bayes rule selects label 1.
h*(x) = 1.
Two Prediction Mechanisms
| Feature | Sample-dependent 1-NN rule h_S | Bayes rule h* |
|---|---|---|
| Information used | The closest labeled example in the observed sample S | The conditional probability η(x) |
| Decision at x | Transfers the closest example's label | Chooses the more probable binary label at x |
| Dependence on S | Depends on the particular sample S | Serves as the optimal benchmark defined from η(x) |
| Role in analysis | The rule whose true error is studied | The benchmark used to assess that error |
Smoothness Through c-Lipschitzness
The c-Lipschitz condition restricts how quickly η can change between input points. In the present setting, the restriction connects Euclidean closeness, measured by ρ, with limited change in conditional label probability: the difference between η(x) and η(x') is bounded by c times the Euclidean distance between x and x'.
The practical interpretation is local smoothness. When two inputs are close under Euclidean distance, their conditional probabilities cannot differ arbitrarily under the c-Lipschitz assumption. As the distance becomes larger, the permitted bound on the change in η becomes larger as well. This condition is one reason a nearby labeled example can be relevant to understanding the label behavior around a new point.
Reading the Lipschitz Restriction
Compare two pairs of input points under the same c-Lipschitz condition. Pair A has a small Euclidean distance, while Pair B has a larger Euclidean distance.
Inspect Pair A: The smaller distance gives a smaller allowed bound on the change between the two conditional probabilities.
Inspect Pair B: The larger distance gives a larger allowed bound on the change between the two conditional probabilities.
Interpret the assumption: The condition does not say that η is constant. It says that its change is limited in proportion to the Euclidean distance.
Closer points are subject to a tighter restriction on how different their conditional label probabilities can be.
The Analysis Setting
The generalization analysis places 1-NN in a specific mathematical setting. The input domain is X = [0, 1]^d. Labels are binary, with Y = {0, 1}. Predictions are evaluated with the 0-1 loss. Distances are measured by the Euclidean distance ρ. The analysis also uses a labeled sample and the smoothness restriction on η. Together, these assumptions provide the setting for studying the true error of the sample-dependent 1-NN rule.
| Part of the setting | Specified assumption | Role in the analysis |
|---|---|---|
| Domain | X = [0, 1]^d | Specifies the input space in which points are considered |
| Labels | Y = {0, 1} | Makes the classification problem binary |
| Loss | 0-1 loss | Defines whether a prediction is correct or incorrect |
| Distance | Euclidean distance ρ | Determines which sample point is nearest |
| Conditional probability | η(x) with the c-Lipschitz restriction | Limits how quickly label probability can change across the domain |
| Sample | Labeled sample S | Determines the sample-dependent hypothesis h_S |
These assumptions are analyzed together rather than as unrelated definitions.
The assumptions connect the geometry of the input space, the binary label structure, the way distance selects a neighbor, and the smoothness of conditional probabilities. That connection supports the study of how well h_S performs beyond the observed sample.
Mistakes in Comparing the Rules
Treating h_S as independent of the training sample.
The closest point and its label are selected from S, so the hypothesis is explicitly sample-dependent.
Fix:
Write h_S and state which sample supplies the nearest labeled example.Treating the nearest label as the conditional probability η(x).
The nearest point supplies one observed label, whereas η(x) is the conditional probability of label 1 at x.
Fix:
Keep the observed neighbor's label separate from the probability-based Bayes benchmark.Assuming the c-Lipschitz condition says η has the same value everywhere.
The condition limits the amount of change according to Euclidean distance; it does not state that the change is always zero.
Fix:
Interpret c-Lipschitzness as a bound on how rapidly η can change.Leaving out the distance function when explaining 1-NN.
The analysis specifies Euclidean distance ρ as the measure used to find the closest sample point.
Fix:
Mention Euclidean distance when tracing the 1-NN decision.Using the Bayes rule as though it were produced by the observed sample.
The Bayes rule is defined from η(x), while the sample-dependent 1-NN rule uses the closest labeled example.
Fix:
Describe h* as the optimal benchmark and h_S as the rule whose true error is analyzed.
Check the Mechanism
A new point x is classified in a binary problem. The closest point in sample S has label 0. Separately, η(x) is greater than 1/2. Identify the prediction made by h_S and the prediction made by h*. Then explain why the two predictions can differ.
Hints
- Start with the source of information used by h_S.
- Then compare η(x) with 1/2 for the Bayes rule.
- Use the words sample-dependent and probability-based in your explanation.
What do you think happens?
In the practice situation, what predictions should the two rules make?
Reveal answer
Answer: h_S predicts 0 and h* predicts 1.
The 1-NN rule transfers the label of the closest observed point, which is 0. The Bayes rule compares η(x) with 1/2; because η(x) is greater than 1/2, it selects label 1.
What the Analysis Separates
- 1-NN is represented by h_S because its prediction depends on the labeled sample S.
- For a new point, 1-NN uses Euclidean distance to find the closest sample point and transfers that point's binary label.
- η(x) = P(Y = 1 | X = x) describes the conditional probability of label 1 and defines the Bayes optimal benchmark.
- The c-Lipschitz condition limits how much η can change as inputs become separated under Euclidean distance.
- The domain, binary labels, 0-1 loss, distance, sample, and smoothness assumptions work together in the analysis of 1-NN's true error.
Key Takeaways
- The sample-dependent hypothesis h_S classifies a new point using the label of its closest observed example.
- The Bayes rule h* uses η(x), the conditional probability of label 1 at x, as its decision basis.
- The 1-NN rule and the Bayes rule are different objects: one depends on a sample, while the other is the optimal probability-based benchmark.
- The c-Lipschitz condition restricts the rate at which η can change with Euclidean distance.
- The specified domain, labels, loss, distance, sample, and smoothness assumptions make it possible to analyze 1-NN generalization error.