Source-linked AI summary
Choice of neighbor order in nearest-neighbor classification
Peter Hall, Byeong U. Park, Richard J. Samworth
TL;DR
Nearest-neighbor classification lacks a sufficiently clear account of how k affects error and lacks practical methods for choosing k. The paper analyzes Poisson and Binomial training-sample models through error-rate expansions, showing that nearest-neighbor risk matches the n^-4/(d+4) rate of second-order kernel classifiers under twice-differentiable densities. These results motivate new methods for selecting k.
Problem
Nearest-neighbor classifiers have poorly understood error behavior as k varies, and practical methods for empirically choosing k have apparently not been given.
Method
The paper derives error-rate expansions for nearest-neighbor classifiers under Poisson and Binomial interpretations of training-sample size.
Results
Nearest-neighbor classifiers under Poisson or Binomial sample-size models attain the n^-4/(d+4) risk-convergence rate associated with second-order kernel density classifiers for twice-differentiable densities.
Takeaways & Limitations
The risk representations motivate new practical methods for choosing the value of k.
Takeaways & Limitations
The analysis confines classification attention to new data in a compact region R and assumes two continuous derivatives, with continuity needed for concise regret formulas.
Abstract
from arXiv · showhide
The $k$th-nearest neighbor rule is arguably the simplest and most intuitively appealing nonparametric classification procedure. However, application of this method is inhibited by lack of knowledge about its properties, in particular, about the manner in which it is influenced by the value of $k$; and by the absence of techniques for empirical choice of $k$. In the present paper we detail the way in which the value of $k$ determines the misclassification error. We consider two models, Poisson and Binomial, for the training samples. Under the first model, data are recorded in a Poisson stream and are "assigned" to one or other of the two populations in accordance with the prior probabilities. In particular, the total number of data in both training samples is a Poisson-distributed random variable. Under the Binomial model, however, the total number of data in the training samples is fixed, although again each data value is assigned in a random way. Although the values of risk and regret associated with the Poisson and Binomial models are different, they are asymptotically equivalent to first order, and also to the risks associated with kernel-based classifiers that are tailored to the case of two derivatives. These properties motivate new methods for choosing the value of $k$.
1. Introduction.
The paper examines how k affects nearest-neighbor misclassification error and addresses the lack of practical methods for choosing k. It analyzes Poisson and Binomial training-sample models and relates their asymptotic behavior to second-order kernel classifiers.
- Nearest-neighbor classification is simple and intuitively appealing, but its error structure and dependence on k remain insufficiently understood.Previous work largely held k fixed, while practical formulas for optimal k were apparently unavailable.
- The paper develops error-rate expansions that characterize risk in terms of properties of the two populations and support optimal choice of k.These expansions lead to new practical methods for selecting the neighbor order.
- Poisson training-sample models treat sample sizes as random, with observations assigned between populations according to prior probabilities.This setting can arise when the population of potential customers is much larger than the number seeking loans.
- Binomial models fix the total number of training observations while randomly apportioning them between the two populations.The two models differ in their risk and regret values but are considered as alternative interpretations of training-sample size.
- For twice-differentiable densities, second-order kernel classifiers achieve risk convergence at rate n^-4/(d+4), and the paper shows nearest-neighbor classifiers have the same property.Here d denotes the number of dimensions, and the rate is described as minimax optimal.
- The paper focuses on smooth classification problems, whereas related work also studies difficult settings with comparatively unsmooth classification boundaries.The smoothness continuum studied by Mammen and Tsybakov connects the smooth and rough cases.
2. Main results.
The paper analyzes k-nearest-neighbor classification under Poisson and Binomial training-sample models, deriving risk expansions and implications for choosing k. Under smoothness and boundary assumptions, the two models share first-order asymptotic behavior, including the optimal order of k.
- Problem setup: The analysis classifies new d-variate observations from two populations with independent training samples and densities f and g.Attention is restricted to new observations in a compact region R; f and g need not be compactly supported.
- Sample-size models: The Poisson model treats training data as a marked point process, while the Binomial model conditions on a fixed total sample size.The Poisson model is used as the primary basis for analysis because it avoids conditioning and has greater symmetry; the Binomial case is handled by reference to it.
- Assumptions: The results assume a codimension-one decision boundary, twice-continuously differentiable densities near it, positive combined density on R, and non-tangential crossings.The boundary consists of isolated points in one dimension, curves in two dimensions, and analogous (d − 1)-dimensional structures in higher dimensions.
- Poisson model: Under the Poisson model, the regret expansion has leading orders k^-1 and (k/ν)4/d, with the optimal choice satisfying k_Pois,opt ∼ const.ν4/(d+4) when α is not identically zero.The expansion provides a more concise account of the faster convergence available for smooth discrimination boundaries than a generic nearest-neighbor bound.
- Binomial model: Under the Binomial model, the difference between its k-nearest-neighbor risk and Bayes risk has the same first-order regret expansion as under the Poisson model.The Binomial and Poisson Bayes risks are also identical under the stated additional condition.
- Choice of k: These theoretical results motivate practical procedures for choosing k, with the paper treating the Poisson model and noting that the Binomial model can be addressed similarly.The paper also relates the nearest-neighbor expansion to second-order kernel-based methods for twice-differentiable densities.
3. Numerical properties.
The numerical experiments assess empirical selection of k and compare it with the error-minimizing deterministic choice across Poisson training-sample settings. The empirical choice performs similarly to the optimum and broadly follows the predicted scaling of kopt.
- Experimental design: 500 Poisson training datasets were simulated for selected intensity constants, using bootstrap resampling fractions r = 1/3, 1/2, 2/3.Each dataset used a Poisson-distributed sample size, draws from the mixture density, and 100 bootstrap resamples for selecting k.
- Empirical choice of k: The estimated error rate with empirical ˜kopt was generally close to that obtained with kopt, the deterministic error-minimizing choice.The optimal value was contained in the one-standard-error interval except for the correlated setting (µ,ν) = (100,200), where two standard errors sufficed.
- Empirical choice of k: The resampling fraction r = 1/3 gave the best results, although differences across fractions were not statistically significant.This suggests limited sensitivity of ˜kopt to the resampling fraction in these simulations.
- Scaling of kopt: When (µ,ν) increased from (100,200) to (400,800), kopt increased from 27 to 71, a factor of 2.63 versus the theoretical value 2.52.The observed rate was reported for the bottom row of Table 1.
- Scaling of kopt: In d = 16, kopt increased from 25 to 61, a factor of 2.44 compared with the theoretical value 2.51.The simulations used normal densities with means differing across all 16 coordinates and intensity pairs (100,200) and (10000,20000).
4. Proof of Theorem 1.
The proof analyzes nearest-neighbor classification through marked Poisson-process representations, local expansions, and normal approximations. It establishes uniform control of classification probabilities and derives the asymptotic risk expansion underlying Theorem 1.
- Poisson-process representation: The Poisson model represents observations as an ordered marked point process, with nearest-neighbor labels modeled by conditionally independent zero-one variables.The proof conditions on the locations of the k nearest points and analyzes the number receiving each mark.
- Local expansion: Taylor expansion of ψ around z supplies first- and second-derivative terms, with the remainder controlled uniformly near the relevant region.The expansion relies on two continuous derivatives of f and g and on E∥Z(k) − z∥2 = O{(k/ν)2/d}.
- Uniform control: The proof combines local Poisson approximations, tail bounds, symmetry, and uniformity arguments to control classification probabilities across the feature region.The argument separately handles neighborhoods of the decision boundary and regions away from it.
- Probability approximation: A normal approximation to the Poisson count yields a weighted uniform error bound of order O(k−1/2) for the distribution of Wk(z).This approximation is applied uniformly over z ∈ Sε and all real standardized arguments.
- Risk expansion: The resulting Poisson risk expansion has leading terms C1(S)k−1 and C2(S)(k/ν)4/d, with lower-order remainder.The constants converge to their limiting forms as µ/(µ + ν) tends to p, which completes the connection to Theorem 1.
P. Hall Department of Mathematics and Statistics University of Melbourne Parkville, VIC 3010 Australia
The passage identifies R. J. Samworth with the Statistical Laboratory at the University of Cambridge.
- R. J. Samworth is affiliated with the Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge.The listed address is Wilberforce Road, Cambridge, CB3 0WB, United Kingdom.