FASTSHAP: REAL-TIME SHAPLEY VALUE ESTIMATION
Year: 2022

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-ofmagnitude speedup.

heading: 1 INTRODUCTION
text: With the proliferation of black-box models, Shapley values (Shapley, 1953) have emerged as a 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 to have high computational complexity, with an exact calculation requiring an exponential number of model evaluations (Van den Broeck et al., 2021). Speed becomes a 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 approaches. 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 evaluations 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) or neural networks (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 flexibility regarding the handling held-out features—a subject of ongoing debate in the field (Aas et al., 2019; Janzing et al., 2020; Frye et al., 2020; Covert et al., 2021).
Here, we introduce a new approach for efficient Shapley value estimation: to achieve the fastest possible run-time, we propose learning a separate explainer model that outputs precise Shapley value estimates in a single forward pass. Naïvely, such a learning-based approach would seem to require a 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 Shapley value explanations.1 We derive an objective function from the Shapley value’s weighted least
∗Equal contribution 1https://git.io/JCqFV (PyTorch), https://git.io/JCqbP (TensorFlow)
squares characterization and investigate several ways to reduce gradient variance during training. Our experiments show that FastSHAP provides accurate Shapley value estimates with an ordersof-magnitude speedup relative to non-amortized estimation approaches. Finally, we also find that FastSHAP generates high-quality image explanations (fig. 1) that outperform gradient-based methods (e.g., IntGrad and GradCAM) on quantitative inclusion and exclusion metrics.

heading: 2 BACKGROUND
text: In this section, we introduce notation used throughout the paper and provide an overview of Shapley values and their weighted least squares characterization. Let x ∈ X be a random vector consisting of d features, or x = (x1, . . . ,xd), and let y ∈ Y = {1, . . . ,K} be the response variable for a classification problem. We use s ∈ {0, 1}d to denote subsets of the indices {1, . . . , d} and define xs := {xi}i:si=1. The symbols x,y, s are random variables and x, y, s denote possible values. We use 1 and 0 to denote vectors of ones and zeros in Rd, so that 1⊤s is a subset’s cardinality, and we use ei to denote the ith standard basis vector. Finally, f(x; η) : X 7→ ∆K−1 is a model that outputs a probability distribution over y given x, and fy(x; η) is the probability for the yth class.

heading: 2.1 SHAPLEY VALUES
text: Shapley values were originally developed as a credit allocation technique in cooperative game theory (Shapley, 1953), but they have since been adopted to explain predictions from black-box machine learning models (Štrumbelj and Kononenko, 2014; Datta et al., 2016; Lundberg and Lee, 2017). For any value function (or set function) v : 2d 7→ R, the Shapley values ϕ(v) ∈ Rd, or ϕi(v) ∈ R for each feature i = 1, . . . , d, are given by the formula
ϕi(v) = 1
d ∑ si ̸=1 ( d− 1 1⊤s )−1( v(s+ ei)− v(s) ) . (1)
The difference v(s + ei) − v(s) represents the ith feature’s contribution to the subset s, and the summation represents a weighted average across all subsets that do not include i. In the model explanation context, the value function is chosen to represent how an individual prediction varies as different subsets of features are removed. For example, given an input-output pair (x, y), the prediction for the yth class can be represented by a value function vx,y defined as
vx,y(s) = link
( E
p(x1−s) [fy (xs,x1−s; η)]
) , (2)
where the held out features x1−s are marginalized out using their joint marginal distribution p(x1−s), and a 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 to model explanation enjoys several useful theoretical properties due to its use of Shapley values: for example, the attributions are zero for irrelevant features, 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 d. Fast approximations are therefore required in practice, as we discuss next.

heading: 2.2 KERNELSHAP
text: KernelSHAP (Lundberg and Lee, 2017) is a popular Shapley value implementation that relies on an alternative Shapley value interpretation. Given a value function vx,y(s), eq. (1) shows that the values ϕ(vx,y) are the features’ weighted average contributions; equivalently, their weighted least squares characterization says that they are the solution to an optimization problem over ϕx,y ∈ Rd,
ϕ(vx,y) = argmin ϕx,y E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕx,y )2] (3)
s.t. 1⊤ϕx,y = vx,y(1)− vx,y(0), (Efficiency constraint)
where the distribution p(s) is defined as
p(s) ∝ d− 1( d
1⊤s
) · 1⊤s · (d− 1⊤s)
(Shapley kernel)
for s such that 0 < 1⊤s < d (Charnes et al., 1988). Based on this view of the Shapley value, Lundberg and Lee (2017) introduced KernelSHAP, a stochastic estimator that solves an approximate 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), KernelSHAP often requires many samples to achieve an accurate estimate, and it must solve eq. (3) separately for each input-output pair (x, y). As a result, it is unacceptably slow for some use cases, particularly in settings with large, high-dimensional models. Our approach builds on KernelSHAP, leveraging the Shapley value’s weighted least squares characterization to design a faster, amortized estimation approach.

