Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning

By Nicolas Papernot, Patrick Drew McDaniel. 2018

574 citations recorded by the source corpus.

Deep neural networks (DNNs) enable innovative applications of machine learning like image recognition, machine translation, or malware detection. However, deep learning is often criticized for its lack of robustness in adversarial settings (e.g., vulnerability to adversarial inputs) and general inability to rationalize its predictions. In this work, we exploit the structure of deep learning to enable new learning-based inference and decision strategies that achieve desirable properties such as robustness and interpretability. We take a first step in this direction and introduce the Deep k-Nearest Neighbors (DkNN). This hybrid classifier combines the k-nearest neighbors algorithm with representations of the data learned by each layer of the DNN: a test input is compared to its neighboring training points according to the distance that separates them in the representations. We show the labels of these neighboring points afford confidence estimates for inputs outside the model's training manifold, including on malicious inputs like adversarial examples--and therein provides protections against inputs that are outside the models understanding. This is because the nearest neighbors can be used to estimate the nonconformity of, i.e., the lack of support for, a prediction in the training data. The neighbors also constitute human-interpretable explanations of predictions. We evaluate the DkNN algorithm on several datasets, and show the confidence estimates accurately identify inputs outside the model, and that the explanations provided by nearest neighbors are intuitive and useful in understanding model failures.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Generalization through Memorization: Nearest Neighbor Language Models (2019, methodology): “Similar k NN models to ours have been proposed for computer vision tasks (Papernot & McDaniel, 2018; Orhan, 2018; Zhao & Cho, 2018), primarily motivated by improving interpretability and robustness to adversarial attacks.”
Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, methodology): “K-Nearest Neighbors Another method that falls within transparent models is that of Kearest Neighbors (KNN), which deals with classification problems in methodologically simple way: it predicts the class of a test sample by oting the classes of its K nearest neighbors (where the neighborhood elation ”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Papernot and McDaniel [229] proposed an algorithm for deep kNN classification, which uses the k-nearest neighbors of a test instance from every hidden layer of a trained neural network.”
Stronger data poisoning attacks break data sanitization defenses (2018, background): “Designing models that are robust to such attacks, as well as coming up with more effective attacks, is an active area of research (Papernot et al., 2016c; Madry et al., 2017; Tramèr et al., 2017; Wong and Kolter, 2018; Raghunathan et al., 2018; Sinha et al., 2018; Athalye et al., 2018; Papernot and ”
Deep Weighted Averaging Classifiers (2018, methodology): “In an unpublished paper, Papernot and McDaniel [39] propose to train a conventional deep model, but make predictions using a k-nearest neighbours approach, with distance computed using all internal nodes of the network.”
To Trust Or Not To Trust A Classifier (2018, positive): “This observation is similar to the work of Papernot and McDaniel [42], who use k -NN regression on the intermediate representations of the network which they showed enhances robustness to adversarial attacks and leads to better calibrated uncertainty estimations.”
Analyzing and Improving Representations with the Soft Nearest Neighbor Loss (2019, methodology): “In our empirical study, we measure uncertainty with the Deep k-Nearest Neighbors (DkNN): the approach relies on a nearest neighbor search in the representation spaces of the model to identify support in the training data for a given test input (Papernot & McDaniel, 2018).”
ProtoAttend: Attention-Based Prototypical Learning (2019, methodology): “We compare dkNN (Papernot and McDaniel, 2018) and prototypical learning (with softmax attention and λconf=0.”
A Simple Cache Model for Image Recognition (2018, methodology): “Two recent papers have used cache memories to improve the robustness of image recognition models against adversarial attacks [12, 18].”
Shallow-Deep Networks: Understanding and Mitigating Network Overthinking (2018, background): “The prior work that proposed early exits (Lee et al., 2015; Szegedy et al., 2015) or error indicators (Szegedy et al., 2013; Papernot & McDaniel, 2018) for off-the-shelf DNNs focused on producing and interpreting a single prediction for each input, rather than on illuminating how this prediction…”
Adversarial Examples on Graph Data: Deep Insights into Attack and Defense (2019, background): “Although adversarial attack for a graph is a relatively new topic, a few works have been done as the defense for adversarial images on convolutional neural networks (e.g., [ Xu et al. , 2018; Papernot and McDaniel, 2018 ] ).”
Aleatoric and Epistemic Uncertainty in Machine Learning: A Tutorial Introduction (2019, background): “Moreover, such models are often lacking robustness and can easily be fooled by “adversarial examples” (Papernot and McDaniel, 2018): Drastic changes of a prediction may already be provoked by minor, actually unimportant changes of an object.”
The role of explainability in creating trustworthy artificial intelligence for health care: a comprehensive survey of the terminology, design choices, and evaluation strategies (2020, methodology): “non-interpretable) model for the subset of data where the interpretable model has unsatisfactory performance and Papernot and McDaniel [58] use K-nearest neighbors in each layer of a deep neural network.”
Attention-Based Prototypical Learning Towards Interpretable, Confident and Robust Deep Neural Networks (2019, methodology): “In (Papernot & McDaniel, 2018), the intermediate representations of the network are used to define a distance metric, and a confidence metric is proposed based on the conformity of the neighbors.”