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

By Marco Ancona, Cengiz Oztireli, Markus H. Gross. 2019

272 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

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

Citations in the corpus

Explaining Models by Propagating Shapley Values of Local Components (2019, positive): “Finally, DASP (Ancona, ¨ Oztireli, and Gross 2019) is an approach that approximates SHAP values for deep networks.”
Explainable machine learning in deployment (2019, neutral): “perturbation-based techniques [8, 14, 22, 34, 50, 61] and gradientbased techniques [7, 41, 57, 59, 60, 62].”
A Survey on Neural Network Interpretability (2020, background): “form so that v can be approximated in polynomial time [72] (also see [74] for another approximation method).”
Analysing Neural Language Models: Contextual Decomposition Reveals Default Reasoning in Number and Gender Assignment (2019, methodology): “the capacities of GCD by improving the gate factorisation with a better Shapley value approximator, such as those proposed by Lundberg and Lee (2017) or Ancona et al. (2019). The axiomatic approach of Montavon (2019) could provide further insight into how GCD relates to other explanation methods, an”
The Explanation Game: Explaining Machine Learning Models with Cooperative Game Theory (2019, methodology): “The details of these techniques are beyond the scope of this work, but we refer the reader to (Maleki et al. 2013; Chen et al. 2018; Aas, Jullum, and Løland 2019; Hunt et al. 2019; Ancona, Oztireli, and Gross 2019).”
Algorithms to estimate Shapley value feature attributions (2022, methodology): “However, as a consequence of DeepLIFT’s ﬂexibility, its baseline Shapley value estimates have higher bias compared to DASP or ShapNets [33, 34].”
Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications (2021, methodology): “The connection of explanation methods to Shapley values for linear models was also made in [5].”
On Interpretability of Artificial Neural Networks: A Survey (2020, methodology): “Furthermore, the definition of Shapley value can be twisted to the neural network function 𝑓 by replacing the features in the input that are not in 𝑆 with the zero value.”
FedCoin: A Peer-to-Peer Payment System for Federated Learning (2020, background): “In [Ancona et al., 2019], a polynomial-time approximation of SV is proposed for deep neural network.”