summaries: This paper proposes a model-agnostic explanations model, local explanation of response generation (LERG), for dialogue response generation task. Due to the sequence-to-sequence natrual, previous works, which normal produces a single label as output, are no longer suitable for this task. This paper regards the explanations as the mutual interaction of segments in input and output sentences. Specifically, it views the sequence prediction as uncertainty estimation of a human response and creates explanations by perturbing the input and calculating the certainty change over the human response. The experiment shows that the proposed approach extract both explicit and implicit relations between input and output segments. This paper studies the model-agnostic explanations of dialogue response generation and proposes a new called local explanation of response generation (LERG). LERG extracts the sorted importance scores of every input-output segment pair from a dialogue response generation model. It views the sequence prediction as uncertainty estimation of a human response and creates explanations by perturbing the input and calculating the certainty change over the human response. The authors show the proposed LERG adhere to three properties of  an ideal explanation of text generation: (1) unbiased approximation, (2) intra-response consistency and (3) causal cause identification. The experiments on a popular benchmark DailyDialog empirically verify the effectiveness of the proposed approach. This work proposes a method to locally explain the dialog response generation process. This method is motivated by the intuition that, such method should answer the question "which parts of the response are influenced the most by parts of the prompt". So the importance scores of every input-output segment pairs are calculated. They also proposed two metrics to evaluate explanations: "necessity" and "sufficiency". The former is defined as the perplexity change after removing top "salient" input features, and the latter is defined based on the intuition a complete explanation should recover model's prediction without the original input. The authors propose a method for “explaining” dialogue responses from sequence generation models; that is, determining what parts of the input influence or “explain” certain elements of the output. The method, LERG, is “learned” in one of two ways to assign a score for each input/output token pair indicating the measure of relevance, and ultimately to link the intent between the two. The authors propose that their method must satisfy three properties: unbiased approximation (LERG should explain benefits of picking response given the context); consistency (LERG should explain each generation step); and cause identification (LERG should sort input features by importance). The authors measure the effectiveness of the proposed method in both automatic evaluations and user studies. The automatic evaluations measure the **necessity** and **sufficiency** of the explained segments of the input text by capturing the model perplexity difference when stripping the segments and only including the segments, respectively, essentially measuring how accurate the method’s explanations are at capturing the relevant segments of the input context. Human evaluations display the segments to humans and ask if they can predict the gold response. Both evaluations show their explanation method significantly outperform both random baselines and other methods from the literature. The paper addresses the local explanation of sequence generation models, specifically under the dialogue response generation setting, and proposes local explanation of response generation (LERG) that computes the mutual interactions between input and output sequences under perturbations as the explanations. Automatic and human evaluations show that LERG is more effective than other baselines.  Contributions:  1. A new local explanation method for dialogue response generation 2. Such an explanation method could be generalized to other generation models as well 3.  A systematic framework to evaluate the dialogue model explanation quality involving both automatic evaluations and human studies.
abstractText: In comparison to the interpretation of classification models, the explanation of sequence generation models is also an important problem, however it has seen little attention. In this work, we study model-agnostic explanations of a representative text generation task – dialogue response generation. Dialog response generation is challenging with its open-ended sentences and multiple acceptable responses. To gain insights into the reasoning process of a generation model, we propose a new method, local explanation of response generation (LERG), that regards the explanations as the mutual interaction of segments in input and output sentences. LERG views the sequence prediction as uncertainty estimation of a human response and then creates explanations by perturbing the input and calculating the certainty change over the human response. We show that LERG adheres to desired properties of explanation for text generation, including unbiased approximation, consistency, and cause identification. Empirically, our results show that our method consistently improves other widely used methods on proposed automaticand humanevaluation metrics for this new task by 4.4-12.8%. Our analysis demonstrates that LERG can extract both explicit and implicit relations between input and output segments. 1
authors.name: Yi-Lin Tuan
authors.name: Connor Pryor
authors.name: Wenhu Chen
authors.name: Lise Getoor
authors.name: William Yang Wang
references.authors: David Alvarez-Melis Tommi Jaakkola
references.title: A causal framework for explaining the predictions of black-box sequence-to-sequence models
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: David Alvarez-Melis Tommi S Jaakkola
references.title: Towards robust interpretability with self-explaining neural networks
references.venue: In NeurIPS,
references.authors: Nabiha Asghar Pascal Poupart Xin Jiang Hang Li
references.title: Deep active learning for dialogue generation
references.venue: In Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (* SEM 2017),
references.authors: Pepa Atanasova Jakob Grue Simonsen Christina Lioma Isabelle Augenstein
references.title: A diagnostic study of explainability techniques for text classification
references.venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),
references.authors: Mohammad Taha Bahadori David Heckerman
references.title: Debiasing concept-based explanations with causal analysis
references.venue: In International Conference on Learning Representations,
references.authors: Mihalj Bakator Dragica Radosav
references.title: Deep learning and medical diagnosis: A review of literature
references.venue: Multimodal Technologies and Interaction,
references.authors: Michael Buhrmester Tracy Kwang Samuel D Gosling
references.title: Amazon’s mechanical turk: A new source of inexpensive, yet high-quality data? 2016
references.authors: Hanjie Chen Yangfeng Ji
references.title: Learning variational word masks to improve the interpretability of neural text classifiers
references.venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),
references.authors: Hanjie Chen Guangtao Zheng Yangfeng Ji
references.title: Generating hierarchical explanations on text classification via feature interaction detection
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,
references.authors: Hanjie Chen Song Feng Jatin Ganhotra Hui Wan Chulaka Gunasekara Sachindra Joshi Yangfeng Ji
references.title: Explaining neural network predictions on sentence pairs via learning word-group masks
references.authors: Angela Fan Mike Lewis Yann Dauphin
references.title: Hierarchical neural story generation
references.venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Christopher Frye Colin Rowat Ilya Feige
references.title: Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability
references.venue: Advances in Neural Information Processing Systems,
references.authors: Christopher Frye Damien de Mijolla Tom Begley Laurence Cowton Megan Stanley Ilya Feige
references.title: Shapley explainability on the data manifold
references.venue: In International Conference on Learning Representations,
references.authors: Leilani H Gilpin David Bau Ben Z Yuan Ayesha Bajwa Michael Specter Lalana Kagal
references.title: Explaining explanations: An overview of interpretability of machine learning
references.venue: IEEE 5th International Conference on data science and advanced analytics (DSAA),
references.authors: Prakhar Gupta Jeffrey P Bigham Yulia Tsvetkov Amy Pavel
references.title: Controlling dialogue generation with semantic exemplars
references.venue: In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,
references.authors: Tom Heskes Evi Sijben Ioan Gabriel Bucur Tom Claassen
references.title: Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models
references.venue: Advances in Neural Information Processing Systems,
references.authors: Jeya Vikranth Jeyakumar Joseph Noor Yu-Hsi Cheng Luis Garcia Mani Srivastava
references.title: How can i explain this to you? an empirical study of deep neural network explanation methods
references.venue: Advances in Neural Information Processing Systems,
references.authors: Rishabh Joshi Vidhisha Balachandran Shikhar Vashishth Alan Black Yulia Tsvetkov
references.title: Dialograph: Incorporating interpretable strategygraph networks into negotiation dialogues
references.venue: In International Conference on Learning Representations,
references.authors: Igor Kononenko
references.title: Machine learning for medical diagnosis: history, state of the art and perspective
references.venue: Artificial Intelligence in medicine,
references.authors: Solomon Kullback Richard A Leibler
references.title: On information and sufficiency
references.venue: The annals of mathematical statistics,
references.authors: I Elizabeth Kumar Suresh Venkatasubramanian Carlos Scheidegger Sorelle Friedler
references.title: Problems with shapley-value-based explanations as feature importance measures
references.venue: In International Conference on Machine Learning,
references.authors: Mike Lewis Yinhan Liu Naman Goyal Marjan Ghazvininejad Abdelrahman Mohamed Omer Levy Ves Stoyanov Luke Zettlemoyer
references.title: Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension
references.authors: Jiwei Li Will Monroe Alan Ritter Dan Jurafsky Michel Galley Jianfeng Gao
references.title: Deep reinforcement learning for dialogue generation
references.venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,
references.authors: Yanran Li Hui Su Xiaoyu Shen Wenjie Li Ziqiang Cao Shuzi Niu
references.title: DailyDialog: A manually labelled multi-turn dialogue dataset
references.venue: In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers),
references.authors: Zhaojiang Lin Andrea Madotto Yejin Bang Pascale Fung
references.title: The adapter-bot: All-in-one controllable conversational model
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
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: Seungwhan Moon Pararth Shah Anuj Kumar Rajen Subba
references.title: Opendialkg: Explainable conversational reasoning with attention-based walks over knowledge graphs
references.venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,
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 International Conference on Learning Representations,
references.authors: Shashi Narayan Shay B Cohen Mirella Lapata
references.title: Don’t give me the details, just the summary! topicaware convolutional neural networks for extreme summarization
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Daniel Povey Arnab Ghoshal Gilles Boulianne Lukas Burget Ondrej Glembek Nagendra Goel Mirko Hannemann Petr Motlicek Yanmin Qian Petr Schwarz
references.title: The kaldi speech recognition toolkit. In IEEE 2011 workshop on automatic speech recognition and understanding, number CONF
references.venue: IEEE Signal Processing Society,
references.authors: Danish Pruthi Bhuwan Dhingra Livio Baldini Soares Michael Collins Zachary C Lipton Graham Neubig William W Cohen
references.title: Evaluating explanations: How much do explanations from the teacher aid students
references.authors: Alec Radford Karthik Narasimhan Tim Salimans Ilya Sutskever
references.title: Improving language understanding by generative pre-training
references.authors: Marc’Aurelio Ranzato Sumit Chopra Michael Auli Wojciech Zaremba
references.title: Sequence level training with recurrent neural networks
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 mining,
references.authors: Cynthia Rudin
references.title: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead
references.venue: Nature Machine Intelligence,
references.authors: Abigail See Stephen Roller Douwe Kiela Jason Weston
references.title: What makes a good conversation? how controllable attributes affect human judgments
references.authors: Avanti Shrikumar Peyton Greenside Anshul Kundaje
references.title: Learning important features through propagating activation differences
references.venue: In International Conference on Machine Learning,
references.authors: Eric Michael Smith Diana Gonzalez-Rico Emily Dinan Y-Lan Boureau
references.title: Controlling style in generated dialogue
references.venue: arXiv preprint arXiv:2009.10855,
references.authors: Erik Strumbelj Igor Kononenko
references.title: An efficient explanation of individual classifications using game theory
references.venue: The Journal of Machine Learning Research,
references.authors: Erik Štrumbelj Igor Kononenko
references.title: Explaining prediction models and individual predictions with feature contributions
references.venue: Knowledge and information systems,
references.authors: Mukund Sundararajan Ankur Taly Qiqi Yan
references.title: Axiomatic attribution for deep networks
references.venue: In International Conference on Machine Learning,
references.authors: Yi-Lin Tuan Yun-Nung Chen Hung-yi Lee
references.title: Dykgchat: Benchmarking dialogue generation grounding on dynamic knowledge graphs
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP),
references.authors: Oriol Vinyals Quoc Le
references.title: A neural conversational model
references.venue: arXiv preprint arXiv:1506.05869,
references.authors: Sarah Wiegreffe Yuval Pinter
references.title: Attention is not not explanation
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: Thomas Wolf Victor Sanh Julien Chaumond Clement Delangue
references.title: Transfertransfo: A transfer learning approach for neural network based conversational agents
references.venue: NeurIPS 2018 CAI Workshop,
references.authors: Zeqiu Wu Michel Galley Chris Brockett Yizhe Zhang Xiang Gao Chris Quirk Rik Koncel-Kedziorski Jianfeng Gao Hannaneh Hajishirzi Mari Ostendorf
references.title: A controllable model of grounded response generation
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Can Xu Wei Wu Yu Wu
references.title: Towards explainable and controllable open domain dialogue generation with dialogue acts
references.venue: arXiv preprint arXiv:1807.07255,
references.authors: Can Xu Wei Wu Chongyang Tao Huang Hu Matt Schuerman Ying Wang
references.title: Neural response generation with meta-words
references.venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,
references.authors: Haiqin Yang Xiaoyuan Yao Yiqun Duan Jianping Shen Jie Zhong Kun Zhang
references.title: Progressive open-domain response generation with multiple controllable attributes
references.authors: H Peyton Young
references.title: Monotonic solutions of cooperative games
references.venue: International Journal of Game Theory,
references.authors: Ruqing Zhang Jiafeng Guo Yixing Fan Yanyan Lan Jun Xu Xueqi Cheng
references.title: Learning to control the specificity in neural response generation
references.venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Saizheng Zhang Emily Dinan Jack Urbanek Arthur Szlam Douwe Kiela Jason Weston
references.title: Personalizing dialogue agents: I have a dog, do you have pets too
references.venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Yizhe Zhang Siqi Sun Michel Galley Yen-Chun Chen Chris Brockett Xiang Gao Jianfeng Gao Jingjing Liu William B Dolan
references.title: Dialogpt: Large-scale generative pre-training for conversational response generation
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations,
sections.heading: 1 Introduction
sections.text: As we use machine learning models in daily tasks, such as medical diagnostics [6, 19], speech assistants [31] etc., being able to trust the predictions being made has become increasingly important. To understand the underlying reasoning process of complex machine learning models a sub-field of explainable artificial intelligence (XAI) [2, 17, 36] called local explanations, has seen promising results [35]. Local explanation methods [27, 39] often approximate an underlying black box model by fitting an interpretable proxy, such as a linear model or tree, around the neighborhood of individual predictions. These methods have the advantage of being model-agnostic and locally interpretable.
  Traditionally, off-the-shelf local explanation frameworks, such as the Shapley value in game theory [38] and the learning-based Local Interpretable Model-agnostic Explanation (LIME) [35] have been shown to work well on classification tasks with a small number of classes. In particular, there has been work on image classification [35], sentiment analysis [8], and evidence selection for question answering [32]. However, to the best of our knowledge, there has been less work studying explanations over models with sequential output and large class sizes at each time step. An attempt by [1] aims at explaining machine translation by aligning the sentences in source and target languages. Nonetheless, unlike translation, where it is possible to find almost all word alignments of the input and output sentences, many text generation tasks are not alignment-based. We further explore explanations over sequences that contain implicit and indirect relations between the input and output utterances.
  1Our code is available at https://github.com/Pascalson/LERG.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  In this paper, we study explanations over a set of representative conditional text generation models – dialogue response generation models [45, 55]. These models typically aim to produce an engaging and informative [3, 24] response to an input message. The open-ended sentences and multiple acceptable responses in dialogues pose two major challenges: (1) an exponentially large output space and (2) the implicit relations between the input and output texts. For example, the open-ended prompt “How are you today?” could lead to multiple responses depending on the users’ emotion, situation, social skills, expressions, etc. A simple answer such as “Good. Thank you for asking.” does not have an explicit alignment to words in the input prompt. Even though this alignment does not exist, it is clear that “good” is the key response to “how are you”. To find such crucial corresponding parts in a dialogue, we propose to extract explanations that can answer the question: “Which parts of the response are influenced the most by parts of the prompt?”
  To obtain such explanations, we introduce LERG, a novel yet simple method that extracts the sorted importance scores of every input-output segment pair from a dialogue response generation model. We view this sequence prediction as the uncertainty estimation of one human response and find a linear proxy that simulates the certainty caused from one input segment to an output segment. We further derive two optimization variations of LERG. One is learning-based [35] and another is the derived optimal similar to Shapley value [38]. To theoretically verify LERG, we propose that an ideal explanation of text generation should adhere to three properties: unbiased approximation, intra-response consistency, and causal cause identification. To the best of our knowledge, our work is the first to explore explanation over dialog response generation while maintaining all three properties.
  To verify if the explanations are both faithful (the explanation is fully dependent on the model being explained) [2] and interpretable (the explanation is understandable by humans) [14], we conduct comprehensive automatic evaluations and user study. We evaluate the necessity and sufficiency of the extracted explanation to the generation model by evaluating the perplexity change of removing salient input segments (necessity) and evaluating the perplexity of only salient segments remaining (sufficiency). In our user study, we present annotators with only the most salient parts in an input and ask them to select the most appropriate response from a set of candidates. Empirically, our proposed method consistently outperforms baselines on both automatic metrics and human evaluation.
  Our key contributions are:
  • We propose a novel local explanation method for dialogue response generation (LERG).
  • We propose a unified formulation that generalizes local explanation methods towards sequence generation and show that our method adheres to the desired properties for explaining conditional text generation.
  • We build a systematic framework to evaluate explanations of response generation including automatic metrics and user study.
