Universal consistency of the k-NN rule in metric spaces and Nagata dimension

DOI10.1051/PS/2020018MaRDI QIDQ5140348zbMATH OpenOpenAlexFDO

Authors Benoit Collins, Sushma Kumari, Vladimir G. Pestov

Publication date 15 December 2020

Published in ESAIM: Probability and Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.00894

zbMATH Keywords

universal consistencyNagata dimension\(k\)-NN classifierdistance tiesgeometric Stone lemmasigma-finite dimensional metric spaces

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Dimension theory in general topology (54F45) Topological data analysis (62R40)

Abstract: The $k$ nearest neighbour learning rule (under the uniform distance tie breaking) is universally consistent in every metric space $X$ that is sigma-finite dimensional in the sense of Nagata. This was pointed out by C'erou and Guyader (2006) as a consequence of the main result by those authors, combined with a theorem in real analysis sketched by D. Preiss (1971) (and elaborated in detail by Assouad and Quentin de Gromard (2006)). We show that it is possible to give a direct proof along the same lines as the original theorem of Charles J. Stone (1977) about the universal consistency of the $k$-NN classifier in the finite dimensional Euclidean space. The generalization is non-trivial because of the distance ties being more prevalent in the non-euclidean setting, and on the way we investigate the relevant geometric properties of the metrics and the limitations of the Stone argument, by constructing various examples.

Recommendations

• Nearest neighbor classification in infinite dimension
• Universal Bayes consistency in metric spaces
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule
• On the strong universal consistency of nearest neighbor regression function estimates
• Rate of convergence of \(k\)-nearest-neighbor classification rule

Cites work

• scientific article; zbMATH DE number 3790697 (Why is no real title available?)
• scientific article; zbMATH DE number 42114 (Why is no real title available?)
• scientific article; zbMATH DE number 2145284 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 3211520 (Why is no real title available?)
• A conjecture of J. Nagata on dimension and metrization
• Consistent Nonparametric Regression for Functional Data Under the Stone–Besicovitch Conditions
• Consistent nonparametric regression. Discussion
• Covering, measure derivation and dimensions
• Distance metric learning for large margin nearest neighbor classification
• Finiteness of inverse moments of (m,n,β)-Laguerre matrices
• Hubs in space: popular nearest neighbors in high-dimensional data
• Nearest neighbor classification in infinite dimension
• Nearest neighbor pattern classification
• On a special metric and dimension
• On a special metric characterizing a metric space of $\mathrm{dim} \leqq n$
• On the almost everywhere convergence of nonparametric regression function estimates
• Open problems left in my wake of research

Cited in

(5)

• Nearest neighbor classification in infinite dimension
• Universal consistency of the \(k\)-NN rule in metric spaces and Nagata dimension. II
• A nearest neighbor characterization of Lebesgue points in metric measure spaces
• scientific article; zbMATH DE number 7415094 (Why is no real title available?)
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule

This page was built for publication: Universal consistency of the \(k\)-NN rule in metric spaces and Nagata dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140348)