NN Rule

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.

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.

m ≥ (4c√d/ε)^(d+1)

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.

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

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

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

• Treating the query point as one of the labels being counted.

  The k-NN output is determined by the labels of the selected training examples.

  Fix: Separate the query point from the training sample and count only the labels of the first k neighbors.

• Using labels from every training example instead of the first k neighbors.

  Only the labels of the k nearest neighbors participate in the decision.

  Fix: First identify the neighbor ordering, then select exactly the first k neighbors before counting.

• Assuming that changing k cannot change the prediction.

  Changing k can add labels to the counted group and change which label has the greater count.

  Fix: Recount the labels whenever k changes.

• Blaming an unexpected result on the majority rule when the real issue is earlier in the trace.

  The majority step is applied only after the selected group has been determined.

  Fix: Check the training sample, query point, neighbor ordering, selected k neighbors, and label counts in that order.

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.