sections.heading: 2 Local Explanation
sections.text: Local explanation methods aim to explain predictions of an arbitrary model by interpreting the neighborhood of individual predictions [35]. It can be viewed as training a proxy that adds the contributions of input features to a model’s predictions [27]. More formally, given an example with input features x = {xi}Mi=1, the corresponding prediction y with probability f(x) = Pθ(Y = y|x) (the classifier is parameterized by θ), we denote the contribution from each input feature xi as φi ∈ R and denote the concatenation of all contributions as φ = [φ1, ...,φM ]T ∈ RM . Two popular local explanation methods are the learning-based Local Interpretable Model-agnostic Explanations (LIME) [35] and the game theory-based Shapley value [38].
  LIME interprets a complex classifier f based on locally approximating a linear classifier around a given prediction f(x). The optimization of the explanation model that LIME uses adheres to:
  ξ(x) = argmin ϕ [L(f,ϕ,πx) + Ω(ϕ)] , (1)
  where we sample a perturbed input x̃ from πx(x̃) = exp(−D(x, x̃)2/σ2) taking D(x, x̃) as a distance function and σ as the width. Ω is the model complexity of the proxy ϕ. The objective of ξ(x) is to find the simplest ϕ that can approximate the behavior of f around x. When using a linear classifier
  dialog input text outputG
  intent
  (a) Controllable dialogue models
  input text positive
  negative
  (b) Explanation of classifier
  dialog input text outputG
  intent
  (c) Our concept
  Figure 1: The motivation of local explanation for dialogue response generation. (c) = (a)+(b).
  φ as the ϕ to minimize Ω(ϕ) [35], we can formulate the objective function as:
  φ = argmin φ
  Ex̃∼πx(Pθ(Y = y|x̃)−φT z)2 , (2)
  where z ∈ {0, 1}M is a simplified feature vector of x̃ by a mapping function h such that z = h(x, x̃) = {�(xi ∈ x̃)}Mi=1. The optimization means to minimize the classification error in the neighborhood of x sampled from πx. Therefore, using LIME, we can find an interpretable linear model that approximates any complex classifier’s behavior around an example x.
  Shapley value takes the input features x = {xi}Mi=1 as M independent players who cooperate to achieve a benefit in a game [38]. The Shapley value computes how much each player xi contributes to the total received benefit:
  ϕi(x) = �
  x̃⊆x\{xi}
  |x̃|!(|x|− |x̃|− 1)! |x|! [Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)] . (3)
  To reduce the computational cost, instead of computing all combinations, we can find surrogates φi proportional to ϕi and rewrite the above equation as an expectation over x sampled from P (x̃):
  φi = |x|
  |x|− 1ϕi = Ex̃∼P (x̃)[Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)], ∀i , (4)
  where P (x̃) = 1 (|x|−1)(|x|−1|x̃| ) is the perturb function.2 We can also transform the above formulation into argmin:
  φi = argmin φi
  Ex̃∼P (x̃)([Pθ(Y = y|x̃ ∪ {xi})− Pθ(Y = y|x̃)]− φi)2 . (5)
