FastSHAP: Real-Time Shapley Value Estimation
Authors: Neil Jethani
Mukund Sudarshan
Ian Connick Covert
Su-In Lee
Rajesh Ranganath
Venue: ICLR 2022 Poster (2022)
Keywords: interpretability
shapley
amortization
explainability
game theory

Abstract: Although Shapley values are theoretically appealing for explaining black-box models, they are costly to calculate and thus impractical in settings that involve large, high-dimensional models. To remedy this issue, we introduce FastSHAP, a new method for estimating Shapley values in a single forward pass using a learned explainer model. To enable efficient training without requiring ground truth Shapley values, we develop an approach to train FastSHAP via stochastic gradient descent using a weighted least-squares objective function. In our experiments with tabular and image datasets, we compare FastSHAP to existing estimation approaches and find that it generates accurate explanations with an orders-of-magnitude speedup.

Published as a conference paper at ICLR 2022
FASTSHAP:
SHAPLEY VALUE
ESTIMATION
Neil Jethani New York University
Mukund Sudarshan New York University
Ian Covert"
University of Washington
Su-In Lee University of Washington
Rajesh Ranganath New York University
ABSTRACT
Although Shapley values are theoretically appealing for explaining black-box models, they are costly to calculate and thus impractical in settings that involve large, high-dimensional models. To remedy this issue, we introduce FastSHAP, a new method for estimating Shapley values in a single forward pass using a learned explainer model. To enable efficient training without requiring ground truth Shapley values, we develop an approach to train FastSHAP via stochastic gradient descent using weighted least squares objective function. In our experi- ments with tabular and image datasets, we compare FastSHAP to existing estima- tion approaches and find that it generates accurate explanations with an orders-of- magnitude speedup.
INTRODUCTION
With the proliferation of black-box models, Shapley values (Shapley, 1953) have emerged as popular explanation approach due to their strong theoretical properties (Lipovetsky and Conklin, 2001; Štrumbelj and Kononenko, 2014; Datta et al., 2016; Lundberg and Lee, 2017). In practice, however, Shapley value-based explanations are known have high computational complexity, with an exact calculation requiring an exponential number of model evaluations (Van den Broeck et al., 2021). Speed becomes critical issue as models increase in size and dimensionality, and for the largest models in fields such as computer vision and natural language processing, there is an unmet need for significantly faster Shapley value approximations that maintain high accuracy.
Recent work has addressed the computational challenges with Shapley values using two main ap- proaches. First, many works have proposed stochastic estimators (Castro et al., 2009; Štrumbelj and Kononenko, 2014; Lundberg and Lee, 2017; Covert et al., 2020) that rely on sampling either feature subsets or permutations; though often consistent, these estimators require many model eval- uations and impose an undesirable trade-off between run-time and accuracy. Second, some works have proposed model-specific approximations, e.g., for trees (Lundberg et al., 2020) neural net- works (Shrikumar et al., 2017; Chen et al., 2018b; Ancona et al., 2019; Wang et al., 2021); while generally faster, these approaches can still require many model evaluations, often induce bias, and typically lack ficxibility regarding the handling held-out features a subject of ongoing debate in the field (Aas et al., 2019; Janzing al., 2020; Frye et al., 2020; Covert al., 2021).
Here, we introduce a new approach for efficient Shapley value estimation: to achieve the fastest possible run-time, we propose learning separate explainer model that outputs precise Shapley value estimates in single forward pass. Naively, such a learning-based approach would seem to require large training set of ground truth Shapley values, which would be computationally intractable. Instead, our approach trains an explainer model by minimizing an objective function inspired by the Shapley value's weighted least squares characterization (Charnes et al., 1988), which enables efficient gradient- based optimization.
Our contributions. We introduce FastSHAP, an amortized approach for generating real-time Shap- We derive an objective function from the Shapley value's 's weighted least
ley value explanations.
"Equal contribution
httpps://ii t. 10/ JCqIV (PyTorch), http:://gtt..t.i:teet to/CqpP (TensorFlow)

---

