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.

REFERENCES

• CH67: T.M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, IT-13:21-27, 1967.
• Cov68: T. M. Cover. Rates of convergence of nearest neighbor decision procedures. In Proceedings of the First Annual Hawaii Conference on Systems Theory, pages 413-415, 1968.
• DH73: R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley ~ Sons, New York, 1973.
• Erd56: A. Erd~lyi. Asymptotic Expansions. Dover, New York, 1956.
• FS61: W. Fulks and J. O. Sather. Asymptotics II: Laplace's method for multiple integrals. Pacific Journal of Mathematics, 11:185-192, 1961.
• PSV92: D. Psaltis, R. R. Snapp, and S. S. Venkatesh. On the finite sample performance of the nearest neighbor classifter. Submitted, 1992.
• SPV91: Robert R. Snapp , Demetri Psaltis , Santosh S. Venkatesh, Asymptotic slowing down of the nearest-neighbor classifier, Proceedings of the 1990 conference on Advances in neural information processing systems 3, p.932-938, October 1990, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Measurement, Performance, Theory