heading: 3 FASTSHAP
text: 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 to efficiently learn the Shapley value function ϕ(vx,y).

heading: 3.1 AMORTIZING SHAPLEY VALUES
text: In our approach, we propose generating Shapley value explanations using a learned parametric function ϕfast(x,y; θ) : X × Y 7→ Rd. Once trained, the parametric function can generate explanations in a single forward pass, providing a significant speedup over methods that approximate Shapley values separately for each sample (x, y). Rather than using a dataset of ground truth Shapley values for training, we train ϕfast(x,y; θ) by penalizing its predictions according to the weighted least squares objective in eq. (3), or by minimizing the following loss,
L(θ) = E p(x) E Unif(y) E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕfast(x,y; θ) )2] , (4)
where Unif(y) represents a uniform distribution over classes. If the model’s predictions are forced to satisfy the Efficiency constraint, then given a large enough dataset and a sufficiently expressive model class for ϕfast, the global optimizer ϕfast(x,y; θ∗) is a function that outputs exact Shapley values (see proof in appendix A). Formally, the global optimizer satisfies the following:
ϕfast(x, y; θ ∗) = ϕ(vx,y) ∀ x ∈ X , y ∈ 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:
ϕefffast(x, y; θ) = ϕfast(x, y; θ) + 1
d
( vx,y(1)− vx,y(0)− 1⊤ϕfast(x, y; θ) ) ︸ ︷︷ ︸
Efficiency gap
. (6)
The normalization step can be applied at inference time and optionally during training; in appendix B, we show that this step is guaranteed to make the estimates closer to the true Shapley values. Second, we can relax the efficiency property by augmenting L(θ) with a penalty on the efficiency gap (see eq. (6)); the penalty requires a parameter γ > 0, and as we set γ → ∞ we can guarantee that efficiency holds (see appendix A). Algorithm 1 summarizes our training approach.
Empirical considerations. Optimizing L(θ) using a single set of samples (x, 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 ∈ {1, . . . ,K}. Then, we experiment with using multiple samples s ∼ p(s) for each input sample x. Finally, we explore paired sampling, where each sample s is paired with its complement 1−s, which has been shown to reduce KernelSHAP’s variance (Covert and Lee, 2021). Appendix C shows proofs that these steps are guaranteed to reduce gradient variance, and ablation experiments in appendix D demonstrate their improvement on FastSHAP’s accuracy.

heading: 3.2 A DEFAULT VALUE FUNCTION FOR FASTSHAP
text: Algorithm 1: FastSHAP training Input: Value function vx,y , learning rate α Output: FastSHAP explainer ϕfast(x,y; θ) initialize ϕfast(x,y; θ) while not converged do
sample x ∼ p(x), y ∼ Unif(y), s ∼ p(s) predict ϕ̂← ϕfast(x, y; θ) if normalize then
set ϕ̂← ϕ̂+d−1 ( vx,y(1)− vx,y(0)− 1T ϕ̂ ) end calculate L ← ( vx,y(s)− vx,y(0)− sT ϕ̂
)2 update θ ← θ − α∇θL
end
FastSHAP has the flexibility to work with any value function vx,y(s). Here, we describe a default value function that is useful for explaining predictions from a classification model.
The value function’s aim is to assess, for each subset s, the classification probability when only the features xs are observed. Because most models f(x; η) do not support making predictions without all the features, we require an approximation that simulates the inclusion of only xs (Covert et al., 2021). To this end, we use a supervised surrogate model (Frye et al., 2020; Jethani et al., 2021) to approximate marginalizing out the remaining features x1−s using their conditional distribution.
Separate from the original model f(x; η), the surrogate model psurr(y | m(x, s);β) takes as input a vector of masked features m(x, s), where the masking function m replaces features xi such that si = 0 with a [mask] value that is not in the support of X . Similar to prior work (Frye et al., 2020; Jethani et al., 2021), the parameters β are learned by minimizing the following loss function:
L(β) = E p(s)
[ DKL ( f(x; η) || psurr(y | m(x, s);β) )] . (7)
It has been shown that the global optimizer to eq. (7), or psurr(y | m(x, s);β∗), is equivalent to marginalizing out features from f(x; η) with their conditional distribution (Covert et al., 2021):
psurr(y | m(x, s);β∗) = E[fy(x; η) | xs = xs]. (8)
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 FastSHAP. We use the surrogate model as a default choice for two reasons. First, it requires a single prediction for each evaluation of vx,y(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).

heading: 4 RELATED WORK
text: 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 efficiently (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, model-agnostic stochastic approximations are more flexible, but they must trade off run-time and accuracy in the explanation. For example, KernelSHAP samples subsets to approximate the solution to a weighted least squares problem (Lundberg and Lee, 2017), while other
approaches sample marginal contributions (Castro et al., 2009; Štrumbelj 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 evaluations, 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 are referred to as amortized explanation methods (Covert et al., 2021; Jethani et 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; Yoon et al., 2018; Schwab and Karlen, 2019; Schulz et al., 2020; Jethani et al., 2021). Notably, one approach generates a 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. However, for Shapley values, generating a large training set would be very costly, so FastSHAP sidesteps the need for a training set using a custom loss function based on the Shapley value’s weighted least squares characterization (Charnes et al., 1988).

heading: 5 STRUCTURED DATA EXPERIMENTS
text: We analyze FastSHAP’s performance by comparing it to 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 vx,y(s). Unless otherwise stated, we use the surrogate model value function introduced in section 3.2. Later, in section 6, we test FastSHAP’s ability to generate image explanations.
Baseline methods. To contextualize FastSHAP’s accuracy, we compare it to several nonamortized stochastic estimators. First, we compare to KernelSHAP (Lundberg and Lee, 2017) and its acceleration that uses paired sampling (Covert and Lee, 2021). Next, we compare to a permutation sampling approach and its acceleration that uses antithetical sampling (Mitchell et al., 2021). As a performance metric, we calculate the proximity to Shapley values that were obtained by running 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.2
Implementation details. We use either neural networks or tree-based models for each of f(x; η) and psurr(y | m(x, s);β). The FastSHAP explainer model ϕfast(x,y; θ) is implemented with a network g(x; θ) : X → Rd×Y that outputs a vector of Shapley values for every y ∈ Y; deep neural networks are ideal for FastSHAP because they have high representation capacity, they can provide many-to-many mappings, and they can be trained by stochastic gradient descent. Appendix D contains more details about our implementation, including model classes, network architectures and training hyperparameters.
2https://github.com/iancovert/shapley-regression/ (License: MIT)
We also perform a series of experiments to determine several training hyperparameters for FastSHAP, exploring (1) whether or not to use paired sampling, (2) the number of subset samples to 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 x sample, additive efficient normalization during both training and inference, and we set γ = 0 (since the normalization step is sufficient to enforce efficiency).

heading: 5.1 ACCURACY OF FASTSHAP EXPLANATIONS
text: Here, we test whether FastSHAP’s estimates are close to the ground truth Shapley values. Our experiments use data from a 1994 United States census, a bank marketing campaign, bankruptcy statistics, and online news articles (Dua and Graff, 2017). The census data contains 12 input features, and the binary label indicates whether a person makes over $50K a year (Kohavi et al., 1996). The marketing dataset contains 17 input features, and the label indicates whether the customer subscribed to a term deposit (Moro et al., 2014). The bankruptcy dataset contains 96 features describing 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 a function of the number of model evaluations for the news, census and bankruptcy datasets. Figure 3 shows results for the marketing 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 FastSHAP requires only a single forward pass of ϕfast(x,y; θ), we show it as a horizontal line.
To reach FastSHAP’s level of accuracy on the news, census and bankruptcy datasets, KernelSHAP 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 FastSHAP’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 600× faster than the original version of KernelSHAP, and 200× faster than the best non-amortized baseline.

heading: 5.2 DISENTANGLING AMORTIZATION AND THE CHOICE OF VALUE FUNCTION
text: 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/In-distribution) vx,y(s) = psurr(y | m(x, s);β)
2. (Marginal/Out-of-distribution) vx,y(s) = Ep(x1−s) [fy (xs,x1−s; η)]
3. (Baseline removal) vx,y(s) = fy(xs, xb1−s; η), where x b ∈ X are fixed baseline values (the
mean for continuous features and mode for discrete ones)
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 FastSHAP 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 evaluations, but in some cases up to nearly 1,000.

heading: 6 IMAGE EXPERIMENTS
text: Images represent a challenging setting for Shapley values due to their high dimensionality and the computational cost of model evaluation. We therefore compare FastSHAP to KernelSHAP on two image datasets. We also consider several widely used gradient-based explanation methods, because they are the most commonly used methods for explaining image classifiers.

heading: 6.1 DATASETS
text: We consider two popular image datasets for our experiments. CIFAR-10 (Krizhevsky et al., 2009) contains 60,000 32 × 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 × 224 using bilinear interpolation to interface with the ResNet-50 architecture (He et al., 2016). Figure 4 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 is cropped to keep the 224 × 224 central region, and the data is split 9,469/1,963/1,962. Example Imagenette explanations are shown in fig. 1.

heading: 6.2 EXPLANATION METHODS
text: 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 KernelSHAP with the zeros baseline value function, which we refer to simply as KernelSHAP, and with the in-distribution surrogate value function, which we refer to as KernelSHAP-S. We also compare these methods to the gradient-based explanation methods GradCAM (Selvaraju et al., 2017), SmoothGrad (Smilkov et al., 2017) and IntGrad (Sundararajan et al., 2017). Gradient-based methods are relatively fast and have therefore been widely adopted for explaining image classifiers. Finally, we also compare to CXPlain (Schwab and Karlen, 2019), an amortized explanation method that generates attributions that are not based on Shapley values.
Implementation details. The models f(x; η) and psurr(y | m(x, s);β) are both ResNet-50 networks (He et al., 2016) pretrained on ImageNet and fine-tuned on the corresponding imaging dataset. FastSHAP, CXPlain, and KernelSHAP are all implemented to output 14×14 superpixel attributions for each class. For FastSHAP, we parameterize ϕfast(x,y; θ) to output superpixel attributions: we use an identical pretrained ResNet-50 but replace the final layers with a 1 × 1 convolutional layer so that the output is 14× 14×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 γ = 0; we 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 are implemented using the shap3 package’s default parameters, and GradCAM, SmoothGrad, and IntGrad are implemented using the tf-explain4 package’s default parameters.
3https://shap.readthedocs.io/en/latest/ (License: MIT) 4https://tf-explain.readthedocs.io/en/latest/ (License: MIT)

heading: 6.3 QUALITATIVE REMARKS
text: 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 conclusions 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 KernelSHAP explanations are noisy and fail to localize important regions. To a lesser extent, CXPlain occasionally highlights important regions. In comparison, the remaining methods (SmoothGrad, IntGrad and DeepSHAP) are granulated and highlight only small parts of the key objects. Next, we consider quantitative metrics that test these observations more systematically.
6.4 QUANTITATIVE EVALUATION
Evaluating the quality of Shapley value estimates requires access to ground truth Shapley values, which is computationally infeasible for images. Instead, we use two metrics that evaluate an explanation’s ability to identify informative image regions. These metrics build on several recent proposals (Petsiuk et al., 2018; Hooker et al., 2018; Jethani et al., 2021) and evaluate the model’s classification accuracy after including or excluding pixels according to their estimated importance.
Similar to Jethani et al. (2021), we begin by training a single evaluation model peval to approximate the f(x; η) model’s output given a subset of features; this serves as an alternative to training separate models on each set of features (Hooker et al., 2018) and offers a more realistic option than masking features with zeros (Schwab and Karlen, 2019). This procedure is analogous to the psurr training procedure in section 3.2, except it sets the subset distribution to p(s) = Uniform({0, 1}d) to ensure all subsets are equally weighted.
Next, we analyze how the model’s predictions change as we remove either important or unimportant features according to each explanation. Using a set of 1,000 images, each image is first labeled by the original model f(x; η) using the most likely predicted class. We then use explanations generated by each method to produce feature rankings and compute the top-1 accuracy (a measure of agreement with the original model) as we either include or exclude the most important features, ranging from 0-
100%. The area under each curve (AUC) is termed the Inclusion AUC or Exclusion AUC.
These metrics match the idea that an accurate image explanation should (1) maximally degrade the performance of peval when important features are excluded, and (2) maximally improve the performance of peval when important features are included (Petsiuk et al., 2018; Hooker et al., 2018). The explanations are evaluated by removing superpixels; for gradient-based methods, we coarsen the explanations using the sum total importance within each superpixel. In appendix E, we replicate these metrics using log-odds rather than top-1 accuracy, finding a similar ordering among methods.
Results. Table 1 shows the Inclusion and Exclusion AUC achieved by each method for both CIFAR-10 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 are removed from the images, the sharpest decline in top-1 accuracy is observed. Additionally, FastSHAP performs well when evaluated on the basis of Inclusion AUC, second only to KernelSHAP-S.
For Imagenette, GradCAM performs competitively with FastSHAP on Exclusion AUC and KernelSHAP-S marginally beats FastSHAP on Inclusion AUC. KernelSHAP-S also outperforms on Inclusion AUC with CIFAR-10, which is perhaps surprising given its high level of noise (fig. 4). However, KernelSHAP-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 explanations, 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. In appendix E, we find that FastSHAP outperforms most baseline methods on Inclusion and Exclusion AUC when using just 25% of the Imagenette data, and that it remains competitive when using just 10%.
6.5 SPEED EVALUATION Table 2: Training and explanation run-times for 1,000 images (in minutes).
CIFAR-10 Imagenette
E xp
la in FastSHAP 0.04 0.04 KernelSHAP 453.69 1089.50 KernelSHAP-S 460.10 586.12 GradCAM 0.38 0.30 IntGrad 0.91 0.92 SmoothGrad 1.00 1.05 DeepSHAP 5.39 6.01 CXPlain 0.04 0.04
Tr ai n FastSHAP 693.57 146.49 KernelSHAP-S 362.03 73.22 CXPlain 538.49 93.00
The image experiments were run using 8 cores of an Intel Xeon Gold 6148 processor and a single NVIDIA Tesla V100. Table 2 records the time required to explain 1,000 images. For FastSHAP, KernelSHAP-S and CXPlain, we also report the time required to train the surrogate and/or explainer models.
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 KernelSHAP requires significantly more time. These results suggest that FastSHAP is well suited for real-time applications where it is crucial to keep explanation times as low as possible. Further, when users need to explain a large quantity of data, FastSHAP’s low explanation cost can quickly compensate for its training time.

heading: 7 DISCUSSION
text: In this work, we introduced FastSHAP, a method for estimating Shapley values in a single forward 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 explanations.
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. FastSHAP 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 problem, FastSHAP stands to benefit as the state of deep learning advances, and it opens a new direction of research for efficient Shapley value estimation.

heading: 8 REPRODUCIBILITY
text: Code to implement FastSHAP is available online in two separate repositories: https://github. com/iancovert/fastshap contains a PyTorch implementation and https://github. com/neiljethani/fastshap/ a TensorFlow implementation, both with examples of tabular and image data experiments. The complete code for our experiments is available at https: //github.com/iclr1814/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.

heading: 9 ACKNOWLEDGEMENTS
text: We thank the reviewers for their thoughtful feedback, and we thank the Lee Lab for helpful discussions. Neil Jethani was partially supported by NIH T32 GM136573. Mukund Sudarshan was partially supported by a PhRMA Foundation Predoctoral Fellowship. Mukund Sudarshan and Rajesh Ranganath were partly supported by NIH/NHLBI Award R01HL148248, and by NSF Award 1922658 NRT-HDR: FUTURE Foundations, Translation, and Responsibility for Data Science. Ian Covert and Su-In Lee were supported by the NSF Awards CAREER DBI-1552309 and DBI-1759487; the NIH Awards R35GM128638 and R01NIAAG061132; and the American Cancer Society Award 127332-RSG-15-097-01-TBG.

heading: A FASTSHAP GLOBAL OPTIMIZER
text: 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 ϕfast(x,y; θ) is
L(θ) = E p(x) E Unif(y) E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕfast(x,y; θ) )2] .
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 ϕfast(x,y; θ) satisfy
1⊤ϕfast(x, y; θ) = vx,y(1)− vx,y(0) ∀ x ∈ X , y ∈ Y.
One option for guaranteeing the efficiency property is to adjust the model outputs using their additive efficient normalization (see section 3). 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 (x, y) as a separate optimization problem over the variable ϕx,y = ϕfast(x, y; θ) ∈ Rd:
min ϕx,y E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕx,y )2] (9)
s.t. ϕx,y = vx,y(1)− vx,y(0).
This is a constrained weighted least squares problem with a unique global minimizer, and it is precisely the Shapley value’s weighted least squares characterization (see eq. (3)). We can therefore conclude that the optimal prediction for each pair (x, y) is the true Shapley values, or ϕ∗x,y = ϕ(vx,y), and that the global optimizer for our objective function is a model ϕfast(x,y; θ∗) that outputs the true Shapley values.
If we incorporate efficiency regularization with parameter γ > 0 rather than a constraint on the model’s predictions, then ϕfast(x,y; θ) is trained using a modified objective. The expected loss for each pair (x, y) yields the following optimization problem over the variable ϕx,y ∈ Rd:
min ϕx,y E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕx,y )2] + γ ( vx,y(1)− vx,y(0)− 1⊤ϕx,y )2 .
For finite hyperparameter values γ ∈ [0,∞), the training objective relaxes the Shapley value’s efficiency property and eliminates the requirement that predictions must sum to the grand coalition’s value. However, using γ = ∞ turns the penalty into a constraint, resulting in the same constrained problem from eq. (9) for each sample (x, y). As a result, we can conclude that setting γ = ∞ ensures that FastSHAP’s global optimizer is a function that outputs the true Shapley values, at least in theory; in practice, excessively large γ values can disrupt gradient-based optimization, and finite values can be expected to yield sufficiently accurate results.
To achieve the global optimum, we require the ability to sample from p(x) (or a sufficiently large dataset), perfect optimization, and a function class for ϕfast(x,y; θ) that is expressive enough to contain the global optimizer. We describe below why neural networks are theoretically justified as a choice of function class.
The universal approximation theorem for neural networks (Cybenko, 1989; Hornik, 1991) guarantees that infinite-width neural networks can represent continuous functions to an arbitrary level of accuracy. Note that if the value function vx,y(s) in FastSHAP for a fixed subset s and label y is understood as a function of the input x, or gs,y(x) = vx,y(s), and the function gs,y(x) is continuous for each s ∈ {0, 1}d and y ∈ Y , then the Shapley value function hy(x) = ϕ(vx,y) is guaranteed to be continuous as well for all y. This is the case in our experiments, where the value function is a surrogate model parameterized by a continuous neural network. Under the mild assumption that hy(x) = ϕ(vx,y) is continuous, we can invoke the universal approximation theorem to claim that an infinite-width neural network can approximate the true Shapley values to an arbitrary degree of accuracy.

