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

Abstract

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.

References in corpus (22)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Towards A Rigorous Science of Interpretable Machine Learning
• End to End Learning for Self-Driving Cars
• What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
• Ensemble Adversarial Training: Attacks and Defenses
• European Union regulations on algorithmic decision-making and a "right to explanation"
• Feature Squeezing: Detecting Adversarial Examples in Deep Neural Networks
• On Calibration of Modern Neural Networks
• Weight Uncertainty in Neural Networks
• Delving into Transferable Adversarial Examples and Black-box Attacks
• A tutorial on conformal prediction
• Certified Defenses against Adversarial Examples
• Interpretability Beyond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV)
• Technical Report on the CleverHans v2.1.0 Adversarial Examples Library
• Adversarial Perturbations Against Deep Neural Networks for Malware Classification
• MagNet: a Two-Pronged Defense against Adversarial Examples
• Parseval Networks: Improving Robustness to Adversarial Examples
• Deep Learning for Case-Based Reasoning through Prototypes: A Neural Network that Explains Its Predictions
• Generating Visual Explanations
• Deep Neural Network Based Malware Detection Using Two Dimensional Binary Program Features
• Rogue Signs: Deceiving Traffic Sign Recognition with Malicious Ads and Logos
• ConvNets and ImageNet Beyond Accuracy: Understanding Mistakes and Uncovering Biases

Cited by in corpus (126)

