On the Resistance of Nearest Neighbor to Random Noisy Labels
This work addresses the robustness of a fundamental ML algorithm to label noise, which is an incremental theoretical and practical contribution for domains like pattern recognition and computer vision.
The paper tackled the problem of nearest neighbor classification under random noisy labels by providing theoretical bounds and proposing a robust variant. The results show that k-nearest neighbor is resistant to symmetric noises, achieving the same consistency rate as in noise-free settings, and the proposed Robust k-Nearest Neighbor (RkNN) method corrects misled examples to improve performance.
Nearest neighbor has always been one of the most appealing non-parametric approaches in machine learning, pattern recognition, computer vision, etc. Previous empirical studies partly shows that nearest neighbor is resistant to noise, yet there is a lack of deep analysis. This work presents the finite-sample and distribution-dependent bounds on the consistency of nearest neighbor in the random noise setting. The theoretical results show that, for asymmetric noises, k-nearest neighbor is robust enough to classify most data correctly, except for a handful of examples, whose labels are totally misled by random noises. For symmetric noises, however, k-nearest neighbor achieves the same consistent rate as that of noise-free setting, which verifies the resistance of k-nearest neighbor to random noisy labels. Motivated by the theoretical analysis, we propose the Robust k-Nearest Neighbor (RkNN) approach to deal with noisy labels. The basic idea is to make unilateral corrections to examples, whose labels are totally misled by random noises, and classify the others directly by utilizing the robustness of k-nearest neighbor. We verify the effectiveness of the proposed algorithm both theoretically and empirically.