sections.heading: 3 Local Explanation for Dialogue Response Generation
sections.text: We aim to explain a model’s response prediction to a dialogue history one at a time and call it the local explanation of dialogue response generation. We focus on the local explanation for a more fine-grained understanding of the model’s behavior.
  3.1 Task Definition
  As depicted in Figure 1, we draw inspiration from the notions of controllable dialogue generation models (Figure 1a) and local explanation in sentiment analysis (Figure 1b). The first one uses a concept in predefined classes as the relation between input text and the response; the latter finds the features that correspond to positive or negative sentiment. We propose to find parts within the input and output texts that are related by an underlying intent (Figure 1c).
  We first define the notations for dialogue response generation, which aims to predict a response y = y1y2...yN given an input message x = x1x2...xM . xi is the i-th token in sentence x with length M and yj is the j-th token in sentence y with length N . To solve this task, a typical sequence-to-sequence model f parameterized by θ produces a sequence of probability masses <Pθ(y1|x), Pθ(y2|x, y1), ..., Pθ(yN |x, y<N )> [45]. The probability of y given x can then be computed as the product of the sequence Pθ(y|x) = Pθ(y1|x)Pθ(y2|x, y1)...Pθ(yN |x, y<N ).
  2� x̃⊆x\{xi} P (x̃) = 1 (|x|−1) � x̃⊆x\{xi} 1/ �|x|−1 |x̃| � = 1 (|x|−1) � |x̃| �|x|−1 |x̃| � / �|x|−1 |x̃| � = (|x|−1)
  (|x|−1) = 1. This affirms that the P (x̃) is a valid probability mass function.
  To explain the prediction, we then define a new explanation model Φ ∈ RM×N where each column Φj ∈ RM linearly approximates single sequential prediction at the j-th time step in text generation. To learn the optimal Φ, we sample perturbed inputs x̃ from a distribution centered on the original inputs x through a probability density function x̃ = π(x). Finally, we optimize Φ by ensuring u(ΦTj z) ≈ g(x̃) whenever z is a simplified embedding of x̃ by a mapping function z = h(x, x̃), where we define g as the gain function of the target generative model f , u as a transform function of Φ and z and L as the loss function. Note that z can be a vector or a matrix and g(·), u(·) can return a scalar or a vector depending on the used method. Therefore, we unify the local explanations (LIME and Shapley value) under dialogue response generation as:
  Definition 1: A Unified Formulation of Local Explanation for Dialogue Response Generation
  Φj = argmin Φj
  L(g(yj |x̃, y<j), u(ΦTj h(x̃))), for j = 1, 2, ..., N . (6)
  The proofs of unification into Equation 6 can be found in Appendix A. However, direct adaptation of LIME and Shapley value to dialogue response generation fails to consider the complexity of text generation and the diversity of generated examples. We develop disciplines to alleviate these problems.
