summaries: The authors proposed a method for generating hierarchical importance attribution for any neural sequence models (LSTM, BERT, etc.) Towards this goal, the authors propose two desired properties: 1) non-additivity, which means the importance of a phrase should be a non-linear function over the importance of its component words; 2) context independence, which means that the attribution of any given phrase should be independent of its context. For example, in the sentence "the film is not interesting", the attribution of "interesting" should be positive while the attribution of "not interesting" should be negative. The paper addresses the problem of hierarchical explanations in deep models that handle compositional semantics of words and phrases. The paper first highlights desirable properties for importance attribution scores in hierarchical explanations, specifically, non-additivity and context independence, and shows how prior work on additive feature attribution and context decomposition doesn’t accurately capture these notions. After highlighting the said properties in context of related work, the authors propose an approach to calculate the context-independent importance of a phrase by computing the difference in scores with and without masking out the phrase marginalized over all possible surrounding word contexts (approximated by sampling surrounding context for a fixed radius under a language model). Furthermore, based on the above, the authors propose two more score attribution approaches -- based on integrating the above sampling step with (1) the contextual decomposition pipeline and (2) the input occlusion pipeline. Experimentally, the authors find that the attribution scores assigned by the proposed approach are more correlated with human annotations compared to prior approaches and additionally, the generated explanations turn out to be more trustworthy when humans evaluate their quality. This paper proposes a hierarchical decomposition method to encode the natural language as mathematical formulation such that the properties of the words and phrases can encoded properly and their importance be preserved independent of the context. This formulation is intuitive and more efficient compared to blindly learning contextual information in the model. The proposed method is a modification of contextual decomposition algorithm by adding a sampling step. They also adapt the proposed sampling method into input occlusion algorithm as another variant of their method. The proposed method is tested on LSTM and BERT models over sentiment datasets of Stanford Sentiment Treebank-2 and Yelp Sentiment Polarity and TACRED relation extraction dataset and showed more interpretable generated hierarchical explanations compared to baselines.
abstractText: The impressive performance of neural networks on natural language processing tasks attributes to their ability to model complicated word and phrase compositions. To explain how the model handles semantic compositions, we study hierarchical explanation of neural network predictions. We identify non-additivity and context independent importance attributions within hierarchies as two desirable properties for highlighting word and phrase compositions. We show some prior efforts on hierarchical explanations, e.g. contextual decomposition, do not satisfy the desired properties mathematically, leading to inconsistent explanation quality in different models. In this paper, we start by proposing a formal and general way to quantify the importance of each word and phrase. Following the formulation, we propose Sampling and Contextual Decomposition (SCD) algorithm and Sampling and Occlusion (SOC) algorithm. Human and metrics evaluation on both LSTM models and BERT Transformer models on multiple datasets show that our algorithms outperform prior hierarchical explanation algorithms. Our algorithms help to visualize semantic composition captured by models, extract classification rules and improve human trust of models1.
authors.name: Xisen Jin
authors.name: Zhongyu Wei
authors.name: Junyi Du
authors.name: Xiangyang Xue
authors.name: Xiang Ren
references.authors: Marco Ancona Enea Ceolini Cengiz Öztireli Markus Gross
references.title: Towards better understanding of gradient-based attribution methods for deep neural networks
references.venue: arXiv preprint arXiv:1711.06104,
references.authors: Daniel W Apley
references.title: Visualizing the effects of predictor variables in black box supervised learning models
references.venue: arXiv preprint arXiv:1612.08468,
references.authors: Dzmitry Bahdanau Kyunghyun Cho Yoshua Bengio
references.title: Neural machine translation by jointly learning to align and translate
references.venue: In 3rd International Conference on Learning Representations,
references.authors: Alexander Binder Grégoire Montavon Sebastian Lapuschkin Klaus-Robert Müller Wojciech Samek
references.title: Layer-wise relevance propagation for neural networks with local renormalization layers
references.venue: In International Conference on Artificial Neural Networks,
references.authors: Chun-Hao Chang Elliot Creager Anna Goldenberg David Duvenaud
references.title: Explaining image classifiers by counterfactual generation
references.venue: In International Conference on Learning Representations,
references.authors: Jianbo Chen Le Song Martin J. Wainwright Michael I. Jordan
references.title: Learning to explain: An information-theoretic perspective on model interpretation
references.authors: Jianbo Chen Le Song Martin J. Wainwright Michael I. Jordan
references.title: L-shapley and c-shapley: Efficient model interpretation for structured data
references.venue: In International Conference on Learning Representations,
references.authors: Jacob Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova. Bert
references.title: Pre-training of deep bidirectional transformers for language understanding
references.venue: arXiv preprint arXiv:1810.04805,
references.authors: Katsushige Fujimoto Ivan Kojadinovic Jean-Luc Marichal
references.title: Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction
references.venue: indices. Games and Economic Behavior,
references.authors: Riccardo Guidotti Anna Monreale Salvatore Ruggieri Franco Turini Fosca Giannotti Dino Pedreschi
references.title: A survey of methods for explaining black box models
references.venue: ACM computing surveys (CSUR),
references.authors: Yotam Hechtlinger
references.title: Interpretation of prediction models using the input gradient
references.venue: arXiv preprint arXiv:1611.07634,
references.authors: Sepp Hochreiter Jürgen Schmidhuber
references.title: Long short-term memory
references.venue: Neural computation,
references.authors: Giles Hooker
references.title: Discovering additive structure in black box functions
references.venue: In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Akos Kádár Grzegorz Chrupała Afra Alishahi
references.title: Representation of linguistic form and function in recurrent neural networks
references.venue: Computational Linguistics,
references.authors: Tao Lei Regina Barzilay Tommi S. Jaakkola
references.title: Rationalizing neural predictions
references.venue: In EMNLP,
references.authors: Jiwei Li Will Monroe Dan Jurafsky
references.title: Understanding neural networks through representation erasure
references.venue: arXiv preprint arXiv:1612.08220,
references.authors: Hui Liu Qingyu Yin William Yang Wang
references.title: Towards explainable NLP: A generative explanation framework for text classification
references.venue: In Proceedings of the 57th Conference of the Association for Computational Linguistics,
references.authors: Yinhan Liu Myle Ott Naman Goyal Jingfei Du Mandar Joshi Danqi Chen Omer Levy Mike Lewis Luke Zettlemoyer Veselin Stoyanov
references.title: Roberta: A robustly optimized bert pretraining approach
references.venue: arXiv preprint arXiv:1907.11692,
references.authors: Scott M Lundberg Su-In Lee
references.title: A unified approach to interpreting model predictions
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sina Mohseni Niloofar Zarei Eric D Ragan
references.title: A survey of evaluation methods and measures for interpretable machine learning
references.venue: arXiv preprint arXiv:1811.11839,
references.authors: W James Murdoch Peter J Liu Bin Yu
references.title: Beyond word importance: Contextual decomposition to extract interactions from lstms
references.venue: In ICLR,
references.authors: Jeffrey Pennington Richard Socher Christopher Manning
references.title: Glove: Global vectors for word representation
references.venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),
references.authors: Matthew E Peters Mark Neumann Mohit Iyyer Matt Gardner Christopher Clark Kenton Lee Luke Zettlemoyer
references.title: Deep contextualized word representations
references.venue: arXiv preprint arXiv:1802.05365,
references.authors: Nina Poerner Hinrich Schütze Benjamin Roth
references.title: Evaluating neural network explanation methods using hybrid documents and morphological agreement
references.venue: arXiv preprint arXiv:1801.06422,
references.authors: Marco Tulio Ribeiro Sameer Singh Carlos Guestrin
references.title: why should I trust you?”: Explaining the predictions of any classifier
references.venue: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data
references.authors: Lloyd S Shapley
references.title: A value for n-person games
references.venue: Contributions to the Theory of Games,
references.authors: Avanti Shrikumar Peyton Greenside Anshul Kundaje
references.title: Learning important features through propagating activation differences
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Karen Simonyan Andrea Vedaldi Andrew Zisserman
references.title: Deep inside convolutional networks: Visualising image classification models and saliency maps
references.venue: arXiv preprint arXiv:1312.6034,
references.authors: Chandan Singh W James Murdoch Bin Yu
references.title: Hierarchical interpretations for neural network predictions
references.venue: In ICLR,
references.authors: Richard Socher Alex Perelygin Jean Wu Jason Chuang Christopher D Manning Andrew Ng Christopher Potts
references.title: Recursive deep models for semantic compositionality over a sentiment treebank
references.venue: In Proceedings of the 2013 conference on empirical methods in natural language processing,
references.authors: Daria Sorokina Rich Caruana Mirek Riedewald Daniel Fink
references.title: Detecting statistical interactions with additive groves of trees
references.venue: In Proceedings of the 25th international conference on Machine learning,
references.authors: Mukund Sundararajan Ankur Taly Qiqi Yan
references.title: Axiomatic attribution for deep networks
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Ian Tenney Dipanjan Das Ellie Pavlick. Bert
references.title: rediscovers the classical nlp pipeline
references.venue: In Association for Computational Linguistics,
references.authors: Michael Tsang Dehua Cheng Yan Liu
references.title: Detecting statistical interactions from neural network weights
references.venue: arXiv preprint arXiv:1705.04977,
references.authors: Michael Tsang Youbang Sun Dongxu Ren Yan Liu
references.title: Can i trust you more
references.venue: model-agnostic hierarchical explanations. ArXiv,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in neural information processing systems,
references.authors: Alex Wang Kyunghyun Cho CIFAR Azrieli
references.title: Global Scholar. Bert has a mouth, and it must speak: Bert as a markov random field language model
references.venue: NAACL HLT 2019,
references.authors: Xiang Zhang Junbo Zhao Yann LeCun
references.title: Character-level convolutional networks for text classification
references.venue: In Advances in neural information processing systems,
references.authors: Yuhao Zhang Victor Zhong Danqi Chen Gabor Angeli Christopher D. Manning
references.title: Positionaware attention and supervised data improve slot filling
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017),
references.authors: Alexander Zien Nicole Krämer Sören Sonnenburg Gunnar Rätsch
references.title: The feature importance ranking measure
references.venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,
references.authors: Luisa M Zintgraf Taco S Cohen Tameem Adel Max Welling
references.title: Visualizing deep neural network decisions: Prediction difference analysis
references.venue: In ICLR,
sections.heading: 1 INTRODUCTION
sections.text: Recent advances in deep neural networks have led to impressive results on a range of natural language processing (NLP) tasks, by learning latent, compositional vector representations of text data (Peters et al., 2018; Devlin et al., 2018; Liu et al., 2019b). However, interpretability of the predictions given by these complex, “black box” models has always been a limiting factor for use cases that require explanations of the features involved in modeling (e.g., words and phrases) (Guidotti et al., 2018; Ribeiro et al., 2016). Prior efforts on enhancing model interpretability have focused on either constructing models with intrinsically interpretable structures (Bahdanau et al., 2015; Liu et al., 2019a), or developing post-hoc explanation algorithms which can explain model predictions without elucidating the mechanisms by which model works (Mohseni et al., 2018; Guidotti et al., 2018). Among these work, post-hoc explanation has come to the fore as they can operate over a variety of trained models while not affecting predictive performance of models. Towards post-hoc explanation, a major line of work, additive feature attribution methods (Lundberg & Lee, 2017; Ribeiro et al., 2016; Binder et al., 2016; Shrikumar et al., 2017), explain a model prediction by assigning importance scores to individual input variables. However, these methods are not ideal for explaining phrase-level importance, as phrase importance is often a non-linear combination of the importance of the words in the phrase. Contextual decomposition (CD) (Murdoch et al., 2018) and its hierarchical extension (Singh et al., 2019) go beyond the additive assumption and compute the contribution solely made by a word/phrase to the model prediction (i.e., individual contribution), by decomposing the output variables of the neural network at each layer. Using the individual contribu-
  1Project page: https://inklab.usc.edu/hiexpl/
  tion scores so derived, these algorithms generate hierarchical explanation on how the model captures compositional semantics (e.g., stress or negation) in making predictions (see Figure 1 for example).
  However, despite contextual decomposition methods have achieved good results in practice, what reveals extra importance that emerge from combining two phrases has not been well studied. As a result, prior lines of work on contextual decomposition have focused on exploring model-specific decompositions based on their performance on visualizations. We identify the extra importance from combining two phrases can be quantified by studying how the importance of the combined phrase differs from the sum of the importance of the two component phrases on its own. Similar strategies have been studied in game theory for quantifying the surplus from combining two groups of players (Fujimoto et al., 2006). Following the definition above, the key challenge is to formulate the importance of a phrase on it own, i.e., context independent importance of a phrase. However, we show contextual decomposition do not satisfy this context independence property mathematically.
  To this end, we propose a formal way to quantify the importance of each individual word/phrase, and develop effective algorithms for generating hierarchical explanations based on the new formulation. To mathematically formalize and efficiently approximate context independent importance, we formulate N -context independent importance of a phrase, defined as the difference of model output after masking out the phrase, marginalized over all possible N words surrounding the phrase in the sentence. We propose two explanation algorithms according to our formulation, namely the Sampling and Contextual Decomposition algorithm (SCD), which overcomes the weakness of contextual decomposition algorithms, and the Sampling and OCclusion algorithm (SOC), which is simple, model-agnostic, and performs competitively against prior lines of algorithms. We experiment with both LSTM and fine-tuned Transformer models to evaluate the proposed methods. Quantitative studies involving automatic metrics and human evaluation on sentiment analysis and relation extraction tasks show that our algorithms consistently outperform competitors in the quality of explanations. Our algorithms manage to provide hierarchical visualization of compositional semantics captured by models, extract classification rules from models, and help users to trust neural networks predictions.
  In summary, our work makes the following contributions: (1) we identify the key challenges in generating post-hoc hierarchical explanations and propose a mathematically sound way to quantify context independent importance of words and phrases for generating hierarchical explanations; (2) we extend previous post-hoc explanation algorithm based on the new formulation of N -context independent importance and develop two effective hierarchical explanation algorithms; and (3) experiments demonstrate that the proposed explanation algorithms consistently outperform the compared methods (with both LSTM and Transformer as base models) over several datasets and models.
