Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.17282 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917655181524992 |
|---|---|
| author | Kumari, Sushma Pestov, Vladimir G. |
| author_facet | Kumari, Sushma Pestov, Vladimir G. |
| contents | We continue to investigate the $k$ nearest neighbour ($k$-NN) learning rule in complete separable metric spaces. Thanks to the results of Cérou 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, Györfi, Krzyżak, and Lugosi (1994) in the Euclidean setting, we manage to show the strong universal consistency in non-Archimedian metric spaces (that is, those of Nagata dimension zero). Combining the theorem of Cérou 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 Korányi and Reimann (1995) and Sawyer and Wheeden (1992). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_17282 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. II Kumari, Sushma Pestov, Vladimir G. Machine Learning 62H30, 54F45 We continue to investigate the $k$ nearest neighbour ($k$-NN) learning rule in complete separable metric spaces. Thanks to the results of Cérou 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, Györfi, Krzyżak, and Lugosi (1994) in the Euclidean setting, we manage to show the strong universal consistency in non-Archimedian metric spaces (that is, those of Nagata dimension zero). Combining the theorem of Cérou 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 Korányi and Reimann (1995) and Sawyer and Wheeden (1992). |
| title | Universal consistency of the $k$-NN rule in metric spaces and Nagata dimension. II |
| topic | Machine Learning 62H30, 54F45 |
| url | https://arxiv.org/abs/2305.17282 |