The interpretability of neural networks has become crucial for their applications in real world with respect to the reliability and trustworthiness. Existing explanation generation methods usually provide important features by scoring their individual contributions to the model prediction and ignore the interactions between features, which eventually provide a bag-of-words representation as explanation. In natural language processing, this type of explanations is challenging for human user to understand the meaning of an explanation and draw the connection between explanation and model prediction, especially for long texts. In this work, we focus on detecting the interactions between features, and propose a novel approach to build a hierarchy of explanations based on feature interactions. The proposed method is evaluated with three neural classifiers, LSTM, CNN, and BERT, on two benchmark text classification datasets. The generated explanations are assessed by both automatic evaluation measurements and human evaluators. Experiments show the effectiveness of the proposed method in providing explanations that are both faithful to models, and understandable to humans. Deep neural networks have become a significant component in natural language processing (NLP), achieving state-of-the-art performance in various NLP tasks, such as text classification (Kim, 2014) , question answering (Rajpurkar et al., 2016) , and machine translation (Bahdanau et al., 2014) . However, the lack of understanding on their decision making leads them to be characterized as black-box models and increases the risk of applying them in real-world applications (Lipton, 2016) . Producing interpretable decisions has been a critical factor on whether people will trust and use the neural network models (Ribeiro et al., 2016) . Most of existing work on local explanation generation for NLP focuses on producing word-level explanations (Ribeiro et al., 2016; Lei et al., 2016; Plumb et al., 2018) , where a local explanation consists of a set of words extracted from the original text. Figure 1 presents an example sentence with its sentiment prediction and corresponding word-level explanation generated by LIME (Ribeiro et al., 2016) . Although the LIME explanation captures a negative sentiment word waste, it presents the explanation in a bag-of-words format. Without resorting to the original text, it is difficult for us to understand the contribution of word a and of, as both of them have no sentiment polarity. The situation will become even more serious when this type of explanations are extracted from longer texts. In this work, we present a novel method to construct hierarchical explanations of a model prediction by capturing the interaction between features. Ultimately, our method is able to produce a hierarchical structure as illustrated in Figure 1 . Produced by the proposed method, this example provides a comprehensive picture of how different granularity of features interacting with each other for model prediction. With the hierarchical structure, this example tells us how the words and phrases are combined and what are the contributions of words and phrases to the final prediction. For example, the contribution of the phrase of good is dominated by the word waste, which eventually leads to the right prediction. Figure 1: A NEGATIVE movie review a waste of good performance with a LIME explanation and a hierarchical explanation, where the color of each block represents the importance of the corresponding word/phrase with respect to the model prediction. To capture feature interactions, we adopt the interacted Shapley value (Lundberg et al., 2018) , an extension of Shapley value (Shapley, 1953) from cooperative game theory, to measure the interactions between features. Based on the interaction scores, we propose a top-down method, called INTERSHAPLEY, to segment a text recursively into phrases and then words eventually. The proposed method is evaluated on text classification tasks with three typical neural network models: long short term memory networks (Hochreiter & Schmidhuber, 1997, LSTM) and convolutional neural networks (Kim, 2014, CNN) , and a state-of-the-art model BERT (Devlin et al., 2018) on some benchmark datasets. The comparison of our method is against several competitive baselines from prior work on explanation generation, including Leave-one-out (Li et al., 2016) , Contextual Decomposition (CD) (Murdoch et al., 2018) and its hierarchical extension (ACD) (Singh et al., 2019) , L-and C-Shapley (Chen et al., 2018) , and LIME (Ribeiro et al., 2016) . Our contribution of this work is three-fold: (1) we propose an effective method to calculate feature importance and extend the Shapley value to measure feature interactions; (2) we design a top-down segmentation algorithm to build hierarchical interpretations based on feature interactions; (3) we compare the proposed method with several competitive baselines via both automatic and human evaluations, and show the INTERSHAPLEY method outperforms the existing methods on both wordand phrase-level explanations. Over the past years, many different research directions have been explored to build interpretable models or improve the interpretability of neural networks: (1) tracking the inner-workings of neural networks to understand their decision-making, such as contextual decomposition (CD) (Murdoch et al., 2018; Godin et al., 2018) ; (2) decoding interpretable knowledge (e.g., contextual information, latent representations) from networks to explain model predictions, such as gradient-based interpretation methods (Hechtlinger, 2016; Sundararajan et al., 2017) and attention-based methods (Ghaeini et al., 2018; Xie et al., 2017) ; (3) modifying neural network architectures to make their output more explainable, such as retreating to simpler models (Alvarez-Melis & Jaakkola, 2018) or incorporating strong regularizers (Yuan et al., 2019) ; and (4) developing explainable model-agnostic methods to learn the behaviors of neural network models and explain them, such as LIME (Ribeiro et al., 2016) and KernelSHAP (Lundberg & Lee, 2017) . The first three directions have limited capacity in realworld applications, as they require deep understanding of neural network architectures (Murdoch et al., 2018) or only work with specific models (Alvarez-Melis & Jaakkola, 2018) . On the other hand, model-agnostic methods (Ribeiro et al., 2016; Lundberg & Lee, 2017) generate explanations solely based on model predictions and can be used even without much expertise on machine learning and deep learning. In this work, we also focus on model-agnostic interpretations. Model-agnostic interpretations. Model-agnostic methods are applicable for any black-box models, generating explanations solely based on model predictions. Li et al. (2016) proposed a method, called Leave-one-out, to probe the black-box model by erasing a given word and observing the change in the probability on the predicted class. Another work, LIME (Ribeiro et al., 2016) , estimated individual word contributions locally by linear approximation based on perturbed examples. A line of most related works are Shapley-based methods, such as SHAP (Lundberg & Lee, 2017) , LShapley and C-Shapley (Chen et al., 2018) , where the variants of Shapley value (Shapley, 1953) are used to evaluate feature importance. They mainly focus on the challenge of reducing computational complexity of Shapley value by approximations (Kononenko et al., 2010; Datta et al., 2016) . Hierarchical interpretations. Previous work on interpreting neural networks mainly focuses on word-level interpretations, where the top-ranked words are selected based on their contributions to the prediction. There are a few works on building hierarchical interpretations. For example, agglomerative contextual decomposition (ACD) (Singh et al., 2019) uses the word-level CD scores as the joining metric determining which features are clustered together. Unlike our method, this work is model-dependent, and proposes a bottom-up clustering method to aggregate features with respect to their interactions. Besides, Lundberg et al. (2018) extented SHAP values to SHAP interaction values to calculate the interactions between features along a given tree structure. Similarly, Chen & Jordan (2019) suggests to utilize a linguistic tree structure to capture the contributions beyond individual features for text classification. The difference with our work is that both methods from (Lundberg et al., 2018; Chen & Jordan, 2019) require hierarchical structures given, while our method constructs the structures without resorting external resources. In this section, we first introduce a new definition of feature importance score in subsection 3.1, which forms the basis of the feature interaction detection method discussed in subsection 3.2. Then, subsection 3.3 presents a novel method of building a hierarchy of explanations by recursively optimizing the feature interaction score on a given text. In this paper, the feature importance score is usually understood as the contribution of a subset of features to each model prediction. It is essential in building a hierarchy of explanations where interaction scores built on top of it are extensively used. Considering a set of features x = (x 1 , . . . , x n ), and a subset of it written as x S , the feature importance score of x S is defined as follows, where g y (x) is the model output with respect to label y, Y is the possible label set, andŷ is the predicted label obtained by the model, i.e.,ŷ = argmax y∈Y g y (x); S is an integer set used to select features with subscript values matching those in S, i.e. x S = {x i |i ∈ S}. More concretely, in this work, x consists of a sequence of words (sentence or text), x i is the i-th word in x. The feature importance score defined in Equation 1 measures the difference between the probability on the predicted class and the probability of the second most probable class. It measures how far the prediction is to the prediction boundary, hence the confidence of classifying x S into the predicted labelŷ. Particularly in text classification, it can be interpreted as the contribution to a specific classŷ. For a given text x, x S is usually considered as a consecutive subsequence of words for interpretable explanations. To compute gŷ (x S ) in Equation 1, it is a common practice that words outside S are replaced with the special token pad (Chen et al., 2018; Shrikumar et al., 2017; Lundberg & Lee, 2017) in order to keep the same length between x and x S . The effectiveness of Equation 1 as a feature importance score is shown in subsection 4.1. By considering the prediction process as a coalition game (Lundberg et al., 2018) , where each player (feature) contributes fairly, the feature interactions can be measured consistently, meaning the computed scores are in line with human intuition and are robust when model changes (Lundberg et al., 2018) . Such scores often have the form of Shapley values. Motivated by the Shapley interaction score (Fujimoto et al., 2006; Lundberg et al., 2018) , and combined with our model-agnostic feature importance score in subsection 3.1, the feature interaction between the p-th and q-th features in z is computed as follows, where z is a set of features, and a feature in z can be a word or a set of words; N is the index set of features from z; |S| is the size of the set S. Additionally, γ p,q (z, S) is the interaction between feature z p and z q considering the contributions from other features in z S , which is defined as The total interaction between z p and z q is the sum of ψ ( p, q, z) and ψ ( q, p, z) (Lundberg et al., 2018) . Since ψ ( p, q, z) is symmetric with respect to p and q, the total interaction between the p-th element and q-th element in z is φ(p, q, z) = 2ψ ( p, q, z). To build a hierarchical interpretation, we adopt a top-down segmentation approach recursively splitting a feature set into two subsets with the minimum interaction score. In other words, a feature set is partitioned into two subsets with strong intra-interactions and weak inter-interactions in each step. The constructed hierarchy of explanations consists of multiple levels and each level is a set of feature subsets. Formally, considering the feature set at the -th level of the hierarchy, z = (z 1 , . . . , z n ), we can obtain various candidate setsẑ +1 for the next layer by splitting one element z i , ∀i ∈ {1, . . . , n } at a time, where n is the size of z . For example, oneẑ , and the size of it is n + 1. Of course, such partition is not unique and the number of potential partitions depends on the size of z . The best feature set at level + 1 satisfies Equation 4 finds the best partition betweenẑ whose interaction score is minimum. At level-zero, there is only one feature set with all input words included, z 0 = x. By splitting z 0 into two subsets z (Chen et al., 2018) , where only k neighbors are involved in computation, the computational complexity measured in number of model evaluations will be O(4 k n log n). So the method scales well with input text size n. Also note that opposite to the top-down method, we can also combine words with the strongest interaction into phrases, then phrases into larger phrases, resulting in the bottom-up method. In some cases, the bottom-up method cannot capture the phrase having opposite sentiment polarity until the last step. Detailed comparisons will be shown in Appendix A. The proposed method is evaluated on text classification tasks with three typical neural network models, a long short-term memories (LSTM) (Hochreiter & Schmidhuber, 1997) , a convolutional neural networks (CNN) (Kim, 2014) , and BERT (Devlin et al., 2018) , on SST (Socher et al., 2013) and IMDB (Maas et al., 2011) datasets. The detailed experimental setup is in Appendix B. We employ both automatic and human evaluations on word-level and phrase-level explanations, to show the ability of INTERSHAPLEY in interpreting neural network models. We adopt two evaluation metrics from prior work on evaluating word-level explanations: the area over the perturbation curve (AOPC) (Nguyen, 2018; Samek et al., 2016) and log-odds scores (Chen et al., 2018) . These two metrics measure local fidelity by deleting or masking words in the decreasing order of their importance scores and comparing the probability change on the predicted label. AOPC. Word-level explanations provide a sequence of words according to their importance scores. AOPC is calculated as the average change in prediction probability on the predicted class over all of the test data by deleting top k% words. Higher AOPCs are better, which means that the deleted words are important for model prediction. whereŷ is the predicted label, N is the number of samples, p(ŷ | ·) is the probability on the predicted class, andx is constructed by dropping the top k% word features from x i . Log-odds. The log-odds score is calculated by averaging the difference of negative logarithmic probabilities on the predicted class over all of the test data before and after masking the top r% features with zero paddings. Under this metric, lower log-odds scores are better. The notations are the same as in Equation 6 with the only difference thatx is constructed by replacing the top r% word features with the special token pad in x i . Figure 2 shows the results of AOPCs and log-odds scores of LSTM model on the SST dataset. IN-TERSHAPLEY achieves the best performance on both evaluation metrics. Together with the other results in Appendix C, this evaluation demonstrates the effectiveness of our method in extracting keywords via feature importance scores, which lays a solid foundation for feature interaction detection. The L-and C-Shapley perform worse on the IMDB dataset than on the SST dataset, because a small window size (2 as recommended) may cause relatively large error in approximating Shapley values for long sentences. The performance of LIME drops significantly on BERT comparing to the other two models, as Figure 9 and 10 show, which suggests that this locally linear approximation may not be capable of deep neural network models. We also observed an interesting phenomenon that the simplest baseline Leave-one-out can achieve relatively good performance, even better than Land C-Shapley, and CD. And we suspect that is because the criteria of Leave-one-out for picking keywords matches the evaluation metrics. This section presents some evaluation on phrase-level explanations extracted with the proposed methods. Take the hierarchy in Figure 1 as an example, the set of phrases extracted from this hierarchical structure include {waste of good performance, waste of good, of good}. On phrase level, we can use the same way as in Equation 1 to compute importance scores. The quantitative evaluation in section 4.2.1 shows our method successfully captures the strongest interactions using a contrastive comparison, and the qualitative analysis in section 4.2.2 illustrates how different levels of features interact with each other while contributing to final predictions. We evaluate the interaction effect of an important phrase by extracting the words within this phrase and then randomly insert them back to the original sentence. For example, in a sentence with n words x = (x 1 , . . . , x i , . . . , x j , . . . , x n ), if (x i , . . . , x j ) is the most important phrase, then for every word in (x i , . . . , x j ), we randomly pick a position in (x 1 , . . . , x i−1 , x j+1 , . . . , x n ) and insert that word back. Letx be the newly constructed word sequence in this way. The quantitative evaluation is to compare the difference between p(ŷ | x) and p(ŷ |x). Intuitively, by breaking the strong interaction within (x i , . . . , x j ), it will lead to a significant drop on the probability of predicted label y. To obtain a robust evaluation, for each sentence x i , we construct K different word sequences {x and compute the average as is the k th disturbed sample of x i , and K = 100 is the number of perturbations for each sentence. Note that when we pick the most important phrase, we consider the one whose length is no more than 5 as the explanation because a very long clause is uninterpretable. Then we calculate the average length of the most important phrases over all test data as the Average Explanation Length (Ave. Exp. length). Table 2 shows the results of cohesion-loss of INTERSHAPLEY and ACD with different models on the SST and IMDB datasets. For the IMDB dataset, we tested on a subset with 2000 randomly selected samples due to computation costs. INTERSHAPLEY outperforms ACD with higher cohesion-loss and smaller average length of generated explanations on both datasets with LSTM, which indicates that INTERSHAPLEY can capture more important and concise phrases. Comparing the results of INTERSHAPLEY for different models, the cohesion-loss of LSTM model improves on the IMDB dataset, while BERT performs the opposite. We reason that it is the length constraint on selected phrases that limits BERTs performance, since BERT often utilizes a large range of context for predictions. Figure 3 visualizes the hierarchical interpretations of INTERSHAPLEY and ACD for LSTM on a negative movie review from the SST dataset, where red and green colors represent the negative and positive sentiments respectively. In this case, LSTM makes a wrong prediction as positive. Figure  3 (a) shows that INTERSHAPLEY gives correct positive and negative sentiments for bravura and emptiness respectively, and captures the interaction between them that bravura exercise flips the polarity of in emptiness to positive, which explains why the model makes the wrong prediction. However, ACD incorrectly marks the two keywords with opposite polarities, and misses the feature interaction, as Figure 3 We employ 10 human annotators to do human evaluation on Amazon Mechanical Turk (AMT). The most important feature (with the highest importance score) is picked from the hierarchy as the explanation, with its length being limited to no more than five words for the ease of human understanding. We evaluate the explanation by asking human annotators to guess the output of a model based on the explanation and the input text (Nguyen, 2018) . For each example, human annotators choose a label from "Negative", "Positive", "N/A" based on their understanding of the explanation, where "N/A" means that the explanation may be some irrelevant words/phrase, and annotators cannot figure out the model's prediction. An example interface is shown in Appendix E. We measure the number of human annotations that are coherent with the actual model predictions, and define the coherence score as the ratio between the coherent annotations and the total number of examples. We randomly pick 60 movie reviews from IMDB dataset, half of which are used in one of the following experiments. First, we compare the explanations obtained from INTERSHAPLEY and ACD with LSTM model. For the same model, higher coherence score means that the explanations are more human understandable. Second, we apply INTERSHAPLEY to the three neural models, and compare the corresponding explanations. For the same interpretation method, a more interpretable mode usually can achieve higher coherence score. Table 3 shows the coherence scores of the two interpretation methods. INTERSHAPLEY outperforms ACD with much higher coherence score, which means that the important features captured by INTERSHAPLEY are highly consistent with human comprehension in explaining model predictions. Table 4 shows the accuracy and coherence scores of different models. INTERSHAPLEY achieves relatively high coherence scores on all of the three neural networks, which validates its ability in interpreting black-box models. Although BERT can achieve higher prediction accuracy than other two models, its coherence score is lower, which illustrates that the interpretability of more complex model is even worse. Coherence Score INTERSHAPLEY 0.88 ACD 0.53 A COMPARISON BETWEEN TOP-DOWN AND BOTTOM-UP APPROACHES Given the sentence a waste of good performance for example, Figure 5 shows the hierarchical interpretations for the LSTM model using the bottom-up and top-down approaches respectively. Figure 5(a) shows that the interaction between waste and good can not be captured until the last (top) layer, while the important phrase waste of good can be extracted in the intermediate layer by top-down algorithm. We can see that waste flips the polarity of of good to negative, causing the model predicting negative as well. Models. In this work, we use a recurrent neural network (RNN) with uni-directional one-layer LSTM Hochreiter & Schmidhuber (1997) , a CNN model with single convolutional layer Kim (2014) , and BERT Devlin et al. (2018) which has achieved remarkable performance on a variety of NLP tasks including text classification. The CNN model includes a single convolutional layer with filters of the window sizes ranging from 3 to 5. The LSTM is also single layer with 300 hidden states. Both models are initialized with 300-dimensional pretrained word embeddings Mikolov et al. (2013) . We use the pre-trained BERT model 1 with 12 transformer layers, 12 self-attention heads, and the hidden size of 768, and fine-tune it in different downstream tasks to achieve the best performance. Datasets. We use two benchmark datasets on text classification: the SST-2 corpus (Socher et al., 2013) and the IMDB corpus (Maas et al., 2011) . Table 5 shows the summary statistics of the datasets. SST-2 is the binary-class version of the Stanford sentiment treebank and IMDB is a balanced dataset with 25000 training examples and 25000 test examples. We split 90% of the training examples for training, and the rest as the development set. Competitive Baselines. We compare our method with some competitive baselines, including Leave-one-out (Li et al., 2016) , CD (Murdoch et al., 2018) , L-and C-Shapley (Chen et al., 2018) , and LIME (Ribeiro et al., 2016) for word-level explanation generation, and ACD (Singh et al., 2019) for phrase-level explanation generation. (
A novel approach to construct hierarchical explanations for text classification by detecting feature interactions. A novel method for providing explanations for predicitions made by text classifiers that outperforms baselines on word level importance scores, and a new metric, cohesion loss, to evaluate span-level importance. An interpretation method based on feature interactions and feature importance score as compared to independent feature contributions.