Published as a conference paper at ICLR 2022
Integrated Gradients
FastSHAP
KernaiS
KamalSHAP-S
GradCAM
Smooth
DeepSHAP
Englian Springer
Gua Pump
Teach
Figure 1: Explanations generated by each method for Imagenette images.
squares characterization and investigate several ways to reduce gradient variance during training. Our experiments show that FastSHAP provides accurate Shapley value estimates with an orders- of-magnitude speedup relative to non-amortized estimation approaches. Finally, also find that FastSHAP generates high-quality image explanations (fig. 1) that outperform gradient-basee meth- ods (e.g., IntGrad and GradCAM) quantitative inclusion and exclusion metrics.
BACKGROUND
In this section, introduce notation used throughout the paper and provide overview of Shapley values and their weighted least squares characterization. Let x E A' be a random vector consisting of d features, classification problem. We use E [0, to denote subsets of the indices {l....,dd d} and define X, : { i: The symbols x, y, are random variables and x. y, denote possible values. We use and 0 to denote vectors of ones and zeros in R2 so that 1 s is a subset's 's cardinality, and we use e; to denote the ith standard basis vector. Finally, fxx 17) X' K is a model that outputs probability distribution over given and (x; is the probability for the yth class.
(x....., X,),, and let E Y f., K} be the response variable for
2.1 SHAPLEY VALUES
Shapley values were originally developed as a credit allocation technique in cooperative game the- ory (Shapley, 1953), but they have since been adopted explain predictions from black-box ma- chine learning models (Strumbelj and Kononenko, 2014; Datta al., 2016; Lundberg and Lee, 2017). For any value function (or set function) v 2d + IR, the Shapley values @(v) E Rd, or (,(v) IR for each feature 1,.... d, are given by the formula
(1)))
1 Σ d #1
d d-11 ITs)
- (u()+
(1)
The difference v(s + e,) v(s) represents the ith feature's contribution the subset and the summation represents a weighted average across all subsets that do not include i. In the model explanation context, the value function chosen to represent how individual prediction varies as different subsets of features are removed. For example, given an input-output pair (I, y). the prediction for the yth class can be represented by a value function Us,y defined
Ur ) link
E ((x1-.)
[fy (Iis (1,,
where the held out features X1-s are marginalized out using their joint marginal distribution p(x1-x), and link function (e.g., logit) is applied to the model output. Recent work has debated the properties of different value function formulations, particularly the choice of how to remove features (Aas et al., 2019; Janzing et al., 2020; Frye et al., 2020; Covert et al., 2021). However, regardless of the formulation, this approach model explanation enjoys several useful theoretical properties due to its use of Shapley values: for example, the attributions are zero for irrelevant fea- tures, and they are guaranteed to sum to the model's prediction. We direct readers to prior work for a detailed discussion of these properties (Lundberg and Lee, 2017; Covert et al., 2021).
Unfortunately, Shapley values also introduce computational challenges: the summation in eq. (1) involves an exponential number of subsets, which makes it infeasible to calculate for large Fast approximations therefore required in practice, discuss next.
2

---

Published as a conference paper at ICLR 2022
2.2 KERNELSHAP
KerneSSHAP (Lundberg and Lee, 2017) is a popular Shapley value implementation that relies on an alternative Shapley value interpretation. Given value function Us,y(S), eq. (1) shows that the values ((2,,y) are the features' weighted average contributions; equivalently, their weighted least squares characterization says that they are the solution to an optimization problem over dx,y E R
((tayy) = arg min E (wa..(() V2,y (0) - (/o)))))
BNLy p(s)
s.t. 1 D2 (2, - -U2,(())
(Efficiency constraint)
where the distribution p(s) is defined as
d
p(s)
(Shapley kernel)
1 8 (d - ss
for such that 0 1 d (Charnes et al., 1988). Based on this view of the Shapley value, Lundberg and Lee (2017) introduced KemeISHAP, a stochastic estimator that solves an approxi- mate version of eq. (3) given some number of subsets sampled from p(s). Although the estimator is consistent and empirically unbiased (Covert and Lee, 2021), KemneSSHA often requires many samples to achieve accurate estimate, and it must solve eq. (3) separately for each input-output pair (z, y). As result, it is unacceptably slow for some use cases, particularly in settings with large, high-ddmensional models. Our approach builds on KemelSHAA. leveraging the Shapley value's weighted least squares characterization to design a faster, amortized estimation approach.
3 FASTSHAP
We now introduce FastSHAP, a method that amortizes the cost of generating Shapley values across many data samples. FastSHAP has two main advantages over existing approaches: (1) it avoids solving separate optimization problems for each input to be explained, and (2) it can use similar data points efficiently learn the Shapley value function ((vx.)))
3.1 AMORTIZING SHAPLEY VALUES
In our approach, we propose generating Shapley value explanations using a learned parametric func- tion d'ass (x, 0) x y + Rd Once trained, the parametric function can generate explanations in single forward pass, providing a significant speedup over methods that approximate Shapley val- ues separately for each sample (ar, y). Rather than using dataset of ground truth Shapley values for training. we train dtast (x, y; 8) by penalizing its predictions according to the weighted least squares objective in eq. (3), or by minimizing the following loss,
((0) E EEE
E p(x) Unifly) p(e)
E
Ux, (Ixxy(s) Ux,y (0) T Orast (aa,xxx,1 ())
(4)
where Unif(y) represents a uniform distribution over classes. the model's predictions are forced to satisfy the Efficiency constraint, then given a large enough dataset and a sufficiently expressive model class for drast the global optimizer Ófast (x. (*) is a function that outputs exact Shapley values (see proof in appendix A). Formally, the global optimizer satisfies the following:
fust y;
y; 0*) d(xx.y) almost surely in p(x,y).
(5)
We explore two approaches to address the efficiency requirement. First, we can enforce efficiency by adjusting the Shapley value predictions using their additive efficient normalization (Ruiz et al., 1998), which applies the following operation to the model's outputs:
Fastt (I, yi 0) étest (x, y: 0) + d (1) Ve.y (0) 1J y/ 8:6))
dtnat (I,
(6)
Efficiency gop
The normalization step can be applied at inference time and optionally during training; in ap- pendix B, we show that this step is guaranteed to make the estimates closer to the true Shapley values. the efficiency
Second, relax the efficiency property by augmenting L(0) with penalty gap (see eq. (6)); the penalty requires a parameter y > 0, and as we set y - oo we can guarantee that efficiency holds (see appendix A). Algorithm 1 summarizes our training approach.
3

---

FastSHAP has the flexibility to work with any value function (s). Here, we de- scribe a default value function that useful Published as a conference paper at ICLR 2022
Empirical considerations. Optimizing [()) using a single set of samples (z. y, s) is problematic because of high variance in the gradients, which can lead to poor optimization. We therefore consider several steps to reduce gradient variance. First, as is conventional in deep learning, we minibatch across multiple samples from p(x). Next, when possible, we calculate the loss jointly across all classes y E (1....; K). Then, we experiment with using multiple samples 8 ~ p(s) for each input sample æ. Finally, we explore paired sampling, where each sample is paired with its complement 1 s, which has been shown to reduce KemelSHAA's variance (Covert and Lee, 2021). Appendix C shows proofs that these steps are guaranteed to reduce gradient variance, and ablation experiments in appendix demonstrate their improvement on FastSHAP's accuracy.
3.2 A DEFAULT VALUE FUNCTION FOR FASTSHAP
Algorithm 1: FastSHAP training
Input: Value function Uz.y. learning rate Output: FastSHAP explainer @rast (x, y;
for explaining predictions from classifica- tion model.
initialize @tast (x. y; while not converged do
The value function's aim is assess, for each subset s, the classification probability when only the features x, observed. Be- cause most models n(x; do not support making predictions without all the features, we require an approximation that simulates the inclusion of only x, (Covert et al., 2021). To this end, we use supervised surrogate model (Frye et al.. 2020; Jethani al., 2021)
sample I p(x). y ~ Unif(y). s p(s)
predict @ 4- Drast (I, y; 0)
if normalize then
set 3 l+d
(2.
end calculate
L (va,((s) vx,y( - sf x))
to approximate marginalizing out the remain- ing features x1-s using their conditional dis- tribution.
update +- 1 - a VoL
end
Separate from the original model f'xx; 11), the surrogate model (y mmxx, s); B) takes as input vector of masked features m22 8). where the masking function m replaces features x; such that 8; = 0 with a [mask] J value that is not in the support of X. Similar to prior work (Frye et al., 2020; Jethani et al., 2021), the parameters 3 are learned by minimizing the following loss function:
[(3)
E p(x) p(s)
E
PKK (xx;;) ll P m(xx mmxx,)):8)) s))
It has been shown that the global optimizer eq. (7), or Peurr (y lent to marginalizing out features from f(x; n) with their conditional distribution (Covert et al., 2021):
m(x, s); 3*), is equiva-
Paurr (y) m(x, s); 3r) = (x: x, xx]]
The choice of distribution over p(s) does not affect the global optimizer of eq. (7), but we use the Shapley kernel to put more weight on subsets likely to be encountered when training FastHHAP. We use the surrogate model as default choice for two reasons. First, it requires a single prediction for each evaluation of (s), which permits faster training than the common approach of averaging across many background samples (Lundberg and Lee, 2017; Janzing et al., 2020). Second, it yields explanations that reflect the model's dependence on the information communicated by each feature, rather than its algebraic dependence (Frye et al., 2020; Covert et al., 2021).
RELATED WORK
Recent work on Shapley value explanations has largely focused on how to remove features (Aas et al., 2019; Frye et al., 2020; Covert et al., 2021) and how to approximate Shapley values effi- ciently (Chen et al., 2018b; Ancona et al., 2019; Lundberg et al., 2020; Covert and Lee, 2021). Model-specific approximations are relatively fast, but they often introduce bias and are entangled with specific feature removal approaches (Shrikumar et al., 2017; Ancona et al., 2019; Lundberg et al., 2020). In contrast, agnel-agn stochastic approximations trade off run-time and accuracy in the explanation. For example, KernelSHAP samples subsets to approximate the solution to weighted least squares problem (Lundherg and Lee, 2017), while other
more flexible, but they must
4

---

Published as a conference paper at ICLR 2022
News
Census
Bankruptcy
0.25
0.20
0.150
Mean 1, distancc
0.20
0.125
0.15
0.100
0.10
0.075
0.10
0.050
0.05
0.05
0.025
0.00
0.00
0.000
250
500
750
3000
1250
3500
0
200
400
600
800
1000
1200
500
1000
1500
2000
Evi's
Evols
KernelSHAP
KemneISHAP (Paired)
Permutation Sampling
Permutation Sampling (Anüthetical
FastSHAP
Figure 2: Comparison of Shapley value approximation accuracy across methods. Using three datasets, we measure the distance of each method's estimates to the ground truth as function of the number of model evaluations. FastSHAP is represented by horizontal line since it requires only a single forward pass. The baselines require x model evaluations achieve FastSHAP's level of accuracy.
approaches sample marginal contributions (Castro et al., 2009; Strumbelj and Kononenko, 2014) or feature permutations (Illés and Kerényi, 2019; Mitchell et al., 2021). FastSHAP trains an explainer model to output an estimate that would otherwise require orders of magnitude more model evalu- ations, and, unlike other fast approximations, it is agnostic to the model class and feature removal approach.
Other methods have been proposed to generate explanations using learned explainer models. These referred to as amortized explanation methods (Covert et al., 2021; Jethani al., 2021), and they include several approaches that are comparable to gradient-based methods in terms of compute time (Dabkowski and Gal, 2017; Chen et al., 2018a, Sa; Yoon et al., 2018; Schwab and Karlen, 2019; Schulz et al., 2020; Jethani et al., 2021). Notably, one approach generates training dataset of ground truth explanations and then learns an explainer model to output explanations directly (Schwab and Karlen, 2019)-a principle that can be applied with any attribution method, at least in theory. How- ever, for Shapley values, generating large training set would be very costly, so FastSHAP sidesteps the need for training set using a custom loss function based on the Shapley value's 's weighted least squares characterization (Charnes et al., 1988).
5 STRUCTURED DATA EXPERIMENTS
We analyze FastSHAP's performance by comparing it several well-understood baselines. First, we evaluate its accuracy on tabular (structured) datasets by comparing its outputs to the ground truth Shapley values. Then, to disentangle the benefits of amortization from the in-distribution value function, we make the same comparisons using different value function formulations Ug (s). Unless otherwise stated, we use the surrogate model value function introduced in section 3.2. Later, in section 6, we test FastSHAP's s ability to generate image explanations.
Baseline methods. To contextualize FastSHAP's accuracy, we compare it to several non- amortized stochastic estimators. First, we compare to KemneSSHAP (Lundberg and Lee, 2017) and its acceleration that uses paired sampling (Covert and Lee, 2021). Next, we compare to a permu- tation sampling approach and its acceleration that uses antithetical sampling (Mitchell et al., 2021). As performance metric, we calculate the proximity to Shapley values that were obtained by run- ning KernelSHAP to convergence; we use these values as our ground truth because KernelSHAP is known to converge to the true Shapley values given infinite samples (Covert and Lee, 2021). These baselines were all run using an open-source implementation."
Implementation details. and (y mxx s); B). The FastSHAP explainer model diast (x. y; f) is implemented with a network g(x; 8) X + Rd x )) that outputs a vector of Shapley values for every y )) deep neural networks are ideal for FastSHAP because they have high representation capacity, they can provide many-to-many mappings, and they be trained by stochastic gradient descent. Appendix D con- tains more details about our implementation, including model classes, network architectures and training hyperparameters.
We use either neural networks or tree-based models for each of f(x; ())
htttps://gi http:/ttcc.////ooooote///aageeee
(License: MIT)
5

