Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation
Authors:
- Marco AnconaMAMarco Ancona
- Cengiz ÖztireliCÖCengiz Öztireli
- Markus GrossMGMarkus Gross
Preprint
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Understanding Deep Neural Networks through Input Uncertainties2019
- Explainable machine-learning predictions for the prevention of hypoxaemia during surgeryNature Biomedical Engineering, 2018
- Explaining nonlinear classification decisions with deep Taylor decompositionPattern Recognition, 2017
- "Why Should I Trust You?"2016
- Axiomatic attribution for multilinear functions2011
- Accurate Telemonitoring of Parkinson's Disease Progression by Noninvasive Speech TestsIEEE Transactions on Biomedical Engineering, 2010
- Polynomial calculation of the Shapley value based on samplingComputers & Operations Research, 2009
- A linear approximation method for the Shapley valueArtificial Intelligence, 2008
- Gate sizing using a statistical delay model2002
- NP-completeness for calculating power indices of weighted majority gamesTheoretical Computer Science, 2001