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

Nicolas Papernot; Patrick McDaniel

Source-linked AI summary

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

Nicolas Papernot, Patrick McDaniel

arXiv:1803.04765v1Mar 13, 2018cs.LGstat.ML

TL;DR

DNNs lack reliable confidence, interpretable explanations, and robustness to adversarial inputs. The paper introduces DkNN, which compares test representations with nearby training points at every layer and uses their labels to assess conformity. DkNN reports more reliable credibility on out-of-distribution inputs and identifies existing adversarial examples through low credibility.

Problem
DNN confidence estimates can be unreliable off the training manifold, while their predictions are difficult to explain and vulnerable to adversarial examples.
Method
DkNN combines nearest-neighbor searches over each DNN layer’s representations with conformal analysis of neighboring training labels.
Results
DkNN credibility was below 10% versus 20%-50% for a given DNN on geometrically transformed or unseen-class inputs, and it identified existing adversarial examples through low credibility.
Takeaways & Limitations
Training-data support across a DNN’s representation hierarchy provides confidence estimates, interpretable exemplars, and a basis for detecting unsupported predictions.

Abstract

from arXiv · show

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.

I. INTRODUCTION

DkNN uses a DNN’s layer-wise representations and training-data neighbors to address unreliable confidence, limited interpretability, and adversarial vulnerability. Its credibility and conformity analyses connect prediction support across layers to confidence, explanations, and robustness.

Approach: DkNN searches for nearby training representations at every DNN layer and checks whether their labels support the final prediction.This uses the network’s modular representations to enforce conformity between intermediate computations and the model’s output.
Motivation: DNN confidence can be misleading because adversarial examples may receive higher output probabilities for an incorrect class than legitimate inputs receive for the correct class.This motivates confidence estimates grounded in support from the training data rather than softmax probabilities alone.
Confidence: Credibility measures how well a test prediction conforms to training data, with low support indicating an ambiguous or adversarial input.The estimate is based on the number of neighboring training labels that differ from the candidate prediction.
Interpretability: Nearest training points provide human-interpretable evidence for why the model produced a prediction.They expose training-manifold points whose representations resemble the test input at different layers.
Robustness: DkNN detects adversarial or out-of-distribution inputs when nearest-neighbor labels become inconsistent across the DNN’s layers.This targets nonconforming predictions rather than attempting to defeat individual adversarial strategies.

Contributions

The paper introduces DkNN as a classification method grounded in hierarchical DNN representations and training data. Its reported contributions cover credibility estimation, interpretability, and adversarial-example detection.

Contributions: DkNN measures prediction nonconformity against training data as an indirect estimate of model credibility.The method builds on DNNs, which learn increasingly abstract representations through successive layers.
Contributions: Below 10% versus 20%-50%: DkNN credibility on geometrically transformed or unseen-class inputs, compared with a given DNN.The authors report this as evidence that DkNN credibility estimates are more reliable on naturally occurring out-of-distribution inputs.
Contributions: DkNN provides interpretability through a study of racial bias and fairness in a well-known DNN.Its explanations use training examples that best explain predictions because they are processed similarly to the test input.
Contributions: DkNN identifies adversarial examples generated by existing algorithms through their low credibility.The paper also reports that adaptive attacks often need to perturb input semantics to change DkNN predictions.

III. ON CONFIDENCE, INTERPRETABILITY & ROBUSTNESS

The paper reviews confidence, interpretability, and robustness challenges in deep learning. It motivates DkNN by contrasting training-manifold evidence with unreliable softmax confidence and computationally difficult Bayesian uncertainty estimates.

Confidence: Softmax probabilities are not reliable confidence estimates for inputs outside the model’s training manifold.Adversarial examples can receive higher confidence for an incorrect class than legitimate inputs receive for the correct class.
Confidence: Bayesian deep learning offers principled uncertainty estimates but remains computationally hard for neural networks.Approximation strategies reduce overhead, yet Bayesian neural networks remain difficult to implement.
Interpretability: DNN explanations are difficult to present because their outputs arise from complex sequences of computations across high-dimensional representations.Interpretability evaluation is also difficult because success criteria are ill-defined and hard to quantify.
Interpretability: DkNN returns exemplar training inputs that explain predictions through similarity in learned representations.This explanation-by-example approach uses prototypes processed similarly to the test input.

