Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation

Abstract

The problem of explaining the behavior of deep neural networks has recently gained a lot of attention. While several attribution methods have been proposed, most come without strong theoretical foundations, which raises questions about their reliability. On the other hand, the literature on cooperative game theory suggests Shapley values as a unique way of assigning relevance scores such that certain desirable properties are satisfied. Unfortunately, the exact evaluation of Shapley values is prohibitively expensive, exponential in the number of input features. In this work, by leveraging recent results on uncertainty propagation, we propose a novel, polynomial-time approximation of Shapley values in deep neural networks. We show that our method produces significantly better approximations of Shapley values than existing state-of-the-art attribution methods.

ICML 2019

References in corpus (10)

• Towards A Rigorous Science of Interpretable Machine Learning
• Learning Important Features Through Propagating Activation Differences
• European Union regulations on algorithmic decision-making and a "right to explanation"
• Explaining NonLinear Classification Decisions with Deep Taylor Decomposition
• Sanity Checks for Saliency Maps
• Not Just a Black Box: Learning Important Features Through Propagating Activation Differences
• Tractable Inference for Complex Stochastic Processes
• Visualizing Deep Neural Network Decisions: Prediction Difference Analysis
• Learning how to explain neural networks: PatternNet and PatternAttribution
• Axiomatic Attribution for Multilinear Functions

Cited by in corpus (14)

• Instance-wise or Class-wise? A Tale of Neighbor Shapley for Concept-based Explanation
• Synthetic Benchmarks for Scientific Research in Explainable Machine Learning
• A Baseline for Shapley Values in MLPs: from Missingness to Neutrality
• A Game-Theoretic Taxonomy of Visual Concepts in DNNs
• Interpreting and Boosting Dropout from a Game-Theoretic View
• Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression
• Towards Interpretable Ensemble Learning for Image-based Malware Detection
• Shapley Interpretation and Activation in Neural Networks
• Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning
• A Unified Game-Theoretic Interpretation of Adversarial Robustness
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• Human-in-the-loop model explanation via verbatim boundary identification in generated neighborhoods
• Ensembles of Random SHAPs
• Learning Propagation Rules for Attribution Map Generation