sections.heading: 2 PRELIMINARIES
sections.heading: 2.1 POST-HOC EXPLANATIONS OF NEURAL SEQUENCE MODELS
sections.text: We consider a sequence of low-dimensional word embeddings x1:T := (x1,x2, ...,xT ), or denoted as x for brevity, as the input to a neural sequence model, such as standard RNNs, LSTM (Hochreiter
  & Schmidhuber, 1997) and Transformers (Vaswani et al., 2017). These neural models extract hidden representations h1:T from the input sequence x, and feed these hidden representations to a prediction layer to generate prediction scores in the label space (e.g., sentiment polarity of a sentence). For LSTM, we use the last hidden state hT to give unnormalized prediction scores s(x) ∈ Rdc over dc label classes as follows.
  s(x) =WlhT , (1)
  whereWl ∈ Rdc×dh is a trainable weight matrix. For Transformers, the representation corresponding to the [CLS] token at the final layer is fed to the prediction layer to generate scores s(x).
  Towards post-hoc explanation of s(x), a notable line of work, additive feature attribution methods (Ribeiro et al., 2016; Shrikumar et al., 2017; Sundararajan et al., 2017; Lundberg & Lee, 2017), measure word-level importance to the model prediction s(x) by attributing an importance score φ(xi,x) to each word in the input sequence xi ∈ x. However, the additive assumption hinders these methods from explaining the complex interactions between words and compositional semantics in a sentence (e.g., modeling negation, transition, and emphasis in sentiment classification), as shown in Figure 1.