C. Robustness in Machine Learning

DNNs can fail on adversarial inputs because small perturbations alter predictions while remaining visually indistinguishable, and learned representations may not be robust. DkNN addresses this by checking layer-wise consistency with training data and returning predictions with confidence and credibility measures.

Motivation: Adversarial examples perturb correctly classified inputs, often invisibly to humans, yet can change the model’s output.The paper describes adversarial inputs as malicious test examples created by perturbing legitimate inputs.
DkNN approach: DkNN compares test-time layer representations with training patterns so each intermediate computation remains consistent with the final prediction.This modifies inference rather than retraining the underlying DNN.
Motivation: DNN representations may be vulnerable to adversarial examples and translation shifts because test-time inputs can fall outside the training distribution.The paper motivates mechanisms for identifying when a model is extrapolating too far from its training data.
DkNN approach: For each DNN layer, DkNN finds k nearest training points and collects their labels to characterize support for candidate predictions.The procedure computes layer-wise neighbors before deriving prediction, confidence, and credibility.
DkNN approach: The method recursively relates representations across layers, enabling algorithmic characterization of how a mistaken input becomes closer to the eventually predicted wrong class.The paper presents this transformation as the target of its robustness analysis.

2) A nearest neighbors approach:

DkNN applies nearest-neighbor classification in the representation space of every DNN layer. It uses locality-sensitive hashing to compare test representations with nearby training representations and aggregate their labels.

A nearest neighbors approach:: DkNN creates a nearest-neighbor classifier in the space defined by each DNN layer.Nearest neighbors make the relationship between model predictions and training data explicit.
A nearest neighbors approach:: After training, the method records every layer’s outputs on training points and pairs those representations with their labels.These recorded representations support a nearest-neighbor classifier at each layer.
A nearest neighbors approach:: Locality-sensitive hashing finds high-dimensional nearest representations using cosine similarity and increases collisions among similar items.The hashing scheme is data-dependent and designed for efficient lookup in learned representation spaces.
A nearest neighbors approach:: For each test representation, DkNN retrieves k closest training points and collects their labels into a layer-specific multi-set.The resulting label collections are denoted Ω_λ in the procedure.

B. Conformal Predictions for DkNN Confidence Estimation

DkNN combines layer-wise neighbor support with inductive conformal prediction to estimate confidence and credibility. Calibration data converts nonconformity scores into empirical p-values used for prediction and uncertainty assessment.

B. Conformal Predictions for DkNN Confidence Estimation: Softmax probabilities are often poorly calibrated, motivating DkNN’s training-data-based confidence and credibility estimates.The paper notes that softmax outputs can overestimate confidence, including on adversarial examples.
B. Conformal Predictions for DkNN Confidence Estimation: DkNN confidence estimates the likelihood that a prediction is correct, while credibility measures how relevant the training set is for that prediction.The paper reports credibility calibration in benign and adversarial environments.
B. Conformal Predictions for DkNN Confidence Estimation: Inductive conformal prediction avoids retraining the DNN for every test input by using a separate calibration set.This makes conformal inference practical for the DNN underlying DkNN.
B. Conformal Predictions for DkNN Confidence Estimation: Nonconformity measures how different a candidate-labeled test input is from previously observed labeled training data.A high nonconformity value indicates weak support from nearby training points for the candidate label.
B. Conformal Predictions for DkNN Confidence Estimation: For each candidate label, DkNN computes nonconformity from neighbor labels and compares it with calibration scores to obtain an empirical p-value.The p-value is the fraction of calibration nonconformity measures larger than the test input’s score.
B. Conformal Predictions for DkNN Confidence Estimation: The prediction is the label with the largest empirical p-value; confidence is one minus the second-largest p-value, and credibility is the prediction’s p-value.These quantities are returned together with the predicted label.

V. EVALUATION OF THE CONFIDENCE OF DKNNS

The evaluation examines how DkNN credibility reflects support from training data, using reliability diagrams across MNIST, SVHN, and GTSRB. It also tests whether credibility can expose mislabeled inputs and distinguish supported from unsupported predictions.