sections.heading: 3.2 Proposed Method
sections.text: Our proposed method is designed to (1) address the exponential output space and diverse responses built within the dialogue response generation task and (2) compare the importance of segments within both input and output text.
  First, considering the exponential output space and diverse responses, recent work often generates responses using sampling, such as the dominant beam search with top-k sampling [11]. The generated response is therefore only a sample from the estimated probability mass distribution over the output space. Further, the samples drawn from the distribution will inherently have built-in errors that accumulate along generation steps [34]. To avoid these errors we instead explain the estimated probability of the ground truth human responses. In this way, we are considering that the dialogue response generation model is estimating the certainty to predict the human response by Pθ(y|x). Meanwhile, given the nature of the collected dialogue dataset, we observe only one response per sentence, and thus the mapping is deterministic. We denote the data distribution by P and the probability of observing a response y given input x in the dataset by P (y|x). Since the mapping of x and y is deterministic in the dataset, we assume P (y|x) = 1. Second, if we directly apply prior explanation methods of classifiers on sequential generative models, it turns into a One-vs-Rest classification situation for every generation step. This can cause an unfair comparison among generation steps. For example, the impact from a perturbed input on yj could end up being the largest just because the absolute certainty Pθ(yj |x, y<j) was large. However, the impact from a perturbed input on each part in the output should be how much the certainty has changed after perturbation and how much the change is compared to other parts.
  Therefore we propose to find explanation in an input-response pair (x, y) by comparing the interactions between segments in (x, y). To identify the most salient interaction pair (xi, yj) (the i-th segment in x and the j-th segment in y), we anticipate that a perturbation x̃ impacts the j-th part most in y if it causes
  D(Pθ(yj |x̃, y<j)||Pθ(yj |x, y<j)) > D(Pθ(yj� |x̃, y<j�)||Pθ(yj� |x, y<j�)), ∀j� �= j , (7)
  where D represents a distance function measuring the difference between two probability masses. After finding the different part xi in x and x̃, we then define an existing salient interaction in (x, y) is (xi, yj).
  In this work, we replace the distance function D in Equation 7 with Kullback–Leibler divergence (DKL) [20]. However, since we reduce the complexity by considering Pθ(y|x) as the certainty estimation of y, we are limited to obtaining only one point in the distribution. We transfer the equation by modeling the estimated joint probability by θ of x and y. We reconsider the joint distributions as Pθ(x̃, y≤j) such that � x̃,y Pθ(x̃, y≤j) = 1 and q(x̃, y) = Pθ,πinv (x̃, y≤j) = Pθ(x, y) such that�
  x̃,y q(x̃, y) = � x̃,y Pθ(x, y≤j) = � x̃,y Pθ,πinv (x̃, y≤j) = 1 with πinv being the inverse function
  of π. Therefore, D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) = DKL(Pθ(x̃, y≤j)||q(x̃, y≤j)) = �
  yj
  �
  x̃
  Pθ(x̃, y≤j) log Pθ(x̃, y≤j) Pθ(x, y≤j) .
  (8)
  Moreover, since we are estimating the certainty of a response y drawn from data distribution, we know that the random variables x̃ is independently drawn from the perturbation model π. Their independent conditional probabilities are P (y|x) = 1 and π(x̃|x). We approximate the multiplier Pθ(x̃, y≤j) ≈ P (x̃, y≤j |x) = P (x̃|x)P (y|x) = π(x̃|x). The divergence can be simplified to
  D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) ≈ �
  yj
  �
  x̃
  π(x̃|x) log Pθ(x̃, y≤j) Pθ(x, y≤j) = Ex̃∼π(·|x) log Pθ(x̃, y≤j) Pθ(x, y≤j) . (9)
  To meet the inequality for all j and j� �= j, we estimate each value ΦTj z in the explanation model Φ being proportional to the divergence term, where z = h(x, x̃) = {�(xi ∈ x̃)}Mi=1. It turns out to be re-estimating the distinct of the chosen segment yj by normalizing over its original predicted probability.
  ΦTj z ∝ Ex̃⊆x\{xi}D(Pθ(x̃, y≤j)||Pθ(x, y≤j)) ≈ Ex̃,x̃⊆x\{xi} log Pθ(x̃, y≤j) Pθ(x, y≤j) . (10)
  We propose two variations to optimize Φ following the unified formulation defined in Equation 6.
  First, since logarithm is strictly increasing, so to get the same order of Φij , we can drop off the logarithmic term in Equation 10. After reducing the non-linear factor, we use mean square error as the loss function. With the gain function g = Pθ(x̃,y≤j)Pθ(x,y≤j) , the optimization equation becomes
  Φj = argmin Φj EP (x̃)( Pθ(x̃, y≤j) Pθ(x, y≤j) −ΦTj z)2, ∀j . (11)
  We call this variation as LERG_L in Algorithm 1, since this optimization is similar to LIME but differs by the gain function being a ratio.
  To derive the second variation, we suppose an optimized Φ exists and is denoted by Φ∗, we can write that for every x̃ and its correspondent z = h(x, x̃),
  Φ∗jz = log Pθ(x̃, y≤j) Pθ(x, y≤j) . (12)
  We can then find the formal representation of Φ∗ij by
  Φ∗ij = Φ ∗ j1−Φ∗j1i=0
  = Φ∗j (z+ ei)−Φ∗jz, ∀x̃ ∈ x\{xi} and z = h(x, x̃) = Ex̃∈x\{xi}[Φ ∗ j (z+ ei)−Φ∗jz] = Ex̃∈x\{xi}[logPθ(yj |x̃ ∪ {xi}, y<j)− logPθ(yj |x̃, y<j)]
  (13)
  We call this variation as LERG_S in Algorithm 1, since this optimization is similar to Shapley value but differs by the gain function being the difference of logarithm. To further reduce computations, we use Monte Carlo sampling with m examples as a sampling version of Shapley value [41].