sections.heading: 2.2 HIERARCHICAL EXPLANATIONS VIA CONTEXTUAL DECOMPOSITION
sections.text: To caputure non-linear compositional semantics, the line of work on contextual decomposition (CD) (Murdoch et al., 2018) designs non-additive measures of importance from individual words/phrases to the model predictions, and further extend to agglomerative contextual decomposition (ACD) algorithm (Singh et al., 2019) for generating hierarchical explanations.
  Given a phrase p = xi:j in the input sequence x, contextual decomposition (CD) attributes a score φ(p,x) as the contribution solely from p to the model’s prediction s(x). Note that φ(p,x) does not equal to the sum of the scores of each word in the phrase, i.e., φ(p,x) 6= ∑ xi∈p φ(xi,x). Starting from the input layer, CD iteratively decomposes each hidden state h of the model into the contribution solely made by p, denoted as β, and the contributions involving the words outside the phrase p, denoted as γ, with the relation h = β+γ holds. The algorithm also keeps the contribution from the bias term, denoted as ζ, temporally before element-wise multiplication.
  For a linear layer h =Wixt+ bi with input xt, when xt lies in the given phrase p, the contribution solely from xt to h is defined as β = Wixt when xt is part of the phrase (i.e., xt ∈ p), and the contribution involving other words in the sentences (denoted as x\p) is defined as γ = 0. The contribution of the bias term ζ is thus bi. When xt lies outside of the phrase, γ is quantified as Wixt and β is 0. In the cases when CD encounters element-wise multiplication operations h = ha hb (e.g., in LSTMs), it eliminates the multiplicative interaction terms which involve the information outside of the phrase p. Specifically, suppose that ha and hb have been decomposed as ha = βa + γa + ζa and hb = βb + γb + ζb, CD computes the β term for ha hb as β = βa βb + βa ζb + ζa βb. When dealing with non-linear activation h′ = σ(h), CD computes the contribution solely from the phrase p as the average activation differences caused β supposing γ is present or absent,
  β′ = 1 2 [σ(β + γ + ζ)− σ(γ + ζ)] + 1 2 [σ(β + ζ)− σ(ζ)]. (2)
  Following the strategies introduced above, CD decomposes all the intermediate outputs starting from the input layer, until reaching the final output of the model hT = β + γ. The logit score Wlβ is treated as the contribution of the given phrase p to the final prediction s(x).
  As a follow-up study, Singh et al. (2019) extends CD algorithm to other families of neural network architectures, and proposes agglomerative contextual decomposition algorithm (ACD). The decomposition of activation functions is modified as β′ = σ(β). For a linear layer h′ = Wh + b with its decomposition h = β + γ, the bias term b is decomposed proportionally and merged into the β′ term of h′, based on β′ =Wβ + |Wβ|/(|Wβ|+ |Wγ|) · b.