heading: B ADDITIVE EFFICIENT NORMALIZATION
text: Here, we provide a geometric interpretation for the additive efficient normalization step and prove that it is guaranteed to yield Shapley value estimates that are closer to their true values. Consider a game v with Shapley values ϕ(v) ∈ Rd, and assume that we have Shapley values estimates ϕ̂ ∈ Rd that do not satisfy the efficiency property. To force this property, we can project these estimates onto the efficient hyperplane, or the subset of Rd where the efficiency property is satisfied. This corresponds to solving the following optimization problem over ϕeff ∈ Rd:
min ϕeff ||ϕeff − ϕ̂||2 s.t. 1⊤ϕeff = v(1)− v(0).
We can solve the problem via its Lagrangian, denoted by L(ϕeff , ν), with the Lagrange multiplier ν ∈ R as follows:
L(ϕeff , ν) = ||ϕeff − ϕ̂||2 + ν ( v(1)− v(0)− 1⊤ϕeff ) ⇒ ϕ∗eff = ϕ̂− 1 v(1)− v(0)− 1⊤ϕ̂ d .
This transformation, where the efficiency gap is split evenly and added to each estimate, is known as additive efficient normalization (Ruiz et al., 1998). We implement it as an output layer for FastSHAP’s predictions to ensure that they satisfy the efficiency property (section 3). This step can therefore be understood as a projection of the network’s output onto the efficient hyperplane.
The normalization step is guaranteed to produce corrected estimates ϕ∗eff that are closer to the true Shapley values ϕ(v) than the original estimates ϕ̂. To see this, note that the projection step guarantees that ϕ̂ − ϕ∗eff and ϕ∗eff − ϕ(v) are orthogonal vectors, so the Pythagorean theorem yields the following inequality:
||ϕ(v)− ϕ̂||2 = ||ϕ(v)− ϕ∗eff ||2 + ||ϕ∗eff − ϕ̂||2
≥ ||ϕ(v)− ϕ∗eff ||2.