sections.heading: 3.3 Properties
sections.text: We propose that an explanation of dialogue response generation should adhere to three properties to prove itself faithful to the generative model and understandable to humans.
  Property 1: unbiased approximation To ensure the explanation model Φ explains the benefits of picking the sentence y, the summation of all elements in Φ should approximate the difference between the certainty of y given x and without x (the language modeling of y).
  �
  j
  �
  i
  Φij ≈ logP (y|x)− logP (y) . (14)
  Algorithm 1: LOCAL EXPLANATION OF RESPONSE GENERATION Input: input message x = x1x2...xM , ground-truth response y = y1y2...yN Input: a response generation model θ to be explained Input: a local explanation model parameterized by Φ // 1st variation – LERG_L for each iteration do
  sample a batch of x̃ perturbed from π(x) map x̃ to z = {0, 1}M1 compute gold probability Pθ(yj |x, y<j) compute perturbed probability Pθ(yj |x̃, y<j) optimize Φ to minimize loss function
  L = �
  j � x̃( Pθ(yj |x̃,y<j) Pθ(yj |x,y<j) −Φ T j z) 2
  // 2nd variation - LERG_S for each i do
  sample a batch of x̃ perturbed from π(x\{xi}) Φij = 1 m � x̃ logPθ(yj |x̃ ∪ {xi}, y<j)− logPθ(yj |x̃, y<j), for ∀j
  return Φij , for ∀i, j
  Property 2: consistency To ensure the explanation model Φ consistently explains different generation steps j, given a distance function if
  D(Pθ(yj |x̃, y<j), Pθ(yj |x̃∪{xi}, y<j)) > D(Pθ(yj� |x̃, y<j�), Pθ(yj� |x̃∪{xi}, y<j�)), ∀j�, ∀x̃ ∈ x\{xi} , (15) then Φij > Φij� .
  Property 3: cause identification To ensure that the explanation model sorts different input features by their importance to the results, if
  g(yj |x̃ ∪ {xi}) > g(yj |x̃ ∪ {x�i}), ∀x̃ ∈ x\{xi, x�i} , (16) then Φij > Φi�j We prove that our proposed method adheres to all three Properties in Appendix B. Meanwhile Shapley value follows Properties 2 and 3, while LIME follows Property 3 when an optimized solution exists. These properties also demonstrate that our method approximates the text generation process while sorting out the important segments in both the input and output texts. This could be the reason to serve as explanations to any sequential generative model.