---

Published as a conference paper at ICLR 2022
Surrogate
Baseline
Marginal
6.10
0.10
Mcon /, diittance
0.06
0.06-
0.02
0.02
0.00
200
400
6:00
200
400
600
250
500
750
1000
1250
1500
KernelSHAP
KerneISHAP (Paired)
Permutation Sampling
Permutation Sampling (Anüthetical
FastSHAP
Figure 3: FastSHAP approximation accuracy for different value functions. Using the market ing dataset, we find that FastSHAP provides accurate Shapley value estimates regardless of the value function (surrogate, marginal, baseline), with the baselines requiring 200- 10001000x model evaluations to achieve Fast- SHAP's level of accuracy. Error bars represent 95% confidence intervals.
We also perform a series of experiments to determine several training hyperparameters for FastSHAP, exploring (1) whether or not use paired sampling, (2) the number of subset samples use, and (3) how to best enforce the efficiency constraint. Based on the results (see appendix D), we use the following settings for our tabular data experiments: we use paired sampling, between 32 and 64 samples of s per sample, additive efficient normalization during both training and inference, and we set y = (since the normalization step is sufficient to enforce efficiency).
5.1 ACCURACY OF FASTSHAP EXPLANATIONS
Here, we test whether FastSHAP's estimates are close to the ground truth Shapley values. Our exper- iments use data from 1994 United States census, a bank marketing campaign, bankrupt statistics, and online news articles (Dua and Graff, 2017). The census data contains 12 input fea- tures, and the binary label indicates whether a person makes over $50K a year (Kohavi et al., 1996). The market ing dataset contains 17 input features, and the label indicates whether the customer subscribed to a term deposit (Moro et al., 2014). The bankrupt dataset contains 96 features de- scribing various companies and whether they went bankrupt (Liang et al., 2016). The news dataset contains 60 numerical features about articles published on Mashable, and our label indicates whether the share count exceeds the median number (1400) (Fernandes et al., 2015). The datasets were each split 80/10/10 for training, validation and testing.
In fig. 2, we show the distance of each method's estimates to the ground truth as function of the number of model evaluations for the news, census and bankrupt ey datasets. Figure shows results for the market ing dataset with three different value functions (see section 5.2). For the baselines, each sample s requires evaluating the model given a subset of features, but since Fast- SHAP requires only a single forward pass of irstt (x, y; 0), we show it as horizontal line.
To reach FastSHAP's level of accuracy on the news, census and bankruptey datasets, Ker- nelSHAP requires between 1,200-2,000 model evaluations; like prior work (Covert and Lee, 2021), we find that paired sampling improves KernelSHAP's rate of convergence, helping reach Fast- SHAP's accuracy in 250-1,000 model evaluations. The permutation sampling baselines tend to be faster: the original version requires between 300-1,000 evaluations, and antithetical sampling takes 200-500 evaluations to reach an accuracy equivalent to FastSHAP. Across all four datasets, however, FastSHAP achieves its level of accuracy at least at least 600x faster than the original version of KernelSHAP, and 200x faster than the best non-amortized baseline.
5.2 DISENTANGLING AMORTIZATION AND THE CHOICE VALUE FUNCTION
In this experiment, we verify that FastSHAP produces accurate Shapley value estimates regardless of the choice of value function. We use the marketing dataset for this experiment and test the following value functions:
1. (Surrogate/Inddistribbtt (s) Psure (v mmx s);
2. (Marginal/Qutt-o--iiitiiii
Uz,y(8. (s) Ep(xi-.) Ifg X1-s
3. (Baseline removal) (s, = fy (x., -::--::-1 n). where x² E X are fixed baseline values (the mean for continuous features and mode for discrete ones)
:

---

Published as a conference paper at ICLR 2022
Integrated
GradCAM
DeepSHUAP
Hone
Bird
Airpaine
Figure 4:
Explanations generated by each method for CIFAR-10 images.
In fig. 3 we compare FastSHAP to the same non-amortized baseline methods, where each method generates Shapley value estimates using the value functions listed above. The results show that FaPtHHP maintains the same computational advantage across all three cases: to achieve the same accuracy as FastSHAP's single forward pass, the baseline methods require at least 200 model evalu- ations, but in some cases up to nearly 1,000.
IMAGE EXPERIMENTS
Images represent a challenging setting for Shapley values due to their high dimensionality and the computational cost of model evaluation. We therefore compare FaPtSHAP to KernelSHAP on two image datasets. We also consider several widely used gradient-baut -bsed explanation methods, because they are the most commonly used methods for explaining image classifiers.
6.1 DATASETS
We consider two popular image datasets for our experiments. CIFAR-10 (Krizhevsky et al., 2009) contains 60,000 32 x 32 images across 10 classes, and we use 50,000 samples for training and 5,000 samples each for validation and testing. Each image is resized to 224 x 224 using bilinear interpolation to interface with the ResNet-50 architecture (He al., 2016). Figure shows example CIFAR-10 explanations generated by each method. The Imagenette dataset (Howard and Gugger, 2020), a subset of 10 classes from the ImageNet dataset, contains 13,394 total images. Each image cropped to keep the 224 x 224 central region, and the data is split 9, 0,469/1,963/1,,1 Example Imagenette explanations are shown in fig. 1.
6.2 EXPLANATION METHODS
We test three Shapley value estimators, FastSHAP, KernelSHAP, and DeepSHAP (Lundberg and Lee, 2017), where the last is an existing approximation designed for neural networks. We test Ker- nelSHAP with the zeros baseline value function, which we refer to simply as KemellSAA, and with the in-distribution surrogate value function, which we refer to as KerneISHAP-S. We also com- pare these methods to the gradient-based explanation methods GradCAM (Selvaraju et al., 2017), SmoothGrad (Smilkov et al., 2017) and IntGrad (Sundararajan al., 2017). Gradient-basse methods are relatively fast and have therefore been widely adopted for explaining image classifiers. Finally, we also compare to CXPlain (Schwab and Karlen, 2019), amortized explanation method that generates attributions that are not based on Shapley values.
Implementation details. The models f(x: 7) and Paurr | mm(x s); are both ResNet-50 net- works (He et al., 2016) pretrained on ImageNet and fine-tuned on the corresponding imaging dataset. FastSHAP, CXPlain, and KerneISHAP are all implemented to output 14 x 14 superpixel attributions for each class. For FastSHAP, we parameterize Prast (x, y; 0) to output superpixel attributions: we use an identical pretrained ResNet-50 but replace the final layers with 1 x convolutional layer so that the output is 14 x 14 x K (see details appendix D). We use an identical network to produce attributions for CXPlain. For FastSHAP, we do not use additive efficient normalization, and we set 7 0; find that this relaxation of the Shapley value's efficiency property does not inhibit FastSHAP's ability to produce high-quality image explanations. KernelSHAP and KernelSHAP-S implemented using the shap package's default parameters, and GradCAM, SmoothGrad, and IntGrad are implemented using the t eeeeeeplliin package's default parameters.
Phttps://shhe readthedocs oo/en///e///e latest// (License: MIT)
'https: htttps:/ttf-epp) lain. readthedocs. io/en/ ateat/ (License: MIT)
7

---

Published as a conference paper at ICLR 2022
6.3 QUALITATIVE REMARKS
Explanations generated by each method are shown in fig. 4 for CIFAR-10 and fig. 1 for Imagenette (see appendix E for more examples). While a qualitative evaluation is insufficient to draw conclu- sions about each method, we offer several remarks on these examples. FastSHAP, and to some extent GradCAM, appear to reliably highlight the important objects, while the KerneISHAP explanations noisy and fail to localize important regions. To lesser extent, CXPlain occasionally highlights important regions. In comparison, the remaining methods (SmoothGrad, IntGrad and DeepSHAP) granulated and highlight only small parts of the key objects. Next, consider quantitative metrics that test these observations more systematically.
Exclusion Curve
6.4 QUANTITATIVE EVALUATION
0.8
Evaluating the quality of Shapley value estimates requires access to ground truth Shapley values, which is computationally infeasible for images. In- stead, we use two metrics that evaluate an expla-
0.7
Top Accuracy
0.6
nation's ability to identify informative image re- gions. These metrics build on several recent pro- posals (Petsiuk et al., 2018: Hooker et al., 2018; Jethani et al., 2021) and evaluate the model's clas- sification accuracy after including or excluding pix- els according to their estimated importance.
0.5
0.4
0.3
0.2
Similar to Jethani et al. (2021), we begin by train- ing single evaluation model Peval approximate the f(x; 7) model's 's output given a subset of fea- tures; this serves an alternative training sepa- rate models on each set of features (Hooker et al., 2018) and offers a more realistic option than mask- ing features with zeros (Schwab and Karlen, 2019). This procedure analogous to the Psur training procedure in section 3.2, except it sets the subset distribution to p(s) = Uniform ((0, 1)d)) to ensure all subsets equally weighted.
20
40
60
80
100
Exclusion %
Inclusion Curve
0.8
Top 1 Accuracy
KemelSHAP
0.6
KereiSHHA-S
GradCAM
0.4
Integrated Gradients
SmoothGrad
DeepSHAP
Next, we analyze how the model's predictions change as we remove either important or unimpor- tant features according to each explanation. Using a set of 1,000 images, each image is first labeled by the original model fx: 17) using the most likely pre- dicted class. We then use explanations generated by each method to produce feature rankings and com- pute the top-1 accuracy (a measure of agreement with the original model) as we either include or ex- clude the most important features, ranging from 0- 100%. The area under each curve (AUC) is termed the Inclusion AUC or Exclusion AUC.
0.2
CXPlain
FAP
0.0
20
40
60
80
100
Inclusion %
Figure 5: Imagenette inclusion and exclusion curves. The change in top- accuracy an in- creasing percentage of the pixels estimated be important are excluded (top) or included (hottom).
These metrics match the idea that accurate image explanation should (1) maximally degrade the performance of Peval when important features are excluded, and (2) maximally improve the perfor- mance of Poval when important features are included (Petsiuk et al., 2018: Hooker al., 2018). The explanations are evaluated by removing superpixels; for gradient-based methods, we coarsen the ex- planations using the sum total importance within each superpixel. In appendix E, we replicate these metrics using log-ode odds rather than top-1 accuracy, finding similar ordering among methods.
Results. Table 1 shows the Inclusion and Exclusion AUC achieved by each method for both CIFAR-I0 and Imagenette. In fig. 5, we also present the curves used to generate these AUCs for Imagenette. Lower Exclusion AUCs and higher Inclusion AUCS are better. These results show that FastSHAP outperforms all baseline methods when evaluated with Exclusion AUC: when the pixels identified as important by FastSHAP removed from the images, the sharpest decline in top-1 1 ac- curacy is observed. Additionally, FastSHAP performs well when evaluated on the basis of Inclusion AUC, second only to KerneISHAP-S.
8

---

Published as a conference paper at ICLR 2022
Table 1: Exclusion and Inclusion AUCs. Evaluation of each method on the basis of Exclusion AUC (lower is better) and Inclusion AUC (higher is better) calculated using top-1 accuracy. Parentheses indicate 95% confidence intervals, and the best methods are bolded in each column.
CIFAR-10
Imagenette
Exclusion AUC
Inclusion AUC
Exclusion AUC
Inclusion AUC
PastSHAP
0.42 (0.41, 0.43)
0.78 (0.77, 0.79)
0.51 (0.49, 0.52)
0.79 (0.78, 0.80)
KernelSHAP
0.64 (0.63, 0.65)
0.78 (0.77, 0.79)
0.68 (0,67, 0.70)
0.77 (0.75, 0.78)
KerneISHAP-S
0.54 (0.52, 0.55)
0.86 (0.85, 0.87)
0.61 (0.60, 0.62)
0.82 (0.80, 0.83)
GradCAM
0.52 (0.51, 0.53)
0.76 (0.75, 0.77)
0.52 (0.50, 0.53)
0.74 (0.73, 0.76)
Integrated Gradients
0.55 (0.54, 0.56)
0.74 (0.73, 0.75)
0.65 (0.64, 0.67)
0.73 (0.71, 0.74)
SmoothGrad
0.70 (0.69, 0.71)
0.72 (0.71, 0.73)
0.72 (0.71, 0.73)
0.73 (0.72, 0.75)
DeepSHAP
0,65 (0.64, 0.66)
0.79 (0.78, 0.80)
0.69 (0,68, 0.71)
0.74 (0.73, 0.75)
CXPlain
0.56 (0.55, 0.57)
0.71 (0.70, 0.72)
0.60 (0.58, 0.61)
0.72 (0.71, 0.74)
For Imagenette, GradCAM performs competitively with FastSHAP on Exclusion AUC and KemelSHAP-S marginally beats FastSHAP on Inclusion AUC. KemelSHAP-S also outperforms on Inclusion AUC with CIFAR-10, which is perhaps surprising given its high level of noise (fig. 4). However, KerneISHAP-S does not do as well when evaluated using Exclusion AUC, and GradCAM does not do as well on Inclusion AUC. The remaining methods are, by and large, not competitive on either metric (except DeepSHAP on CIFAR- 10 Inclusion AUC). An accurate explanation should perform well on both metrics, so these results show that FastSHAP provides the most versatile ex- planations, because it is the only approach to excel at both Inclusion and Exclusion AUC.
Finally, we also test FastSHAP's robustness to limited training data. appendix E, we find that FastSHAP outperforms most baseline methods Inclusion and Exclusion AUC when using just 25% the Imagenette data, and that remains competitive when using just 10%.
6.5 SPEED EVALUATION
Table 2: Training and explanation run-times for 1,000 images (in minutes).
The image experiments were run using cores of an Intel Xcon Gold 6148 processor and sin- gle NVIDIA Tesla V100. Table records the time required to explain 1,000 images. For Fast- SHAP, KernelSHAP-S and CXPlain, we also report the time required to train the surrogate and/or explainer models.
CIFAR-10
Imagenette
FastSHAP
0.04
0.04
KemeISHAP
453.69
1089.50
KemeISHAP-S
460.10
586.12 12
Explain
GradCAM
0.38
0.30
IntGrad
0.91
0.92
The amortized explanation methods, FastSHAP and CXPlain, incur a fixed training cost but very low marginal cost for each explanation. The gradient-based methods are slightly slower, but KemnelSHAP requires significantly more time. These results suggest that FastSHAP is well suited for real-time applications where cru- cial to keep explanation times as low as possible. Further, when users need to explain large quantity of data, FastSHAP's s low explanation cost can quickly compensate for its training time.
SmoothGrad
1.05
DeepSHAP
5.39
6.01
CXPlain
0.04
0.04
FastSHAP
693.57
146.49
Train
KemeISHAP-S
362.03
73.22
CXPlain
538.49
93.00
DISCUSSION
In this work, we introduced FastSHAP, a method for estimating Shapley values in single for- ward pass using a learned explainer model. To enable efficient training, we sidestepped the need for a training set and derived a learning approach from the Shapley value's weighted least squares characterization. Our experiments demonstrate that FastSHAP can produce accurate Shapley value estimates while achieving a significant speedup over non-amortized approaches, as well as more accurate image explanations than popular gradient-based methods.
While Shapley values provide a strong theoretical grounding for model explanation, they have not been widely adopted for explaining large-scale models due to their high computational cost. Fast- SHAP can solve this problem, making fast and high-quality explanations possible in fields such as computer vision and natural language processing. By casting model explanation as a learning prob- lem, FastSHAP stands to benefit as the state of deep learning advances, and it opens a new direction of research for efficient Shapley value estimation.

---

Published as a conference paper at ICLR 2022
8 REPRODUCIBILITY
Code to implement FastSHAP is available online in two separate repositories: https: com/ / contains PyTorch implementation and https://githi: TensorFlow implementation, both with examples of tabu- lar and image data experiments. The complete code for our experiments available https: //githtt thub. com com/iclrne ficcrr1144 1181411astttaaaie
com/neil jethani/ / fastshap/
and details are described throughout section 5 and section 6, with model architectures and hyperparameters reported in appendix D. Proofs for our theoretical claims are provided in appendix A, appendix B, and appendix C.
ACKNOWLEDGEMENT
We thank the reviewers for their thoughtful feedback, and thank the Lee Lab for helpful dis- cussions. Neil Jethani was partially supported by NIH T32 GM136573. Mukund Sudarshan was partially supported by PhRMA Foundation Predoctoral Fellowship. Mukund Sudarshan and Rajesh Ranganath were partly supported by NIH/NHLBI Award N01HL148248 and by NSF Award 1922658 NRT-HDR: FUTURE Foundations, Translation, and Responsibility for Data Sci- ence. lan Covert and Su-In Lee were supported by the NSF Awards CAREER DBI-1552309 and DBI-1759487; the NIH Awards R35GM128638 and ROINIAAGO6! 132; and the American Cancer Society Award
REFERENCES
Aas, K., Jullum, M., and Løland, A. (2019). Explaining individual predictions when features are dependent: More accurate approximations to Shapley values. arXiv preprint arXiv: 10464.
Ancona, M., Oztireli, C., and Gross, M. (2019). Explaining deep neural networks with a polyno- mial time algorithm for Shapley value approximation. In International Conference Machine Learning, pages 272-281. PMLR.
Castro, J., Gómez, D., and Tejada, J. (2009). Polynomial calculation of the Shapley value based on sampling. Computers Operations Research, 3665):1726
Charnes, A., Golany, B., Keane, M., and Rousseau, J. (1988). Extremal principle solutions of games in characteristic function form: core, Chebychev and Shapley value generalizations. In Econometrics of Planning and Efficiency, pages 123-133. Springer.
Chen, J., Song, L., Wainwright, M., and Jordan, M. (2018a). Learning to explain: An information- theoretic perspective on model interpretation. International Conference on Machine Learning, pages 883 892. PMLR.
Chen, J., Song, L., Wainwright, M. J., and Jordan, M. (2018b). L-Shapley and C-Shapley: Efficient model interpretation for structured data. arXiv preprint arXiv: 02610.
Chen, T. and Guestrin, C. (2016). XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794.
Covert, I. and Lee, S.-L (2021). Improving KemelSHAP. Practical Shapley value estimation using linear regression. In International Conference on Artificial Intelligence and Statistics, pages 3457- 3465. PMLR.
Covert, I., Lundberg, S., and Lee, S.-I. (2020). Understanding global feature contributions with additive importance measures. Advances in Neural Information Processing Systems, 33.
Covert, I., Lundberg, S., and Lee, S.-I. (2021). Explaining by removing: A unified framework for model explanation. Journal of Machine Learning Research, 22(209):1-90.
Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314.
Dabkowski, P. and Gal, Y. (2017). Real time image saliency for black box classifiers. In Advances in Neural Information Processing Systems, pages 6967-6976.
10

---

Published as a conference paper at ICLR 2022
Datta, A., Sen, S., and Zick, Y. (2016). Algorithmic Transparency via Quantitative Input Influence: Theory and Experiments with Learning Systems. In Proceedings 2016 IEEE Symposium on Security and Privacy, SP 2016, pages 098.117. Institute of Electrical and Electronics Engineers Inc.
Dua, D. and Graff, C. (2017). UCI machine learning repository.
Fernandes, K., Vinagre, P., and Cortez, P. (2015). A proactive intelligent decision support system for predicting the popularity online news. Portuguese Conference on Artificial Intelligence. pages 535-546. Springer.
Frye, C., de Mijolla, D., Begley, T., Cowton, L.,, Stanley, M., and Feige. I. (2020), Shapley explain- ability on the data manifold. International Conference on Learning Representations.
He. K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770- 778.
Hooker, S., Erhan, D., Kindermans, P.-.,, and Kim, (2018). A benchmark for interpretability methods in deep neural networks. arXiv preprint arXiv:1800 10758.
Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural Net- works, 4(2):511257.
Howard, J. and Gugger, S. (2020). FastAl: layered API for deep learning. Information, 11(2):108.
Illés, F. and Kerényi, P. (2019). Estimation of the Shapley value by ergodic sampling. arXiv preprint arXiv:1906.0522.
Janzing, D., Minorics, L., and Blöbaum, P. (2020). Feature relevance quantification in explainable Al: A causal problem. International Conference on Artificial Intelligence and Statistics, pages 2907-2916. PMLR.
Jethani, N., Sudarshan, M., Aphinyanaphongs. Y., and Ranganath, R. (2021). Have learned to explain?: How interpretability methods can learn to encode predictions their interpretations. In International Conference Artificial Intelligence and Statistics, pages 1459-1467. PMLR.
Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. (2017). LightGBM: A highly efficient gradient boosting decision tree. Advances in Neural Information Processing Systems, 50:3146-3152
Kohavi, R. al. (1996). Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Knowledge Discovery and Data Mining, volume 96, pages 202-207.
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images.
Liang, D., Lu, C.-C., Tsai, C.-F. and Shih, G.-A (2016). Financial ratios and corporate governance indicators in bankruptey prediction: A comprehensive study. European Journal of Operational Research, 252(2):561-577
Lipovetsky, S. and Conklin, M. (2001). Analysis of regression in game theory approach. Applied Stochastic Models in Business and Industry, 17(4)31193330
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, M., Nair, B., Katz, R., Himmel- farb. J., Bansal, N., and Lee, S.-I. (2020). From local explanations to global understanding with explainable AI for trees. Nature Machine Intelligence, 2(1):56-67.
Lundberg, S. M. and Lee, S. (2017). A unified approach to interpreting model predictions. Ad- vances in Neural Information Processing Systems, 30:4765-4774,
Mitchell, R., Cooper, J.. Frank, E.,, and Holmes, G. (2021). Sampling permutations for Shapley value estimation, arXiv preprint arXiv:2104 10t.22994..99 12199.
Moro, S., Cortez, P. and Rita, P. (2014). A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31.

---

Published as a conference paper at ICLR 2022
Petsiuk, V., Das, A., and Saenko, K. (2018). RISE: Randomized input sampling for explanation of black-box models. arXiv preprint arXiv:1806.0742)
Ruiz, L. M., Valenciano, F,, and Zarzuelo, J. M. (1998), The family of least square values for transferable utility games. Games and Economic Behavior, 24(1-2):09-1330
Schulz, K., Sixt, L.,, Tombari, F., and Landgraf. T. (2020). Restricting the flow: Information bottle- necks for attribution. arXiv preprint arXiv:2001.00396.
Schwab, P. and Karlen, W. (2019). CXPlain: Causal explanations for model interpretation under uncertainty. In Advances in Neural Information Processing Systems, pages 10220-10230.
Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D. (2017). Grad- CAM: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE International Conference on Computer Vision, pages 618-626.
Shapley, L. S. (1953). A value for n-person games. Contributions to the Theory of Games, 2(28):307- 317.
Shrikumar, A., Greenside, P., and Kundaje, A. (2017). Learning important features through propagat- ing activation differences. In International Conference Machine Learning, pages 3145-3 3153. PMLR.
Smilkov, D., Thorat, N., Kim, B., Viégas, F,, and Wattenberg, M. (2017). Smoothgrad: removing noise by adding noise. arXiv preprint arXiv:1706.03383
Strumbelj, E. and Kononenko, I. (2014). Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems, 41(3):447-665.
Sundararajan, M., Taly, A., and Yan, Q. (2017). Axiomatic attribution for deep networks. Inter- national Conference on Machine Learning, pages 1319-3328. PMLR.
Van den Broeck, G., Lykov, A., Schleich, M., and Suciu, D. (2021). On the tractability of SHAP explanations. In Proceedings of the 35th Conference on Artificial Intelligence (AAAI).
Wang, R., Wang. X., and Inouye, D. I. (2021). Shapley explanation networks. In International Conference Learning Representations.
Yoon, J., Jordon, J., and van der Schaar, M. (2018). INVASE: Instance-wist variable selection using neural networks. In International Conference on Learning Representations.
12

---

Published as a conference paper at ICLR 2022
A FASTSHAP GLOBAL OPTIMIZER
Here, we prove that FastSHAP is trained using an objective function whose global optimizer outputs the true Shapley values. Recall that the loss function for the explainer model G (x, y; 0)
(() = E E
E p(x) Unifly) p(s)
(Ux Uxxy (0) s drast (x, (x))
As mentioned in the main text, it is necessary to force the model to satisfy the Efficiency constraint, or the property that the predictions from Grast y; satisfy
@fast (z, y; 0) = Uz (1) U2 (0) VzEd,Ey.
One option for guaranteeing the efficiency property adjust the model outputs using their additive efficient normalization (see section 3.1). Incorporating this constraint on the predictions, we can then view the loss function as an expectation across (x, y) and write the expected loss for each sample (ar, y) separate optimization problem over the variable Px,y E Rd:
min E 2x.u p(s) [V (s) - U2,2 (0) - -s &n..y) T P
(9)
s.t. 2z
v u
(0)
This a constrained weighted least squares problem with unique global minimizer, and it is precisely the Shapley value's s weighted least squares characterization (see eq. (3)). We can therefore conclude that the optimal prediction for each pair (I, y) is the true Shapley values, or that oz,y = ((vr.y) As a result, the global optimizer for our objective a model @rast (x 0*) that outputs the true Shapley values almost everywhere in the data distribution p(x,y).
Achieving the global optimum requires the ability to sample from p(x) (or a sufficiently large dataset), perfect optimization, and function class for érest (x, y; 0) that expressive enough to contain the global optimizer. The universal approximation theorem (Cybenko, 1989; Hornik, 1991)
implies that a sufficiently large neural network can represent the Shapley value function arbitrary accuracy as long as it is continuous function. Specifically, we require the function (x) = of ((v,,))
to be continuous x for y. This holds in practice when we use a surrogate model parameterized by continuous neural network, because (8) is continuous in æ for all (s, v), and the Shapley value is a linear combination of (s, across different values of s (see eq. (1)).
Another approach to enforce the efficiency property is by using efficiency regularization, penal- izing the efficiency gap in the explainer model's predictions (section 3.1). If we incorporate this regularization term with parameter problem for each (I, y) pair:
0, then our objective yields the following optimization
min E (V2,p U2 (0) ST do.w) &z, p(s)
"| + (V - (22 1 1T
For finite hyperparameter values 7 E [0, oo), this problem relaxes the Shapley value's 's efficiency property and eliminates the requirement that predictions must to the grand coalition's value. However, as we let - oc, the penalty term becomes closer to the hard constraint in eq. (9). Note that practice, we use finite values for y and observe sufficiently accurate results, whereas using excessively large y values would render gradient-based optimization ineffective.
B ADDITIVE EFFICIENT NORMALIZATION
Here, provide geometric interpretation for the additive efficient normalization step and prove that it is guaranteed to yield Shapley value estimates closer to their true values. Consider a game o with Shapley values o(v) E Rd, and assume that we have Shapley values estimates e RR that do not satisfy the efficiency property. To force this property to hold, can project these estimates
13

---

Published as a conference paper at ICLR 2022
onto the efficient hyperplane, the subset of R where the efficiency property is satisfied. This corresponds to solving the following optimization problem over Pell E RR:
min Pal
211 s.t. 1 Dell v(() - v(O).
We can solve the problem via its Lagrangian, denoted by L( 11), with the Lagrange multiplier E R as follows:
L(det, v) = ||cefft -b11 + [(1) v(0) 1 Oeff
11) v0)) 1 1
d
This transformation, where efficiency gap split evenly and added to each estimate, known additive efficient normalization (Ruiz et al., 1998). We implement it as output layer for Fast- SHAP's predictions to ensure that they satisfy the efficiency property (section 3). This step can therefore be understood as projection of the network's 's output onto the efficient hyperplane.
The normalization step is guaranteed to produce corrected estimates 6ā that are closer to the true Shapley values Φ(v) than the original estimates d. To see this, note that the projection step guar- antees that ò der and Dett Φ(v) orthogonal vectors, so the Pythagorean theorem yields the following inequality:
11((v) -o(1)-611 [ló(v) diall + l1 - 8|12
2 [ló(() - diaf 11
C REDUCING GRADIENT VARIANCE
Recall that objective function (()) is defined as follows:
(())
E
E
E p(s)
(Uxxy(s) -22 (0) 5 "rrst (x. y; 0])
p(x) Unif(y)
The objective's gradient is given by
VaC(O)
= E E E
V V(x,,,
(10)
p(x) Unifly) p(s)
where define
V (x, U, = (V Un. T Drast (xx yy; 01)²
When FastSHAP is trained with single sample (x, s), the gradient covariance is given by Cov (V(x, 0)). which may be too large for effective optimization. We use several strategies to reduce gradient variance. First, given a model that outputs estimates for all classes y E {1..... K}. we calculate the loss jointly for all classes. This yields gradients that denote V(x, s; f). defined as
V (z,
E Unif(y)
V (Z,,y,
where we have the relationship
14

---

Published as a conference paper at ICLR 2022
Cov(V(x, s)) N Cor(V(x.y,ss01)
due to the law of total covariance. Next, we consider minibatches of independent æ samples, which yields gradients Vo(x, s; 0) with covariance given by
1 Cov (ov Cov
Cov (ov(Vxxx,s;0)
We then consider sampling m independent coalitions for each input resulting in the gradients Vg (x, with covariance given by
Cov (ov
Cov Cov((V(xs;))) mb
Finally, we consider paired sampling approach, where each sample ~ p(s) is paired with its com- plement Paired sampling has been shown reduce KernelSHAP's variance (Covert and Lee, 2021), and our experiments show that it helps improve FastSHAP's accuracy (appendix D).
The training algorithm in the main text is simplified by omitting these gradient variance reduc- tion techniques, so we also provide algorithm 2 below, which includes minibatching, multiple coalition samples, paired sampling, efficiency regularization and parallelization over all output classes
Algorithm 2: Full FastSHAP training
Input: Value function Uz.y: learning rate o. batch size b, samples m. penalty parameter
Output: FastSHAP explainer y;;
initialize fastt (x. y; ()
while converged do
set R < 0, C + 0 for 1..... do
sample x p(x)
for y = 1,.................. do
predict à + Diant (x,
calculate R R (0) ())) // Pre-normalization
if normalize then
set Φ +- 3 d= (1) Un.yy (n. -0)
end for j .......m. do
if paired sampling and mod 2 = then set + 1 // Invert previous subset else
sample s p(s)
end
calculate L t L + (sn))() (0. - TT))
end
end
end
update +-6 8 - aVo ( + 6K
end
15

---

Published as a conference paper at ICLR 2022
Bankruptcy
Census
Marketing
News
Mean dist
0.10
0.05
40
60
# Training samples
Training samples FAStSHAP
Training samples
# Training samples
FastSHAP (Paired Sampling)
Figure 6: FastSHAP accuracy as function the number of training samples. The results show that using more samples per x improves FastSHAP's closeness to the ground truth Shapley values, as does the use of paired sampling.
D FASTSHAP MODELS AND HYPERPARAMETERS
In this section, we describe the models and architectures used for each dataset, as well as the hyper- parameters used when training FastSHAP.
D.1 MODELS
Tabular datasets. For the original model fx; 1)), we neural networks for the news and marketing datasets and gradient boosted trees for the census (LightGBM (Ke et al., 2017)) and bankrupt (XGBoost (Chen and Guestrin, 2016)) datasets. The FastSHAP model 0rast yx y; 0) and the surrogate model Psurr (y mm(x, s); 3) are implemented using neural networks that consist of 2-3 fully connected layers with 128 units and ReLU activations. The Peurr models use softmax out- put layer, while 0last has no output activation. The models are trained using Adam with a learning rate of 10-3, and we use learning rate scheduler that multiplies the learning rate by a factor of 0.5 after 3 epochs of no validation loss improvement. Early stopping was triggered after the validation loss ceased to improve for 10 epochs.
Image datasets. The models f(x; 1)) and Paur ResNet-50 models pretrained Imagenet. We use these without modification to the architecture and fine-tune them on each image dataset. To create the @rast (x, y: 0) model, we modify the architecture to return tensor of size 14 14 K. First, the layers after the 4th convolutional block are removed; the output of this block is 14 x 14 X 256. We then append 2D convolutional layer with K filters, each of size 1 1, so that the output is 14 x 14 x K and the yth 14 x 14 slice corresponds to the superpixel-level Shapley values for each class y E V. Each model is trained using Adam with a learning rate of 10-3 and we use learning rate scheduler that multiplies the learning rate by a factor of 0.8 after 3 epochs of no validation loss improvement. Early stopping was triggered after the validation loss ceased to improve for 20 epochs.
D.2 FASTSHAP HYPERPARAMETERS
We now explore various settings of FastSHAP's hyperparameters and observe their impact on Fast- SHAP's performance. There are two types of hyperparameters: sampling hyperparameters, which affect the number of samples of taken during training, and efficiency hyperparameters, which con- trol how we enforce the Efficiency constraint. Sampling hyperparameters include: (1) whether to use paired sampling, and (2) the number of samples of s per x to take during training. Efficiency hyperparameters include: (1) the choice of in eq. (4), and (2) whether to perform the additive efficient normalization during training, inference or both.
To understand the effect of sampling hyperparameters, tabular datasets from the main text. We use the in-distribution value function Psur and compute the ground truth SHAP values the same way in previous experiments (i.e., by running Ker- nelSHAP to convergence).
perform experiments using the same
Figure shows the mean E, distance between FastSHAP's estimates and the ground truth. We find that across all four datasets, increasing the number of training samples of s generally improves the mean &g distance to ground truth. We also find that for any fixed number of samples (greater than 1), using paired sampling improves FastSHAP's accuracy.
Table shows the results of an ablation study for the efficiency hyperparameters. Normalization (or Norm.) refers to the additive efficient normalization step (applied during training and inference,
16

---

Published as a conference paper at ICLR 2022
Table FastSHAP ablation results. The distance the ground truth Shapley values displayed for several FastSHAP variations, showing that normalization helps and that the penalty is unnecessary.
Census
Bankruptcy
&2
E
&2
Normalization
0.0229
0.0863
0.0295
0.2436
Normalization Penalty
0.0261
0.0971
0.0320
0.2740
Inference Norm.
0.0406
0.1512
0.0407
0,3450
Inference Norm. + Penalty
0.0452
0.1671
0.0473
0.4471
No Norm.
0.0501
0.1933
0.0408
0.3474
No Norm. Penalty
0.0513
0.1926
0.0474
0.4490
or only during inference), and penalty refers to the efficiency regularization technique with the parameter set Y 0.1. We find that using normalization during training uniformly achieves better results than without normalization or with normalization only during inference. The efficiency regularization approach proves to be less effective, generally leading to less accurate Shapley value estimates. Based on these results, we opt to use additive efficient normalization in our tabular data experiments.
E ADDITIONAL RESULTS FOR IMAGE EXPERIMENTS
In this section, we provide additional results for the FastSHAP image experiments.
E. INCLUSION AND EXCLUSION METRICS
Table 4 shows inclusion and exclusion metrics when replicated using log-odds rather than accu- racy. Similar to our metrics described in the main text, we choose the class predicted by the original model for each image, and measure the average log-odds for that class we include exclude important features according to the explanations generated by each method. The results confirm roughly the same ordering between methods, with FastSHAP being the only method to achieve strong results on both metrics for both datasets. Figure shows the raw inclusion and exclusion curves for both the accuracy and -ogooddd-drrived metrics.
Table Exclusion and Inclusion AUCs calculated using average log-odds of the predicted class.
CIFAR-10
Imagenetle
Exclusion AUC
Inclusion AUC
Exclusion AUC
Inclusion AUC
FastSHAP
5.92 (5.62, 6.14)
5.36 (5.16,, 5.63)
7.98 (7.68, 8.33)
5.40 (5.16,, 5.60)
KemeiSHAP
9.88 (9.55, 10.20)
5.36 (5.14, 5.63)
10.68 (10.66, 11.00)
5.07 (4.81, 5.31)
KemeISHAP-S
8.01 (7.68, 8.34)
6.80 (6.65, 6.96)
9.39 (9.11, 9.66)
6.01 (5.78, 6.26)
GradCAM
7.75 (7.44, 8.09)
4.99 (4,81,
7.77 (7.49, 8.05)
4.65 (4.40, 4.89)
Integrated Gradients
8.34 (8.03, 8.61)
4.58 (4.37, 4.85)
10.14 (9.79, 10.46)
4.34 (4.10, 4.58)
SmoothGrad
10.99 (10.67, 11.29)
(4.08, 4.58)
11.19 (10.84, 11.48)
4.47 (4.24, 4.70)
Seep
9.96 (9.61, 10.24)
5.47 (5.28, 5.76)
10.93 (10.61, 11.20)
4.63 (4.38, 4.85)
CXPlain
8.34 (8.00, 8,58)
4.02 (3.80.
9.13 (8.83, 9.41)
4.33 (4.11,
17

---

Published as a conference paper at ICLR 2022
Exclusion Curve
Inclusion Curve
KemeiSHAP
Log Odds
Log Odds
KerneISHAP-S
GradCAM
Integrated Gradients
SmoothGrad
DeepSHAP
-4
CXPlain
-6-
FastSHAP
20
40
60
80
100
20
40
60
80
100
Exclusion %
Inclusion %
(a) Imagenette: Log-odds derived inclusion and exclusion curves.
Exclusion Curve
Inclusion Curve
0.9
0.8
Top 1 Accuracy
0.7
Top 1 Accuracy
KemeiSHAP
0.6
0.6
KemeiSHAP-S
GradCAM
0.4
0.4
Integrated Gradients
SmoothGrad
0.3
DeepSHAP
0.2
0.2
CXPlain
FastSHAP
0
20
40
60
80
100
20
40
60
80
100
Exclusion %
Inclusion %
(b) CIFAR-10: Accuracy derived inclusion exclusion curves.
Exclusion Curve
Inclusion Curve
0.9
0.8
Top 1 Accuracy
0.7
Top 1 Accuracy
KemelSHAP
0.6
KemeISHAP-S
GradCAM
Integrated Gradients
0.4
0.4
SmoothGrad
DeepSHAP
0.2
CXPlain
0.2
FastSHAP
0.0
0
20
40
100
20
40
60
80
100
Exclusion %
Inclusion
(c) CIFAR-10: Log-odds derived inclusion and exclusion curves.
Figure 7: Additional inclusion and exclusion curves. The change in top-1 accuracy average log-odds of the predicted class as increasing percentage of the pixels estimated be important excluded (left) included (right) from of 1,000 images.
18

---

Published as a conference paper at ICLR 2022
Exclusion AUC Learning Curve
Inclusion AUC Learning Curve
0.725
0.82
0.700
0.675
0.80
Exclusion AUC
Inclusion AUC
0.78
0.625
0.600
0.76
0.575
0.74
0.550
0.525
0.72
20
40
60
80
100
20
40
60
80
100
Percent of Dataset
Percent of Dataset
FastSHAP
KernelSHAP-S GradCAM
Integrated Gradients
DeepSHAP
KerneiSHAP
SmoothGrad
CXPlain
Figure 8: FastSHAP robustness to limited data. The curves generated by training FastSHAP with varying portions of the Imagenette dataset and evaluating the Inclusion and Exclusion AUC. Horizontal lines show the Exclusion and Inclusion AUCs each the baseline methods, as reported table 1.
E.2 FASTSHAP ROBUSTNESS TO LIMITED DATA
To test FastSHAP's robustness the size of the training data, we compare its performance when trained with varying amounts of the Imagenette dataset. Figure 8 plots the change in inclusion and exclusion AUC, caleulated using top-1 accuracy, achieved when training FastSHAP with 95%, 85%, 75%, 50%. 25%, 15%, 10%, and 5% of the training dataset. We find that FastSHAP remains competitive when using just 10% the data, and that outperforms most baseline methods by large margin when using just 25%.
19

---

Published as a conference paper at ICLR 2022
E.3 EXAMPLE FASTSHAP IMAGE EXPLANATIONS
Finally, we show additional explanations generated by FastSHAP and the baseline methods for both CIFAR-10 and Imagenette.
Airpiane
Automobile
Bird
Cat
Deer
Dog
Frog
Horse
Ship
Truck
2.2
1111
341
321
22
3611
36.
361
3611
161
161
16
1611
26.7
161
J6.1
261
1611
111
154
360
1611
105
-61
16.1
21
94
2.1
8.0
9.5
15.1
45
33
94
102
125
24
154
45.0
36.1
15.1
3500
452
99
2.4
-1.
12.
361
4,7
161
361
9A
35
25.1
26.1
452
261
3k1
163
161
25.1
12.5
-611
433
-6.1
17
3.5
161
-611
J61
36.1
145
95
Figure 9: Explanations generated by FastSHAP for 18 randomly selected CIFAR-10 images. Each col- umn corresponds to CIFAR-10 class, and the model's 's prediction (in logits) is provided helow each image.
20

---

Published as a conference paper at ICLR 2022
Tanch
Springer
Player
Chain
Church
Truck
Golf Ball
Parachute
-74
52
-74
-7.9
-14
-3
-13
3.4
32
-748
.15
312
35
41
15
4.4
4.7
4.0
35
33
302
52
98
22.4
J02
J0.1
453
3.5
33
99
55
3.
3,3
83
461
23
301
24
72
71
70
91
35
32
31
5.0
31
22
90
icle
101
72
45
44
42
44
43
44
44
45
362
41
4.6
+7
+2
73
Figure 10: Explanations generated by FastSHAP for 18 randomly selected Imagenette images. Each column corresponds Imagenette class, and the model's prediction (in logits) provided below each image.
21

---

Published as a conference paper at ICLR 2022
KerneiSHAP
KamelSHAP-S
Grad
Gradients
SmoothGred
DeepSHAP
CXPlais
Cat
Bird
Frog
Ship
Frog
Cat
Ireg
Brrd
Track
Dag
Ship
Airphane
Horse
Automobile
Figure 11: Explanations generated for the predicted class for 15 randomly selected CIFAR-10 images. Each column corresponds explanation method, and each labeled with the image's corresponding class.
22

---

Published as a conference paper at ICLR 2022
Integrated
FastSHAP
KerneiSHAP
KernelSHAP-S
GradCAM
SmoothGrad
DeepSHAP
OXPlain
Englich
Springee
Church
Gas Pamp
Church
Cassette Blayer
French Horn
Church
Gas Pump
Chain Saw
French Pamm
Golf Ball
Gas Pump
Tench
Tench
Colf Ball
itles
celes
ille
Figure 12: Explanations generated for the predicted class for 15 randomly selected Imagenette images. Each column corresponds explanation method, and each labeled with the image's corresponding class.
23


Reviews:
[{"review_id": "t3DDvzWHr3r", "reviewer": "Reviewer_wDJz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The paper proposes an effective method for estimating Shapley values that is much faster than existing works.\n- The method is validated on structure and image datasets.\n- The running time for different methods is well presented.\n\nWeaknesses\n- Besides the image classification tasks, could the proposed method work on other tasks, such as segmentation or NLP-related tasks?\n- Compared with the FastSHAP, other methods can achieve better Exclusion AUC and Inclusion AUC for both CIFAR10 and Imagenette in Table 1. Could the authors explain more on why other methods can obtain better results?", "summary_of_the_paper": "The paper works on improving the runtime for estimating Shapley values. The work introduces FastSHAP that estimates Shapley values with a learned explainer model. The method is validated on tabular and image datasets (CIFAR10 and Imagenette).", "summary_of_the_review": "Overall, the paper introduces an interesting approach for estimating Shaley values in real run-time. The effectiveness of the method is well demonstrated across different tasks/datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Rz8YTXUqe4X", "reviewer": "Reviewer_Asf6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The FastSHAP method is elegant and provides an effective solution to the computational bottleneck of Shapley value estimation. However, there are concerns and questions below about the paper:\n\n- Why is the loss function in L2 form? Why don't you use other norm functions?\n\n- How can one pick the learning rate of the method? What type of validation reward would be used?\n\n- It is unclear how to optimally pick the loss coefficient for the efficiency gap objective. \n\n- What are the approximations that the optimal solution for Eq. (7) is given by Eq. (8)? It should be explained better. \n\n- In Fig. 4, the competitor models have very poor explanation quality, compared to the original papers that proposed them. How did you optimize their hyperparameters? Could there be unfairness in regenerating the results by those methods? Also, why doesn't it show results with the exact Shapley values?\n\n- The gap with KernelSHAP is still somehow noticeable in Fig. 5 that reduces the impact of the contribution. \n\n- Parallelization constitutes an important aspect of the runtime, but there is not much discussion on it. How can one parallelize different algorithmic operations, especially for the GPU implementation?\n\n- What is the impact of dataset size on the accuracy of explanations? Some discussions on it would be needed. ", "summary_of_the_paper": "For fast estimation of Shapley values, a new method is proposed, based on a single forward pass using a learned explainer model. On tabular and image datasets, accurate and fast estimation of feature attributions are demonstrated.", "summary_of_the_review": "Overall, the paper makes an important contribution for post-hoc explanation of ML models, in computationally efficient ways. The paper is well written with strong results, but there is further room for improvement. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KJCOFmCSZ6Y", "reviewer": "Reviewer_zqFs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Post-rebuttal:\nThe response partly addresses my concerns. However, I think the organization needs to be improved. The core contribution should be highlighted and the connection between sections should be strenthened.\n-------------------------------------------------\nPros:\n1. Efficiently estimating the Shapley value without groundtruth label is highly demanded, and the motivation is very clearly and in high significance.\n\n2. The experimental results including the exclusion and inclusion curve show the approximation accuracy of the proposed method. Meanwhile, the runtime is competitive with the SOTA method.\n\nCons:\n1. The main problem is the writing, and the organization of this paper should be improved. Since the presented method is based on the prior work KernelSHAP, the detailed information of KernelSHAP should be explained well. For example, what is $v_{x,y}(0)$ and $v_{x,y}(s)$? Meanwhile, the connection between Section 3.1 and 3.2 is not strong although the subtitle is connected.\n\n2. The novelty is also concerned. Eq. (6)-(8) all comes from prior works and the authors seem to combine the results without obvious modification. I think the contribution of extending other theoretical results to the efficient Shapley value estimation should be clarified clearly.\n\n3. The discussion for the experimental results are not sufficient. For example, FastSHAP outperforms all listed baselines in the exclusion curve but underforms KernelSHAP-S in the inclusion curve. What is the reason for the counter-intuitive phenomenon? Meanwhile, the bold results in Table 1 is confusing.", "summary_of_the_paper": "This paper proposes FastSHAP to efficiently estimate the Shapley value in a single forward pass using a learned explainer model. Since there is no label to train the Shapley value estimator, stochastic gradient optimization using a weighted least squares-like objective function is applied to train FastSHAP. The experimental results and the deployment efficiency shows the superiority of the presented method.\n\n", "summary_of_the_review": "Please see the Cons in the main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5SkFNj12sxs", "reviewer": "Reviewer_GNuc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a significant idea of reducing the runtime for estimating the Shapley value. I really love the extensive simulations that the authors conducted. \n\nHere are some comments: \n1. (\"... how to remove features\") on page 2. I don't think that the goal of the works of (Aas et al., 2019, Janzing et al., 2020, etc.) is to remove features. Instead, these papers aim to choose the set function such that the resultant Shapley values have causal interpretation when there is a feature dependence.\n\n2. In Eq. (4), Unif(y) seems undefined.\n\n3. I think the paper should explicitly compare the computational complexity of the existing approximation methods, including the permutation-based algorithm [Štrumbelj and Kononenko, 2014], kernel-SHAP [Lundberg and Lee, 2017], etc., to see how the orders-of-magnitude speedup was achieved. \n\n4. I am not sure what the authors want to tell from the simulation results in Figs. (2,3). I think the authors intend to tell that FastSHAP has higher performances compared to other works. However, I don't think this observation can be generalized because FastSHAP values are approximations of true Shapely Values onto the predefined function space. In other words, FastSHAP projects the solution of Eq. (3)  (i.e., the true Shapley) onto the predefined functional space. Then, we cannot make a general statement that FastSHAP achieves higher accuracy than other Shapley values because the functional space does not confine them. \n\n5. For the practical benefit, I recommend adding the guideline for choosing the functional class for \\phi_{fast}(x,y,\\theta). \n\n--- \n## Updated comments. \n\nThe authors addressed all the comments that I raised. \n\nI agree that this paper provides a substantial empirical benefit for the XAI literature. However, I raised some issues on the novelty because I expected a theoretical guarantee for the outstanding performance of FastSHAP. Nevertheless, I decided to appreciate the paper's importance because it is evident that the proposed method can significantly reduce computational complexity. \n\nI updated the scores toward acceptance because I believe the proposed approach will help the XAI community. Specifically, the scores are \n* Technical Novelty And Significance: 2 -> 3\n* Empirical Novelty And Significance: 2 -> 4\n* Recommendation: 5 -> 8 \n\n### Some minor note \n* Is \"Single forward pass\" broadly used words? I couldn't understand the contribution in the Introduction Section because \"Single forward pass\" looks exotic to me. I could grasp the contribution by seeing Eq. (4). It would be great if the contribution can be explained in simpler terms.\n\n ", "summary_of_the_paper": "This paper introduced FastSHAP, a new method for estimating Shapley values, reducing runtime significantly. ", "summary_of_the_review": "- Overall, I think there should be an explicit comparison of the computational complexities of FastSHAP and other algorithms. \n\n- Instead of comparing the performance, a more extensive comparison of the runtime is needed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper introduces an interesting approach for estimating Shaley values in real run-time. The effectiveness of the method is well demonstrated across different tasks/datasets.
Decision: Accept (Poster)