Credibility definition: DkNN defines nonconformity from neighboring training points whose labels disagree with the prediction, with greater disagreement indicating weaker support.Confidence and credibility are computed using conformal prediction; credibility characterizes how relevant the training set is to the prediction.
Experimental setup: The evaluation uses MNIST, SVHN, and GTSRB, with k = 75 and calibration sets of 750, 750, and 850 examples respectively.The calibration set is held out from the test data, and the DkNN has a limited performance impact or improves accuracy.
Evaluation caveat: Credibility evaluation lacks a direct ground truth because datasets provide labels but do not specify the expected credibility of model predictions.Ambiguous inputs also make 100% credibility undesirable in some cases.
In-distribution calibration: Reliability diagrams compare binned prediction accuracy with DNN softmax confidence and DkNN credibility across MNIST, SVHN, and GTSRB.The diagrams use bars for mean accuracy within credibility bins and show data density across bins.
In-distribution calibration: Softmax confidence exceeds 0.8 for most test data, whereas DkNN credibility uses a broader range, especially for harder SVHN inputs.The broader credibility range reflects differences in support and the difficulty of classifying inputs in the test distribution.
Mislabeled inputs: DkNN credibility identifies MNIST and SVHN test images assigned high credibility to classes different from their dataset labels, revealing likely labeling errors.The examples were found by searching for inputs whose highly credible DkNN class disagreed with the recorded label.

C. Credibility on out-of-distribution samples

The out-of-distribution evaluation tests whether DkNN credibility falls when inputs lack support in the model’s training manifold. Across unrelated datasets and geometric transformations, DkNN assigns lower credibility than softmax probabilities.

Experimental design: DkNN is evaluated on inputs from different classification tasks and on geometrically transformed inputs that lack support in the training manifold.The unrelated datasets include NotMNIST for MNIST and CIFAR-10 for SVHN, alongside rotated test inputs.
MNIST results: 6% and 9% are the DkNN’s mean credibilities for NotMNIST and rotated MNIST, versus 33% and 31% for softmax probabilities.These comparisons are reported for the MNIST model.
Conclusion: DkNN credibility is better calibrated on out-of-distribution samples because outliers receive low credibility reflecting limited training-data support.The reported out-of-distribution experiments are conducted in benign settings; adversarial examples are evaluated later.

VI. EVALUATION OF THE INTERPRETABILITY OF DKNNS

The interpretability evaluation treats DkNN nearest neighbors as explanations by example and applies them to understanding model bias. Neighbors reveal visual evidence associated with predictions and show how cropping can change the predicted class.

Explanations by example: DkNN nearest neighbors provide training examples whose representations are close to a test input and can help humans rationalize the prediction.This explanation strategy is evaluated through a downstream fairness-related application.
Fairness application: The fairness application focuses on potential computer-vision bias related to skin color and uses a reproduced ResNet/ImageNet experiment.The study uses a pretrained TensorFlow model and the ImageNet training dataset.
Bias analysis: The evaluation connects nearest neighbors to understanding how training data yields model biases, as a step toward eliminating bias during DNN training.The paper frames this as a practical use of interpretability for debugging model limitations.
ResNet case study: For the Obama image classified as basketball, the 10 nearest neighbors from the last hidden layer include 7 black and 3 white basketball players.The basketball’s color and elevated position resemble the football in the test image, suggesting a possible basis for the prediction.
ResNet case study: Removing the football changes the prediction to racket, whose neighbors are white tennis players sharing a green background, white clothing, and raised-arm positions.The comparison offers an alternative or complementary explanation alongside the previously identified bias.
Practical implications: The nearest-neighbor heuristic can support semiautomated debugging and suggest removing ambiguous training points or adding new ones to address bias.These proposed uses extend beyond immediate human trust in model predictions.

VII. EVALUATION OF THE ROBUSTNESS OF DKNNS

The DkNN identifies many adversarial examples through low credibility and provides more reliable confidence estimates than softmax probabilities. Its robustness evaluation also examines adaptive attacks and the representation-level ambiguity underlying mispredictions.