heading: C REDUCING GRADIENT VARIANCE
text: Recall that our objective function L(θ) is defined as follows:
L(θ) = E p(x) E Unif(y) E p(s)
[( vx,y(s)− vx,y(0)− s⊤ϕfast(x,y; θ) )2] .
The objective’s gradient is given by
∇θL(θ) = E p(x) E Unif(y) E p(s)
[ ∇(x,y, s; θ) ] , (10)
where we define
∇(x, y, s; θ) := ∇θ ( vx,y(s)− vx,y(0)− s⊤ϕfast(x, y; θ) )2 .
When FastSHAP is trained with a single sample (x, y, s), the gradient covariance is given by Cov ( ∇(x,y, s; θ) ) , 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 ∈ {1, . . . ,K}, we calculate the loss jointly for all classes. This yields gradients that we denote as∇(x, s; θ), defined as
∇(x, s; θ) := E Unif(y) [∇(x,y, s; θ)],
where we have the relationship
Cov ( ∇(x, s; θ) ) Cov ( ∇(x,y, s; θ) ) due to the law of total covariance. Next, we consider minibatches of b independent x samples, which yields gradients ∇b(x, s; θ) with covariance given by
Cov ( ∇b(x, s; θ) ) = 1
b Cov
( ∇(x, s; θ) ) .
We then consider sampling m independent coalitions s for each input x, resulting in the gradients ∇mb (x, s; θ) with covariance given by
Cov ( ∇mb (x, s; θ) ) = 1
mb Cov
( ∇(x, s; θ) ) .
Finally, we consider a paired sampling approach, where each sample s ∼ p(s) is paired with its complement 1− s. Paired sampling has been shown to 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 reduction 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 vx,y , learning rate α, batch size b, samples m, penalty parameter γ Output: FastSHAP explainer ϕfast(x,y; θ) initialize ϕfast(x,y; θ) while not converged do
setR← 0, L ← 0 for i = 1, . . . , b do
sample x ∼ p(x) for y = 1, . . . ,K do
predict ϕ̂← ϕfast(x, y; θ) calculateR← R+ ( vx,y(1)− vx,y(0)− 1⊤ϕ̂ )2 // Pre-normalization
if normalize then set ϕ̂← ϕ̂+ d−1 ( vx,y(1)− vx,y(0)− 1⊤ϕ̂ ) end for j = 1, . . . ,m do
if paired sampling and i mod 2 = 0 then set s← 1− s // Invert previous subset else sample s ∼ p(s) end
calculate L ← L+ ( vx,y(s)− vx,y(0)− s⊤ϕ̂ )2 end
end end update θ ← θ − α∇θ ( L bmK + γ R bK ) end