sections.heading: 4 Experiments
sections.text: Explanation is notoriously hard to evaluate even for digits and sentiment classification which are generally more intuitive than explaining response generation. For digit classification (MNIST), explanations often mark the key curves in figures that can identify digit numbers. For sentiment analysis, explanations often mark the positive and negative words in text. Unlike them, we focus on identifying the key parts in both input messages and their responses. Our move requires an explanation include the interactions of the input and output features.
  To evaluate the defined explanation, we quantify the necessity and sufficiency of explanations towards a model’s uncertainty of a response. We evaluate these aspects by answering the following questions.
  • necessity: How is the model influenced after removing explanations?
  • sufficiency: How does the model perform when only the explanations are given?
  Furthermore, we conduct a user study to judge human understandings of the explanations to gauge how trustworthy the dialog agents are.
sections.heading: 4.1 Dataset, Models, Methods
sections.text: We evaluate our method over chit-chat dialogues for their more complex and realistic conversations. We specifically select and study a popular conversational dataset called DailyDialog [25] because its dialogues are based on daily topics and have less uninformative responses.Due to the large variation of topics, open-ended nature of conversations and informative responses within this dataset, explaining dialogue response generation models trained on DailyDialog is challenging but accessible.3
  We fine-tune a GPT-based language model [33, 47] and a DialoGPT [55] on DailyDialog by minimizing the following loss function:
  L = − �
  m
  �
  j
  logPθ(yj |x, y<j) , (17)
  where θ is the model’s parameter. We train until the loss converges on both models and achieve fairly low test perplexities compared to [25]: 12.35 and 11.83 respectively. The low perplexities demonstrate that the models are more likely to be rationale and therefore, evaluating explanations over these models will be more meaningful and interpretable.
  We compare our explanations LERG_L and LERG_S with attention [46], gradient [43], LIME [35] and Shapley value [42]. We use sample mean for Shapley value to avoid massive computations (Shapley for short), and drop the weights in Shapley value (Shapley-w for short) due to the intuition that not all permutations should exist in natural language [12, 21]. Our comparison is fair since all methods requiring permutation samples utilize the same amount of samples.4
