Efficient Shapley Values Estimation by Amortization for Text Classification (2023)

Abstract: Despite the popularity of Shapley Values in explaining neural text classification models, computing them is prohibitive for large pretrained models due to a large number of model evaluations. In practice, Shapley Values are often estimated with a small number of stochastic model evaluations. However, we show that the estimated Shapley Values are sensitive to random seed choices – the top-ranked features often have little overlap across different seeds, especially on examples with longer input texts. This can only be mitigated by aggregating thousands of model evaluations, which on the other hand, induces substantial computational overheads. To mitigate the trade-off between stability and efficiency, we develop an amortized model that directly predicts each input feature’s Shapley Value without additional model evaluations. It is trained on a set of examples whose Shapley Values are estimated from a large number of model evaluations to ensure stability. Experimental results on two text classification datasets demonstrate that our amortized model estimates Shapley Values accurately with up to 60 times speedup compared to traditional methods. Further, our model does not suffer from stability issues as inference is deterministic. We release our code at https://github.com/yangalan123/Amortized-Interpretability .

## introduction many powerful natural language processing (nlp) models used in commercial systems only allow users to access model outputs. when these systems are applied in high-stakes domains, such as healthcare, finance, and law, it is essential to interpret how these models come to their decisions. to this end, post-hoc black-box explanation methods have been proposed to identify the input features that are most critical to model predictions @xcite . a famous class of post-@xmath0: heatmaps of explanation scores of an example from yelp-polarity based on two runs of kernelshap (ks) using different random seeds. ks is run on a fine-tuned bert model using 200 samples per instance (approx. 3.47s per instance on average using a single a100 gpu, more than 150 times slower than one forward inference of the bert model). the darker each token is, the higher its explanation score. clearly, interpretation results are significantly different when using different seeds. despite the widespread usage of shapley values methods, we observe that when they are applied to text data, the estimated explanation score for each token varies significantly with the random seeds used for sampling. figure 1 shows an example of interpreting a bert-based sentiment classifier @xcite on yelp-polarity dataset, a restaurant review dataset @xcite by ks. the set of tokens with high explanation scores varies significantly when using different random seeds. they become stable only when the number of perturbation samples increases to more than 2,000. as ks requires model prediction for each perturbation sample, the inference cost can be substantial. for example, it takes about 183 seconds to interpret each instance in yelp-polarity using the ks captum implementation @xcite on an a100 gpu. in addition, this issue becomes more severe when the input text gets longer, as more perturbation samples are needed for reliable estimation of shapley values. this sensitivity to the sampling process leads to an unreliable interpretation of the model predictions and hinders developers from understanding model behavior. to achieve a better trade-off between efficiency and stability, we propose a simple yet effective amortization method to estimate the explanation scores. motivated by the observation that different instances might share a similar set of important words (e.g., in sentiment classification, emotional words are strong label indicators @xcite ), an amortized model can leverage similar interpretation patterns across instances when predicting the explanation scores. specifically, we amortize the cost of computing explanation scores by precomputing them on a set of training examples and train an amortized model to predict the explanation scores given the input. at inference time, our amortized model directly outputs explanation scores for new instances. although we need to collect a training set for every model we wish to interpret, our experiments show that with as few as 5000 training instances, the amortized model achieves high estimation accuracy. we show our proposed amortized model in figure 2 . the experimental results demonstrate the effi-ciency and effectiveness of our approach. first, our model reduces the computation time from about 3.47s per instance to less than 50ms, foot_0 which is 60 times faster than the baseline methods. second, our model is robust to randomness in training (e.g., random initialization, random seeds used for generating reference explanation scores in the training dataset), and produces stable estimations over different random seeds. third, we show that the amortized model can be used along with svs to perform local adaption, i.e., adapting to specific instances at inference time, thus further improving performance if more computation is available (6.3). finally, we evaluate our model from the functionality perspective @xcite by examining the quality of the explanation in downstream tasks. we perform case studies on feature selection and domain calibration using the estimated explanation scores, and show that our method outperforms the computationally expensive ks method. there are other interpretability methods in nlp. for example, gradient-based methods @xcite , which use the gradient w.r.t. each input dimension as a measure for its saliency. reference-based methods @xcite consider the model output difference between the original input and reference input (e.g., zero embedding vectors). ## background in this section, we briefly review the basics of shapley values, focusing on its application to the text classification task. local explanation of black-box text classification models. in text classification tasks, inputs are usually sequences of discrete tokens @xmath1, w 2 , . . . , w l ]. here l is the length of x and may vary across examples; w j is the j-th token of x. the classification model m clf takes the input x and predict the label as ŷ = arg max @xmath2. local explanation methods treat each data instance independently and compute an explanation score ϕ(j, y), representing the contribution of w j to the label y. usually, we care about the explanation scores when @xmath3. shapley values (sv) are concepts from game theory originally developed to assign credits in cooperative games @xcite @xcite . let @xmath4, 1} l be a masking of the input and define x s @xmath5:s @xmath6. in this paper, we follow the common practice @xcite @xcite to replace masked tokens with [pad] in the input before sending it to the classifier. let |s| represent the number of non-zero terms in s. shapley values ϕ sv (i, y) @xcite are computed by: intuitively, ϕ sv (i, y) computes the marginal contributions of each token to the model prediction. computing sv is known to be np-hard @xcite . in practice, we estimate shapley values approximately for efficiency. shapley values sampling (svs) @xcite is a widely-used monte-carlo estimator of sv: here σ @xmath7. [σ j ] i-1 represents the set of indices ranked lower than i in σ j . s([σ j ]) maps the indices set [σ j ] to a mask @xmath8, 1} l such that s @xmath9. m is the number of perturbation samples used for computing svs. kernelshap although svs has successfully reduced the exponential time complexity to polynomial, it still requires sampling permutations and needs to do sequential updates following sampled orderings and computing the explanation scores, which is an apparent efficiency bottleneck. lundberg and lee (2017) introduce a more efficient estimator, kernelshap (ks), which allows better parallelism and computing explanation scores for all tokens at once using linear regression. that is achieved by showing that computing sv is equivalent to solving the following optimization problem: ## stability of local explanation one of the most common applications of sv is feature selection, which selects the most important features by following the order of the explanation scores. people commonly use ks with an affordable number of perturbation samples in practice (the typical numbers of perturbation samples used in the literature are around @xcite @xcite . however, as we see in figure 1 , the ranking of the scores can be quite sensitive to random seeds when using stochastic estimation of sv. in this section, we investigate this stability issue. we demonstrate stochastic approximation of sv is unstable in text classification tasks under common settings, especially with long texts. in particular, when ranking input tokens based on explanation scores, spearman's correlation between rankings across different runs is low. measuring ranking stability. given explanation scores produced by different random seeds using an sv estimator, we want to measure the difference between these scores. specifically, we are interested in the difference in the rankings of the scores as this is what we use for feature selection. to measure the ranking stability of multiple runs using different random seeds, we compute spearman's correlation between any two of them and use the average spearman's correlation as the measure of the ranking stability. in addition, we follow @xcite to report top-k intersections between two rankings, since in many applications only the top features are of explanatory interest. we measure the size of the intersection of top-k features from two different runs. setup. we conduct our experiments on the validation set of the yelp-polarity dataset @xcite and mnli dataset @xcite . yelp-polarity is a binary sentiment classification task and mnli is a three-way textual entailment classification task. we conduct experiments on 500 random samples with balanced labels (we refer to these datasets as "stability evaluation sets" subsequently). results are averaged over 5 different random seeds. 3 we use the publicly available finetuned bert-base-uncased checkpoints foot_4 @xcite as the target models to interpret and use the implementation of captum @xcite to compute the explanation scores for both ks and svs. for each explanation method, we test with the recommended numbers of pertur longer input suffers more from instability. we also plot the spearman's correlation decomposed at different input lengths in figure 3 . here, we observe a clear trend that the ranking stability degrades significantly even at an input length of 20 tokens. the general trend is that the longer the input length is, the worse the ranking stability. the same trend holds across datasets. as many nlp tasks involve sentences longer than 20 tokens (e.g., sst-2 @xcite , mnli @xcite ), obtaining stable explanations to analyze nlp models can be quite challenging. discussion: why shapley values estimation is unstable in text domain? one of the most prominent characteristics of the text domain is that individual tokens/n-grams can have a large impact on the label. thus they need to be all included in the perturbation samples for an accurate estimate. when the input length grows, the number of n-grams will grow fast. as shown in section 3, the probability of certain n-grams getting sampled is drastically reduced as each n-gram will be sampled with equivalent probability. therefore, the observed model output will have a large variance as certain n-grams may not get sampled. a concurrent work @xcite presented a related theoretical analysis on why the uniform sampling setting in sv computation can lead to suboptimal attribution. ## amortized inference for shapley values motivated by the above observation, we propose to train an amortized model to predict the explanation scores given an input without any model evaluation on perturbation samples. the inference cost is thus amortized by training on a set of pre-computed reliable explanation scores. we build an amortized explanation model for text classification in two stages. in the first stage, we construct a training set for the amortized model. we compute reliable explanation scores as the reference scores for training using the existing sv estimator. as shown in section 4, svs-25 is the most stable sv estimator and we use it to obtain reference scores. in the second stage, we train a bert-based amortized model that takes the text as input and outputs the explanation scores using mse loss. specifically, given input tokens x, we use a pretrained language model m lm to encode words into d-dim embeddings ⃗ @xmath10, . . . , ⃗ e l(x) ] ∈ r l(x)×d . then, we use a linear layer to transform each ⃗ e i to the predicted explanation score ϕ am (i, ŷi ) = w⃗ e i + b. to train the model, we use mse loss to fit ϕ am (i, ŷ) to the precomputed reference scores ϕ(i, ŷ) over the training set x train . this is an amortized model in the sense that there are no individual sampling and model queries for each test example x as in svs and ks. when a new sample comes in, the amortized model makes a single inference on the input tokens to predict their explanation scores. ## experiments in this section, we present experiments to demonstrate the properties of the proposed approach in terms of accuracy against reference scores (6.1) and sensitivity to training-time randomness (6.2). we also show that we achieve a better fit via a local adaption method that combines our approach with svs (6.3). then, we evaluate the quality of the explanations generated by our amortized model on two downstream applications (6.5). ## conclusion in this paper, we empirically demonstrated that it is challenging to obtain stable explanation scores on long text inputs. inspired by the fact that different instances can share similarly important features, we proposed to efficiently estimate the explanation scores through an amortized model trained to fit pre-computed reference explanation scores. in the future, we plan to explore model architecture and training loss for developing effective amortized models. in particular, we may incorporate sorting-based loss to learn the ranking order of features. additionally, we could investigate the transferability of the amortized model across different domains, as well as exploring other shap-based methods instead of the time-consuming svs-25 in the data collection process to improve efficiency further.