heading: D FASTSHAP MODELS AND HYPERPARAMETERS
text: In this section, we describe the models and architectures used for each dataset, as well as the hyperparameters used when training FastSHAP.
D.1 MODELS Tabular datasets. For the original model f(x; η), we use neural networks for the news and marketing datasets and gradient boosted trees for the census (LightGBM (Ke et al., 2017)) and bankruptcy (XGBoost (Chen and Guestrin, 2016)) datasets. The FastSHAP model ϕfast(x,y; θ) and the surrogate model psurr(y | m(x, s);β) are implemented using neural networks that consist of 2-3 fully connected layers with 128 units and ReLU activations. The psurr models use a softmax output layer, while ϕfast has no output activation. The models are trained using Adam with a learning rate of 10−3, and we use a 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; η) and psurr are ResNet-50 models pretrained on Imagenet. We use these without modification to the architecture and fine-tune them on each image dataset. To create the ϕfast(x,y; θ) model, we modify the architecture to return a tensor of size 14 × 14 ×K. First, the layers after the 4th convolutional block are removed; the output of this block is 14× 14× 256. We then append a 2D convolutional layer with K filters, each of size 1 × 1, so that the output is 14×14×K and the yth 14×14 slice corresponds to the superpixel-level Shapley values for each class y ∈ Y . Each model is trained using Adam with a learning rate of 10−3, and we use a 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 FastSHAP’s performance. There are two types of hyperparameters: sampling hyperparameters, which affect the number of samples of s taken during training, and efficiency hyperparameters, which control 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, we perform experiments using the same tabular datasets from the main text. We use the in-distribution value function psurr and compute the ground truth SHAP values the same way as in our previous experiments (i.e., by running KernelSHAP to convergence).
Figure 6 shows the mean ℓ2 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 ℓ2 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 3 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,
or only during inference), and penalty refers to the efficiency regularization technique with the parameter set to γ = 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.

heading: E ADDITIONAL RESULTS FOR IMAGE EXPERIMENTS
text: In this section, we provide additional results for the FastSHAP image experiments.
E.1 INCLUSION AND EXCLUSION METRICS Table 4 shows our inclusion and exclusion metrics when replicated using log-odds rather than accuracy. Similar to our metrics described in the main text, we choose the class predicted by the original model for each image, and we measure the average log-odds for that class as we include or 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 7 shows the raw inclusion and exclusion curves for both the accuracy and log-odds-derived metrics.
E.2 FASTSHAP ROBUSTNESS TO LIMITED DATA To test FastSHAP’s robustness to 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, calculated 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% of the data, and that it outperforms most baseline methods by a large margin when using just 25%.
E.3 EXAMPLE FASTSHAP IMAGE EXPLANATIONS Finally, we show additional explanations generated by FastSHAP and the baseline methods for both CIFAR-10 and Imagenette.
Airplane
Automobile
Bird
Cat
Deer
Dog
Frog
Horse
Ship
Truck

Review summaries:
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.  

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).