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

arXiv: https://arxiv.org/abs/1903.10992 · HTML: https://mlsanity.com/paper/1903.10992/

## Key facts

- Cited by 115 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2019.

## Built on by (most cited first, 30 of 115)

- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Synthetic Benchmarks for Scientific Research in Explainable Machine Learning](https://mlsanity.com/paper/2106.12543/) (2021)
- [MogaNet: Multi-order Gated Aggregation Network](https://mlsanity.com/paper/2211.03295/) (2022)
- [Explainable Artificial Intelligence: A Survey of Needs, Techniques, Applications, and Future Direction](https://mlsanity.com/paper/2409.00265/) (2024)
- [Explainability-based Backdoor Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2104.03674/) (2021)
- [Discovering and Explaining the Representation Bottleneck of DNNs](https://mlsanity.com/paper/2111.06236/) (2021)
- [Shapley Explanation Networks](https://mlsanity.com/paper/2104.02297/) (2021)
- [Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00285/) (2021)
- [Explaining a Series of Models by Propagating Shapley Values](https://mlsanity.com/paper/2105.00108/) (2021)
- [Explain Any Concept: Segment Anything Meets Concept-Based Explanation](https://mlsanity.com/paper/2305.10289/) (2023)
- [Defining and Quantifying the Emergence of Sparse Concepts in DNNs](https://mlsanity.com/paper/2111.06206/) (2021)
- [Explaining Deepfake Detection by Analysing Image Matching](https://mlsanity.com/paper/2207.09679/) (2022)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [LINe: Out-of-Distribution Detection by Leveraging Important Neurons](https://mlsanity.com/paper/2303.13995/) (2023)
- [Neural Response Interpretation through the Lens of Critical Pathways](https://mlsanity.com/paper/2103.16886/) (2021)
- [Toward Explainable AI for Regression Models](https://mlsanity.com/paper/2112.11407/) (2021)
- [Architecture-Agnostic Masked Image Modeling -- From ViT back to CNN](https://mlsanity.com/paper/2205.13943/) (2022)
- [Repairing Neural Networks by Leaving the Right Past Behind](https://mlsanity.com/paper/2207.04806/) (2022)
- [Interpretable Geometric Deep Learning via Learnable Randomness Injection](https://mlsanity.com/paper/2210.16966/) (2022)
- [Does a Neural Network Really Encode Symbolic Concepts?](https://mlsanity.com/paper/2302.13080/) (2023)
- [SHAQ: Incorporating Shapley Value Theory into Multi-Agent Q-Learning](https://mlsanity.com/paper/2105.15013/) (2021)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [You Mostly Walk Alone: Analyzing Feature Attribution in Trajectory Prediction](https://mlsanity.com/paper/2110.05304/) (2021)
- [Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search](https://mlsanity.com/paper/2206.09811/) (2022)
- [Best of both worlds: local and global explanations with human-understandable concepts](https://mlsanity.com/paper/2106.08641/) (2021)
- [Interpretable deep-learning models to help achieve the Sustainable Development Goals](https://mlsanity.com/paper/2108.10744/) (2021)
- [A Unified Game-Theoretic Interpretation of Adversarial Robustness](https://mlsanity.com/paper/2111.03536/) (2021)

## Abstract (arXiv)

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.