sections.heading: 4.2 Necessity: How is the model influenced after removing explanations?
sections.text: Assessing the correctness of estimated important feature relevance requires labeled features for each model and example pair, which is rarely accessible. Inspired by [2, 4] who removes the estimated salient features and observe how the performance changes, we introduce the notion necessity that extends their idea. We quantify the necessity of the estimated salient input features to the uncertainty estimation of response generation by perplexity change of removal (PPLCR), defined as:
  PPLCR := exp 1 m [−
  � j logPθ(yj |xR,y<j)+ � j logPθ(yj |x,y<j)] , (18)
  where xR is the remaining sequence after removing top-k% salient input features.
  3We include our experiments on personalized dialogues and abstractive summarization in Appendix E 4More experiment details are in Appendix C
  As shown in Figure 2a and Figure 3a5, removing larger number of input features consistently causes the monotonically increasing PPLCR. Therefore, to reduce the factor that the PPLCR is caused by, the removal ratio, we compare all methods with an additional baseline that randomly removes features. LERG_S and LERG_L both outperform their counterparts Shapley-w and LIME by 12.8% and 2.2% respectively. We further observe that Shapley-w outperforms the LERG_L. We hypothesize that this is because LERG_L and LIME do not reach an optimal state.
  4.3 Sufficiency: How does the model perform when only the explanations are given?
  Even though necessity can test whether the selected features are crucial to the model’s prediction, it lacks to validate how possible the explanation itself can determine a response. A complete explanation is able to recover model’s prediction without the original input. We name this notion as sufficiency testing and formalize the idea as:
  PPLA := exp − 1m � j logPθ(yj |xA,y<j) , (19)
  where xA is the sequential concatenation of the top-k% salient input features.
  As shown in Figure 2b and Figure 3b, removing larger number of input features gets the PPLA closer to the perplexity of using all input features 12.35 and 11.83. We again adopt a random baseline to compare. LERG_S and LERG_L again outperform their counterparts Shapley-w and LIME by 5.1% and 3.4% respectively. Furthermore, we found that LERG_S is able to go lower than the original 12.35 and 11.83 perplexities. This result indicates that LERG_S is able to identify the most relevant features while avoiding features that cause more uncertainty during prediction.
  4.4 User Study
  To ensure the explanation is easy-to-understand by non machine learning experts and gives users insights into the model, we resort to user study to answer the question: “If an explanation can be understood by users to respond?”
  We ask human judges to compare explanation methods. Instead of asking judges to annotate their explanation for each dialogue, to increase their agreements we present only the explanations (Top 20% features) and ask them to choose from four response candidates, where one is the ground-truth, two are randomly sampled from other dialogues, and the last one is randomly sampled from other turns in the same dialogue. Therefore the questionnaire requires human to interpret the explanations but not guess a response that has word overlap with the explanation. The higher accuracy indicates the higher quality of explanations. To conduct more valid human evaluation, we randomly sample 200 conversations with sufficiently
  long input prompt (length≥ 10). This way it filters out possibly non-explainable dialogues that can cause ambiguities to annotators and make human evaluation less reliable.
  We employ three workers on Amazon Mechanical Turk [7] 6 for each method of each conversation, resulting in total 600 annotations. Besides the multiple choice questions, we also ask judges to claim their confidences of their choices. The details can be seen in Appendix D. The results are listed in Table 1. We observe that LERG_L performs slightly better than LIME in accuracy while maintaining similar annotator’s confidence. LERG_S significantly outperforms Shapley-w in both accuracy and annotators’ confidence. Moreover, these results indicates that when presenting users with only 20% of the tokens they are able to achieve 56% accuracy while a random selection is around 25%.
  (a) Implication: find the "hot potato" might indicate "gasoline".
  (b) Sociability: find "No" for the "question mark" and "thanks" for the "would like", the polite way to say "want".
  (c) Error analysis: related but not the best
  Figure 4: Two major categories of local explanation except word alignment and one typical error. The horizontal text is the input prompt and the vertical text is the response.
