Paper Info
Title
Bellman strikes again!: the growth rate of sample complexity with dimension for the nearest neighbor classifier
Abstract
The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk Rm given that a reference m-sample of labeled points, drawn independently from Euclidean n-space according to a fixed probability distri bution, is available to the classifier. For a family of smooth distributions, it is shown that the m-sample risk Rm has a complete asymptotic expansion ******, where ** denotes the nearest neighbor risk in the infinite sample limit. Explicit definitions of the expansion coefficents are given in terms of the underlying distribution. As the convergence rate of **** dramatically slows down as n increases, this analysis provides an analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included. The rates of convergence for less restrictive families of distributions are also discussed.
Year
DOI
Venue
1992
10.1145/130385.130396
COLT
Keywords
Field
DocType
expansion coefficents,sample complexity,m-sample risk,euclidean n-space,nearest neighbor classifier,reference m-sample,finite sample performance,nearest neighbor risk,infinite sample limit,complete asymptotic expansion,convergence rate,growth rate,bellman strike,rate of convergence,numerical simulation,asymptotic expansion,nearest neighbor,curse of dimensionality,pattern recognition
Convergence (routing),k-nearest neighbors algorithm,Asymptotic expansion,Curse of dimensionality,Rate of convergence,Artificial intelligence,Euclidean geometry,Classifier (linguistics),Nearest neighbor search,Machine learning,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89791-497-X
4
0.62
References 
Authors
2
3
Name
Order
Citations
PageRank
Santosh S. Venkatesh138171.80
Robert R. Snapp25652.96
Demetri Psaltis3431209.24