Name
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 is available to the classifier. The statistical setup assumes that the pattern classes arise in nature with fixed a priori probabilities and that points representing the classes are drawn from Euclidean n-space according to fixed class-conditional probability distributions. The sample is assumed to consist of m independently generated class-labeled points. For a family of smooth class-conditional distributions characterized by asymptotic expansions in general form, it is shown that the m-sample risk Rm has a complete asymptotic series expansion Rm~R∞+Σk=2∞ ckm-kn/ (m→∞), where R∞ denotes the nearest neighbor risk in the infinite-sample limit and the coefficients ck are distribution-dependent constants independent of the sample size m. The analysis thus provides further analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included, and extensions of the theory discussed. The analysis also contains a novel application of Laplace's asymptotic method of integration to a multidimensional integral where the integrand attains its maximum on a continuum of points |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1109/18.335893 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
asymptotic expansion,sample size m,complete asymptotic series expansion,fixed class-conditional probability distribution,m-sample risk,nearest neighbor classifier,reference m-sample,finite sample performance,nearest neighbor risk,asymptotic method,exact integral expression,pattern analysis,convergence,pattern recognition,numerical simulation | Journal | 40 |
Issue | ISSN | ISBN |
3 | 0018-9448 | 0-7803-0878-6 |
Citations | PageRank | References |
11 | 1.06 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Demetri Psaltis | 1 | 431 | 209.24 |
| Robert R. Snapp | 2 | 56 | 52.96 |
| Santosh S. Venkatesh | 3 | 381 | 71.80 |