On The Resistance Of Nearest Neighbor To Random Noisy Labels

Abstract

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, wh

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keygao2016on

Related papers

• Certifiable Robustness For Nearest Neighbor Classifiers (2022)0.00
• Knet: A Deep Knn Network To Handle Label Noise (2021)0.00
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• SVD Provably Denoises Nearest Neighbor Data (2026)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Leveraging Reinforcement Learning For Evaluating Robustness Of KNN Search Algorithms (2021)0.00