sections.heading: 3 METHODOLOGY
sections.text: In this section, we start by identifying desired properties of phrase-level importance score attribution for hierarchical explanations. We propose a measure of context-independent importance of a phrase and introduce two explanation algorithms instantiated from the proposed formulation.
sections.heading: 3.1 PROPERTIES OF IMPORTANCE ATTRIBUTION FOR HIERARCHICAL EXPLANATION
sections.text: Despite the empirical success of CD and ACD, no prior works analyze what common properties a score attribution mechanism should satisfy to generate hierarchical explanations that reveal compositional semantics formed between phrases. Here we identify two properties that an attribution method should satisfy to generate informative hierarchical explanations.
  Non-additivity. Importance of a phrase φ(p,x) should not be a sum over the importance scores of all the component words xi ∈ p, i.e., φ(p,x) 6= ∑ xi∈p φ(xi,x), in contrast to the family of additive feature attribution methods. The property is also suggested by Murdoch et al. (2018).
  Context Independence. For deep neural networks, when two phrases combine, their importance to predicting a class may greatly change. The surplus by combining two phrases can be quantified by the difference between the importance of the combined phrase and the sum of the importance of two phrases on its own. It follows the definition of marginal interactions (Fujimoto et al., 2006) in game theory. According to the definition, the importance of two component phrases should be at least evaluated independently to each other. Formally, if we are only interested in how combining two phrases p1 and p2 contribute to a specific prediction for an input x, we expect for input sentences x̃ where only p2 is replaced to another phrase, the importance attribution for p1 remains the same, i.e., φ(p1,x) = φ(p1, x̃). In our bottom-up hierarchical explanation setting, we are interested in how combining a phrase and any other contextual words or phrases in the input x contribute. Therefore, we expect φ(p,x) = φ(p, x̃) given the phrase p in two different contexts x and x̃.
  Limitations of CD and ACD. Unfortunately, while CD and ACD try to construct decomposition so that β terms represent the contributions solely from a given a phrase, the assigned importance scores by these algorithms do not satisfy the context independence property mathematically. For CD, we see the computation of β involves the γ term of a specific input sentence in Eq. 2 (see Figure 2(a) for visualization). Similarly, for ACD, the decomposition of the bias term involves the γ terms of a specific input sentence. As a result, the β terms computed by both algorithms depend on the context of the phrase p.
  Given the limitation of prior works, we start by formulating a importance measure of phrases that satisfies both non-additivity and context independence property.
