Venkatesh, Santosh S. and Snapp, Robert R. and Psaltis, Demetri
(1992)
*Bellman strikes again!: the growth rate of sample complexity with dimension for the nearest neighbor classifier.*
In:
COLT '92 Proceedings of the fifth annual workshop on Computational learning theory.
ACM
, New York, NY, pp. 93-102.
ISBN 0-89791-497-X.
https://resolver.caltech.edu/CaltechAUTHORS:20170103-173502617

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170103-173502617

## 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 R_m given that a reference m-sample of labeled points, drawn independently from Euclidean n-space according to a fixed probability distribution, is available to the classifier. For a family of smooth distributions, it is shown that the m-sample risk R_m has a complete asymptotic expansion R_m ~ R_∞ + Σ^∞_(k=1) c_(2k)m^(-2k/n), where R_∞ denotes the nearest neighbor risk in the infinite sample limit. Explicit definitions of the expansion coefficients are given in terms of the underlying distribution. As the convergence rate of R_m → R_∞ 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.

Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| |||||||||

Additional Information: | © 1992 ACM. | |||||||||

DOI: | 10.1145/130385.130396 | |||||||||

Record Number: | CaltechAUTHORS:20170103-173502617 | |||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170103-173502617 | |||||||||

Official Citation: | Santosh S. Venkatesh, Robert R. Snapp, and Demetri Psaltis. 1992. Bellman strikes again!: the growth rate of sample complexity with dimension for the nearest neighbor classifier. In Proceedings of the fifth annual workshop on Computational learning theory (COLT '92). ACM, New York, NY, USA, 93-102. DOI=http://dx.doi.org/10.1145/130385.130396 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 73195 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | Kristin Buxton | |||||||||

Deposited On: | 04 Jan 2017 15:50 | |||||||||

Last Modified: | 11 Nov 2021 05:12 |

Repository Staff Only: item control page