{'fraction_non_alphanumeric': 0.0340141418920695, 'fraction_numerical': 0.006913229766317063, 'mean_word_length': 4.847525361205041, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Why Attentions May Not Be Interpretable?

Attention-based methods have played important roles in model interpretations, where the calculated attention weights are expected to highlight the critical parts of inputs~(e.g., keywords in sentences). However, recent research found that attention-as-importance interpretations often do not work as we expected. For example, learned attention weights sometimes highlight less meaningful tokens like"[SEP]",",", and".", and are frequently uncorrelated with other feature importance indicators like gradient-based measures. A recent debate over whether attention is an explanation or not has drawn considerable interest. In this paper, we demonstrate that one root cause of this phenomenon is the combinatorial shortcuts, which means that, in addition to the highlighted parts, the attention weights themselves may carry extra information that could be utilized by downstream models after attention layers. As a result, the attention weights are no longer pure importance indicators. We theoretically analyze combinatorial shortcuts, design one intuitive experiment to show their existence, and propose two methods to mitigate this issue. We conduct empirical studies on attention-based interpretation models. The results show that the proposed methods can effectively improve the interpretability of attention mechanisms.


INTRODUCTION
Interpretation for machine learning models has gained increasing interest and becomes necessary in practice as the industry rapidly embraces machine learning technologies. Model interpretation explains how models make decisions, which is particularly essential in mission-critical domains where the accountability and transparency of the decision-making process are crucial, such as medicine [32], security [5], and criminal justice [18].
Attention mechanisms have played important roles in model interpretations. As shown in Figure 1, attention mechanism as building blocks in neural networks are often applied to provide interpretability along with improving performance [7,30,33], and hard attention-based models are also used in explaining arbitrary blackbox models' predictions, by selecting a fixed number of input components to approximate the predictions [4,6,17]. More concretely, we formalize the attention mechanisms as Attention( , , ) = Mask( , ) ⊙ 1 as in [30], where is the query and ⟨ , ⟩ are the key-value pairs. Mask(·, ·) maps the query and keys to the attention weights (denoted as masks in this paper), and then the masks filter the information of . In other words, the masks are expected to represent the importance of different parts of (e.g., words of a sentence, pixels of an image) and highlight those the models focus on to make decisions.
However, recent research suggested that the feature parts highlighted by attention mechanisms do not necessarily correlate with intuitively greater importance on the final predictions. For example, Clark et al. [8] found that a surprisingly large amount of BERT's attention focuses on less meaningful tokens like "[SEP]", ",", and ".". Moreover, many researchers have provided evidence to support or refute the interpretability of the attention mechanisms. There have been lots of debates on whether attention is an explanation or not recently [12,26,34].
In this paper, we propose that a root cause hindering the interpretability of attention mechanisms is combinatorial shortcuts. As mentioned earlier, we expect that the results of attention mechanisms mainly contain information from the highlighted parts of , which is a critical assumption for attention-based interpretations' effectiveness. However, as the results are products of the masks and , we find that the masks themselves can carry extra information other than the highlighted parts of , which the downstream parts of models could utilize. As a result, the calculated masks may work as another kind of "encoding layers" rather than providing pure feature importance. For an extreme example, in a (binary) text classification task, the attention mechanisms could highlight the first word for positive cases and highlight the last one for negative cases, regardless of the word semantics. The downstream parts of attention layers can then predict the label by checking whether the first or the last word is highlighted, which may give good accuracy scores but completely fail to provide interpretability 2 .
We further study the effectiveness of attention-based interpretations and dive into the combinatorial shortcut problem. From the perspective of causal effect estimations, we first analyze the difference between coventional attention mechanisms and ideal interpretations theoretically, and then show the existence of combinatorial shortcuts through a constructive experiment. Based on the observations, we propose two methods to mitigate the issue, i.e., random attention pretraining and instance weighting for mask-neutral learning. Without loss of generality, we examine the effectiveness of the proposed methods with an end-to-end attention-based modelinterpretation approach, i.e., L2X [6], which can select a given number of input components to explain arbitrary black-box models. Experimental results show that the proposed methods can successfully mitigate the adverse impact of combinatorial shortcuts and improve explanation performance.

RELATED WORK
Attention mechanisms for model interpretations Attention mechanisms have been widely adopted in natural language processing [1,31], computer vision [11,16], recommendations [2,42] and so on. Attention mechanisms have been used to explain how models make decisions by exhibiting the importance distribution over inputs [7,20,33], which we can regard as a kind of modelspecific interpretation. Besides, there are also attention-based methods for model-agnostic interpretations. For example, L2X [6] is a hard attention model [37] that employs Gumbel-softmax [13] for instancewise feature selection. VIBI [3] improved L2X to encourage the briefness of the learned explanation by adding a constraint for the feature scores to a global prior. Liang et al. [17] and Yu et al. [38] improved attention-style model interpretation methods through adversarial training to encourage the gap between the predictability of selected/unselected features.
However, there has been a debate on the interpretability of attention mechanisms recently. Jain and Wallace [12] suggested that "attention is not explanation" by finding that the attention weights are frequently uncorrelated with other feature importance indicators like gradient-based measures. On the other side, Wiegreffe and Pinter [34] argued that "attention is not not-explanation" by challenging many assumptions underlying Jain and Wallace [12] and suggested that they did not disprove the usefulness of attention mechanisms for explainability. Serrano and Smith [26] applied a different analysis based on intermediate representation erasure and found that while attention noisily predicts input components' overall importance to a model, it is by no means a fail-safe indicator.
In this work, we take another perspective on this problem called combinatorial shortcuts, and show that it can provide one root cause of the phenomenon. We analyze why combinatorial shortcuts exist and propose theoretically guaranteed methods to alleviate the problem.
Causal effect estimations Causal effect is an important concept for quantitative empirical analyses. The causal effect of one treatment, , over another, , is defined as the difference between what would have happened if a particular unit had been exposed to and what would have happened if the unit had been exposed to [24]. Randomized experiments, where the experimental units across the treatment groups are randomly allocated, play a critical role in causal inference. However, when randomized experiments are infeasible, researchers have to resort to nonrandomized data from surveys, censuses, and administrative records [35], and there may be some other variables controlling the treatment allocation process in such data. For example, consider the causal inference between uranium mining and health. Ideally, the treatment (uranium mining) should be randomly allocated. However, mining workers are usually stronger people among all humans in the world. If some appropriate measures are absent, we may draw biased conclusions like "uranium mining has no adverse health impact because the average life span of uranium mine workers is not shorter than that of ordinary people". For recovering causal effects from nonrandomized data, instance weighting-based approaches have been used widely [9,23,35].

COMBINATORIAL SHORTCUTS
In this section, by showing the difference between attention mechanisms and ideal explanations, we analyze why attention mechanisms become less interpretable from the perspective of causal effect estimations, and conduct an experiment to demonstrate the existence of combinatorial shortcuts.

The difference between attention mechanisms and ideal explanations
Firstly, we analyze what ideal explanations are. Although the concept of "explanation" may differ in different situations, following   Figure 2. Note that we report the results on the training set to demonstrate how models fit the data.

No.
Encoder where L (·) is the loss function and E(·) calculates the expectation, we say that for this sample, 1 is superior to 2 in term of interpretability. If an unbiased estimation of E( | ⊙ ) is available, the best mask for sample ⟨ , ⟩ that can select the most informative features can be obtained by solving argmin L E( | ⊙ ), . As a conclusion, under the definitions above, the ideal explanation * for sample ⟨ , ⟩ is argmin L E( | ⊙ ), with an unbiased estimation of E( | ⊙ ).
In practice, we often need to train models to estimate E( | ⊙ ). Ideally, if the data (combinations of and , as well as the label ) is exhaustive and the model is consistent, we can train a model to obtain an unbiased estimation of E( | ⊙ ) following the empirical risk minimization principle [10,29]. Nevertheless, it is impossible to exhaust all combinations of and . Taking a step back, from the perspective of causal effect estimations, we could consider different as different treatment, and randomized combinations for and can still be proven to give unbiased estimations on expectations [24].
However, attention mechanisms do not work in this way. Considering the downstream part of attention models, i.e., the part estimating the function E( | ⊙ ), we can find that it receives highly selective combinations of and . The used mask during the training procedure is a mapping from query and keys, making the used mask for samples highly related to the feature (and as well). Consequently, the training procedure of the attention mechanism produces a nonrandomized experiment [27]. Therefore the model cannot learn unbiased E( | ⊙ ). In turn, the attention mechanism will try to select biased features to adapt the biased estimations to minimize the overall loss functions, and thus fail to highlight the essential features. As a result, the attention mechanism and downstream part may cooperate and find unexpected ways to fit the data, e.g., highlighting the first word for positive cases and the last word for negative cases, ultimately failing to provide interpretability. This paper denotes the effects of nonrandomized combination for and that hinders the interpretability of attention mechanisms as combinatorial shortcuts.

Experimental demonstration for the combinatorial shortcuts
To intuitively demonstrate the existence of combinatorial shortcuts, we design a simple experiment on text classification tasks. As Figure 2 shows, we train attention models, where the query of attention is encoded with the whole sentences. However, we only allow attention to highlight keywords among the first five tokens and four default tokens, i.e., "A", "B", "C", and "D". After the Attention module, the weighted sequences are further encoded to a fixed-length vector with the Encoder module, and finally to predict the labels. Since the default tokens appear in all samples and do not carry any meaningful information, if the attention mechanism can highlight the inputs' critical parts, little attention should be paid to them. Moreover, we could check whether the models put differential attention to default tokens for different classes to show if the information is encoded in the mask due to combinatorial shortcuts.
We use the real-world IMDB dataset [19] for experiments and examine different settings regarding the Encoder module in Figure 2, i.e., whether the encoder is a simple sum pooling or a positionaware trainable neural network model, i.e., recurrent convolutional neural network (RCNN) proposed by Lai et al. [14]. We use pretrained GloVe word embeddings [21] and keep them fixed to prevent shortcuts through word embeddings. We train soft attention models for 25 epochs with RMSprop optimizers using default parameters and record the averaged results of 10 runs. The results are reported in Table 1.
As we can see in Table 1, the attention models placed more than half of the attention weights to the default tokens, and the weights for different classes were significantly different. Taking Pooling encoders as an example, the models put up to 68.0% attention weights to default token "A" for positive samples, and put 36.6%, 38.3%, and 18.5% attention weights to default token "B", "C", and "D" respectively for negative samples, summing up to 93.4% in total. As for RCNN encoders, the results were similar. The reason for observing repeatable results on default tokens with different initialization may be due to their slight asymmetry in the GloVe embedding space, i.e., "A" is slightly closer to "good" than to "bad", while the other three default tokens are just the opposite. These results suggest that the attention mechanism may not work as expected to highlight the critical parts of inputs and provide interpretability. Instead, they learn to work as another kind of "encoding layers" and utilize the default tokens to fit the data through combinatorial shortcuts.

METHODS FOR MITIGATING COMBINATORIAL SHORTCUTS
In this section, based on the perspective of causal effect estimations introduced in Section 3.1, we come up with two methods, random attention pretraining and mask-neutral learning with instance weighting respectively, to mitigate combinatorial shortcuts for better interpretability. Then we compare the pros and cons of the two methods.

Random attention pretraining
We first propose a simple and straightforward method to address the issue. As analyzed in Section 3.1, the fundamental reason for combinatorial shortcuts is the biased estimation of E( | ⊙ ), and random combinations of and can give unbiased results in theory. Inspired by this idea, we can generate the masks completely at random and train the attention model's downstream part. We then fix the downstream part, replace the random attention with a trainable attention layer, and train the attention layer only. As the downstream parts of neural networks are trained unbiasedly and fixed, solely training the attention layers is solving * = argmin L E( | ⊙ ), with an unbiased estimation of E( | ⊙ ). Thus the interpretability is guaranteed.

Mask-neutral learning with instance weighting
The second method is based on instance weighting, which has been successfully applied for mitigating sample selection bias [39,40], social prejudices bias [41], and also for recovering the causal effects [9,35]. The core idea of this method is that instead of fitting a biased E( | ⊙ ), with instance weighting, we could recover a mask-neutral distribution where the masks are unrelated to the labels. Thus the downstream parts of attention layers become less biased, and combinatorial shortcuts can be partially mitigated.
Assumptions about the biased distribution and the maskneutral distribution We first define the mask-neutral distribution and its relationship with the biased distribution with which ordinary attention mechanisms are trained. Considering the downstream part of the attention layers, which estimates 4 , M is the feature mask space, and S is the binary sampling indicator space. During the training procedure, the selective combination of masks and features result in combinatorial shortcuts. We assume for any given sample ( , , , ) drawn independently from Q, it will be selected to appear in the training of attention mechanisms if and only if = 1, which results in the biased distribution P. We use (·) to represent probabilities of the biased distribution P, and (·) for the mask-neutral distribution Q, then we have Ideally, we should have ⊥ ( , ) on Q to obtain unbiased E( | ⊙ ) as discussed in Section 3.1. However, when both sides are vectors, it will be intractable. Therefore, we take a step back and only assume ⊥ on Q, i.e., If is completely at random, P will be consistent with Q. However, the attention layers are highly selective, making that only some combinations of and are visible to the downstream model. We assume that and control . And for any given and , the probability of selection is greater than 0, defined as To further simplify the problem, we assume that the selection does not change the marginal probability of and , i.e., In other words, we assume that although is dependent on the combination of and in Q, it is independent on either or only, i.e., ( | ) = ( ) and ( | ) = ( ).

The unbiased expectation of loss with instance weighting
We show that, by adding proper instance weights, we can obtain an unbiased estimation of the loss on the mask-neutral distribution Q, with only the data from the biased distribution P. Fact 1 shows that, by a proper instance-weighting method, the downstream part of the attention model can learn on the maskneutral distribution Q, where ( | ) = ( ). Therefore, the independence between and is encouraged, then it will be hard for the classifier to approximate solely by . Thus, the classifier will have to use useful information from , and have the combinatorial shortcuts problem mitigated.
We present the proof for Fact 1 as follows.
Proof. We first present an equation with the weight , Then we have □ Mask-neutral learning With Fact 1, we now propose maskneutral learning for better interpretability of attention mechanisms. As shown, by adding instance weight = ( ) ( | ) to the loss function, we can obtain unbiased loss of the mask-neutral distribution. As distribution P is directly observable, estimating (·) is possible. In practice, we could train a classifier to estimate ( | ) along with the training of the attention layer, optimize it and the attention layers, as well as the other parts of models alternatively.

Comparison of the two methods
As analyzed in Section 3.1, random attention pretraining is complete in theory. However, it may be practically incompetent because there are countless viable cases of the combinations of and . It could be challenging to estimate E( | ⊙ ) well, especially when the dimension of input features is high or strong co-adapting patterns exist in the data. Under such cases, the pretraining procedure may become less efficient as it needs to explore all possible masks evenly, even if most of the masks are worthless. In conclusion, the model may fail to estimate complex E( | ⊙ ) functions well in some cases, which finally limits the interpretability.
Compared with the random attention pretraining method, the instance weighting-based approach concentrates more on the useful masks to address the shortcomings. Thus it will suffer less from the efficiency problem. Nevertheless, the effectiveness of the instance weighting method relies on the assumptions as shown in Equation (1)-(4). However, in some cases, the assumptions may not hold. For example, in Equation (3), we assume that given and , is independent on . In other words, controls only through . This assumption is necessary for simplifying the problem, but may not sometimes hold when given and , can still influence . Besides, the effectiveness of the method also relies on an accurate estimation of ( | ), which may require careful tuning as the probability ( | ) is dynamically changing along the training process of attention mechanisms.

EXPERIMENTS
In this section, we present the experimental results of the proposed methods. For simplicity, we denote random attention pretraining as Pretraining and mask-neutral learning with instance weighting as Weighting. Firstly, we analyze the effectiveness of mitigating combinatorial shortcuts. Then, we examine the effectiveness of improving interpretability.

Experiments for mitigating combinatorial shortcuts
We applied the proposed methods to the experiments introduced in Section 3.2 to check whether we can mitigate the combinatorial shortcuts. We summarize the results in Table 2.
As presented, after applying Pretraining and Weighting, the percentage of attention weights assigned to the default tokens were significantly reduced. Since that the default tokens do not provide useful information but only serve as carriers for combinatorial shortcuts, the results reveal that our methods have mitigated the combinatorial shortcuts successfully.

Experiments for improving interpretability
In this section, using L2X [6] as an example and basis, we present the effectiveness of mitigating combinatorial shortcuts for better interpretability.

Task and evaluation.
The task is the same as Chen et al. [6] and Liang et al. [17], i.e., to find a small subset of input components that suffices on its own to yield the same outcome by the model to be explained, and the relative importance of each feature is allowed to vary across instances. We assume that we have access  to the to-be-explained black-box model, and the task asks for the importance score of each feature component, and then the top most important feature components could be obtained. We use the same evaluation method as Chen et al. [6] and Liang et al. [17], i.e., a predictive evaluation that assesses how accurate the to-beexplained model can approximate the original model-outputs using the selected feature components only, and we report this post-hoc accuracy. More details about the calculation of post-hoc accuracy are in Appendix A.3.

Experimental settings.
Here we present the experimental settings. Due to space constraints, we present more details in Appendix A.
Basic settings Similar to Liang et al. [17], to further enrich the information for model explanations, we incorporate the to-beexplained model's outputs, i.e.,^, as part of the query for feature selection. As obtaining the outputs requires no further information apart from samples' features and the to-be-explained model, it does not hurt the model-agnostic property of explanation methods nor requires additional annotations. We adopt binary feature-attribution masks to select features, i.e., top values of the mask are set to 1, others are set to 0, then we treat ⊙ as the selected features [6]. We repeated ten times with different initialization for each method on each dataset and report the averaged post-hoc accuracy results.

Experimental results.
Following the aforementioned evaluation scheme, we report the results in Table 3.
From the table, we can find that directly adding^to the query did not always improve the performance by comparing Row (4) and (7). Interestingly, for the text classification datasets, adding^led to decreased performance, and meanwhile, Pretraining outperformed Table 4: The example results of explanation from IMDB. The model to be explained makes the incorrect prediction for this sample, i.e., the ground-truth label of the review text is negative, while the trained model predicts positive for it.

L2X
Aussie Shakespeare for 18-24 set. With blood, blood and more blood, and good dose of nudity. This will not be for every one on may levels, to violent for some too cheap for most. Done on low budget they try and do there best but it only works sporadically. And this macbeth just seem to be lacking, it's just not compelling. Although there is some good acting on the part of most you don't get into there heads especially mecbeths. The best performance came from Gary sweet and the strangest mick molly. If your into Shakespeare then see it, but if you like your cheese mature you will love it. It not a bad film but it not that good either. Sam Peckenpah would of loved it, that is if it was filmed as a western. I was expecting a lot from this, as I loved romper stomper. But this is was a vacant effort. (Prediction with key words: negative) L2X with^Aussie Shakespeare for 18-24 set. With blood, blood and more blood, and good dose of nudity. This will not be for every one on may levels, to violent for some too cheap for most. Done on low budget they try and do there best but it only works sporadically. And this macbeth just seem to be lacking, it's just not compelling. Although there is some good acting on the part of most you don't get into there heads especially mecbeths. The best performance came from Gary sweet and the strangest mick molly. If your into Shakespeare then see it, but if you like your cheese mature you will love it. It not a bad film but it not that good either. Sam Peckenpah would of loved it, that is if it was filmed as a western. I was expecting a lot from this, as I loved romper stomper. But this is was a vacant effort. (Prediction with key words: positive)

L2X with( Pretrain)
Aussie Shakespeare for 18-24 set. With blood, blood and more blood, and good dose of nudity. This will not be for every one on may levels, to violent for some too cheap for most. Done on low budget they try and do there best but it only works sporadically. And this macbeth just seem to be lacking, it's just not compelling.
Although there is some good acting on the part of most you don't get into there heads especially mecbeths. The best performance came from Gary sweet and the strangest mick molly. If your into Shakespeare then see it, but if you like your cheese mature you will love it. It not a bad film but it not that good either. Sam Peckenpah would of loved it, that is if it was filmed as a western. I was expecting a lot from this, as I loved romper stomper. But this is was a vacant effort.
(Prediction with key words: positive)

L2X with( Weight)
Aussie Shakespeare for 18-24 set. With blood, blood and more blood, and good dose of nudity. This will not be for every one on may levels, to violent for some too cheap for most. Done on low budget they try and do there best but it only works sporadically. And this macbeth just seem to be lacking, it's just not compelling.
Although there is some good acting on the part of most you don't get into there heads especially mecbeths. The best performance came from Gary sweet and the strangest mick molly. If your into Shakespeare then see it, but if you like your cheese mature you will love it. It not a bad film but it not that good either. Sam Peckenpah would of loved it, that is if it was filmed as a western. I was expecting a lot from this, as I loved romper stomper. But this is was a vacant effort.
(Prediction with key words: positive)  Weighting. For the image classification datasets, we had the exact opposite conclusion. We ascribe this phenomenon to the inherent differences between the two tasks. Intuitively, people could easily guess the emotional polarity of a sentence from a few randomly selected words in a sentence, but it is not easy to guess the content of a picture from a few randomly selected pixels in an image. The function of E( | ⊙ ) may be smoother and more comfortable to learn for text classification tasks than for image classification tasks. As a result, as discussed in Section 4.3, it may be hard for Pretraining to learn reasonable estimations of E( | ⊙ ) efficiently for images. Thus the performance of interpretability is limited, especially for MNIST, where the digital numbers are placed randomly, compared with F-MNIST, where the items are aligned better. By comparing with the baselines (especially L2X with^), we find that despite the simplicity, Pretraining and Weighting can outperform most of the baselines and give comparable results with AIL, which is state of the art and utilizes additional information of the to-be-explained models, i.e., their gradients. We conclude that mitigating the combinatorial shortcuts can effectively improve interpretability.

Visualization examples of explanation.
Here, we present the interpretation results of the examples from the tested datasets. Please note that we are trying to explain how machine learning models make decisions. These models are trained on datasets of limited size, and the datasets may be more or less biased, so the interpretation results may be inconsistent with ordinary people's understanding, especially for images.
IMDB We first present an example from IMDB dataset. The results are in Table 4. Explanations to the functional tokens like <START> and <PAD> are omitted.
As shown from the example, L2X with^tends to select highfrequency but meaningless words (e.g., and), or niche words which are merged as <UNK> token (e.g., Aussie and sporadically). This phenomenon explains the reason why L2X with^get poor posthoc accuracy scores during our experiments on text classification datasets, and as analyzed in Section 3, this can be ascribed to the combinatorial shortcuts. After applying the proposed methods (i.e., Pretrain and Weight), the combinatorial shortcut problem has been mitigated successfully, and the explaining model can select better words for explanations. Besides, we can find that after adding the information of^to the query, the explanation models could better capture the key parts corresponding to the original given model to be explained. For example, L2X selects "is was a vacant effort" in Table 4 and the given model predicts negative with the selected words by L2X, however, the model to be explained actually predicts positive for this example, and after adding^and applying the proposed methods, the explanation results become more consistent to the given model.
Yelp P. In this section, we present an example from Yelp P. dataset. The results are in Table 5. Similarly, explanations to the functional tokens like <START> and <PAD> are omitted.
Compared with the results of IMDB, we find that the explanation results of L2X seem to be more susceptible to the combinatorial shortcut problem, as words like a and tokens like <PAD> appear in the explanation results of L2X more frequently. This phenomenon may be ascribed to that the sentences in Yelp P. are shorter than IMDB, thus the explainer could more easily capture the global meaning of the sentences and form combinatorial shortcuts. For L2X with^, the results are consistent with the results of IMDB, i.e., meaningless words and <UNK> tokens are frequently selected. Pretrain and Weight can help mitigate the problem of combinatorial shortcuts, and thus improve the performance of interpretability.
MNIST Figure 3 shows four examples from MNIST. We find that the given model to be explained predicts all samples with label 8 in the test set correctly, so we choose the least confident sample to present in the 4th row of Figure 3.
The gray parts of images are unselected pixels, while the white/black parts are selected pixels. We find a very significant tendency that L2X and Weight tend to select white pixels in the image, while L2X with^and Pretrain tend to select black pixels. In the 2nd row of Figure 3, only Weight select the right parts which makes the model to be explained predict 8 for this sample. Figure 4 shows four examples from Fashion-MNIST. Similarly, the gray parts of images are unselected pixels, and the white/black parts are selected pixels.

F-MNIST
Interestingly, we find that L2X tends to select the pixels on the edges. Similar to the examples of L2X in Table 4, the highlighted parts given by L2X may tend to be important generally, however, it may not be the most significant part for explaining the predictions of given models. On the other side, the explanations given by Weight tend to be of the neckline parts and the shoulder parts of the clothing, and maybe more informative to explain the predictions of machine learning models. For example, in the 3rd row of Figure 4, L2X selects the edges of the given image, while the model to be explained judges that the select features suggest that the image belongs to a Pullover.

CONCLUSION
Attention-based model interpretations have been popular for their convenience to integrate with neural networks. However, many researchers find that attention sometimes yields non-interpretable results, and there has been a debate on the interpretability of the attention mechanisms. This paper proposes that the combinatorial shortcuts are one of the root causes hindering attention mechanisms' interpretability. We analyze the combinatorial shortcuts   theoretically and design experiments to show their existence. Furthermore, we propose two methods to mitigate combinatorial shortcuts for better interpretability. Experiments show that the proposed methods effectively mitigate the adverse impacts and improve the interpretability of attention mechanisms. The results presented in this paper can help us better understand how attention mechanisms work.

A DETAILS ABOUT THE EVALUATION SCHEME
Here we present the structure of the models used for our experiments, as well as how the evaluation metrics are calculated.
A.1 The text classification models for IMDB and Yelp P.
The structure of neural network models to be explained for text classification datasets (including IMDB and Yelp P.) is presented in Table 6. This model structure achieved accuracy scores of about 96.1% and 89.0% on the train set and the test set of IMDB respectively, and about 96.0% and 95.4% on the train set and test set of Yelp P. respectively. The structures of explainers, as well as the approximators of models including L2X, VIBI, AIL, and L2X withâ re slightly different from this to incorporate global information when selecting features and to select keywords. During our experiments, we find that while Pretrain prefers powerful approximators, Weight works more stable with simple approximators. This result is consistent with the results in Table 2. Besides, as estimating E( | ⊙ ) requires good calibrations, layers that act differently during training and testing, like Dropout and BatchNormalization layers, may not be welcomed by explanation models.  The structure of neural network models to be explained for image classification datasets (including MNIST and F-MNIST) is presented in Table 7. This model structure achieved accuracy scores of more than 99.8% on both the train set and test set of MNIST, and about 96.1% and 92.2% on the train set and test set of F-MNIST respectively. The structures of explainers, as well as the approximators of models including L2X, VIBI, AIL, and L2X with^, are slightly different from this to incorporate global information and to select pixels.

A.3 Calculation of the evaluation metrics
The same with Chen et al. [6] and Liang et al. [17], we used posthoc accuracy for quantitatively validating the effectiveness of the methods. After feature selection, unselected words of texts were filled with <PAD> tokens, and unselected pixels of images were filled with their average values. Then we used the model to be explained to predict the labels and compared whether the labels change or not. If the model makes consistent predictions before and after feature selection, the selected features may be informative for the model to make the decisions.

A.4 Brief introduction to the baseline methods
Among the baseline methods, Gradient [28] takes advantage of the property of neural networks and selects the input features which have the most significant absolute values of gradients. LIME [22] explains a model by quantifying the model's sensitivity to changes in the input. CXPlain [25] involves the real labels to compute the loss-function values by erasing each feature to zero and normalizes the loss-function values as the surrogate for ideal explanations for a neural network model to learn. Our methods follow the same paradigm as L2X [6], VIBI [3], and AIL [17], which use hard attention to select a fixed number of features to approximate the output of the original models to be explained. VIBI improves L2X to encourage the briefness of the learned explanation by adding a constraint for the feature scores to a global prior. AIL [17] is the state-of-the-art method that use adversarial training to encourage the gap between the predictability of selected/unselected features, additionally, AIL incorporate the outcome it aims to justify explicitly, as well as the gradients of the original model w.r.t. the samples to provide a warm start.

A.5 Comparison with adversarial solutions for improving interpretability
Liang et al. [17] and Yu et al. [38] also mentioned the phenomenon that attention could find a degenerated solution where attention could highlight feature components at different positions for different classes, and then the downstream parts of models may predict the label through this pattern, resulting in the lack of interpretability. And they used adversarial training to indirectly mitigate this combinatorial shortcut problem. However, they did not analyze why combinatorial shortcuts exist, and the adversarial scheme may change the behavioral tendency of models. For example, considering a sample with features { , ′ , , ′ , noisy features}, where ′ is collinear with , ′ is collinear with , and is relatively more predictive than while they are somehow complementary, the adversarial methods that encourage the gap between the predictability of selected/unselected features may tend to select and ′ to maximum the gap, and fail to select and which might be more interpretable.