sections.heading: 3.2 CONTEXT-INDEPENDENT IMPORTANCE
sections.text: Given a phrase p := xi:j appearing in a specific input x1:T , we first relax our setting and define the importance of a phrase independent of contexts of length N adjacent to it. The N-context independent importance is defined as the output difference after masking out the phrase p, marginalized over all the possible contexts of length N , denoted as x̂δ , around p in the input x. For an intuitive example, to evaluate the context independent importance up to one word of very in the sentence The film is very interesting in a sentiment analysis model, we sample some possible adjacent words before and after the word very, and average the prediction difference after some practice of masking the word very. Figure 2 illustrates an example for the sampling and masking steps. The N -context independent importance is formally written as,
  φ(p, x̂) = Exδ [s(x−δ; x̂δ)− s(x−δ\p; x̂δ)], (3)
  where x−δ denotes the resulting sequence after masking out a context of length N surrounding the phrase p from the input x. Here, x̂δ is a sequence of length N sampled from a distribution p(x̂δ|x−δ), which is conditioned on the phrase p as well as other words in the sentence x. Accordingly, we use s(x−δ; x̂δ) to denote the model prediction score after replacing the masked-out context x−δ with a sampled context x̂δ . We use x\p to denote the operation of masking out the phrase p from the input sentence x. The specific implementation of this masking out operation varies across different explanation algorithms.
  Following the notion of N -context independent importance, we define context-independent importance of a phrase p by increasing the size of the context N to sufficiently large (e.g., length of the sentence). The context independent importance can be equivalently written as follows.
  φg(p) = Ex[s(x)− s(x\p)|p ⊆ x]. (4)
  While it is possible to compute the expectations in Eqs. 3 and 4 by sampling from the training set, it is common that a phrase occurs sparsely in the corpus. Therefore, we approximate the N -context independent importance by sampling from a language model pretrained on the training corpus. The language model helps model a smoothed distribution of p(x̂δ|x−δ). In practice, all our explanation algorithms make use of N -context independent importance following Eq. 3, where the size of the neighborhood N is a parameter to be specified to approximate the context independent importance.