B. Explaining DNN Mispredictions on Adversarial Examples: Adversarial examples introduce lower-layer representation ambiguity that accumulates through the DNN and can substantially change its final prediction despite small input perturbations.The evaluation analyzes candidate-label patterns across layers to expose this mechanism.
C. Robustness of the DkNN Algorithm to Adaptive Attacks: The DkNN is reported as robust to the adaptive attacks considered, which align internal representations with training points from an incorrect class.The attacks are evaluated against the DNN underlying the DkNN inference algorithm.
A. Identifying Adversarial Examples with the DkNN Algorithm: The DkNN identifies adversarial examples because their predictions generally have low credibility, unless the predicted label is correct.This extends its out-of-distribution detection behavior to adversarial test data.
A. Identifying Adversarial Examples with the DkNN Algorithm: The DkNN’s error rate remains high despite improving over the underlying DNN, so improved adversarial performance does not eliminate classification errors.This limitation is discussed alongside the lower-layer ambiguity observed for adversarial inputs.
A. Identifying Adversarial Examples with the DkNN Algorithm: DkNN credibility is better calibrated than softmax probabilities, often indicating recovery of an adversarial example’s true label when credibility is high.Reliability diagrams compare DkNN credibility with undefended-DNN softmax probabilities on GTSRB adversarial examples.

B. Explaining DNN Mispredictions on Adversarial Examples

Nearest-neighbor representations expose how adversarial perturbations create ambiguity across DNN layers and how adaptive attacks must manipulate internal representations. The analysis also shows that some successful attacks can produce images ambiguous to human observers.

B. Explaining DNN Mispredictions on Adversarial Examples: Adversarial examples have more candidate labels than legitimate inputs in lower layers, introducing ambiguity that later contributes to the model’s mistake.For clean and adversarial inputs, candidate-label counts decrease toward the output layer as representations become more abstract.
B. Explaining DNN Mispredictions on Adversarial Examples: The number of neighboring labels matching the DNN prediction varies across attacks, and is especially low for CW examples that the DkNN often recovers correctly.This mismatch between neighboring representations across layers indicates weak training-data support for the model’s prediction.
C. Robustness of the DkNN Algorithm to Adaptive Attacks: An attack that targets the DkNN must both fool the underlying DNN and align internal representations with training data from the incorrectly predicted class.The paper evaluates this feature-adversary strategy under a strong adversary assumed to know the defender’s training set.
C. Robustness of the DkNN Algorithm to Adaptive Attacks: Feature adversarial examples are arranged by original class in rows and DkNN prediction in columns, enabling comparison of source and predicted classes.The figure shows SVHN examples; analogous MNIST results are placed in the Appendix.
C. Robustness of the DkNN Algorithm to Adaptive Attacks: Many feature adversarial images are ambiguous to human vision despite small ℓ∞ perturbations of 0.3 for MNIST and 0.1 for SVHN.This observation raises questions about norm-ball-based evaluation of vision attacks and defenses.

VIII. CONCLUSIONS

DkNN inspects internal DNN representations and compares test representations with training neighbors to provide confidence, interpretability, and robustness. Its credibility measure assesses agreement with training data, while the neighbors support understandable predictions.

DkNN compares layer representations at test time with the nearest neighbors used to train the model.This produces a credibility measure for conformance between representation predictions and training data.
Credibility is higher when predictions agree with training data and lower when predictions lack training-data support.The latter includes ambiguous inputs and maliciously perturbed adversarial examples.
Nearest neighbors make predictions interpretable because they are understandable points in the input domain that support the prediction.
Integrating simple inference procedures as ancillary validation offers a potential avenue for improving security in machine-learning systems.The authors identify availability and integrity as open areas that may benefit from this perspective.

APPENDIX

The appendix supplies implementation, architecture, reliability, nearest-neighbor-label, and feature-adversarial-example materials for the evaluation datasets. These materials point readers to the main experimental sections for setup and interpretation.

Models were trained with Adam using a learning rate of 10^-3.
The evaluated DNN architectures and dataset-specific layer selections are documented in Table III.The table also states that the architectures were implemented using TensorFlow and CleverHans.
Additional reliability diagrams are provided for MNIST and GTSRB, with setup and interpretation described in Section VII-A.
Figures 9 and 10 show reliability diagrams on adversarial examples for MNIST and SVHN, respectively.Both captions direct readers to Figure 6 for details.
Additional diagrams analyze nearest-neighbor labels on clean and adversarial MNIST and SVHN data.Figures 11 and 12 show the number of candidate labels for MNIST and SVHN, while Figure 13 shows feature adversarial examples for MNIST.