K-nearest-neighbor regression consistency in complex metric spaces studied
On k-nearest-neighbor regression in metric spaces
Machine Learning
Summary
This paper investigates how well a popular method called k-nearest-neighbor regression works when data points live in complicated spaces defined only by distances. The authors identify conditions under which predictions become more accurate as the data grows, offering a refined understanding that is less strict than old assumptions. They also demonstrate cases where the method can fail, especially with certain infinite-dimensional spaces, even when data is simple and noise-free. Their work clarifies when and how one can trust k-nearest-neighbor regression in these settings.
What this means in practice
- •For machine learning engineers: Design reliable k-NN regression algorithms for data in complex metric spaces ensuring mean squared consistency under certain moment conditions.
- •For geospatial analysts: Apply insights about response and neighbor distribution to improve regression accuracy on spatial data with non-Euclidean distance metrics.
A theory result. No direct application yet.
Authors
László Györfi, Vladimir G. Pestov, Harro Walk, Roi Weiss
Abstract
We study mean squared consistency of k-nearest-neighbor regression for metric space valued features. For a fixed feature distribution mu with atomless distance distributions, we describe how neighbor selection redistributes probability through the density of a uniformly chosen neighbor of an independent query. This gives separate conditions for the approximation error and the conditional response variance, and weakens Stone's domination condition when stronger response moments are available. In particular, when k_n tends to infinity and k_n/n tends to zero, a uniform L2(mu) bound on the selection densities suffices under a finite fourth response moment. We give a corresponding condition in terms of neighborhoods of fixed population mass and recover the Euclidean density bound. Finite global Nagata dimension gives Stone's domination. While sigma-finite Nagata dimensionality is known to ensure universal consistency of k-NN classification in complete separable spaces, we show that this is not the case for mean squared consistency with unbounded responses: we construct a space in this class on which one fixed noiseless response with all finite moments has diverging mean squared error.