sections.heading: 3.3 SAMPLING AND CONTEXTUAL DECOMPOSITION ALGORITHM
sections.text: In CD, the desirable context independence property is compromised when computing decomposition of activation functions, as discussed in Section 3.1. Following the new formulation of contextindependent importance introduced in Section 3.2, we present a simple modification of the contextual decomposition algorithm, and develop a new sampling and contextual decomposition (SCD) algorithm for effective generation of hierarchical explanations.
  SCD is a layer-wise application of our formulation. The algorithm only modifies the way to decompose activation functions in CD. Specifically, given the output h = s(l)(x) at an intermediate layer l with the decomposition h = β + γ, we decompose the activation value σ(h) into β′ + γ′, with the following definition:
  β′ = Eγ∼p(γ|x−δ)[σ(β + γ)− σ(γ)] = Eh∼p(h|x−δ)[σ(h)− σ(h− β)], (5)
  i.e., β′ is defined as the expected difference between the activation values when the β term is present or absent. h is computed for different input sequences x with the contexts of the phrase p sampled from the distribution p(x̂δ|x−δ). Eq. 5 is a layer wise application of Eq. 4, where the masking operation is implemented with calculating σ(h − β). Figure 2(b) provides a visualization for the decomposition.
  Algorithmic Details. To perform sampling, we first pretrain a LSTM language model from two directions on the training data. During sampling, we mask the words that are not conditioned in p(x̂δ|x−δ). Some other sampling options include performing Gibbs sampling from a masked language model (Wang et al., 2019). The algorithm then obtain a set of samples S by sampled from the language model. For each sample in S, the algorithm records the input of the i-th non-linear activation function to obtain a sample set S(i)h . During the explanation, the β term of the i-th non-linear
  activation function is calculated as,
  β′ = 1
  |S(i)h | ∑ h∈S(i)h [σ(h)− σ(h− β)]. (6)
  Some neural models such as Transformers involve operations that normalize over different dimensions of a vectors, e.g. layer normalization operations. We observe improved performance by not decomposing the normalizer of these terms when the phrase p is shorter than a threshold, assuming that the impact of p to the normalizer can be ignored. Besides, for element-wise multiplication in LSTM models, we treat them in the same way as other non-linear operations and decompose them as Eq. 5, where the decomposition of h1 h2 is written as β′ = Eγ1,γ2 [(β1+γ1) (β2+γ2)−γ1 γ2]. We avoid decomposing softmax functions.
sections.heading: 3.4 SAMPLING AND OCCLUSION ALGORITHM
sections.text: We show it is possible to fit input occlusion (Li et al., 2016) algorithm into our formulation. Input occlusion algorithm calculate the importance of p specific to an input sentence x by observing the prediction difference caused by replacing the phrase p with padding tokens, noted as 0p,
  φ(p,x) = s(x)− s(x−p;0p) (7)
  It is obvious that the importance score obtained by the input occlusion algorithm is dependent on the all the context words of p in x. To eliminate the dependence, we sample the context around the phrase p. This leads to the Sampling and Occlusion (SOC) algorithm, where the importance of phrases is defined as the expected prediction difference after masking the phrase for each replacement of contexts.
  Algorithmic Details. Similar to SCD, SOC samples neighboring words x̂δ from a trained language model p(x̂δ|x−δ) and obtain a set of neighboring word replacement S . For each replacement x̂δ ∈ S , the algorithm computes the model prediction differences after replacing the phrase p with padding tokens. The importance φ(p,x) is then calculated as the average prediction differences. Formally, the algorithm calculates,
  φ(p,x) = 1 |S| ∑ x̂δ∈S [s(x−δ; x̂δ)− s(x−{δ,p}; x̂δ;0p)]. (8)
  Sampling and Occlusion is advantageous in that it is model-agnostic and easy to implement. The input occlusion algorithm inside Eq. 8 can also be replaced with other measure of phrase importance, such as Shapley values (Shapley, 1953), with the phrase p and other input words considered as players. We expect it is helpful for longer sequences when there are multiple evidences outside the context region saturating the prediction.
sections.heading: 4 EXPERIMENTS
sections.text: We evaluate explanation algorithms on both shallow LSTM models and deep fine-tuned BERT Transformer (Devlin et al., 2018) models. We use two sentiment analysis datasets, namely the Stanford Sentiment Treebank-2 (SST-2) dataset (Socher et al., 2013) and the Yelp Sentiment Polarity dataset (Zhang et al., 2015), as well as TACRED relation extraction dataset (Zhang et al., 2017) for experiments. The two tasks are modeled as binary and multi-class classification tasks respectively. For the SST-2 dataset, while it provides sentiment polarity scores for all the phrases on the nodes of the constituency parsing trees, we do not train our model on these phrases, and use these scores as the evaluation for the phrase level explanations. Our Transformer model is fine-tuned from pretrained BERT (Devlin et al., 2018) model. See Appendix A for other implementation details.
  Compared Methods. We compare our explanation algorithm with following baselines: Input occlusion (Li et al., 2016) and Integrated Gradient+SHAP (GradSHAP) (Lundberg & Lee, 2017); two algorithms applied for hierarchical explanations, namely Contextual Decomposition (CD) (Murdoch et al., 2018), and Agglomerative Contextual Decomposition (ACD) (Singh et al., 2019). We
  also compare with a naive however neglected baseline in prior literature, which directly feed the given phrase to the model and take the prediction score as the importance of the phrase, noted as Direct Feed. In BERT models, Direct Feed is implemented by turning off the attention mask of words except the [CLS] token and the phrase to be explained. For our algorithms, we list the performance of corpus statistic based approach (Statistic) for approximating context independent importance in Eq. 3, Sampling and Contextual Decomposition (SCD), and Sampling and Occlusion (SOC) algorithm. In section 4.4, we also consider padding instead of sampling the context words in SCD and SOC.
