Source-linked AI summary
Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation
Marco Ancona, Cengiz Öztireli, Markus Gross
TL;DR
Deep neural networks are difficult to explain reliably, while exact Shapley values are computationally prohibitive. The paper introduces DASP, a polynomial-time approximation using uncertainty propagation in DNNs, and reports better approximations than existing attribution methods. It also reports that DASP outperforms fast but coarse backpropagation-based Shapley approximators, while not guaranteeing exact recovery.
Problem
DNN attribution methods often lack strong theoretical foundations, while exact Shapley evaluation is exponentially expensive and sampling methods require many DNN evaluations.
Method
DASP approximates Shapley values in DNNs through perturbation steps and uncertainty propagation using probabilistic distributions propagated through the network.
Results
DASP requires a polynomial number of network evaluations and empirically outperforms sampling-based and backpropagation-based attribution methods as Shapley-value approximators.
Takeaways & Limitations
DASP provides a practical approximation of Shapley values for DNNs while retaining the paper’s focus on theoretically motivated attribution.
Takeaways & Limitations
DASP is not guaranteed to recover exact Shapley values, and extensions to recurrent neural networks and stronger theoretical guarantees remain future directions.
Abstract
from arXiv · showhide
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.
1. Introduction
Deep neural networks offer broad problem-solving potential, but their black-box behavior complicates adoption where interpretability and transparency are required. The paper motivates theoretically grounded attribution and introduces a polynomial-time Shapley approximation evaluated against existing methods.
- Motivation: DNN black-box behavior remains a barrier to adoption in domains requiring interpretability, including decisions subject to a right to explanation.European regulators introduced a legal right to explanation for automated decisions with deep impacts on people.
- Motivation: Attribution explanations can be unreliable or misleading despite visual appeal, partly because some methods have limited theoretical understanding and evaluation lacks reliable ground-truth metrics.The paper motivates axiomatic approaches as a way to design methods with stronger theoretical guarantees.
- Shapley values: Shapley values provide a cooperative-game-theoretic attribution scheme whose desirable axioms motivate their use for explaining nonlinear models.The paper presents them as a unique way of assigning attributions satisfying certain properties.
- Computational challenge: Exact Shapley evaluation is NP-hard and feasible only for fewer than 20-25 input features, while sampling methods require thousands of DNN evaluations as feature count grows.KernelSHAP combines sampling with lasso regression to reduce the number of samples.
- Contributions: The work formulates a polynomial-time Shapley approximation for DNNs and empirically compares its approximation power with existing attribution methods on three datasets and architectures.The contribution also endorses an axiomatic comparison of Shapley values with state-of-the-art attribution methods.
2. Attribution Methods
The paper distinguishes backpropagation-based and perturbation-based attribution methods, then describes Shapley values as a perturbation-based approach grounded in average marginal contributions. Exact computation is generally prohibitive, motivating approximate methods and highlighting practical costs of perturbation.
- Method categories: Attribution methods divide into backpropagation-based methods using backward passes and perturbation-based methods that remove or alter features and measure output changes.The paper reviews methods applicable across architectures and input types.
- Backpropagation-based methods: Backpropagation methods can provide local information but do not directly compute a feature’s marginal contribution for highly nonlinear functions.The paper discusses LRP, DeepLIFT, and Integrated Gradients as methods proposed to address this limitation.
- Perturbation-based methods: Perturbation methods estimate feature contributions by removing or perturbing features and measuring the resulting variation in the target output.Occlusion sequentially sets each feature to zero, implicitly defining a zero baseline.
- Perturbation-based methods: Perturbation-based methods are often simple but slow because they require several network evaluations, and their perturbation choices can heavily affect explanations.The number of features perturbed and the perturbation itself are hyperparameters.
- Shapley values: Shapley values quantify each player’s total contribution through average marginal contributions across coalitions, adapted to neural networks by replacing absent features with a baseline.For a neural network, xS retains features in S and replaces the rest with the baseline.
- Computational challenge: Exact Shapley computation evaluates all 2^N feature subsets, making it prohibitive beyond a couple of dozen variables; sampling provides an approximate alternative.For some simple functions, exact polynomial-time computation is possible, such as max-pooling layers with O(N^2) evaluations.
3. Axiomatic comparison of attribution methods
The paper evaluates attribution methods against established axioms and shows that Shapley values uniquely satisfy Axioms 1-5 while also satisfying implementation invariance. Several methods coincide with Shapley values for linear models with a zero baseline, but differ for nonlinear models.
- Linear versus nonlinear models: Occlusion, Gradient × Input, Integrated Gradients, and DeepLIFT produce exact Shapley values for linear models when using a zero baseline.For nonlinear models, these methods produce different attributions.
- Axiomatic framework: The comparison evaluates attribution methods using conservation, null player, symmetry, linearity, continuity, and implementation invariance.These properties are treated as desirable theoretical criteria for explanations.
- Axioms: Completeness requires attributions to sum to the difference between the function values at the input and baseline, while the null-player axiom assigns zero to unused variables.Completeness is also called efficiency, summation to delta, or conservation.
- Axioms: Symmetry requires equal attribution for variables playing identical roles, and linearity requires attributions to combine with the same weights as linearly combined sub-networks.Continuity and implementation invariance impose additional consistency requirements across nearby inputs and functionally equivalent networks.
- Method comparison: Gradient × Input and Occlusion fail Completeness, while LRP and DeepLIFT fail Implementation Invariance under the cited comparisons.The paper uses these differences to motivate evaluating methods against desirable theoretical properties.
4. Deep Approximate Shapley Propagation
DASP approximates Shapley values by replacing exhaustive coalition enumeration with distributions over random coalitions and propagating their moments through a neural network. This yields a polynomial-time procedure for dense networks while retaining approximations of feature contributions.
- Approximation principle: Coalitions of size k are represented as input vectors with k actual feature values and zero baselines elsewhere, forming a random variable X_k.This distribution provides the input uncertainty propagated through the network.
- Distribution propagation: DASP propagates coalition-induced means and variances through DNN layers using uncertainty propagation and Lightweight Probabilistic Deep Networks.LPNs transform point-activation layers into uncertainty-propagation layers by matching first- and second-order moments.
- Distribution propagation: For affine layers, the method analytically propagates Gaussian means and variances, with corresponding adaptations for convolution and mean-pooling operations.ReLU and max-pooling distributions are also approximated using analytically derived moments.
- Computational cost: Algorithm 1 loops over input features and selected coalition sizes, propagates the resulting distributions, and accumulates each feature’s marginal contribution.The output is the approximate Shapley-value vector R_c.
- Computational cost: O(N^2) network evaluations approximate Shapley values when all coalition sizes are tested, compared with O(2^N) for exact computation.Testing only K coalition sizes further reduces the cost to O(KN) evaluations.
5. Experiments
Experiments compare DASP with attribution methods across Parkinsons, DNA-sequence, and MNIST tasks using Shapley-based ground truths and RMSE or Spearman correlation. DASP generally achieves more accurate Shapley approximations with fewer evaluations than competing methods.
- DASP is evaluated alongside Integrated Gradients, DeepLIFT variants, RevealCancel, Occlusion, Shapley sampling, and KernelSHAP across three datasets.The experiments use different network architectures and compare methods against Shapley-based ground truths.
- 5.2. Parkinsons disability assessment: DASP better approximates Shapley values than biased methods with few coalition sizes, while unbiased sampling methods need significantly more evaluations to outperform it.This comparison is reported for the Parkinsons task using exact Shapley values as ground truth.
- 5.3. Classifying regulatory DNA sequences: On DNA sequences, DASP and sampling outperform backpropagation-based methods, while KernelSHAP requires significantly more evaluations to reach the same rank correlation as DASP.DeepLIFT (Mix) is the strongest backpropagation-based method in this experiment.
- 5.4. Digits classification (MNIST): On MNIST, backpropagation-based methods produce noisier maps, and DASP shows an accuracy gap over biased approximators and an evaluation-efficiency gap over sampling and KernelSHAP.KernelSHAP performs worse than simple sampling in this experiment, which the authors speculate may reflect its linearity assumption on complex models.
6. Conclusions
The paper motivates Shapley values for reliable DNN explanations and proposes DASP, which approximates them through uncertainty propagation with polynomially many network evaluations. Empirically, DASP requires fewer evaluations than sampling methods and outperforms fast but coarse backpropagation-based approximators, while theoretical guarantees and broader architectural coverage remain future work.
- For nonlinear models, Shapley values uniquely satisfy several desirable theoretical properties that motivate their use for reliable explanations.
- DASP approximates Shapley values in DNNs using uncertainty propagation and requires a polynomial number of network evaluations.
- DASP empirically needs fewer evaluations than sampling-based methods for the same approximation error and outperforms fast, coarse backpropagation-based approximators.
- The authors identify extending DASP to recurrent neural networks and deriving theoretical guarantees as future directions.They also seek better approximations through new probabilistic frameworks.