NN Rule

In the NN-rule analysis, however, dimension affects how many training examples are needed.

Programming

Why Dimension Matters

Adding dimensions to a data point may sound like adding only a few more measurements. In the NN-rule analysis, however, dimension affects how many training examples are needed. The required sample size can grow exponentially with the Euclidean dimension d. This is the curse of dimensionality: the learning problem can become difficult because the data space has gained dimensions, even though the learning rule itself has not changed.

What happens to the required number of training examples as the input dimension increases?

The important relationship is exponential rather than proportional. When d increases, the number of examples needed to control the relevant error term can increase rapidly. The exact requirement depends on the analysis and its parameters; the claim is not that every data set automatically needs one identical number of examples.

Smoothness and Error

The NN-rule analysis uses a Lipschitz coefficient c and the Euclidean dimension d. The coefficient c controls how rapidly the target behavior may vary as the input changes. A larger c permits more rapid output variation relative to input changes. Dimension d contributes a separate burden: as d grows, the sample-size requirement becomes more severe.

How are smoothness, dimension, and the Lipschitz coefficient connected in determining the NN-rule error requirement?

Formula, step by step

1
c is the Lipschitz coefficient and controls how rapidly the target behavior may vary.
2
d is the Euclidean dimension and appears both inside the base through √d and in the exponent d + 1.
3
ε is the error tolerance that the relevant error term must be smaller than.
4
The condition states that the sample size m must be at least this large for the last term in the Theorem 19.3 bound to be smaller than ε.
5
The rapid growth comes especially from the exponent d + 1, so increasing dimension can make the requirement exponential rather than proportional.

Theorem 19.4 Lower Bound

The exponential requirement is not presented only as a cautious upper-bound calculation. Theorem 19.4 gives a lower-bound implication for learning itself. For any c greater than 1 and every learning rule L, there is a distribution over [0,1]^d × {0,1} whose η is c-Lipschitz and whose Bayes error is 0, yet for sample sizes m ≤ (c + 1)^d / 2, the true error of L is greater than 1/4.

What minimum training-set requirement does the theorem imply as dimension changes?

This theorem says that, for some distributions, every learning rule faces a true-error lower bound when the sample is no larger than the stated exponential threshold. The distribution can still have zero Bayes error. Therefore, the difficulty in this result comes from insufficient data, not from unavoidable classification noise.

Tracing a k-NN Decision

Definition

The k-nearest-neighbors rule, abbreviated k-NN, is a classification rule for binary classification. Its input is a training sample, a chosen value of k, and a point being considered. After the neighbors have been identified and ordered by proximity, the rule selects the first k neighbors and returns the majority label among them.

How does a query point move through neighbor selection until the majority label becomes the output?

Worked example

A Three-Neighbor Vote

A query point has three selected nearest neighbors. Their labels are Red, Blue, and Red. What label does the k-NN rule return when k is 3?

1
Identify the selected group
The rule considers only the first k neighbors in the proximity ordering. Here, k is 3, so all three listed neighbors participate.
2
Count the labels
Red appears twice, while Blue appears once.
3
Return the majority
Red has the greater count among the selected neighbors.

Result

The predicted label is Red.

Keep the roles separate while tracing the rule. The training sample supplies labeled examples. The query point is the point to classify. The selected neighbors are the first k points in the neighbor ordering. Their labels are counted, and the majority label becomes the predicted output. Only the labels of the selected neighbors participate in the decision.

Changing the Neighborhood

Before

Selected labels: Red, Blue, Red k = 3 Majority label: Red

With k = 3, the selected group contains two Red labels and one Blue label.

After

Selected labels: Red, Blue, Red, Blue, Blue k = 5 Majority label: Blue

With k = 5, two additional labels are counted, giving two Red labels and three Blue labels.

The parameter k determines how many neighbors contribute labels to the majority decision. If k changes, the group being counted can change as well. A different group can have a different majority, so the classification result can change when k changes. The rule itself remains unchanged: count the labels among the first k neighbors and return the label with the greater count.

Tracing Mistakes

Common mistake
Treating the query point as one of the labels being counted.
What it looks like
The query point is the point being classified; it is not itself a neighbor label in the majority calculation.
Why it fails
The k-NN output is determined by the labels of the selected training examples.
Do this instead
Separate the query point from the training sample and count only the labels of the first k neighbors.
Common mistake
Using labels from every training example instead of the first k neighbors.
What it looks like
A training sample may contain more labeled points than the selected neighborhood.
Why it fails
Only the labels of the k nearest neighbors participate in the decision.
Do this instead
First identify the neighbor ordering, then select exactly the first k neighbors before counting.
Common mistake
Assuming that changing k cannot change the prediction.
What it looks like
A smaller selected group can have a Red majority, while a larger group can have a Blue majority.
Why it fails
Changing k can add labels to the counted group and change which label has the greater count.
Do this instead
Recount the labels whenever k changes.
Common mistake
Blaming an unexpected result on the majority rule when the real issue is earlier in the trace.
What it looks like
The labels may have been taken from the wrong neighbors or the wrong value of k may have been used.
Why it fails
The majority step is applied only after the selected group has been determined.
Do this instead
Check the training sample, query point, neighbor ordering, selected k neighbors, and label counts in that order.

EASY

A query point has an ordered neighbor-label list of Red, Blue, Blue, Red, Red. Trace the k-NN rule for k = 3 and then for k = 5. State the selected labels, the counts for both classes, and the predicted label in each case.

Hints

For each value of k, use only the first k labels.
Count Red and Blue separately.
The output is the label with the greater count.

Your attempt (not saved)

Key Takeaways

1
In the NN-rule analysis, the required training-set size can grow exponentially with dimension d.
2
The Lipschitz coefficient c controls permitted output variation, while d controls the severity of the dimensional growth.
3
The condition m ≥ (4c√d/ε)^{^d+1} shows why dimension creates rapid sample-size growth.
4
Theorem 19.4 states that for some zero-Bayes-error distributions, every learning rule has true error greater than 1/4 when m ≤ (c + 1)^{^d} / 2.
5
The k-NN rule takes a training sample, a query point, and a chosen k; it returns the majority label among the k nearest neighbors.

At a glance

Higher dimension can make the NN learning requirement grow exponentially rather than proportionally.
The Lipschitz coefficient controls smoothness, while dimension appears in the sample-size requirement through both the base and exponent.
Theorem 19.4 gives an exponential lower-bound threshold for every learning rule on some distributions.
k-NN classifies a query by counting labels among its first k nearest neighbors.
Unexpected k-NN results should be traced through neighbor ordering, the selected value of k, and the final label counts.

More concepts starting with N