The Resistance to Label Noise in K-NN and DNN Depends on its Concentration

Understand

We investigate the classification performance of K-nearest neighbors (K-NN) and deep neural networks (DNNs) in the presence of label noise.

• We first show empirically that a DNN's prediction for a given test example depends on the labels of the training examples in its local neighborhood.
• This motivates us to derive a realizable analytic expression that approximates the multi-class K-NN classification error in the presence of label noise, which is of independent importance.
• We then suggest that the expression for K-NN may serve as a first-order approximation for the DNN error.