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

DOI10.1051/PS/2020018zbMATH Open1455.62123arXiv2003.00894OpenAlexW3006969417MaRDI QIDQ5140348FDOQ5140348

Authors: Benoit Collins, Sushma Kumari, Vladimir G. Pestov 

Publication date: 15 December 2020

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)