sections.heading: 4.1 HIERARCHICAL VISUALIZATION OF IMPORTANT WORDS AND PHRASES
sections.text: We verify the performance of our algorithms in identifying important words and phrases captured by models. We follow the quantitative evaluation protocol proposed in CD algorithm (Murdoch et al., 2018) for evaluating word-level explanations, which computes Pearson correlation between the coefficients learned by a linear bag-of-words model and the importance scores attributed by explanation methods, also noted as the word ρ. When the linear model is accurate, its coefficients could stand for general importance of words. For evaluating phrase level explanations, we notice the SST-2 dataset provides human annotated real-valued sentiment polarity for each phrase on constituency parsing trees. We generate explanations for each phrase on the parsing tree and evaluate the Pearson correlation between the ground truth scores and the importance scores assigned for phrases, also noted as the phrase ρ. We drawK = 20 samples forN = 10 words adjacent to the phrase to be explained at the sampling step in our SOC and SCD algorithms. The parameter setting is trade-off between the efficiency and performance. See Section 4.4 for detailed parameter analysis.
  Table 1 shows word ρ and phrase ρ achieved by our algorithms and competitors. Generally, explanation algorithms that follow our formulations achieve highest word ρ and phrase ρ for all the datasets and models. SOC and SCD perform robustly on the deep Transformer model, achieving higher word
sections.heading: He is also survived by S-PERSON parents and a sister , O-PERSON , of Washington , and
sections.heading: He is also survived by S-PERSON parents and a sister , O-PERSON , of Washington , and
sections.text: ρ and phrase ρ than input occlusion and contextual decomposition algorithms by a large margin. We see the simple Direct Feed method provide promising results on shallow LSTM networks, but fail in deeper Transformer models. The statistic based approximation of the context independent importance, which do not employ a trained sampler, yields competitive words ρ but low phrase ρ. Our analysis show that it is common that a long phrase does not exist in previously seen examples. In this case, phrase ρ achieved by statistic based approximation is pushed towards that of the input occlusion algorithm.
  Qualitative study also shows that our explanation visualize complicated compositional semantics captured by models, such as positive segments in the negative example, and adversative conjunctions connected with “but”. We present an example explanation provided by SOC algorithm in Figure 3 and Appendix.
