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

被引:0
作者
Kumari, Sushma [1 ]
Pestov, Vladimir G. [2 ,3 ]
机构
[1] Def Inst Adv Technol DIAT, Pune 411025, Maharashtra, India
[2] Univ Fed Paraiba, Dept Matemat, Joao Pessoa, PB, Brazil
[3] Univ Ottawa, Dept Math & Stat, Ottawa, ON K1N 6N5, Canada
基金
日本学术振兴会;
关键词
k-NN classifier; universal consistency; strong universal consistency; distance ties; Nagata dimension; de Groot dimension; sigma-finite dimensional metric spaces; Heisenberg group; Lebesgue-Besicovitch property;
D O I
10.1051/ps/2024002
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We continue to investigate the k nearest neighbour (k-NN) learning rule in complete separable metric spaces. Thanks to the results of Cerou and Guyader (2006) and Preiss (1983), this rule is known to be universally consistent in every such metric space that is sigma-finite dimensional in the sense of Nagata. Here we show that the rule is strongly universally consistent in such spaces in the absence of ties. Under the tie-breaking strategy applied by Devroye, Gyorfi, Krzyzak, and Lugosi (1994) in the Euclidean setting, we manage to show the strong universal consistency in non-Archimedian metric spaces (i.e., those of Nagata dimension zero). Combining the theorem of Cerou and Guyader with results of Assouad and Quentin de Gromard (2006), one deduces that the k-NN rule is universally consistent in metric spaces having finite dimension in the sense of de Groot. In particular, the k-NN rule is universally consistent in the Heisenberg group which is not sigma-finite dimensional in the sense of Nagata as follows from an example independently constructed by Koranyi and Reimann (1995) and Sawyer and Wheeden (1992).
引用
收藏
页码:132 / 160
页数:29
相关论文
共 22 条
[1]  
Assouad P, 2006, REV MAT IBEROAM, V22, P893
[2]  
Cerou F., 2006, ESAIM: Probability and Statistics, V10, P340, DOI DOI 10.1051/PS:2006014
[3]   Universal consistency of the k-NN rule in metric spaces and Nagata dimension*** [J].
Collins, Benoit ;
Kumari, Sushma ;
Pestov, Vladimir G. .
ESAIM-PROBABILITY AND STATISTICS, 2020, 24 :914-934
[5]  
de Groot J., 1957, Can. J. Math, P511
[6]   NECESSARY AND SUFFICIENT CONDITIONS FOR THE POINTWISE CONVERGENCE OF NEAREST NEIGHBOR REGRESSION FUNCTION ESTIMATES [J].
DEVROYE, L .
ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1982, 61 (04) :467-481
[7]   ON THE STRONG UNIVERSAL CONSISTENCY OF NEAREST-NEIGHBOR REGRESSION FUNCTION ESTIMATES [J].
DEVROYE, L ;
GYORFI, L ;
KRZYZAK, A ;
LUGOSI, G .
ANNALS OF STATISTICS, 1994, 22 (03) :1371-1385
[8]  
Devroye L., 1985, Nonparametric Density Estimation: The L1-View
[9]  
Devroye L., 1996, A Probabilistic Theory of Pattern Recognition
[10]  
Fremlin D.H., 2003, Broad Foundations, corrected second printing of the 2001 original, V2, p563+12