Conditional Probability in 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…
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.
- 1Locate the neighbor
Use the Euclidean distance ρ to compare x with the points in S.
- 2Select the closest point
The point in S with the smallest distance from x is the 1-nearest neighbor.
- 3Transfer 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?
- 1Interpret η(x)
η(x) is the conditional probability of label 1 at x.
- 2Compare the alternatives
Because η(x) is greater than 1/2, label 1 is more probable than label 0 at x.
- 3Apply 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 |
The two rules can make predictions through different mechanisms, even when they are evaluated at the same input.
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.
- 1Inspect Pair A
The smaller distance gives a smaller allowed bound on the change between the two conditional probabilities.
- 2Inspect Pair B
The larger distance gives a larger allowed bound on the change between the two conditional probabilities.
- 3Interpret 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
Common mistake Treating h_S as independent of the training sample.
What it looks likeSaying that 1-NN always produces the same prediction rule before identifying the observed sample.
Why it failsThe closest point and its label are selected from S, so the hypothesis is explicitly sample-dependent.
Do this insteadWrite h_S and state which sample supplies the nearest labeled example.
Common mistake Treating the nearest label as the conditional probability η(x).
What it looks likeCalling the label transferred from the closest point the value of η(x).
Why it failsThe nearest point supplies one observed label, whereas η(x) is the conditional probability of label 1 at x.
Do this insteadKeep the observed neighbor's label separate from the probability-based Bayes benchmark.
Common mistake Assuming the c-Lipschitz condition says η has the same value everywhere.
What it looks likeConcluding that η(x) and η(x') must be equal whenever the condition holds.
Why it failsThe condition limits the amount of change according to Euclidean distance; it does not state that the change is always zero.
Do this insteadInterpret c-Lipschitzness as a bound on how rapidly η can change.
Common mistake Leaving out the distance function when explaining 1-NN.
What it looks likeSaying that 1-NN chooses a nearby example without specifying how nearness is determined.
Why it failsThe analysis specifies Euclidean distance ρ as the measure used to find the closest sample point.
Do this insteadMention Euclidean distance when tracing the 1-NN decision.
Common mistake Using the Bayes rule as though it were produced by the observed sample.
What it looks likeDescribing h*(x) as the label of the closest point in S.
Why it failsThe Bayes rule is defined from η(x), while the sample-dependent 1-NN rule uses the closest labeled example.
Do this insteadDescribe 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
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
- 11-NN is represented by h_S because its prediction depends on the labeled sample S.
- 2For a new point, 1-NN uses Euclidean distance to find the closest sample point and transfers that point's binary label.
- 3η(x) = P(Y = 1 | X = x) describes the conditional probability of label 1 and defines the Bayes optimal benchmark.
- 4The c-Lipschitz condition limits how much η can change as inputs become separated under Euclidean distance.
- 5The 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.