Volume 24, 2020
|Page(s)||914 - 934|
|Published online||27 November 2020|
Department of Mathematics, Kyoto University, Kitashirakawa Oiwake-cho,
2 Department of Mathematical Engineering, Musashino University, 1 Chome-1-20 Shinmachi, Nishitokyo, Tokyo 202-8585, Japan.
3 Instituto de Matemática e Estatística, Universidade Federal da Bahia, Ondina, Salvador–BA, 40.170-115, Brazil.
4 Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON K1N 6N5, Canada.
*** Corresponding author: firstname.lastname@example.org
Accepted: 22 June 2020
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érou 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.
Mathematics Subject Classification: 62H30 / 54F45
Key words: k-NN classifier / universal consistency / geometric Stone lemma / distance ties / Nagata dimension / sigma-finite dimensional metric spaces
S.K. would like to thank JICA-FRIENDSHIP scholarship (fellowship D-1590283/ J-1593019) for supporting her doctoral study at Kyoto University and Department of Mathematics, Kyoto University for supporting the Brazil research trip under the KTGU project.
© EDP Sciences, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.