sections.heading: 4.5 Qualitative Analysis
sections.text: We further analyzed the extracted explanation for each dialogue. We found that these fine-grained level explanations can be split into three major categories: implication / meaning, sociability, and oneto-one word mapping. As shown in Figure 4a, the “hot potato” in response implies the phenomenon of “reduce the price of gasoline”. On the other hand, Figure 4b demonstrates that a response with sociability can sense the politeness and responds with “thanks”. We ignore word-to-word mapping here since it is intuitive and can already be successfully detected by attention models. Figure 4c shows a typical error that our explanation methods can produce. As depicted, the word “carry” is related to “bags”,“suitcases”, and “luggage”. Nonetheless a complete explanation should cluster “carry-on luggages”. The error of explanations can result from (1) the target model or (2) the explanation method. When taking the first view, in future work, we might use explanations as an evaluation method for dialogue generation models where the correct evaluation metrics are still in debates. When taking the second view, we need to understand that these methods are trying to explain the model and are not absolutely correct. Hence, we should carefully analyze the explanations and use them as reference and should not fully rely on them.
sections.heading: 5 Related Work and Discussion
sections.text: Explaining dialogue generation models is of high interest to understand if a generated response is reasonably produced rather than being a random guess. For example, among works about controllable dialogue generation [15, 26, 37, 40, 48, 50, 51, 53], Xu et al. [49] takes the dialog act in a controllable response generation model as the explanation. On the other hand, some propose to make dialogue response generation models more interpretable through walking on knowledge graphs [18, 28, 44]. Nonetheless, these works still rely on models with complex architecture and thus are not fully interpretable. We observe the lack of a model-agnostic method to analyze the explainability of dialogue response generation models, thus proposing LERG.
  Recently, there are applications and advances of local explanation methods [27, 35, 38]. For instance in NLP, some analyze the contributions of segments in documents to positive and negative sentiments [4, 8, 9, 29]. Some move forwards to finding segments towards text similarity [10], retrieving a text span towards question-answering [32], and making local explanation as alignment model in machine translation [1]. These tasks could be less complex than explaining general text generation models, such as dialogue generation models, since the the output space is either limited to few classes or able to find one-to-one mapping with the input text. Hence, we need to define how local explanations on text generation should work. However, we would like to note that LERG serves as a general formulation for explaining text generation models with flexible setups. Therefore, the distinct of prior work can also be used to extend LERG, such as making the explanations hierarchical. To move forward with the development of explanation methods, LERG can also be extended to dealing
  5We did a z-test and a t-test [22] with the null hypothesis between LERG_L and LIME (and LERG_S and Shapley). For both settings the p-value was less than 0.001, indicating that the proposed methods significantly outperform the baselines.
  6https://www.mturk.com
  with off- /on- data manifold problem of Shapley value introduced in [13], integrating causal structures to separate direct / in-direct relations [12, 16], and fusing concept- / feature- level explanations [5].
sections.heading: 6 Conclusion
sections.text: Beyond the recent advances on interpreting classification models, we explore the possibility to understand sequence generation models in depth. We focus on dialogue response generation and find that its challenges lead to complex and less transparent models. We propose local explanation of response generation (LERG), which aims at explaining dialogue response generation models through the mutual interactions between input and output features. LERG views the dialogue generation models as a certainty estimation of a human response so that it avoids dealing with the diverse output space. To facilitate future research, we further propose a unification and three properties of explanations for text generation. The experiments demonstrate that LERG can find explanations that can both recover a model’s prediction and be interpreted by humans. Next steps can be taking models’ explainability as evaluation metrics, integrating concept-level explanations, and proposing new methods for text generation models while still adhering to the properties.
sections.heading: 7 Acknowledgement
sections.text: We thank all the reviewers precious comments in revising this paper. This material is based on work that is partially funded by an unrestricted gift from Google.
title: Local Explanation of Dialogue Response Generation