• Deep learning for time series classification: a review
• Interpretable machine learning: definitions, methods, and applications
• Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods
• The role of explainability in creating trustworthy artificial intelligence for health care: a comprehensive survey of the terminology, design choices, and evaluation strategies
• This Looks Like That: Deep Learning for Interpretable Image Recognition
• To Trust Or Not To Trust A Classifier
• Designing Interpretable ML System to Enhance Trust in Healthcare: A Systematic Review to Proposed Responsible Clinician-AI-Collaboration Framework
• Adversarial Machine Learning in Image Classification: A Survey Towards the Defender's Perspective
• The Fishyscapes Benchmark: Measuring Blind Spots in Semantic Segmentation
• Backdoor Attacks and Countermeasures on Deep Learning: A Comprehensive Review
• Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
• Shallow-Deep Networks: Understanding and Mitigating Network Overthinking
• Thieves on Sesame Street! Model Extraction of BERT-based APIs
• MetaPoison: Practical General-purpose Clean-label Data Poisoning
• MOCCA: Multi-Layer One-Class ClassificAtion for Anomaly Detection
• Detection of Face Recognition Adversarial Attacks
• Generalization through Memorization: Nearest Neighbor Language Models
• A Closer Look at Domain Shift for Deep Learning in Histopathology
• Adversarial Attacks on Time-Series Intrusion Detection for Industrial Control Systems
• Deep Weighted Averaging Classifiers
• Why is the Mahalanobis Distance Effective for Anomaly Detection?
• Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching
• Accelerating Deep Learning by Focusing on the Biggest Losers
• The Role of Machine Learning in the Next Decade of Cosmology
• Explaining and Improving Model Behavior with k Nearest Neighbor Representations
• Sufficient Conditions for Idealised Models to Have No Adversarial Examples: a Theoretical and Empirical Study with Bayesian Neural Networks
• Increasing the Confidence of Deep Neural Networks by Coverage Analysis
• Multi-Branch Deep Radial Basis Function Networks for Facial Emotion Recognition
• Operational Calibration: Debugging Confidence Errors for DNNs in the Field
• Understanding the Decision Boundary of Deep Neural Networks: An Empirical Study
• What can AI do for me: Evaluating Machine Learning Interpretations in Cooperative Play
• Towards Feature Space Adversarial Attack
• Deep Learning Through the Lens of Example Difficulty
• Learning Densities in Feature Space for Reliable Segmentation of Indoor Scenes
• Automatic Large Scale Detection of Red Palm Weevil Infestation using Aerial and Street View Images
• Differentiable Top-k Operator with Optimal Transport
• ProtoAttend: Attention-Based Prototypical Learning
• TRUST-LAPSE: An Explainable and Actionable Mistrust Scoring Framework for Model Monitoring
• Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective
• DaST: Data-free Substitute Training for Adversarial Attacks
• A Tutorial on Distance Metric Learning: Mathematical Foundations, Algorithms, Experimental Analysis, Prospects and Challenges (with Appendices on Mathematical Background and Detailed Algorithms Explanation)
• KNN-BERT: Fine-Tuning Pre-Trained Models with KNN Classifier
• Sequential Interpretability: Methods, Applications, and Future Direction for Understanding Deep Learning Models in the Context of Sequential Data
• Why model why? Assessing the strengths and limitations of LIME
• DNN or k-NN: That is the Generalize vs. Memorize Question
• The Hidden Uncertainty in a Neural Networks Activations
• Enhancing Gradient-based Attacks with Symbolic Intervals
• SoK: Machine Learning Governance
• Certification of embedded systems based on Machine Learning: A survey
• Real-time Out-of-distribution Detection in Learning-Enabled Cyber-Physical Systems
• Are all outliers alike? On Understanding the Diversity of Outliers for Detecting OODs
• A Marauder's Map of Security and Privacy in Machine Learning
• Assurance Monitoring of Cyber-Physical Systems with Machine Learning Components
• The Local Elasticity of Neural Networks
• Deep learning for time series classification
• Assurance Monitoring of Learning Enabled Cyber-Physical Systems Using Inductive Conformal Prediction based on Distance Learning
• A Simple Cache Model for Image Recognition
• AdvKnn: Adversarial Attacks On K-Nearest Neighbor Classifiers With Approximate Gradients
• Detecting OODs as datapoints with High Uncertainty
• To Trust or Not to Trust a Regressor: Estimating and Explaining Trustworthiness of Regression Predictions
• Misleading Failures of Partial-input Baselines
• Improving the Tightness of Convex Relaxation Bounds for Training Certifiably Robust Classifiers
• Evaluating the feasibility of interpretable machine learning for globular cluster detection
• $n$-ML: Mitigating Adversarial Examples via Ensembles of Topologically Manipulated Classifiers
• Rearchitecting Classification Frameworks For Increased Robustness
• Improving Entity Linking by Modeling Latent Entity Type Information
• Justification-Based Reliability in Machine Learning
• Train and You'll Miss It: Interactive Model Iteration with Weak Supervision and Pre-Trained Embeddings
• DeepNNK: Explaining deep models and their generalization using polytope interpolation
• Channel-Wise Early Stopping without a Validation Set via NNK Polytope Interpolation
• Reinforcement Learning Based Handwritten Digit Recognition with Two-State Q-Learning
• Towards Privacy-preserving Explanations in Medical Image Analysis
• KNN-enhanced Deep Learning Against Noisy Labels
• Medical Aegis: Robust adversarial protectors for medical images
• FastIF: Scalable Influence Functions for Efficient Model Interpretation and Debugging
• On Convergence of Nearest Neighbor Classifiers over Feature Transformations
• Deep k-NN for Noisy Labels
• Embedded Encoder-Decoder in Convolutional Networks Towards Explainable AI
• Improving the robustness of ImageNet classifiers using elements of human visual cognition
• DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation
• Online Anomaly Detection in Surveillance Videos with Asymptotic Bounds on False Alarm Rate
• On the Exploitability of Audio Machine Learning Pipelines to Surreptitious Adversarial Examples
• Locally Adaptive Label Smoothing for Predictive Churn
• Advancing Post Hoc Case Based Explanation with Feature Highlighting
• Graph Regularized Autoencoder and its Application in Unsupervised Anomaly Detection
• D-square-B: Deep Distribution Bound for Natural-looking Adversarial Attack
• Learning Adaptive Language Interfaces through Decomposition
• Harnessing value from data science in business: ensuring explainability and fairness of solutions
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
• Multi-Expert Adversarial Attack Detection in Person Re-identification Using Context Inconsistency
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection
• A statistical framework for efficient out of distribution detection in deep neural networks
• Beating Attackers At Their Own Games: Adversarial Example Detection Using Adversarial Gradient Directions
• Astro2020 Science White Paper: The Next Decade of Astroinformatics and Astrostatistics
• Resilience from Diversity: Population-based approach to harden models against adversarial attacks
• Deep Latent Defence
• A Survey on Assessing the Generalization Envelope of Deep Neural Networks: Predictive Uncertainty, Out-of-distribution and Adversarial Samples
• A Hierarchical Feature Constraint to Camouflage Medical Adversarial Attacks
• Improving Calibration and Out-of-Distribution Detection in Medical Image Segmentation with Convolutional Neural Networks
• Online Black-Box Confidence Estimation of Deep Neural Networks
• Deep Repulsive Prototypes for Adversarial Robustness
• DeepStreamCE: A Streaming Approach to Concept Evolution Detection in Deep Neural Networks
• Explainable AI for Natural Adversarial Images
• Immuno-mimetic Deep Neural Networks (Immuno-Net)
• MPC-guided Imitation Learning of Neural Network Policies for the Artificial Pancreas
• DM algorithms in health industry
• Analyzing and Interpreting Neural Networks for NLP: A Report on the First BlackboxNLP Workshop
• Self-Checking Deep Neural Networks in Deployment
• An empirical analysis of phrase-based and neural machine translation
• Graphs for deep learning representations
• Instance-Based Neural Dependency Parsing
• Adversarial Imitation Attack
• Towards a Model for LSH
• ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense
• ProtoShotXAI: Using Prototypical Few-Shot Architecture for Explainable AI
• Mathematical Models for Local Sensing Hashes
• Interpreting Equivariant Representations
• Active Learning for UAV-based Semantic Mapping
• Learning Rich Nearest Neighbor Representations from Self-supervised Ensembles
• Neighborhood Watch: Representation Learning with Local-Margin Triplet Loss and Sampling Strategy for K-Nearest-Neighbor Image Classification
• Logit-based Uncertainty Measure in Classification
• Deep Adversarially-Enhanced k-Nearest Neighbors
• Towards Self-Explainable Graph Neural Network
• Training Machine Learning Models by Regularizing their Explanations
• Label Smoothed Embedding Hypothesis for Out-of-Distribution Detection
• Twin Systems for DeepCBR: A Menagerie of Deep Learning and Case-Based Reasoning Pairings for Explanation and Data Augmentation