sections.heading: 4.2 EXPLANATION AS CLASSIFICATION PATTERN EXTRACTION FROM MODELS
sections.text: We show our explanation algorithm is a nature fit for extracting phrase level classification rules from neural classifiers. With the agglomerative clustering algorithm in Singh et al. (2019), our explanation effectively identify phrase-level classification patterns without evaluating all possible phrases in the sentence even when a predefined hierarchy does not exist. Figure 4 show an example of automatically constructed hierarchy and extracted classification rules in an example in the TACRED dataset.
sections.heading: 4.3 ENHANCING HUMAN TRUST OF MODELS
sections.text: We follow the human evaluation protocol in Singh et al. (2019) and study whether our explanations help subjects to better trust model predictions. We ask subjects to rank the provided visualizations based on how they would like to trust the model. For the SST-2 dataset, we show subjects the predictions of the fine-tuned BERT model, and the explanations generated by SOC, SCD, ACD and GradSHAP algorithms for phrases. The phrase polarities are visualized in a hierarchy with the provided parsing tree of each sentence in the dataset. For the TACRED dataset, we show the explanations provided by SOC, SCD, CD and Direct Feed algorithms on the LSTM model. We binarilize the importance of a phrase by calculating the difference between its importance to the predicted class and the its top importance to other classes, and the hierarchies are constructed automatically with agglomerative clustering (Singh et al., 2019). Figure 5 shows average ranking score of explanations, where 4 for the best, and 1 for the worst. On the SST-2 dataset, SOC achieves significantly higher ranking score than ACD and GradSHAP, showing a p-value less than 0.05 and 0.001 respectively. On the TACRED dataset, SCD achieve the best ranking score, showing significantly better ranking score than CD and Direct Feed with a p-value less than 10−6 .
sections.heading: 4.4 PARAMETER ANALYSIS
sections.text: Both SOC and SCD algorithms require specifying the size of the context region N and the number of samples K. In Figure 6 (also Figure 7 in Appendix) we show the impact of these parameters. We also plot the performance curves when we pad the contexts instead of sampling. We see sampling the context achieves much better performance than padding the context given a fixed size of the context region N . We also see word ρ and phrase ρ increase as the number of samples K increases. The overall performance also increases as the size of the context region N increases at the early stage, and saturates when N grows large, which is consistent with our hypothesis that words or phrases usually do not interact with the words that are far away them in the input.
sections.heading: 5 RELATED WORKS
sections.text: Interpretability of neural networks has been studied with vairous techniques, including probing learned features with auxiliary tasks (Tenney et al., 2019), or designing models with inherent interpretability (Bahdanau et al., 2015; Lei et al., 2016). A major line of work, local explanation algorithms, explains predictions by assigning importance scores for input features. This line of work include input occlusion (Kádár et al., 2017), gradient based algorithms (Simonyan et al., 2013; Hechtlinger, 2016; Ancona et al., 2017), additive feature attribution methods (Ribeiro et al., 2016; Shrikumar et al., 2017; Sundararajan et al., 2017), among which Shapley value based approaches (Lundberg & Lee, 2017) have been studied intensively because of its good mathematical properties. In the context of input occlusion explanations, researchers also study how to efficiently marginalize over input features to be explained (Zintgraf et al., 2017; Chang et al., 2019), while our research show extra focus could be placed on marginalizing over contexts. Regarding explanations of models with structured inputs, Chen et al. (2019) propose L-Shapley and C-Shapley for efficient approximation of Shapley values, with a similar hypothesis with us that the importance of a word is usually only strongly dependent on its neighboring contexts. Chen et al. (2018) propose a feature selection based approach for explanation in an information theoretic perspective.
  On the other hand, global explanation algorithms (Guidotti et al., 2018) have also been studied for identifying generally important features, such as Feature Importance Ranking Measure (Zien et al., 2009), Accumulated Local Effects (Apley, 2016), while usually restricted in the domain of tabular data. We note that the context independence property in our proposed methods implies we study hierarchical explanation as a global explanation problem (Guidotti et al., 2018). Compared with local explanation algorithms, global explanation algorithms are less studied for explaining individual predictions (Poerner et al., 2018), because they reveal the average behavior of models. However, with a hierarchical organization, we show global explanations are also powerful at explaining individual predictions, achieving better human evaluation scores and could explain compositional semantics where local explanation algorithms such as additive feature attribution algorithms totally fail. Moreover, we note that the use of explanation algorithms is not exclusive; we may apply explanation algorithms of different categories to make a more holistic explanation of model predictions.
  Another closely related field is statistical feature interaction detection (Hooker, 2004; Sorokina et al., 2008; Tsang et al., 2017) from learned models, which usually focus on tabular data only. An exception is (Tsang et al., 2018), which also studies word interactions in neural sequence model predictions, but does not study interactions in a phrase level.
sections.heading: 6 CONCLUSION
sections.text: In this work, we identify two desirable properties for informative hierarchical explanations of predictions, namely the non-additivity and context-independence. We propose a formulation to quantify context independent importance of words and phrases that satisfies the properties above. We revisit the prior line of works on contextual decomposition algorithms, and propose Sampling and Contextual Decomposition (SCD) algorithm and Sampling and Occlusion algorithm (SOC). Experiments on multiple datasets and models show that our explanation algorithms generate informative hierarchical explanations, help to extract classification rules from models, and enhance human trust of models.
sections.heading: ACKNOWLEDGEMENTS
sections.text: This research is based upon work supported in part by NSF SMA 18-29268 and JP Morgan AI Research Award. We would like to thank all the collaborators in USC INK research lab for their constructive feedback on the work.
sections.heading: B PERFORMANCE ON ADVERSARIAL MODELS
sections.text: For computing context independent importance of a phrase, an intuitive and simple alternative approach, which is nevertheless neglected in prior literature, is to only feed the input to the model and treat the prediction score as the explanation. In Table 1, while the score of the Direct Feed is lower than that of the best performing algorithms, the score is rather competitive.
  The potential risk of this explanation is that it assumes model performs reasonably on incomplete sentence fragments that are significantly out of the data distribution. As a result, the explanation of short phrases can be misleading. To simulate the situation, we train a LSTM model on inversed labels on isolate words, in addition to the original training instances. The model could achieve the same accuracy as the original LSTM model. However, the word ρ and the phrase ρ of Direct Feed drop by a large margin, showing a word ρ of -0.38 and 0.09. SOC and SCD are still robust on the adverse LSTM model, both showing a word ρ and phrase ρ of more than 0.60 and 0.55.
  The masking operation could also cause performance drop because the masked sentence can be out of data distribution when explaining long phrases. For SOC, the risk can be resolved by implementing the masking operation of the phrase p by another round of sampling from a language model conditioned on its context x−p, but we do not find empirical evidence showing that it improves performance.
  C EXPLANATION HEATMAPS
title: TOWARDS HIERARCHICAL IMPORTANCE ATTRIBU-