What training objectives have prior methods used to train dialogue generation model?
Dialogue Generation Training Objectives. To
train a dialogue response generation model, meth-
ods have been developed from maximizing the
likelihood between the hypothesis and the ground-
truth (Vinyals and Le, 2015; Serban et al., 2016),
guiding responses to match a higher reward in
reinforcement learning (Li et al., 2016d), and al-
lowing for extra latent variables to optimize diver-
gence through variational autoencoder (Zhao et al.,
2017) or generative adversarial networks (Li et al.,
2017a; Tuan and Lee, 2019). Recent works have
introduced the concept of causal inference (Hol-
land, 1986; Imai et al., 2008; Pearl, 2009; Cunning-
ham, 2021) into generative adversarial network-
based (Zhu et al., 2020) and multiple-stage infer-
ence based dialogue generation model (Tuan et al.,
2020). Utterance-level offline reinforcement learn-
ing has also been explored to optimize response
generation (Jaques et al., 2020; Verma et al., 2022).
However, they were studied by expanding available
sequence data with imaginations. Now by provid-
ing a chit-chat dialogue DAG structure that is en-
riched with multiple if-else cases, CausalDialogue
can be studied for causal inference and offline re-
inforcement learning on response generation. We
also propose a new method called ExMATE for
better optimizing a response generation model on
the DAG data structure.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We investigate the task of building open domain, conversational dialogue systems based on large dialogue corpora using generative models. Generative models produce system responses that are autonomously generated word-by-word, opening up the possibility for realistic, flexible interactions. In support of this goal, we extend the recently proposed hierarchical recurrent encoder-decoder neural network to the dialogue domain, and demonstrate that this model is competitive with state-of-the-art neural language models and back-off n-gram models. We investigate the limitations of this and similar approaches, and show how its performance can be improved by bootstrapping the learning from a larger question-answer pair corpus and from pretrained word embeddings.
[{"first":"Iulian","last":"Serban","middle":["V."]},{"first":"Alessandro","last":"Sordoni","middle":[]},{"first":"Yoshua","last":"Bengio","middle":[]},{"first":"Aaron","last":"Courville","middle":[]},{"first":"Joelle","last":"Pineau","middle":[]}]
Adversarial Learning for Neural Dialogue Generation
We apply adversarial training to open-domain dialogue generation, training a system to produce sequences that are indistinguishable from human-generated dialogue utterances. We cast the task as a reinforcement learning problem where we jointly train two systems: a generative model to produce response sequences, and a discriminator—analagous to the human evaluator in the Turing test— to distinguish between the human-generated dialogues and the machine-generated ones. In this generative adversarial network approach, the outputs from the discriminator are used to encourage the system towards more human-like dialogue. Further, we investigate models for adversarial evaluation that uses success in fooling an adversary as a dialogue evaluation metric, while avoiding a number of potential pitfalls. Experimental results on several metrics, including adversarial evaluation, demonstrate that the adversarially-trained system generates higher-quality responses than previous baselines
[{"first":"Jiwei","last":"Li","middle":[]},{"first":"Will","last":"Monroe","middle":[]},{"first":"Tianlin","last":"Shi","middle":[]},{"first":"Sébastien","last":"Jean","middle":[]},{"first":"Alan","last":"Ritter","middle":[]},{"first":"Dan","last":"Jurafsky","middle":[]}]
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
While recent neural encoder-decoder models have shown great promise in modeling open-domain conversations, they often generate dull and generic responses. Unlike past work that has focused on diversifying the output of the decoder from word-level to alleviate this problem, we present a novel framework based on conditional variational autoencoders that capture the discourse-level diversity in the encoder. Our model uses latent variables to learn a distribution over potential conversational intents and generates diverse responses using only greedy decoders. We have further developed a novel variant that is integrated with linguistic prior knowledge for better performance. Finally, the training procedure is improved through introducing a bag-of-word loss. Our proposed models have been validated to generate significantly more diverse responses than baseline approaches and exhibit competence of discourse-level decision-making.
[{"first":"Tiancheng","last":"Zhao","middle":[]},{"first":"Ran","last":"Zhao","middle":[]},{"first":"Maxine","last":"Eskenazi","middle":[]}]
A Neural Conversational Model
Conversational modeling is an important task in natural language understanding and machine intelligence. Although previous approaches exist, they are often restricted to specific domains (e.g., booking an airline ticket) and require hand-crafted rules. In this paper, we present a simple approach for this task which uses the recently proposed sequence to sequence framework. Our model converses by predicting the next sentence given the previous sentence or sentences in a conversation. The strength of our model is that it can be trained end-to-end and thus requires much fewer hand-crafted rules. We find that this straightforward model can generate simple conversations given a large conversational training dataset. Our preliminary results suggest that, despite optimizing the wrong objective function, the model is able to converse well. It is able extract knowledge from both a domain specific dataset, and from a large, noisy, and general domain dataset of movie subtitles. On a domain-specific IT helpdesk dataset, the model can find a solution to a technical problem via conversations. On a noisy open-domain movie transcript dataset, the model can perform simple forms of common sense reasoning. As expected, we also find that the lack of consistency is a common failure mode of our model.
[{"first":"Oriol","last":"Vinyals","middle":[]},{"first":"Quoc","last":"Le","middle":[]}]
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Data-driven, knowledge-grounded neural conversation models are capable of generating more informative responses. However, these models have not yet demonstrated that they can zero-shot adapt to updated, unseen knowledge graphs. This paper proposes a new task about how to apply dynamic knowledge graphs in neural conversation model and presents a novel TV series conversation corpus (DyKgChat) for the task. Our new task and corpus aids in understanding the influence of dynamic knowledge graphs on responses generation. Also, we propose a preliminary model that selects an output from two networks at each time step: a sequence-to-sequence model (Seq2Seq) and a multi-hop reasoning model, in order to support dynamic knowledge graphs. To benchmark this new task and evaluate the capability of adaptation, we introduce several evaluation metrics and the experiments show that our proposed approach outperforms previous knowledge-grounded conversation models. The proposed corpus and model can motivate the future research directions.
[{"first":"Yi-Lin","last":"Tuan","middle":[]},{"first":"Yun-Nung","last":"Chen","middle":[]},{"first":"Hung-yi","last":"Lee","middle":[]}]
Counterfactual Off-Policy Training for Neural Dialogue Generation
Learning a neural response generation model on data synthesized under the adversarial training framework helps to explore more possible responses. However, most of the data synthesized de novo are of low quality due to the vast size of the response space. In this paper, we propose a counterfactual off-policy method to learn on a better synthesis of data. It takes advantage of a real response to infer an alternative that was not taken using a structural casual model. Learning on the counterfactual responses helps to explore the high-reward area of the response space. An empirical study on the DailyDialog dataset shows that our approach significantly outperforms the HRED model as well as the conventional adversarial training approaches.
[{"first":"Qingfu","last":"Zhu","middle":[]},{"first":"Wei-Nan","last":"Zhang","middle":[]},{"first":"Ting","last":"Liu","middle":[]},{"first":"William Yang","last":"Wang","middle":[]}]
Deep Reinforcement Learning for Dialogue Generation
Recent neural models of dialogue generation offer great promise for generating responses for conversational agents, but tend to be shortsighted, predicting utterances one at a time while ignoring their influence on future outcomes. Modeling the future direction of a dialogue is crucial to generating coherent, interesting dialogues, a need which led traditional NLP models of dialogue to draw on reinforcement learning. In this paper, we show how to integrate these goals, applying deep reinforcement learning to model future reward in chatbot dialogue. The model simulates dialogues between two virtual agents, using policy gradient methods to reward sequences that display three useful conversational properties: informativity (non-repetitive turns), coherence, and ease of answering (related to forward-looking function). We evaluate our model on diversity, length as well as with human judges, showing that the proposed algorithm generates more interactive responses and manages to foster a more sustained conversation in dialogue simulation. This work marks a first step towards learning a neural conversational model based on the long-term success of dialogues.
[{"first":"Jiwei","last":"Li","middle":[]},{"first":"Will","last":"Monroe","middle":[]},{"first":"Alan","last":"Ritter","middle":[]},{"first":"Michel","last":"Galley","middle":[]},{"first":"Jianfeng","last":"Gao","middle":[]},{"first":"Dan","last":"Jurafsky","middle":[]}]
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Dialogue systems, also known as interactive conversational agents, virtual agents and sometimes chatterbots, are used in a wide set of applications ranging from technical support services to language learning tools and entertainment Shawar and Atwell 2007). Dialogue systems can be divided into goal-driven systems, such as technical support services, and non-goal-driven systems, such as language learning tools or computer game characters. Our current work focuses on the second case, due to the availability of large corpora of this type, though the model may eventually prove useful for goal-driven systems also.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Perhaps the most successful approach to goal-driven systems has been to view the dialogue problem as a partially observable Markov decision process (POMDP) . Unfortunately, most deployed dialogue systems use hand-crafted features for the state and action space representations, and require either a large annotated task-specific corpus or a horde of human subjects willing to interact with the unfinished system. This not only makes it expensive and time-consuming to deploy a real dialogue system, but also limits its usage to a narrow domain. Recent work has tried to push goal-driven systems towards learning with few examples using constraints on the POMDP  as well as learning the observed features themselves with neural network models (Henderson,Thomson,and Young 1 Y.B. is a CIFAR senior Fellow Copyright c 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 2014), yet such approaches still require either hand-crafted features or large corpora of annotated task-specific simulated conversations.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
On the other end of the spectrum are the non-goaldriven systems (Ritter, Cherry, and Dolan 2011;Banchs and Li 2012;Ameixa et al. 2014). Most recently Sordoni et al. (2015b) and Shang et al. (2015) have drawn inspiration from the use of neural networks in natural language modeling and machine translation tasks (Cho et al. 2014). There are several motivations for developing nongoal-driven systems. First, they may be deployed directly for tasks which do not naturally exhibit a directly measurable goal (e.g. language learning) or simply for entertainment. Second, if they are trained on corpora related to the task of a goal-driven dialogue system (e.g. corpora which cover conversations on similar topics) then these models can be used to train a user simulator, which can then train the POMDP models discussed earlier Pietquin and Hastie 2013). This would alleviate the expensive and time-consuming task of constructing a large-scale task-specific dialogue corpus. In addition to this, the features extracted from the non-goal-driven systems may be used to expand the state space representation of POMDP models (Singh et al. 2002). This can help generalization to dialogues outside the annotated task-specific corpora.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Our contribution is in the direction of end-to-end trainable, non-goal-driven systems based on generative probabilistic models. We define the generative dialogue problem as modeling the utterances and interactive structure of the dialogue. As such, we view our model as a cognitive system, which has to carry out natural language understanding, reasoning, decision making and natural language generation in order to replicate or emulate the behavior of the agents in the training corpus. Our approach differs from previous work on learning dialogue systems through interaction with humans Gasic et al. 2013;Cantrell et al. 2012;Mohan and Laird 2014), because it learns off-line through examples of human-human dialogues and aims to emulate the dialogues in the training corpus instead of maximize a task-specific objective function. Contrary to explanation-based learning (Mohan and Laird 2014) and rule-based inference systems (Langley et al. 2014), our model does not require a predefined state or action space representation. These representations are instead learned directly from the corpus examples together with inference mechanisms, which map dialogue utterances to dialogue states, and action generation mechanisms, which map dialogue states to dialogue acts and stochastically to response utterances. We believe that training such a model end-to-end to minimize a single objective function, and with minimum reliance on hand-crafted features, will yield superior performance in the long run. Furthermore, we focus on models which can be trained efficiently on large datasets and which are able to maintain state over long conversations.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We experiment with the well-established recurrent neural networks (RNN) and n-gram models. In particular, we adopt the hierarchical recurrent encoder-decoder (HRED) (Sordoni et al. 2015a) and demonstrate that it is competitive with other models in the literature. We extend the model architecture to better suit the dialogue task. We show that performance can be substantially improved by bootstrapping from pretrained word embeddings and by pretraining the model on a larger question-answer pair (Q-A) corpus. To carry out experiments, we introduce the MovieTriples dialogue dataset based on movie scripts.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We consider a dialogue as a sequence of M utterances D = {U 1 , . . . , U M } involving two interlocutors. Each U m contains a sequence of N m tokens, i.e. U m = {w m,1 , . . . , w m,Nm }, where w m,n is a random variable taking values in the vocabulary V and representing the token at position n in utterance m. The tokens represent both words and speech acts, e.g. pause and end of turn tokens. A generative model of dialogue parameterizes a probability distribution P -governed by parameters θ -over the set of all possible dialogues of arbitrary lengths. The probability of a dialogue D can be decomposed:
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Nm n=1 P θ (w m,n |w m,<n , U <m ),
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
(1) U <m = {U 1 , . . . , U m−1 }, w m,<n = {w m,1 , . . . , w m,n−1 }, i.e. the tokens preceding n in the utterance U m . The task is analogous to language modeling, with the critical difference that speech acts are included as separate tokens. Sampling from the model can be performed as in standard language modeling: sampling one word at a time from the conditional distribution P θ (w m,n |w m,<n , U <m ) conditioned on the previously sampled words.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Using standard n-grams to compute joint probabilities over dialogues, e.g. computing probability tables for each token given the n preceding tokens, suffers from the curse of dimensionality and is intractable for any realistic vocabulary size. To overcome this, Bengio et al. (2003) proposed a distributed (dense) vector representation of words, called word embeddings, which parameterizes P θ (w m,n |w m,<n , U <m ) as a smooth function using a neural network. By means of such distributed representations, the recurrent neural network (RNN) based language model (Mikolov et al. 2010) has pushed state-of-the-art performance by learning long ngram contexts while avoiding data sparsity issues. Overall, RNNs have performed well on a variety of NLP tasks such as machine translation (Cho et al. 2014;Sutskever, Vinyals, and Le 2014;Bahdanau, Cho, and Bengio 2015) and information retrieval (Sordoni et al. 2015a).
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
A recurrent neural network (RNN) models an input sequence of tokens {w 1 , . . . , w N } using the recurrence:
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
where h n ∈ R d h is called a recurrent, or hidden, state and acts as a vector representation of the tokens seen up to position n. In particular, the last state h N may be viewed as an order-sensitive compact summary of all the tokens. In language modeling tasks, the context information encoded in h n is used to predict the next token in the sentence:
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
The functions f and g are typically defined as:
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
The matrix I ∈ R d h ×|V | contains the input word embeddings, i.e. each column I j is a vector corresponding to token j in the vocabulary V . Due to the size of the model vocabulary V , it is common to approximate the I matrix with a low-rank decomposition, i.e. I = XE, where X ∈ R d h ×de and E ∈ R de×|V | , and d e < d h . This approach has also 1: The computational graph of the HRED architecture for a dialogue composed of three turns. Each utterance is encoded into a dense vector and then mapped into the dialogue context, which is used to decode (generate) the tokens in the next utterance. The encoder RNN encodes the tokens appearing within the utterance, and the context RNN encodes the temporal structure of the utterances appearing so far in the dialogue, allowing information and gradients to flow over longer time spans. The decoder predicts one token at a time using a RNN. Adapted from Sordoni et al. (2015a).
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
the advantage that the embedding matrix E may separately be bootstrapped (e.g. learned) from larger corpora. Analogously, the matrix O ∈ R d h ×|V | represents the output word embeddings, where each possible next token is projected into another dense vector and compared to the hidden state h n . The probability of seeing token v at position n + 1 increases if its corresponding embedding vector O v is "near" the context vector h n . The parameter H is called a recurrent parameter, because it links h n−1 to h n . All parameters are learned by maximizing the log-likelihood of the parameters on a training set using stochastic gradient descent.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Our work extends the hierarchical recurrent encoderdecoder architecture (HRED) proposed by Sordoni et al. (2015a) for web query suggestion. In the original framework, HRED predicts the next web query given the queries already submitted by the user. The history of past submitted queries is considered as a sequence at two levels: a sequence of words for each web query and a sequence of queries. HRED models this hierarchy of sequences with two RNNs: one at the word level and one at the query level. We make a similar assumption, namely, that a dialogue can be seen as a sequence of utterances which, in turn, are sequences of tokens. A representation of HRED is given in Figure 1.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
In dialogue, the encoder RNN maps each utterance to an utterance vector. The utterance vector is the hidden state obtained after the last token of the utterance has been processed. The higher-level context RNN keeps track of past utterances by processing iteratively each utterance vector. After processing utterance U m , the hidden state of the context RNN represents a summary of the dialogue up to and includ-ing turn m, which is used to predict the next utterance U m+1 . This hidden state can be interpreted as the continuous-valued state of the dialogue system. The next utterance prediction is performed by means of a decoder RNN, which takes the hidden state of the context RNN and produces a probability distribution over the tokens in the next utterance. The decoder RNN is similar to the RNN language model (Mikolov et al. 2010), but with the important difference that the prediction is conditioned on the hidden state of the context RNN. It can be interpreted as the response generation module of the dialogue system. The encoder, context and decoder RNNs all make use of the GRU hidden unit (Cho et al. 2014). Everywhere else we use the hyperbolic tangent as activation function. It is also possible to use the maxout activation function between the hidden state and the projected word embeddings of the decoder RNN (Goodfellow et al. 2013). The same encoder RNN and decoder RNN parameters are used for every utterance in a dialogue. This helps the model generalize across utterances. Further details of the architecture are described by Sordoni et al. (2015a).
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
For modeling dialogues, we expect the HRED model to be superior to the standard RNN model for two reasons. First, because the context RNN allows the model to represent a form of common ground between speakers, e.g. to represent topics and concepts shared between the speakers using a distributed vector representation, which we hypothesize to be important for building an effective dialogue system (Clark and Brennan 1991). Second, because the number of computational steps between utterances is reduced. This makes the objective function more stable w.r.t. the model parameters, and helps propagate the training signal for first-order optimization methods (Sordoni et al. 2015a).
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
In HRED, the utterance representation is given by the last hidden state of the encoder RNN. This architecture worked well for web queries, but may be insufficient for dialogue utterances, which are longer and contain more syntactic articulations than web queries. For long utterances, the last state of the encoder RNN may not reflect important information seen at the beginning of the utterance. Thus, we also experiment with a model where the utterance encoder is a bidirectional RNN. Bidirectional RNNs run two chains: one forward through the utterance tokens and another backward, i.e. reversing the tokens in the utterance. The forward hidden state at position n summarizes tokens preceding position n and the backwards hidden state summarizes tokens following position n. 1 To obtain a fixed-length representation for the utterance, we summarize the information in the forward and backward RNN hidden states by either: 1) taking the concatenation of the last state of each RNN as input to the context RNN, or 2) applying L 2 pooling over the temporal dimension of each chain, and taking the concatenation of the two pooled states as input to the context RNN. 2 The bidirectional structure will effectively introduce additional short term dependencies, which has proven useful in similar architectures (Bahdanau, Cho, and Bengio 2015;Sutskever, Vinyals, and Le 2014). In experiments below, we refer to this variant as HRED-Bidirectional.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
The commonsense knowledge that the dialogue interlocutors share may be difficult to infer if the dataset is not sufficiently large. Therefore, our models may be improved by learning word embeddings from larger corpora. We choose to initialize our word embeddings E with Word2Vec 3 (Mikolov et al. 2013) trained on the Google News dataset containing about 100 billion words. The sheer size of the dataset ensures that the embeddings contain rich semantic information about each word.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
To learn a good initialization point for all model parameters, instead of only the word embeddings, we can further pretrain the model on a large non-dialogue corpus, which covers similar topics and types of interactions between interlocutors. One such corpus is the Q-A SubTle corpus containing about 5.5M Q-A pairs constructed from movie subtitles (Ameixa et al. 2014). We construct an artificial dialogue dataset by taking each {Q, A} pair as a two-turn dialogue D = {U 1 = Q, U 2 = A} and use this to pretrain the model.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
The MovieTriples dataset has been developed by expanding and preprocessing the Movie-DiC dataset by Banchs  al. (2012) to make it fit the generative dialogue modeling framework. The dataset is available upon request. Movie scripts span a wide range of topics, contain long interactions with few participants and relatively few spelling mistakes and acronyms. As observed by Forchini (2009): "movie language can be regarded as a potential source for teaching and learning spoken language features". Therefore, we believe bootstrapping a goal-driven spoken dialogue system based on movie scripts will improve performance. We used the Python-based natural language toolkit NLTK (Bird, Klein, and Loper 2009) to perform tokenization and named-entity recognition. All names and numbers were replaced with the <person> and <number> tokens respectively (Ritter, Cherry, and Dolan 2010). To reduce data sparsity further, all tokens were transformed to lowercase letters, and all but the 10,000 most frequent tokens were replaced with a generic <unk> token.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We then generated "triples" {U 1 , U 2 , U 3 }, i.e. dialogues of three turns between two interlocutors A and B, for which A emits a first utterance U 1 , B responds with U 2 and A responds with a last utterance U 3 (Sordoni et al. 2015b). To capture the interactive dialogue structure, a special end-of-utterance token is appended to all utterances and a continued-utterance token between breaks in lines from the same speaker. To avoid co-dependencies between triples coming from the same movie, we first split the movies into training, validation and test set, and then construct the triples. Statistics are reported in Table 1.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We evaluate the different variants of our HRED model, and compare against several alternatives, including basic n-gram models (Goodman 2001), a standard (non-hierarchical) RNN trained on the concatenation of the utterances in each triple, and a context-sensitive model (DCGM-I) recently proposed by Sordoni et al. (2015b).
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Accurate evaluation of a non-goal-driven dialogue system is an open problem (Galley et al. 2015;Pietquin and Hastie 2013;Schatzmann, Georgila, and Young 2005). There is no well-established method for automatic evaluation, and human-based evaluation is expensive. Nevertheless, for probabilistic language models word perplexity is a well-established performance metric (Bengio et al. 2003;Mikolov et al. 2010), and has been suggested for generative dialogue models previously (Pietquin and Hastie 2013). We define word perplexity:
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
for a model with parameters θ, dataset with N triples {U n 1 , U n 2 , U n 3 } N n=1 , and N W the number of tokens in the entire dataset. Lower perplexity is indicative of a better model. Perplexity explicitly measures the model's ability to account for the syntactic structure of the dialogue (e.g. turn-taking) and the syntactic structure of each utterance (e.g. punctuation marks). In dialogue, the distribution over the words in the next utterance is highly multi-modal, e.g. there are many possible answers, which makes perplexity particularly appropriate because it will always measure the probability of regenerating the exact reference utterance.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We also consider the word classification error (also known as word error-rate). This is defined as the number of words in the dataset the model has predicted incorrectly divided by the total number of words in the dataset. 4 Each word contributes either zero or 1/N W to the count, which means that it is more robust to unlikely (e.g. unpredictable) words. However, it is also less fine-grained than word perplexity. Instead of measuring the whole distribution, it only measures the regions of high probability.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Ultimately, we care about generating syntactically and semantically coherent dialogues. For example, utterances which are grammatically correct and reflect the distribution of topics in the corpus, and whole dialogues which reflect the interaction patterns and topical evolutions of the dialogues in the corpus. Despite having been proposed before (Pietquin and Hastie 2013;Schatzmann, Georgila, and Young 2005). it is not clear how well word perplexity and word classification errors correlate with this goal. Nevertheless, optimizing probabilistic models using word perplexity has shown promising results in several machine learning tasks including statistical machine translation (Auli et al. 2013;Sutskever, Vinyals, and Le 2014;Bahdanau, Cho, and Bengio 2015), speech recognition (Hinton et al. 2012;Deng and Li 2013) and image caption generation (Kiros, Salakhutdinov, and Zemel 2014;. Based on these empirical findings, we expect to be able to discriminate between models based on word perplexity, and to use word classification error and qualitative analysis of generated dialogues to understand the performance of the models in depth.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
To train the neural network models, we optimized the loglikelihood of the triples using the recently proposed Adam optimizer (Kingma and Ba 2014). 5 Our implementation relied on the open-source Python library Theano (Bastien et al. 2012). 6 The best hyperparameters of the models were chosen by early stopping with patience on the validation set perplexity (Bengio 2012). We initialized the recurrent parameter matrices as orthogonal matrices, and all other parameters from a Gaussian random distribution with mean zero and standard deviation 0.01. For the baseline RNN, we tested hidden state spaces d h = 200, 300 and 400. For HRED we experimented with encoder and decoder hidden state spaces of size 200, 300 and 400. Based on preliminary results and due to GPU memory limitations, we limited ourselves to size 300 when not bootstrapping or bootstrapping from Word2Vec, and to size 400 when bootstrapping from SubTle. Preliminary experiments showed that the context RNN state space at and above 300 performed similarly, so we fixed it at 300 when not bootstrapping or bootstrapping from Word2Vec, and to 1200 when bootstrapping from SubTle. For all models, we used word embedding of size 400 when bootstrapping from SubTle and of size 300 otherwise. To help generalization, we used the maxout activation function, between the hidden state and the projected word embeddings of the decoder RNN, when not bootstrapping and when bootstrapping from Word2Vec. We used L 2 pooling for all HRED models, except when bootstrapping from SubTle since it appeared to perform slightly worse.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Bootstrapping Word Embeddings Our embedding matrix E was initialized using the publicly available 300 dim. Word2Vec embeddings trained on the Google News corpus (Mikolov et al. 2013). Special dialogue tokens, which did not exist in the Word2Vec embeddings, were initialized from a Gaussian random distribution as before. The training procedure was carried out in two stages. First, we trained each neural model with fixed Word2Vec embeddings. During this stage, we also trained the speech act and placeholder tokens, together with tokens not covered by the original Word2Vec embeddings. In the second stage, we then trained all parameters of each neural model until convergence.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Bootstrapping SubTle We processed the SubTle corpus by following the same procedure as used for MovieTriples, but treating the last utterances U 3 as empty. The final Sub-Tle corpus contained 5,503,741 Q-A pairs, and a total of 93,320,500 tokens. When bootstrapping from the SubTle corpus, we found that all models performed slightly better when randomly initializing and learning the word embeddings from SubTle compared to fixing the word embeddings to those given by Word2Vec. For this reason, we do not report results combining bootstrapping from the SubTle corpus with Word2Vec word embeddings.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
The HRED models were pretrained for approximately four epochs on the SubTle dataset, after which performance did not appear to improve further. Then, we fine-tuned the pretrained models on the MovieTriples dataset holding the word embeddings fixed.   
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Our results are presented in Table 2. All neural models beat state-of-the-art n-grams models substantially w.r.t. both word perplexity and word classification error. Without bootstrapping, the RNN model performs similarly to the more complex DCGM-I and HRED models. This can be explained by the size of the dataset, which makes it easy for the HRED and DCGM-I model to overfit. The last four lines of Table 2 confirm that bootstrapping the model parameters achieves significant gains in both measures. Bootstrapping from SubTle is particularly useful since it allows a gain of nearly 10 perplexity points compared to the HRED model without bootstrapping. We believe that this is because it trains all model parameters, unlike bootstrapping from Word2Vec, which only trains the word embeddings.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
In general, we find that the gains due to architectural choice are smaller than those obtained by bootstrapping, which can be explained by the fact that we are in a regime of relatively little training data compared to other natural language processing tasks, such as machine translation, and hence we would expect the differences to grow with more training data and longer dialogues. Overall, the bidirectional structure appears to capture and retain information from the U 1 and U 2 utterances better than either the RNN and the original HRED model. This confirms our earlier hypothesis, and demonstrates the potential of HRED for modeling long dialogues.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We also considered the use of beam-search for RNNs (Graves 2012) to approximate the most probable (MAP) last utterance, U 3 , given the first two utterances, U 1 and U 2 . MAP outputs are presented in Table 3 for HRED-Bidirectional bootstrapped from Sub-Tle corpus. As shown here, the model often produced sensible answers. However, in fact, the majority of the predictions were generic, such as I don't know or I'm sorry. We observed the same phenomenon for the RNN model, and similar observations can be inferred by remarks in the recent literature (Sordoni et al. 2015b;Vinyals and Le 2015). To the best of our knowledge, we are the first to emphasize and discuss it in details. 7 There are several possible explanations for this behavior. Firstly, due to data scarcity, the models may only have learned to predict the most frequent utterances. Since the dialogues are inherently ambiguous and multi-modal, predicting them accurately would require more data than other natural language processing tasks. Secondly, the majority of tokens were punctuation marks and pronouns. Since every token is weighted equally during training, the gradient signal of the neural networks is dominated by these punctu-ation and pronoun tokens. This makes it hard for the neural networks to learn topic-specific embeddings and even harder to predict diverse utterances. This suggests exploring neural architectures which explicitly separate semantic structure from syntactic structure. Finally, the context of a triple may be too short. In that case, the models should benefit from longer contexts and by conditioning on other information sources, such as semantic and visual information.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
An important implication of this observation is that metrics based on MAP outputs (e.g. cosine similarity, BLEU, Levenshtein distance) will primarily favor models that output the same number of punctuation marks and pronouns as are in the test utterances, as opposed to similar semantic content (e.g. nouns and verbs). This would be systematically biased and not necessarily in any way correlate with the objective of producing appropriate responses. We therefore cannot justify the use of such metrics when the results are known to lack diversity.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Nevertheless, we also note that this problem did not occur when we generated stochastic samples (as opposed to the MAP outputs). In fact, the stochastic samples contained a large variety of topic-specific words and often appeared to maintain the topic of the conversation.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
We have demonstrated that a hierarchical recurrent neural network generative model can outperform both n-gram based models and baseline neural network models on the task of modeling utterances and speech acts. To support our investigation, we introduced a novel dataset called MovieTriples based on movie scripts, which are suitable for modeling long, open domain dialogues close to human spoken language. In addition to the recurrent hierarchical architecture, we found two crucial ingredients for improving performance: the use of a large external monologue corpus to initialize the word embeddings, and the use of a large related, but non-dialogue, corpus in order to pretrain the recurrent net. This points to the need for larger dialogue datasets.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Empirical performance of all models was measured using perplexity. While this is an established measure for generative models, in the dialogue setting utterances may be overwhelmed by many common words especially arising from colloquial or informal exchanges. It may be fruitful to investigate other measures of performance for generative dialogue systems. We also considered actual responses produced by the model. The MAP outputs tended to produce somewhat generic, but conversationally acceptable, responses. Stochastic samples from the model produced more diverse dialogues.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Future work should study models for full length dialogues, as opposed to triples, and model other speech acts, such as interlocutors entering or leaving the dialogue and executing actions. Finally, our analysis of the model MAP outputs suggests that it would be beneficial to include longer and additional context, including other modalities such as audio and video.
Adversarial Learning for Neural Dialogue Generation
Open domain dialogue generation (Ritter et al., 2011;Sordoni et al., 2015;Xu et al., 2016;Li et al., 2016b;Serban et al., 2016c aims at generating meaningful and coherent dialogue responses given the dialogue history. Prior systems, e.g., phrase-based machine translation systems (Ritter et al., 2011;Sordoni et al., 2015) or end-to-end neural systems (Shang et al., 2015;Vinyals and Le, 2015;Li et al., 2016a;Yao et al., 2015;Luan et al., 2016) approximate such a goal by predicting the next dialogue utterance given the dialogue history using the maximum likelihood estimation (MLE) objective. Despite its success, this over-simplified training objective leads to problems: responses are dull, generic (Sordoni et al., 2015;Serban et al., 2016a;Li et al., 2016a), repetitive, and short-sighted (Li et al., 2016d).
Adversarial Learning for Neural Dialogue Generation
Solutions to these problems require answering a few fundamental questions: what are the crucial aspects that characterize an ideal conversation, how can we quantitatively measure them, and how can we incorporate them into a machine learning system? For example, Li et al. (2016d) manually define three ideal dialogue properties (ease of answering, informativeness and coherence) and use a reinforcement-learning framework to train the model to generate highly rewarded responses. Yu et al. (2016b) use keyword retrieval confidence as a reward. However, it is widely acknowledged that manually defined reward functions can't possibly cover all crucial aspects and can lead to suboptimal generated utterances. A good dialogue model should generate utterances indistinguishable from human dialogues. Such a goal suggests a training objective resembling the idea of the Turing test (Turing, 1950). We borrow the idea of adversarial training (Goodfellow et al., 2014;Denton et al., 2015) in computer vision, in which we jointly train two models, a generator (a neural SEQ2SEQ model) that defines the probability of generating a dialogue sequence, and a discriminator that labels dialogues as human-generated or machine-generated. This discriminator is analogous to the evaluator in the Turing test. We cast the task as a reinforcement learning problem, in which the quality of machinegenerated utterances is measured by its ability to fool the discriminator into believing that it is a human-generated one. The output from the discriminator is used as a reward to the generator, pushing it to generate utterances indistinguishable from human-generated dialogues.
Adversarial Learning for Neural Dialogue Generation
The idea of a Turing test-employing an evaluator to distinguish machine-generated texts from human-generated ones-can be applied not only to training but also testing, where it goes by the name of adversarial evaluation. Adversarial evaluation was first employed in Bowman et al. (2016) to evaluate sentence generation quality, and preliminarily studied for dialogue generation by Kannan and Vinyals (2016). In this paper, we discuss potential pitfalls of adversarial evaluations and necessary steps to avoid them and make evaluation reliable.
Adversarial Learning for Neural Dialogue Generation
Experimental results demonstrate that our approach produces more interactive, interesting, and non-repetitive responses than standard SEQ2SEQ models trained using the MLE objective function.
Adversarial Learning for Neural Dialogue Generation
In this section, we describe in detail the components of the proposed adversarial reinforcement learning model. The problem can be framed as follows: given a dialogue history x consisting of a sequence of dialogue utterances, 1 the model needs to generate a response y = {y 1 , y 2 , ..., y T }. We view the process of sentence generation as a sequence of actions that are taken according to a policy defined by an encoder-decoder recurrent neural network.
Adversarial Learning for Neural Dialogue Generation
The adversarial REINFORCE algorithm consists of two components: a generative model G and a discriminative model D.
Adversarial Learning for Neural Dialogue Generation
Generative model The generative model G defines the policy that generates a response y given dialogue history x. It takes a form similar to SEQ2SEQ models, which first map the source input to a vector representation using a recurrent net and then compute the probability of generating each token in the target using a softmax function.
Adversarial Learning for Neural Dialogue Generation
Discriminative model The discriminative model D is a binary classifier that takes as input a sequence of dialogue utterances {x, y} and outputs a label indicating whether the input is generated by humans or machines. The input dialogue is encoded into a vector representation using a hierarchical encoder Serban et al., 2016b), 2 which is then fed to a 2-class softmax function, returning the probability of the input dialogue episode being a machine-generated dialogue (denoted Q − ({x, y})) or a human-generated dialogue (denoted Q + ({x, y})).
Adversarial Learning for Neural Dialogue Generation
The key idea of the system is to encourage the generator to generate utterances that are indistinguishable from human generated dialogues. We use policy gradient methods to achieve such a goal, in which the score of current utterances being human-generated ones assigned by the discriminator (i.e., Q + ({x, y})) is used as a reward for the generator, which is trained to maximize the expected reward of generated utterance(s) using the REINFORCE algorithm (Williams, 1992): 1 We approximate the dialogue history using the concatenation of two preceding utterances. We found that using more than 2 context utterances yields very tiny performance improvements for SEQ2SEQ models.
Adversarial Learning for Neural Dialogue Generation
2 To be specific, each utterance p or q is mapped to a vector representation hp or hq using LSTM (Hochreiter and Schmidhuber, 1997). Another LSTM is put on sentence level, mapping the context dialogue sequence to a single representation.
Adversarial Learning for Neural Dialogue Generation
Given the input dialogue history x, the bot generates a dialogue utterance y by sampling from the policy. The concatenation of the generated utterance y and the input x is fed to the discriminator. The gradient of (1) is approximated using the likelihood ratio trick (Williams, 1992;Glynn, 1990;Aleksandrov et al., 1968):
Adversarial Learning for Neural Dialogue Generation
where π denotes the probability of the generated responses. b({x, y}) denotes the baseline value to reduce the variance of the estimate while keeping it unbiased. 3 The discriminator is simultaneously updated with the human generated dialogue that contains dialogue history x as a positive example and the machine-generated dialogue as a negative example.
Adversarial Learning for Neural Dialogue Generation
Step (REGS)
Adversarial Learning for Neural Dialogue Generation
The REINFORCE algorithm described has the disadvantage that the expectation of the reward is approximated by only one sample, and the reward associated with this sample (i.e., (2)) is used for all actions (the generation of each token) in the generated sequence. Suppose, for example, the input history is what's your name, the human-generated response is I am John, and the machine-generated response is I don't know. The vanilla REINFORCE model assigns the same negative reward to all tokens within the human-generated response (i.e., I, don't, know), whereas proper credit assignment in training would give separate rewards, most likely a neutral reward for the token I, and negative rewards to don't and know. We call this reward for every generation step, abbreviated REGS. Rewards for intermediate steps or partially decoded sequences are thus necessary. Unfortunately, the discriminator is trained to assign scores to fully generated sequences, but not partially decoded ones. We propose two strategies for computing intermediate step rewards by (1) using Monte Carlo (MC) search and (2) training a discriminator that is able to assign rewards to partially decoded sequences.
Adversarial Learning for Neural Dialogue Generation
In (1) Monte Carlo search, given a partially decoded s P , the model keeps sampling tokens from the distribution until the decoding finishes. Such a process is repeated N (set to 5) times and the N generated sequences will share a common prefix s P . These N sequences are fed to the discriminator, the average score of which is used as a reward for the s P . A similar strategy is adopted in Yu et al. (2016a). The downside of MC is that it requires repeating the sampling process for each prefix of each sequence and is thus significantly time-consuming. 4 In (2), we directly train a discriminator that is able to assign rewards to both fully and partially decoded sequences. We break the generated sequences into partial sequences, namely {y
Adversarial Learning for Neural Dialogue Generation
as positive examples and instances {y −
Adversarial Learning for Neural Dialogue Generation
as negative examples. The problem with such a strategy is that earlier actions in a sequence are shared among multiple training examples for the discriminator (for example, token y + 1 is contained in all partially generated sequences, which results in overfitting. To mitigate this problem, we adopt a strategy similar to when training value networks in AlphaGo (Silver et al., 2016), in which for each collection of subsequences of Y , we randomly sample only one example from {y + 1:t } N Y + t=1 and one example from
Adversarial Learning for Neural Dialogue Generation
, which are treated as positive and negative examples to update the discriminator. Compared with the Monte Carlo search model, this strategy is significantly more time-effective, but comes with the weakness that the discriminator becomes less accurate after partially decoded sequences are added in as training examples. We find that the MC model performs better when training time is less of an issue.
Adversarial Learning for Neural Dialogue Generation
For each partially-generated sequence Y t = y 1:t , the discriminator gives a classification score Q + (x, Y t ). We compute the baseline b(x, Y t ) using a similar model to the vanilla REINFORCE model. This yields the following gradient to update the generator:
Adversarial Learning for Neural Dialogue Generation
Comparing (3) with (2), we can see that the values for rewards and baselines are different among generated tokens in the same response.
Adversarial Learning for Neural Dialogue Generation
Teacher Forcing Practically, we find that updating the generative model only using Eq. 1 leads to unstable training for both vanilla Reinforce and REGS, with the perplexity value skyrocketing after training the model for a few hours (even when the generator is initialized using a pre-trained SEQ2SEQ model). The reason this happens is that the generative model can only be indirectly exposed to the gold-standard target sequences through the reward passed back from the discriminator, and this reward is used to promote or discourage its (the generator's) own generated sequences. Such a training strategy is fragile: once the generator (accidentally) deteriorates in some training batches and the discriminator consequently does an extremely good job in recognizing sequences from the generator, the generator immediately gets lost. It knows that its generated sequences are bad based on the rewards outputted from the discriminator, but it does not know what sequences are good and how to push itself to generate these good sequences (the odds of generating a good response from random sampling are minute, due to the vast size of the space of possible sequences). Loss of the reward signal leads to a breakdown in the training process.
Adversarial Learning for Neural Dialogue Generation
To alleviate this issue and give the generator more direct access to the gold-standard targets, we propose also feeding human generated responses to the generator for model updates. The most straightforward strategy is for the discriminator to automatically assign a reward of 1 (or other positive values) to the human generated responses and for the generator to use this reward to update itself on human generated examples. This can be seen as having a teacher intervene with the generator some fraction of the time and force it to generate the true responses, an approach that is similar to the professor-forcing algorithm of Lamb et al. (2016).
Adversarial Learning for Neural Dialogue Generation
A closer look reveals that this modification is the same as the standard training of SEQ2SEQ mod-
Adversarial Learning for Neural Dialogue Generation
Sample (X,Y) from real data .
Adversarial Learning for Neural Dialogue Generation
SampleŶ ∼ G(·|X) .
Adversarial Learning for Neural Dialogue Generation
Update D using (X, Y ) as positive examples and
Adversarial Learning for Neural Dialogue Generation
Compute Reward r for (X,Ŷ ) using D. .
Adversarial Learning for Neural Dialogue Generation
Update G on (X,Ŷ ) using reward r .
Adversarial Learning for Neural Dialogue Generation
Teacher-Forcing: Update G on (X, Y ) . End End Figure 1: A brief review of the proposed adversarial reinforcement algorithm for training the generator G and discriminator D. The reward r from the discriminator D can be computed using different strategies according to whether using REINFORCE or REGS. The update of the generator G on (X,Ŷ ) can be done by either using Eq.2 or Eq.3. D-steps is set to 5 and G-steps is set to 1. els, making the final training alternately update the SEQ2SEQ model using the adversarial objective and the MLE objective. One can think of the professor-forcing model as a regularizer to regulate the generator once it starts deviating from the training dataset.
Adversarial Learning for Neural Dialogue Generation
We also propose another workaround, in which the discriminator first assigns a reward to a human generated example using its own model, and the generator then updates itself using this reward on the human generated example only if the reward is larger than the baseline value. Such a strategy has the advantage that different weights for model updates are assigned to different human generated examples (in the form of different reward values produced by the generator) and that human generated examples are always associated with nonnegative weights.
Adversarial Learning for Neural Dialogue Generation
A sketch of the proposed model is shown in Figure 1.
Adversarial Learning for Neural Dialogue Generation
We first pre-train the generative model by predicting target sequences given the dialogue history.
Adversarial Learning for Neural Dialogue Generation
We trained a SEQ2SEQ model (Sutskever et al., 2014) with an attention mechanism (Bahdanau et al., 2015; on the OpenSubtitles dataset. We followed protocols recommended by Sutskever et al. (2014), such as gradient clipping, mini-batch and learning rate decay. We also pre-train the discriminator. To generate negative examples, we decode part of the training data. Half of the negative examples are generated using beamsearch with mutual information reranking as described in Li et al. (2016a), and the other half is generated from sampling.
Adversarial Learning for Neural Dialogue Generation
For data processing, model training and decoding (both the proposed adversarial training model and the standard SEQ2SEQ models), we employ a few strategies that improve response quality, including: (2) Remove training examples with length of responses shorter than a threshold (set to 5). We find that this significantly improves the general response quality. 5 (2) Instead of using the same learning rate for all examples, using a weighted learning rate that considers the average tf-idf score for tokens within the response. Such a strategy decreases the influence from dull and generic utterances. 6 (3) Penalizing intra-sibling ranking when doing beam search decoding to promote N-best list diversity as described in Li et al. (2016c). (4) Penalizing word types (stop words excluded) that have already been generated. Such a strategy dramatically decreases the rate of repetitive responses such as no. no. no. no. no. or contradictory responses such as I don't like oranges but i like oranges.
Adversarial Learning for Neural Dialogue Generation
In this section, we discuss strategies for successful adversarial evaluation. Note that the proposed adversarial training and adversarial evaluation are separate procedures. They are independent of each other and share no common parameters.
Adversarial Learning for Neural Dialogue Generation
The idea of adversarial evaluation, first proposed by Bowman et al. (2016), is to train a discriminant function to separate generated and true sentences, in an attempt to evaluate the model's sentence generation capability. The idea has been preliminarily studied by Kannan and Vinyals (2016) in the context of dialogue generation. Adversarial evaluation also resembles the idea of the Turing test, which 5 To compensate for the loss of short responses, one can train a separate model using short sequences. 6 We treat each sentence as a document. Stop words are removed. Learning rates are normalized within one batch. For example, suppose t1, t2, ..., ti, ... ,tN denote the tf-idf scores for sentences within current batch and lr denotes the original learning rate. The learning rate for sentence with index i is N · lr · t i i t i . To avoid exploding learning rates for sequences with extremely rare words, the tf-idf score of a sentence is capped at L times the minimum tf-idf score in the current batch. L is empirically chosen and is set to 3. requires a human evaluator to distinguish machinegenerated texts from human-generated ones. Since it is time-consuming and costly to ask a human to talk to a model and give judgements, we train a machine evaluator in place of the human evaluator to distinguish the human dialogues and machine dialogues, and we use it to measure the general quality of the generated responses.
Adversarial Learning for Neural Dialogue Generation
Adversarial evaluation involves both training and testing. At training time, the evaluator is trained to label dialogues as machine-generated (negative) or human-generated (positive). At test time, the trained evaluator is evaluated on a held-out dataset. If the human-generated dialogues and machinegenerated ones are indistinguishable, the model will achieve 50 percent accuracy at test time.
Adversarial Learning for Neural Dialogue Generation
We define Adversarial Success (AdverSuc for short) to be the fraction of instances in which a model is capable of fooling the evaluator. AdverSuc is the difference between 1 and the accuracy achieved by the evaluator. Higher values of AdverSuc for a dialogue generation model are better.
Adversarial Learning for Neural Dialogue Generation
One caveat with the adversarial evaluation methods is that they are model-dependent. We approximate the human evaluator in the Turing test with an automatic evaluator and assume that the evaluator is perfect: low accuracy of the discriminator should indicate high quality of the responses, since we interpret this to mean the generated responses are indistinguishable from the human ones. Unfortunately, there is another factor that can lead to low discriminative accuracy: a poor discriminative model. Consider a discriminator that always gives random labels or always gives the same label. Such an evaluator always yields a high AdverSuc value of 0.5. Bowman et al. (2016) propose two different discriminator models separately using unigram features and neural features. It is hard to tell which feature set is more reliable. The standard strategy of testing the model on a held-out development set is not suited to this case, since a model that overfits the development set is necessarily superior.
Adversarial Learning for Neural Dialogue Generation
To deal with this issue, we propose setting up a few manually-invented situations to test the ability of the automatic evaluator. This is akin to setting up examinations to test the ability of the human evaluator in the Turing test. We report not only the AdverSuc values, but also the scores that the evalu-ator achieves in these manually-designed test cases, indicating how much we can trust the reported Ad-verSuc. We develop scenarios in which we know in advance how a perfect evaluator should behave, and then compare AdverSuc from a discriminative model with the gold-standard AdverSuc. Scenarios we design include:
Adversarial Learning for Neural Dialogue Generation
• as positive examples and dialogues with responses replaced by the utterances immediately following the true responses. A perfect evaluation should give an AdverSuc of 0 (accuracy 100%). The evaluator reliability error (ERE) is the average deviation of an evaluator's adversarial error from the gold-standard error in the above tasks, with equal weight for each task. The smaller the error, the more reliable the evaluator is.
Adversarial Learning for Neural Dialogue Generation
Evaluator reliability error uses scenarios constructed from human-generated dialogues to assess feature or hyper-parameter choice for the evaluator. Unfortunately, no machine-generated responses are involved in the ERE metric. The following example illustrates the serious weakness resulting from this strategy: as will be shown in the experiment section, when inputs are decoded using greedy or beam search models, most generation systems to date yield an adversarial success less than 10 percent (evaluator accuracy 90 percent). But when using sampling for decoding, the adversarial success skyrockets to around 40 percent, 7 only 10 percent less than what's needed to pass the Turing test. A close look at the decoded sequences using sampling tells a different story: the responses from 7 Similar results are also reported in Kannan and Vinyals (2016).   Tables 5 and 6. sampling are sometimes incoherent, irrelevant or even ungrammatical. We thus propose an additional sanity check, in which we report the accuracy of distinguishing between machine-generated responses and randomly sampled responses (machine-vs-random for short). This resembles the N-choose-1 metric described in Shao et al. (2017). Higher accuracy indicates that the generated responses are distinguishable from randomly sampled human responses, indicating that the generative model is not fooling the generator simply by introducing randomness. As we will show in Sec. 5, using sampling results in high AdverSuc values but low machine-vs-random accuracy.
Adversarial Learning for Neural Dialogue Generation
In this section, we detail experimental results on adversarial success and human evaluation.  
Adversarial Learning for Neural Dialogue Generation
ERE We first test adversarial evaluation models with different feature sets and model architectures for reliability, as measured by evaluator reliability error (ERE). We explore the following models: (1) SVM+Unigram: SVM using unigram features. 8 A 8 Trained using the SVM-Light package (Joachims, 2002). multi-utterance dialogue (i.e., input messages and responses) is transformed to a unigram representation; (2) Concat Neural: a neural classification model with a softmax function that takes as input the concatenation of representations of constituent dialogues sentences; (3) Hierarchical Neural: a hierarchical encoder with a structure similar to the discriminator used in the reinforcement; and (4) SVM+Neural+multi-lex-features: a SVM model that uses the following features: unigrams, neural representations of dialogues obtained by the neural model trained using strategy (3), 9 the forward likelihood log p(t|s) and backward likelihood p(s|t).
Adversarial Learning for Neural Dialogue Generation
ERE scores obtained by different models are reported in Table 2. As can be seen, the hierarchical neural evaluator (model 3) is more reliable than simply concatenating the sentence-level representations (model 2). Using the combination of neural features and lexicalized features yields the most reliable evaluator. For the rest of this section, we report results obtained by the Hierarchical Neural setting due to its end-to-end nature, despite its inferiority to SVM+Neural+multil-features. Table 3 presents AdverSuc values for different models, along with machine-vs-random accuracy described in Section 4.3. Higher values of Adver-Suc and machine-vs-random are better.
Adversarial Learning for Neural Dialogue Generation
Baselines we consider include standard SEQ2SEQ models using greedy decoding (MLEgreedy), beam-search (MLE+BS) and sampling, as well as the mutual information reranking model of Li et al. (2016a) with two algorithmic variations:
Adversarial Learning for Neural Dialogue Generation
(1) MMI+p(t|s), in which a large N-best list is first 9 The representation before the softmax layer.  Table 3: AdverSuc and machine-vs-random scores achieved by different training/decoding strategies. generated using a pre-trained SEQ2SEQ model and then reranked by the backward probability p(s|t) and (2) MMI−p(t), in which language model probability is penalized during decoding. Results are shown in Table 3. What first stands out is decoding using sampling (as discussed in Section 4.3), achieving a significantly higher AdverSuc number than all the rest models. However, this does not indicate the superiority of the sampling decoding model, since the machine-vs-random accuracy is at the same time significantly lower. This means that sampled responses based on SEQ2SEQ models are not only hard for an evaluator to distinguish from real human responses, but also from randomly sampled responses. A similar, though much less extreme, effect is observed for MMI−p(t), which has an AdverSuc value slightly higher than Adver-Reinforce, but a significantly lower machine-vsrandom score.
Adversarial Learning for Neural Dialogue Generation
By comparing different baselines, we find that MMI+p(t|s) is better than MLE-greedy, which is in turn better than MLE+BS. This result is in line with human-evaluation results from Li et al. (2016a). The two proposed adversarial algorithms achieve better performance than the baselines. We expect this to be the case, since the adversarial algorithms are trained on an objective function more similar to the evaluation metric (i.e., adversarial success). REGS performs slightly better than the vanilla RE-INFORCE algorithm.
Adversarial Learning for Neural Dialogue Generation
For human evaluation, we follow protocols defined in Li et al. (2016d), employing crowdsourced judges to evaluate a random sample of 200 items. We present both an input message and the generated outputs to 3 judges and ask them to decide which of the two outputs is better (single-turn general quality). Ties are permitted. Identical strings are assigned the same score. We also present the judges with multi-turn conversations simulated between the two agents. Each conversation consists   Table 4. We observe a significant quality improvement on both single-turn quality and multi-turn quality from the proposed adversarial model. It is worth noting that the reinforcement learning system described in Li et al. (2016d), which simulates conversations between two bots and is trained based on manually designed reward functions, only improves multiturn dialogue quality, while the model described in this paper improves both single-turn and multiturn dialogue generation quality. This confirms that the reward adopted in adversarial training is more general, natural and effective in training dialogue systems.
Adversarial Learning for Neural Dialogue Generation
In this paper, drawing intuitions from the Turing test, we propose using an adversarial training approach for response generation. We cast the model in the framework of reinforcement learning and train a generator based on the signal from a discriminator to generate response sequences indistinguishable from human-generated dialogues. We observe clear performance improvements on multiple metrics from the adversarial training strategy. The adversarial training model should theoretically benefit a variety of generation tasks in NLP. Unfortunately, in preliminary experiments applying the same training paradigm to machine translation, we did not observe a clear performance boost. We conjecture that this is because the adversarial training strategy is more beneficial to tasks in which there is a big discrepancy between the distributions of the generated sequences and the reference target sequences. In other words, the adversarial approach is more beneficial on tasks in which entropy of the targets is high. Exploring this relationship further is a focus of our future work.   
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
The dialog manager is one of the key components of dialog systems, which is responsible for modeling the decision-making process. Specifically, it typically takes a new utterance and the dialog context as input, and generates discourse-level decisions (Bohus and Rudnicky, 2003;Williams and Young, 2007). Advanced dialog managers usually have a list of potential actions that enable them to have diverse behavior during a conversation, e.g. different strategies to recover from non-understanding . However, the conventional approach of designing a dialog manager (Williams and Young, 2007) does not scale well to open-domain conversation models because of the vast quantity of possible decisions. Thus, there has been a growing interest in applying encoder-decoder models (Sutskever et al., 2014) for modeling open-domain conversation (Vinyals and Le, 2015;Serban et al., 2016a). The basic approach treats a conversation as a transduction task, in which the dialog history is the source sequence and the next response is the target sequence. The model is then trained end-to-end on large conversation corpora using the maximum-likelihood estimation (MLE) objective without the need for manual crafting.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
However recent research has found that encoder-decoder models tend to generate generic and dull responses (e.g., I don't know), rather than meaningful and specific answers (Li et al., 2015;Serban et al., 2016b). There have been many attempts to explain and solve this limitation, and they can be broadly divided into two categories (see Section 2 for details): (1) the first category argues that the dialog history is only one of the factors that decide the next response. Other features should be extracted and provided to the models as conditionals in order to generate more specific responses (Xing et al., 2016;Li et al., 2016a); (2) the second category aims to improve the encoder-decoder model itself, including decoding with beam search and its variations (Wiseman and Rush, 2016), encouraging responses that have long-term payoff (Li et al., 2016b), etc.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Building upon the past work in dialog managers and encoder-decoder models, the key idea of this paper is to model dialogs as a one-to-many problem at the discourse level. Previous studies indicate that there are many factors in open-domain dialogs that decide the next response, and it is nontrivial to extract all of them. Intuitively, given a similar dialog history (and other observed inputs), there may exist many valid responses (at the discourse-level), each corresponding to a certain configuration of the latent variables that are not presented in the input. To uncover the potential responses, we strive to model a probabilistic distribution over the distributed utterance embeddings of the potential responses using a latent variable ( Figure 1). This allows us to generate diverse responses by drawing samples from the learned distribution and reconstruct their words via a decoder neural network. Specifically, our contributions are three-fold: 1. We present a novel neural dialog model adapted from conditional variational autoencoders (CVAE) , which introduces a latent variable that can capture discourse-level variations as described above 2. We propose Knowledge-Guided CVAE (kgC-VAE), which enables easy integration of expert knowledge and results in performance improvement and model interpretability. 3. We develop a training method in addressing the difficulty of optimizing CVAE for natural language generation (Bowman et al., 2015). We evaluate our models on human-human conversation data and yield promising results in: (a) generating appropriate and discourse-level diverse responses, and (b) showing that the proposed training method is more effective than the previous techniques.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Since the emergence of the neural dialog model, the problem of output diversity has received much attention in the research community. Ideal output responses should be both coherent and diverse. However, most models end up with generic and dull responses. To tackle this problem, one line of research has focused on augmenting the in-put of encoder-decoder models with richer context information, in order to generate more specific responses. Li et al., (2016a) captured speakers' characteristics by encoding background information and speaking style into the distributed embeddings, which are used to re-rank the generated response from an encoder-decoder model. Xing et al., (2016) maintain topic encoding based on Latent Dirichlet Allocation (LDA) (Blei et al., 2003) of the conversation to encourage the model to output more topic coherent responses.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
On the other hand, many attempts have also been made to improve the architecture of encoderdecoder models. Li et al,. (2015) proposed to optimize the standard encoder-decoder by maximizing the mutual information between input and output, which in turn reduces generic responses. This approach penalized unconditionally high frequency responses, and favored responses that have high conditional probability given the input. Wiseman and Rush (2016) focused on improving the decoder network by alleviating the biases between training and testing. They introduced a searchbased loss that directly optimizes the networks for beam search decoding. The resulting model achieves better performance on word ordering, parsing and machine translation. Besides improving beam search, Li et al., (2016b) pointed out that the MLE objective of an encoder-decoder model is unable to approximate the real-world goal of the conversation. Thus, they initialized a encoderdecoder model with MLE objective and leveraged reinforcement learning to fine tune the model by optimizing three heuristic rewards functions: informativity, coherence, and ease of answering.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
The variational autoencoder (VAE) (Kingma and Welling, 2013;Rezende et al., 2014) is one of the most popular frameworks for image generation. The basic idea of VAE is to encode the input x into a probability distribution z instead of a point encoding in the autoencoder. Then VAE applies a decoder network to reconstruct the original input using samples from z. To generate images, VAE first obtains a sample of z from the prior distribution, e.g. N (0, I), and then produces an image via the decoder network. A more advanced model, the conditional VAE (CVAE), is a recent modification of VAE to generate diverse images conditioned on certain attributes, e.g. generating different human faces given skin color . Inspired by CVAE, we view the dialog contexts as the conditional attributes and adapt CVAE to generate diverse responses instead of images.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Although VAE/CVAE has achieved impressive results in image generation, adapting this to natural language generators is non-trivial. Bowman et al., (2015) have used VAE with Long-Short Term Memory (LSTM)-based recognition and decoder networks to generate sentences from a latent Gaussian variable. They showed that their model is able to generate diverse sentences with even a greedy LSTM decoder. They also reported the difficulty of training because the LSTM decoder tends to ignore the latent variable. We refer to this issue as the vanishing latent variable problem. Serban et al., (2016b) have applied a latent variable hierarchical encoder-decoder dialog model to introduce utterance-level variations and facilitate longer responses. To improve upon the past models, we firstly introduce a novel mechanism to leverage linguistic knowledge in training end-to-end neural dialog models, and we also propose a novel training technique that mitigates the vanishing latent variable problem. 
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Each dyadic conversation can be represented via three random variables: the dialog context c (context window size k − 1), the response utterance x (the k th utterance) and a latent variable z, which is used to capture the latent distribution over the valid responses. Further, c is composed of the dialog history: the preceding k-1 utterances; conversational floor (1 if the utterance is from the same speaker of x, otherwise 0) and meta features m (e.g. the topic). We then define the conditional distribution p(x, z|c) = p(x|z, c)p(z|c) and our goal is to use deep neural networks (parametrized by θ) to approximate p(z|c) and p(x|z, c). We refer to p θ (z|c) as the prior network and p θ (x, |z, c) as the response decoder. Then the generative process of x is (Figure 2 (a)):
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
1. Sample a latent variable z from the prior network p θ (z|c).
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
2. Generate x through the response decoder p θ (x|z, c).
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
CVAE is trained to maximize the conditional log likelihood of x given c, which involves an intractable marginalization over the latent variable z. As proposed in , CVAE can be efficiently trained with the Stochastic Gradient Variational Bayes (SGVB) framework (Kingma and Welling, 2013) by maximizing the variational lower bound of the conditional log likelihood. We assume the z follows multivariate Gaussian distribution with a diagonal covariance matrix and introduce a recognition network q φ (z|x, c) to approximate the true posterior distribution p(z|x, c).  have shown that the variational lower bound can be written as: Figure 3 demonstrates an overview of our model. The utterance encoder is a bidirectional recurrent neural network (BRNN) (Schuster and Paliwal, 1997) with a gated recurrent unit (GRU) (Chung et al., 2014) to encode each utterance into fixedsize vectors by concatenating the last hidden states of the forward and backward RNN u
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
x is simply u k . The context encoder is a 1-layer GRU network that encodes the preceding k-1 utterances by taking u 1:k−1 and the corresponding conversation floor as inputs. The last hidden state h c of the context encoder is concatenated with meta features and c = [h c , m]. Since we assume z follows isotropic Gaussian distribution, the recognition network q φ (z|x, c) ∼ N (µ, σ 2 I) and the prior network p θ (z|c) ∼ N (µ , σ 2 I), and then we have: We then use the reparametrization trick (Kingma and Welling, 2013) to obtain samples of z either from N (z; µ, σ 2 I) predicted by the recognition network (training) or N (z; µ , σ 2 I) predicted by the prior network (testing). Finally, the response decoder is a 1-layer GRU network with initial state
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
The response decoder then predicts the words in x sequentially.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
In practice, training CVAE is a challenging optimization problem and often requires large amount of data. On the other hand, past research in spoken dialog systems and discourse analysis has suggested that many linguistic cues capture crucial features in representing natural conversation. For example, dialog acts (Poesio and Traum, 1998) have been widely used in the dialog managers (Litman and Allen, 1987;Raux et al., 2005;Zhao and Eskenazi, 2016) to represent the propositional function of the system. Therefore, we conjecture that it will be beneficial for the model to learn meaningful latent z if it is provided with explicitly extracted discourse features during the training. In order to incorporate the linguistic features into the basic CVAE model, we first denote the set of linguistic features as y. Then we assume that the generation of x depends on c, z and y. y relies on z and c as shown in Figure 2. Specifically, during training the initial state of the response decoder is s 0 = W i [z, c, y] + b i and the input at every step is [e t , y] where e t is the word embedding of t th word in x. In addition, there is an MLP to predict y = MLP y (z, c) based on z and c. In the testing stage, the predicted y is used by the re-sponse decoder instead of the oracle decoders. We denote the modified model as knowledge-guided CVAE (kgCVAE) and developers can add desired discourse features that they wish the latent variable z to capture. KgCVAE model is trained by maximizing:
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Since now the reconstruction of y is a part of the loss function, kgCVAE can more efficiently encode y-related information into z than discovering it only based on the surface-level x and c. Another advantage of kgCVAE is that it can output a highlevel label (e.g. dialog act) along with the wordlevel responses, which allows easier interpretation of the model's outputs.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
A straightforward VAE with RNN decoder fails to encode meaningful information in z due to the vanishing latent variable problem (Bowman et al., 2015). Bowman et al., (2015) proposed two solutions: (1) KL annealing: gradually increasing the weight of the KL term from 0 to 1 during training;
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
(2) word drop decoding: setting a certain percentage of the target words to 0. We found that CVAE suffers from the same issue when the decoder is an RNN. Also we did not consider word drop decoding because Bowman et al,. (2015) have shown that it may hurt the performance when the drop rate is too high.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
As a result, we propose a simple yet novel technique to tackle the vanishing latent variable problem: bag-of-word loss. The idea is to introduce an auxiliary loss that requires the decoder network to predict the bag-of-words in the response x as shown in Figure 3(b). We decompose x into two variables: x o with word order and x bow without order, and assume that x o and x bow are conditionally independent given z and c: p(x, z|c) = p(x o |z, c)p(x bow |z, c)p(z|c). Due to the conditional independence assumption, the latent variable is forced to capture global information about the target response. Let f = MLP b (z, x) ∈ R V where V is vocabulary size, and we have:
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
where |x| is the length of x and x t is the word index of t th word in x. The modified variational lower bound for CVAE with bag-of-word loss is (see Appendix A for kgCVAE):
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
We will show that the bag-of-word loss in Equation 6 is very effective against the vanishing latent variable and it is also complementary to the KL annealing technique.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
We chose the Switchboard (SW) 1 Release 2 Corpus (Godfrey and Holliman, 1997) to evaluate the proposed models. SW has 2400 two-sided telephone conversations with manually transcribed speech and alignment. In the beginning of the call, a computer operator gave the callers recorded prompts that define the desired topic of discussion. There are 70 available topics. We randomly split the data into 2316/60/62 dialogs for train/validate/test. The pre-processing includes (1) tokenize using the NLTK tokenizer (Bird et al., 2009); (2) remove non-verbal symbols and repeated words due to false starts; (3) keep the top 10K frequent word types as the vocabulary. The final data have 207, 833/5, 225/5, 481 (c, x) pairs for train/validate/test. Furthermore, a subset of SW was manually labeled with dialog acts (Stolcke et al., 2000). We extracted dialog act labels based on the dialog act recognizer proposed in (Ribeiro et al., 2015). The features include the uni-gram and bi-gram of the utterance, and the contextual features of the last 3 utterances. We trained a Support Vector Machine (SVM) (Suykens and Vandewalle, 1999) with linear kernel on the subset of SW with human annotations. There are 42 types of dialog acts and the SVM achieved 77.3% accuracy on held-out data. Then the rest of SW data are labelled with dialog acts using the trained SVM dialog act recognizer.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
We trained with the following hyperparameters (according to the loss on the validate dataset): word embedding has size 200 and is shared across everywhere. We initialize the word embedding from Glove embedding pre-trained on Twitter (Pennington et al., 2014). The utterance encoder has a hidden size of 300 for each direction. The context encoder has a hidden size of 600 and the response decoder has a hidden size of 400. The prior network and the MLP for predicting y both have 1 hidden layer of size 400 and tanh non-linearity. The latent variable z has a size of 200. The context window k is 10. All the initial weights are sampled from a uniform distribution [-0.08, 0.08]. The mini-batch size is 30. The models are trained end-to-end using the Adam optimizer (Kingma and Ba, 2014) with a learning rate of 0.001 and gradient clipping at 5. We selected the best models based on the variational lower bound on the validate data. Finally, we use the BOW loss along with KL annealing of 10,000 batches to achieve the best performance. Section 5.4 gives a detailed argument for the importance of the BOW loss.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
We compared three neural dialog models: a strong baseline model, CVAE, and kgCVAE. The baseline model is an encoder-decoder neural dialog model without latent variables similar to (Serban et al., 2016a). The baseline model's encoder uses the same context encoder to encode the dialog history and the meta features as shown in Figure 3. The encoded context c is directly fed into the decoder networks as the initial state. The hyperparameters of the baseline are the same as the ones reported in Section 4.2 and the baseline is trained to minimize the standard cross entropy loss of the decoder RNN model without any auxiliary loss. Also, to compare the diversity introduced by the stochasticity in the proposed latent variable versus the softmax of RNN at each decoding step, we generate N responses from the baseline by sampling from the softmax. For CVAE/kgCVAE, we sample N times from the latent z and only use greedy decoders so that the randomness comes entirely from the latent variable z.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Automatically evaluating an open-domain generative dialog model is an open research challenge . Following our one-tomany hypothesis, we propose the following metrics. We assume that for a given dialog context c, there exist M c reference responses r j , j ∈ [1, M c ]. Meanwhile a model can generate N hypothesis responses h i , i ∈ [1, N ]. The generalized responselevel precision/recall for a given dialog context is:
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
where d(r j , h i ) is a distance function which lies between 0 to 1 and measures the similarities between r j and h i . The final score is averaged over the entire test dataset and we report the performance with 3 types of distance functions in order to evaluate the systems from various linguistic points of view: (Chen and Cherry, 2014): BLEU is a popular metric that measures the geometric mean of modified ngram precision with a length penalty (Papineni et al., 2002;Li et al., 2015). We use BLEU-1 to 4 as our lexical similarity metric and normalize the score to 0 to 1 scale.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Distance of Bag-of-word Embedding: a simple method to obtain sentence embeddings is to take the average or extrema of all the word embeddings in the sentences (Forgues et al., 2014;Adi et al., 2016). The d(r j , h i ) is the cosine distance of the two embedding vectors. We used Glove embedding described in Section 4 and denote the average method as A-bow and extrema method as E-bow. The score is normalized to [0, 1].
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
3. Dialog Act Match: to measure the similarity at the discourse level, the same dialogact tagger from 4.1 is applied to label all the generated responses of each model. We set d(r j , h i ) = 1 if r j and h i have the same dialog acts, otherwise d(r j , h i ) = 0.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
One challenge of using the above metrics is that there is only one, rather than multiple reference responses/contexts. This impacts reliability of our measures. Inspired by (Sordoni et al., 2015), we utilized information retrieval techniques (see Appendix A) to gather 10 extra candidate reference responses/context from other conversations with the same topics. Then the 10 candidate references are filtered by two experts, which serve as the ground truth to train the reference response classifier. The result is 6.69 extra references in average per context. The average number of distinct reference dialog acts is 4.2. The proposed models outperform the baseline in terms of recall in all the metrics with statistical significance. This confirms our hypothesis that generating responses with discourse-level diversity can lead to a more comprehensive coverage of the potential responses than promoting only word-level diversity. As for precision, we observed that the baseline has higher or similar scores than CVAE in all metrics, which is expected since the baseline tends to generate the mostly likely and safe responses repeatedly in the N hypotheses. However, kgCVAE is able to achieve the highest precision and recall in the 4 metrics at the same time (BLEU1-4, A-BOW). One reason for kgCVAE's good performance is that the predicted dialog act label in kgCVAE can regularize the generation process of its RNN decoder by forcing it to generate more coherent and precise words. We further analyze the precision/recall of BLEU-4 by looking at the average score versus the number of distinct reference dialog acts. A low number of distinct dialog acts represents the situation where the dialog context has a strong constraint on the range of the next response (low entropy), while a high number indicates the opposite (highentropy). Figure 4 shows that CVAE/kgCVAE achieves significantly higher recall than the baseline in higher entropy contexts. Also it shows that CVAE suffers from lower precision, especially in low entropy contexts. Finally, kgCVAE gets higher precision than both the baseline and CVAE in the full spectrum of context entropy.  Table 2 shows the outputs generated from the baseline and kgCVAE. In example 1, caller A begins with an open-ended question. The kgCVAE model generated highly diverse answers that cover multiple plausible dialog acts. Further, we notice that the generated text exhibits similar dialog acts compared to the ones predicted separately by the model, implying the consistency of natural language generation based on y. On the contrary, the responses from the baseline model are limited to local n-gram variations and share a similar prefix, i.e. "I'm". Example 2 is a situation where caller A is telling B stories. The ground truth response is a back-channel and the range of valid answers is more constrained than example 1 since B is playing the role of a listener. The baseline successfully predicts "uh-huh". The kgCVAE model is also able to generate various ways of back-channeling. This implies that the latent z is able to capture context-sensitive variations, i.e. in low-entropy dialog contexts modeling lexical diversity while in high-entropy ones modeling discourse-level diversity. Moreover, kgCVAE is occasionally able to generate more sophisticated grounding (sample 4) beyond a simple back-channel, which is also an acceptable response given the dialog context.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
In addition, past work (Kingma and Welling, 2013) has shown that the recognition network is able to learn to cluster high-dimension data, so we conjecture that posterior z outputted from the recognition network should cluster the responses into meaningful groups. Figure 5 visualizes the posterior z of responses in the test dataset in 2D space using t-SNE (Maaten and Hinton, 2008). We found that the learned latent space is highly correlated with the dialog act and length of responses, which confirms our assumption. 
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Finally, we evaluate the effectiveness of bag-ofword (BOW) loss for training VAE/CVAE with the RNN decoder. To compare with past work (Bowman et al., 2015), we conducted the same language modelling (LM) task on Penn Treebank using VAE. The network architecture is same except we use GRU instead of LSTM. We compared four different training setups: (1) standard VAE without any heuristics; (2) VAE with KL annealing (KLA); (3) VAE with BOW loss; (4) VAE with both BOW loss and KLA. Intuitively, a well trained model should lead to a low reconstruction Table 2: Generated responses from the baselines and kgCVAE in two examples. KgCVAE also provides the predicted dialog act for each response. The context only shows the last utterance due to space limit (the actual context window size is 10).
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
loss and small but non-trivial KL cost. For all models with KLA, the KL weight increases linearly from 0 to 1 in the first 5000 batches. Table 3 shows the reconstruction perplexity and the KL cost on the test dataset. The standard VAE fails to learn a meaningful latent variable by having a KL cost close to 0 and a reconstruction perplexity similar to a small LSTM LM (Zaremba et al., 2014). KLA helps to improve the reconstruction loss, but it requires early stopping since the models will fall back to the standard VAE after the KL weight becomes 1. At last, the models with BOW loss achieved significantly lower perplexity and larger KL cost.   Figure 6 visualizes the evolution of the KL cost. We can see that for the standard model, the KL cost crashes to 0 at the beginning of training and never recovers. On the contrary, the model with only KLA learns to encode substantial information in latent z when the KL cost weight is small. However, after the KL weight is increased to 1 (after 5000 batch), the model once again decides to ignore the latent z and falls back to the naive implementation. The model with BOW loss, however, consistently converges to a non-trivial KL cost even without KLA, which confirms the im-portance of BOW loss for training latent variable models with the RNN decoder. Last but not least, our experiments showed that the conclusions drawn from LM using VAE also apply to training CVAE/kgCVAE, so we used BOW loss together with KLA for all previous experiments. 
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
In conclusion, we identified the one-to-many nature of open-domain conversation and proposed two novel models that show superior performance in generating diverse and appropriate responses at the discourse level. While the current paper addresses diversifying responses in respect to dialogue acts, this work is part of a larger research direction that targets leveraging both past linguistic findings and the learning power of deep neural networks to learn better representation of the latent factors in dialog. In turn, the output of this novel neural dialog model will be easier to explain and control by humans. In addition to dialog acts, we plan to apply our kgCVAE model to capture other different linguistic phenomena including sentiment, named entities,etc. Last but not least, the recognition network in our model will serve as the foundation for designing a datadriven dialog manager, which automatically discovers useful high-level intents. All of the above suggest a promising research direction.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
This work was funded by NSF grant CNS-1512973. The opinions expressed in this paper do not necessarily reflect those of NSF.
A Neural Conversational Model
Advances in end-to-end training of neural networks have led to remarkable progress in many domains such as speech recognition, computer vision, and language processing. Recent work suggests that neural networks can do more than just mere classification, they can be used to map complicated structures to other complicated structures. An example of this is the task of mapping a sequence to another sequence which has direct applications in natural language understanding . The main advantage of this framework is that it requires little feature engineering and domain specificity whilst matching or surpassing state-of-the-art results. This advance, in our opinion, allows researchers to work on tasks for which domain knowledge may not be readily available, or for tasks which are simply too hard to design rules manually.
A Neural Conversational Model
Conversational modeling can directly benefit from this formulation because it requires mapping between queries and reponses. Due to the complexity of this mapping, conversational modeling has previously been designed to be very narrow in domain, with a major undertaking on feature engineering. In this work, we experiment with the conversation modeling task by casting it to a task of predicting the next sequence given the previous sequence or sequences using recurrent networks . We find that this approach can do surprisingly well on generating fluent and accurate replies to conversations. We test the model on chat sessions from an IT helpdesk dataset of conversations, and find that the model can sometimes track the problem and provide a useful answer to the user. We also experiment with conversations obtained from a noisy dataset of movie subtitles, and find that the model can hold a natural conversation and sometimes perform simple forms of common sense reasoning. In both cases, the recurrent nets obtain better perplexity compared to the n-gram model and capture important long-range correlations. From a qualitative point of view, our model is sometimes able to produce natural conversations.
A Neural Conversational Model
Our approach makes use of the sequence-to-sequence (seq2seq) framework described in . The model is based on a recurrent neural network which reads the input sequence one token at a time, and predicts the output sequence, also one token at a time. During training, the true output sequence is given to the model, so learning can be done by backpropagation. The model is trained to maximize the cross entropy of the correct sequence given its context. During inference, given that the true output sequence is not observed, we simply feed the predicted output token as input to predict the next output. This is a "greedy" inference approach. A less greedy approach would be to use beam search, and feed several candidates at the previous step to the next step. The predicted sequence can be selected based on the probability of the sequence.
A Neural Conversational Model
Concretely, suppose that we observe a conversation with two turns: the first person utters "ABC", and second person replies "WXYZ". We can use a recurrent neural network, Figure 1. Using the seq2seq framework for modeling conversations. and train to map "ABC" to "WXYZ" as shown in Figure 1 above. The hidden state of the model when it receives the end of sequence symbol "<eos>" can be viewed as the thought vector because it stores the information of the sentence, or thought, "ABC".
A Neural Conversational Model
The strength of this model lies in its simplicity and generality. We can use this model for machine translation, question/answering, and conversations without major changes in the architecture. Applying this technique to conversation modeling is also straightforward: the input sequence can be the concatenation of what has been conversed so far (the context), and the output sequence is the reply.
A Neural Conversational Model
Unlike easier tasks like translation, however, a model like sequence-to-sequence will not be able to successfully "solve" the problem of modeling dialogue due to several obvious simplifications: the objective function being optimized does not capture the actual objective achieved through human communication, which is typically longer term and based on exchange of information rather than next step prediction. The lack of a model to ensure consistency and general world knowledge is another obvious limitation of a purely unsupervised model.
A Neural Conversational Model
In our experiments we used two datasets: a closed-domain IT helpdesk troubleshooting dataset and an open-domain movie transcript dataset. The details of the two datasets are as follows.
A Neural Conversational Model
In our first set of experiments, we used a dataset which was extracted from a IT helpdesk troubleshooting chat service. In this service, costumers face computer related issues, and a specialist help them by conversing and walking through a solution. Typical interactions (or threads) are 400 words long, and turn taking is clearly signaled. Our training set contains 30M tokens, and 3M tokens were used as validation. Some amount of clean up was performed, such as removing common names, numbers, and full URLs.
A Neural Conversational Model
We also tested our model on the OpenSubtitles dataset (Tiedemann, 2009). This dataset consists of movie conversations in XML format. It contains sentences uttered by characters in movies. We applied a simple processing step removing XML tags and obvious non-conversational text (e.g., hyperlinks) from the dataset. As turn taking is not clearly indicated, we treated consecutive sentences assuming they were uttered by different characters. We trained our model to predict the next sentence given the previous one, and we did this for every sentence (noting that this doubles our dataset size, as each sentence is used both for context and as target). Our training and validation split has 62M sentences (923M tokens) as training examples, and the validation set has 26M sentences (395M tokens). The split is done in such a way that each sentence in a pair of sentences either appear together in the training set or test set but not both. Unlike the previous dataset, the OpenSubtitles is quite large, and rather noisy because consecutive sentences may be uttered by the same character. Given the broad scope of movies, this is an open-domain conversation dataset, contrasting with the technical troubleshooting dataset.
A Neural Conversational Model
In this section, we describe the experimental results with the two datasets and show some samples of the interactions with the system that we trained. We also compare the performance of our system against a popular rule-based bot (CleverBot 1 ) using human evaluations on a set of 200 questions.
A Neural Conversational Model
In this experiment, we trained a single layer LSTM with 1024 memory cells using stochastic gradient descent with gradient clipping. The vocabulary consists of the most common 20K words, which includes special tokens indicating turn taking and actor.
A Neural Conversational Model
At convergence, this model achieved a perplexity of 8, whereas an n-gram model achieved 18. Below is a few samples of simulated troubleshooting sessions for most three of the most common IT problems (remote access, software crashes, and password issues). In these conversations, Machine is our Neural Conversational Model, and Human the human actor interacting with it. 
A Neural Conversational Model
In this experiment, we trained a two-layered LSTM using AdaGrad with gradient clipping. Each layer of the LSTM has 4096 memory cells, and we built a vocabulary consisting of the most frequent 100K words. To speed up the softmax, we project the memory cells to 2048 linear units before feeding the information to the classifier.
A Neural Conversational Model
At convergence the perplexity of the recurrent model on the validation set is 17. Our smoothed 5-gram model achieves a perplexity of 28. Interestingly, adding the soft attention mechanism of (Bahdanau et al., 2014) did not significantly improve the perplexity on neither training or validation sets.
A Neural Conversational Model
In addition to the perplexity measure, our simple recurrent model does often produce plausible answers. Here are a few sample question-answer pairs that allowed us to understand the capabilities of the model when trained on the noisy but large dataset of OpenSubtitles from movies. Again, in these conversations, Machine is our Neural Conversational Model, and Human the human actor interacting with it. We find it encouraging that the model can remember facts, understand contexts, perform common sense reasoning without the complexity in traditional pipelines. What surprises us is that the model does so without any explicit knowledge representation component except for the parameters in the word vectors.
A Neural Conversational Model
Perhaps most practically significant is the fact that the model can generalize to new questions. In other words, it does not simply look up for an answer by matching the question with the existing database. In fact, most of the questions presented above, except for the first conversation, do not appear in the training set.
A Neural Conversational Model
Nonetheless, one drawback of this basic model is that it only gives simple, short, sometimes unsatisfying answers to our questions as can be seen above. Perhaps a more problematic drawback is that the model does not capture a consistent personality. Indeed, if we ask not identical but semantically similar questions, the answers can sometimes be inconsistent. This is expected due to the simplicity of our model and the dataset in our experiments. The conversation below illustrates such failure: 
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
In the chit-chat dialogue generation, neural conversation models (Sutskever et al., 2014;Sordoni et al., 2015;Vinyals and Le, 2015) have emerged for its capability to be fully data-driven and endto-end trained. While the generated responses are often reasonable but general (without useful information), recent work proposed knowledgegrounded models (Eric et al., 2017;Ghazvininejad et al., 2018;Zhou et al., 2018b;Qian et al., 2018) to incorporate external facts in an end-toend fashion without hand-crafted slot filling. Effectively combining text and external knowledge graphs have also been a crucial topic in question answering (Yin et al., 2016;Hao et al., 2017;Levy et al., 2017;Sun et al., 2018;Das et al., 2019). Nonetheless, prior work rarely analyzed the model capability of zero-shot adaptation to dynamic knowledge graphs, where the states/entities and their relations are temporal and evolve as a single time scale process. For example, as shown in Figure 1, the entity Jin-Xi was originally related to the entity Feng, Ruozhao with the type Ene-myOf, but then evolved to be related to the entity Nian, Shilan.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The goal of this paper is to facilitate knowledgegrounded neural conversation models to learn and zero-shot adapt with dynamic knowledge graphs. To our observation, however, there is no existing conversational data paired with dynamic knowledge graphs. Therefore, we collect a TV series corpus-DyKgChat, with facts of the fictitious life of characters. DyKgChat includes a Chinese palace drama Hou Gong Zhen Huan Zhuan (HGZHZ), and an English sitcom Friends,which contain dialogues, speakers, scenes (e.g., the places and listeners), and the corresponded knowl-HGZHZ Zhen-Huan: She must be frightened. It should blame me. I should not ask her to play chess. 甄 甄 甄嬛 嬛 嬛: 姐姐定是嚇壞了。都怪臣妾不好，好端端的來叫梅姐姐下棋做什麼。 Doctor-Wen: Relax, Concubine-Huan madame. Lady Shen is just injured but is fine. 溫 溫 溫太 太 太醫 醫 醫: 莞 莞 莞嬪 嬪 嬪娘 娘 娘娘 娘 娘請放心，惠 惠 惠貴 貴 貴人 人 人的精神倒是沒有大礙，只是傷口燒得有些厲害。
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Joey: C' mon , you're going out with the guy! There's gotta be something wrong with him! Chandler: Alright Joey, be nice. So does he have a hump? A hump and a hairpiece? edge graphs including explicit information such as the relations FriendOf, EnemyOf, and Resi-denceOf as well as the linked entities. Table 1 shows some examples from DyKgChat.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Prior graph embedding based knowledgegrounded conversation models (Sutskever et al., 2014;Ghazvininejad et al., 2018;Zhu et al., 2017) did not directly use the graph structure, so it is unknown how a changed graph will influence the generated responses. In addition, key-value retrieved-based models (Yin et al., 2016;Eric et al., 2017;Levy et al., 2017;Qian et al., 2018) retrieve only one-hop relation paths. As fictitious life in drama, realistic responses often use knowledge entities existing in multi-hop relational paths, e.g., the residence of a friend of mine. Therefore, we propose a model that incorporates multi-hop reasoning (Lao et al., 2011;Neelakantan et al., 2015; on the graph structure into a neural conversation generation model. Our proposed model, called quick adaptive dynamic knowledge-grounded neural conversation model (Qadpt), is based on a Seq2Seq model (Sutskever et al., 2014) with a widely-used copy mechanism (Gu et al., 2016;Merity et al., 2017;Xing et al., 2017;Zhu et al., 2017;Eric et al., 2017;Ke et al., 2018). To enable multi-hop reasoning, the model factorizes a transition matrix for a Markov chain.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
In order to focus on the capability of producing reasonable knowledge entities and adapting with dynamic knowledge graphs, we propose two types of automatic metrics. First, given the provided knowledge graphs, we examine if the models can generate responses with proper usage of multi-hop reasoning over knowledge graphs. Second, after randomly replacing some crucial entities in knowledge graphs, we test if the models can accordingly generate correspondent responses. The empirical results show that our proposed model has the desired advantage of zero-shot adaptation with dynamic knowledge graphs, and can serve as a preliminary baseline for this new task. To sum up, the contributions of this paper are three-fold:
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
• A new task, dynamic knowledge-grounded conversation generation, is proposed. • A newly-collected TV series conversation corpus DyKgChat is presented for the target task. • We benchmark the task by comparing many prior models and the proposed quick adaptive dynamic knowledge-grounded neural conversation model (Qadpt), providing the potential of benefiting the future research direction.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For each single-turn conversation, the input message and response are respectively denoted as x = {x t } m t=1 and y = {y t } n t=1 , where m and n are their lengths. Each turn (x, y) is paired with a knowledge graph K, which is composed of a collection of triplets (h, r, t), where h, t ∈ V (the set of entities) and r ∈ L (the set of relationships). Each word y t in a response belongs to either generic words W or knowledge graph entities V. The task is two-fold:
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
1. Given an input message x and a knowledge graph K, the goal is to generate a sequence {ŷ t } n t=1 that is not only as similar as possible to the ground-truth {y t } n t=1 , but contains correct knowledge graph entities to reflect the information. 2. After a knowledge graph is updated to K , where some triplets are revised to (h, r, t ) or (h, r , t), the generated sequence should contain correspondent knowledge graph entities in K to reflect the updated information.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To evaluate dynamic knowledge-grounded conversation models, we propose two types of evaluation metrics for validating two aspects described above.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
There are three metrics focusing on the knowledge-related capability.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Knowledge word accuracy (KW-Acc). Given the ground-truth sentence as the decoder inputs, at each time step, it evaluates how many knowledge graph entities are correctly predicted.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
KW-Acc = n t=1 P (ŷ t = y t | y 1 y 2 . . . y t−1 , y t ∈ V).
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For example, after perceiving the partial groundtruth response "If Jin-Xi not in" and knowing the next word should be a knowledge graph entity, KW-Acc measures if the model can predict the correct word "Yongshou Palace".
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Knowledge and generic word classification (KW/Generic). Given the ground-truth sentence as the decoder inputs, at each time step, it measures the capability of predicting the correct class (a knowledge graph entity or a generic word) and adopts micro-averaging. The true positive, false negative and false positive are formulated as:
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
y t ∼ P (· | y 1 y 2 . . . y t−1 ).
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Considering the knowledge graph entities in the reference y = {y t } n t=1 as positives, in the inference stage, we use the generated knowledge entities to compute true positive, false positive, and true negative, and adopt micro-averaging. TP = |{ŷ t ∈ {y t ∈ V} n t=1 ,ŷ t ∈ V} n t=1 |, FN = |{y t / ∈ {ŷ t ∈ V} n t=1 , y t ∈ V} n t=1 |, FP = |{ŷ t / ∈ {y t ∈ V} n t=1 ,ŷ t ∈ V} n t=1 |, y t ∼ P (· |ŷ 1ŷ2 . . .ŷ t−1 ).
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For example, after input a sentence "Where's JinXi?", if a model generates "Hi, Zhen-Huan, JinXi is in Yangxin-Palace." when reference is "JinXi is in Yongshou-Palace.", where bolded words are knowledge entities. Recall is 1 2 and precision is 1 3 .
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Each knowledge graph is randomly changed by (1) shuffling a batch (All), (2) replacing the predicted entities (Last1), or (3) replacing the last two steps of paths predicting the generated entities (Last2). We have two metrics focusing on the capability of adaptation.   Change rate. It measures if the responses are different from the original ones (with original knowledge graphs). The higher rate indicates that the model is more sensitive to a changed knowledge graph. Therefore, the higher rate may not be better, because some changes are worse. The following metric is proposed to deal with the issue, but change rate is still reported.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Accurate change rate. This measures if the original predicted entities are replaced with the hypothesis set, where this ensures that the updated responses generate knowledge graph entities according to the updated knowledge graphs.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
(1) In All, the hypothesis set is the collection of all entities in the new knowledge graph.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
(2) In Last1 and Last2, the hypothesis set is the randomly-selected substitutes.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
This section introduces the collected DyKgChat corpus for the target knowledge-grounded conversation generation task.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To build a corpus where the knowledge graphs would naturally evolves, we collect TV series conversations, considering that TV series often contain complex relationship evolution, such as  friends, jobs, and residences. We choose TV series with different languages and longer episodes. We download the scripts of a Chinese palace drama "Hou Gong Zhen Huan Zhuang" (HGZHZ; with 76 episodes and hundreds of characters) from Baidu Tieba, and the scripts of an English sitcom "Friends" (with 236 episodes and six main characters) 2 . Their paired knowledge graphs are manually constructed according to their wikis written by fans 34 . Noted that the knowledge graph of HGZHZ is mainly built upon the top twenty-five appeared characters.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The datasets are split 5% as validation data and 10% as testing data, where the split is based on multi-turn dialogues and balanced on speakers. The boundaries of dialogues are annotated in the original scripts. The tokenization of HGZHZ considers Chinese characters and knowledge entities; the tokenization of Friends considers spaceseparated tokens and knowledge entities. The data statistics after preprocessing is detailed in Table 2. The relation types r ∈ L of each knowledge graph and their percentages are listed in Table 3, and the knowledge graph entities are plotted as word clouds in Figure 2.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Due to the excessive labor of building dynamic knowledge graphs aligned with all episodes, we currently collect a fixed knowledge graph G containing all information that once exists for each TV series. To build the aligned dynamic knowledge 2 https://github.com/npow/ friends-chatbot 3 https://zh.wikipedia.org/wiki/後 宮 甄 嬛 傳 (電視劇) 4 https://friends.fandom.com/wiki/ Friends_Wiki graphs, we sample the top-five shortest paths on knowledge graphs from each source to each target, where the sources are knowledge entities in the input message and the scene {x t ∈ V}, and the targets are knowledge entities in the ground-truth response {y t ∈ V}. We manually check whether the selected number of shortest paths are able to cover most of the used relational paths. The dynamic knowledge graphs are built based on an ensemble of the following possible subgraphs:
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
• The sample for each single-turn dialogue.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
• The sample for each multi-turn dialogue.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
• The manually-annotated subgraph for each period. While the first rule is adopted for simplicity, the preliminary models should at least work on this type of subgraphs. The subgraphs are defined as the dynamic knowledge graphs {K}, which are updated every single-turn dialogue.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Data imbalance. As shown in Table 2, the turns with knowledge graph entities are about 58.9% and 15.93% of HGZHZ and Friends respectively. Apparently in Friends, the training data with knowledge graph entities are too small, so fine- tuning on this subset with knowledge graph entities might be required.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Shortest paths. The lengths of shortest paths from sources to targets are shown in Figure 3. Most probabilities lie on two and three hops rather than zero and one hop, so key-value extraction based text generative models (Eric et al., 2017;Levy et al., 2017;Qian et al., 2018) are not suitable for this task.On the other hand, multi-hop reasoning might be useful for better retrieving correct knowledge graph entities.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Dynamics. The distribution of graph edit distances among dynamic knowledge graphs are 57.24 ± 24.34 and 38.16 ± 15.99 for HGZHZ and Friends respectively, revealing that the graph dynamics are spread out: some are slightly changed while some are largely changed, which matches our intuition.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Knowledge-Grounded Neural Conversation Model
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To our best knowledge, no prior work focused on dynamic knowledge-grounded conversation; thus we propose Qadpt as the preliminary model. As illustrated in Figure 4, the model is composed of (1) a Seq2Seq model with a controller, which decides to predict knowledge graph entities k ∈ V or generic words w ∈ W, and (2) a reasoning model, which retrieves the relational paths in the knowledge graph.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Qadpt is based on a Seq2Seq model (Sutskever et al., 2014;Vinyals and Le, 2015), where the encoder encodes an input message x into a vector e(x) as the initial state of the decoder. At each time step t, the decoder produces a vector d t conditioned on the ground-truth or predicted y 1 y 2 . . . y t−1 . Note that we use gated recurrent unit (GRU)  in our experiments.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Each predicted d t is used for three parts: output projection, controller, and reasoning. For output projection, the predicted d t is transformed into a distribution w t over generic words W by a projection layer.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To decide which vocabulary set (knowledge graph entities V or generic words W) to use, the vector d t is transformed to a controller c t , which is a widely-used component (Eric et al., 2017;Zhu et al., 2017;Ke et al., 2018;Zhou et al., 2018b;Xing et al., 2017) similar to copy mechanism (Gu et al., 2016;Merity et al., 2017;. The controller c t is the probability of choosing from knowledge graph entities V, while 1 − c t is the probability of choosing from generic words W. Note that we take the controller as a special symbol KB in generic words, so the term 1 − c t is already multiplied to w t . The controller here can be flexibly replaced with any other model.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
w t = P (W | y 1 y 2 . . . y t−1 , e(x)), (4) c t = P (KB | y 1 y 2 . . . y t−1 , e(x)),
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
where φ is the output projection layer, and k t is the predicted distribution over knowledge graph entities V (detailed in subsection 4.3), and o t is the produced distribution over all vocabularies.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To ensure that Qadpt can zero-shot adapt to dynamic knowledge graphs, instead of using attention mechanism on graph embeddings (Ghazvininejad et al., 2018;Zhou et al., 2018b), we leverage the concept of multi-hop reasoning (Lao et al., 2011). The reasoning procedure can be divided into two stages: (1) forming a transition matrix and (2) reasoning multiple hops by a Markov chain. In the first stage, a transition matrix T t is viewed as multiplication of a path matrix R t and the adjacency matrix A of a knowledge graph K. The adjacency matrix is a binary matrix indicating if the relations between two entities exist. The path matrix is a linear transformation θ of d t , and represents the probability distribution of each head h ∈ V choosing each relation type r ∈ L. Note that a relation type self-loop is added.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
where R t ∈ IR |V|×1×|L| , A ∈ IR |V|×|L|×|V| , and T t ∈ IR |V|×|V| . In the second stage, a binary vector s ∈ IR |V| is computed to indicate whether each knowledge entity exists in the input message x. First, the vector s is multiplied by the transition matrix. A new vector s T t is then produced to denote the new probability distribution over knowledge entities after one-hop reasoning. After N times reasoning 5 , the final probability distribution over knowledge entities is taken as the generated knowledge entity distribution k t :
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The loss function is the cross-entropy of the predicted word o t and the ground-truth distribution:
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
where ψ is the parameters of GRU layers. Compared to prior work, the proposed reasoning approach explicitly models the knowledge reasoning path, so an updated knowledge graphs will definitely change the results without retraining. 5 We choose N = 6 because of the maximum length of shortest paths in Figure 3 
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Because this reasoning method is stochastic, we compute the probabilities of the possible reasoning paths by the reasoning model, and infer the one with the largest probability as the retrieved reasoning path.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The recent knowledge-grounded conversation models (Sordoni et al., 2015;Ghazvininejad et al., 2018;Zhu et al., 2017;Zhou et al., 2018b) generated responses conditioned on conversation history and external knowledge. Ghazvininejad et al. (2018) used memory networks (Weston et al., 2015b,a;Sukhbaatar et al., 2015) to attend on external facts, and added the encoded information to the decoding process. Zhu et al. (2017) added a copy mechanism (Gu et al., 2016;Merity et al., 2017; for improving its performance. Zhou et al. (2018b) presented two-level graph attention mechanisms (Veličković et al., 2018) to produce more informative responses.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For knowledge from unstructured texts, Ghazvininejad et al. (2018) used bag-of-word representations and Long et al. (2017) applied a convolutional neural network to encode the whole texts. With structured knowledge graphs, Zhu et al. (2017) and Zhou et al. (2018b) utilized graph embedding methods (e.g., TransE (Bordes et al., 2013)) to encode each triplet.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The above methods generated responses without explicit relationship to each external knowledge triplet. Therefore, when a triplet is added or deleted, it is unknown whether their generated responses can change accordingly. Moon et al. (2019) recently presented a similar concept, walking on the knowledge graph, for response generation. Nonetheless, their purpose is to find explainable path on a large-scaled knowledge graph instead of adaptation with the changed knowledge graphs. Hence, the proposed attention-based graph walker may suffer from the same issue as previous embedding-based methods.   
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
We leverage multi-hop reasoning (Lao et al., 2011) to allow our model to quickly adapt to dynamic knowledge graphs. Recently, prior work used convolutional neural network (Toutanova et al., 2015), recurrent neural network (Neelakantan et al., 2015;Das et al., 2017), and reinforcement learning Das et al., 2018;Shen et al., 2018) to model multi-hop reasoning on knowledge graphs, and has proved this concept useful in link prediction. These reasoning models, however, have not yet explored on dialogue generation. The proposed model is the first attempt at adapting conversations via a reasoning procedure.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For all models, we use gated recurrent unit (GRU) based Seq2Seq models Chung et al., 2014;Vinyals and Le, 2015). Both encoder and decoder for HGZHZ are 256 dimension with 1 layer; ones for Friends are 128 dimension with 1 layer. We benchmark the task, dynamic knowledgegrounded dialogue generation, and corpus DyKgChat by providing a detailed comparison between the prior conversational models and our proposed model as the preliminary experiments. We evaluate their capability of quick adaptation by randomized whole, last 1, last 2 reasoning paths as described in Section 2.1.2. We evaluate the produced responses by sentence-level BLEU-2 (Papineni et al., 2002;Liu et al., 2016), perplexity, distinct-n , and our proposed metrics for predicting knowledge entities descrin section 2.1.1.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
Because of the significant data imbalance of Friends, we first train on whole training data, and then fine-tune the models using the subset containing knowledge entities. Early stopping is adopted in all experiments.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
We compare our model with prior knowledgegrounded conversation models: the memory network (Ghazvininejad et al., 2018) and knowledgeaware model (KAware) (Zhu et al., 2017;Zhou et al., 2018b). We also leverage the topic-aware model (TAware) (Xing et al., 2017;Wu et al., 2018;Zhou et al., 2018a) by attending on knowledge graphs and using two separate output projection layers (generic words and all knowledge graph entities). In our experiments, MemNet is modified for fair comparison, where the memory pool of MemNet stores TransE embeddings of knowledge triples (Zhou et al., 2018b). The maximum number of the stored triplets are set to the maximum size of all knowledge graphs for    (Weston et al., 2015b) is also implemented (MemNet+multi) 6 . To empirically achieve better performance, we also utilize the attention of MemNet for TAware and KAware. Moreover, we empirically find that multi-hop MemNet deteriorate the performance of KAware (compared to one-hop), while it could enhance the performance of TAware. A standard Seq2Seq model (Vinyals and Le, 2015) is also shown as a baseline without using external knowledge. We also leverage multi-hop MemNet and the attention of TAware to strength Qadpt (+multi and +TAware).
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
As shown in Table 4, MemNet, TAware and KAware significantly change when the knowledge graphs are largely updated (All) and can also achieve good accurate change rate. For them, the more parts updated (All >> Last2 > Last1), the more changes and accurate changes. However, when the knowledge graphs are slightly updated (Last1 and Last2), the portion of accurate changes over total changes (e.g., the Last1 score 1.17/31.78 for HGZHZ with MemNet model) is significantly low. Among the baselines, KAware has better performance on Last1. On the other hand, Qadpt outperforms all baselines when the knowledge graphs slightly change (Last1 and Last2) in terms of accurate change rate. The proportion of accurate changes over total changes also show significantly better performance than the prior models. Figure 5 shows the distribution of lengths of the inferred relation paths for Qadpt models. After combining TAware or MemNet, the distribution becomes more similar to the test data. Table 5 shows the results of the proposed metrics for correctly predicting knowledge graph entities. On both HGZHZ and Friends, TAware+multi and Qadpt significantly outperform MemNet for KW-Acc and KW/Generic, and MemNet outperforms all other models by KW/Generic precision (100%). This demonstrates that these models can better predict knowledge graph entities, but are slightly worse at making good choices of when to predict generic words (KW/Generic). Table 6 presents the BLEU-2 scores (as recommended in the prior work (Liu et al., 2016)), perplexity (PPL), and distinct scores. The results show that all models have similar levels of BLEU-2 and PPL, while Qadpt+multi has slightly better distinct scores. The results suggest the same claim as Liu et al. (2016) 
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
To perform human evaluation, we randomly select examples from the knowledge-related outputs of all models, because it is difficult for human to distinguish which generic response is better. We recruit fifteen annotators to judge the results. Each annotator was randomly assigned with 20 examples, and was guided to rank the results of five models: Seq2Seq, MemNet, TAware, KAware, and Qadpt. They were asked to rank all results according to two criteria: (1) fluency and (2) information. Fluency measures which output is more proper as a response to a given input message. Information measures which output contains more correct information (in terms of knowledge words here) according to a given input message and a referred response. The evaluation results are classified into "win", "tie", and "lose" for comparison. The human evaluation results and the annotator agreement in the form of Cohen's kappa (Cohen, 1960) are reported in Table 7. According to a magnitude guideline (Landis and Koch, 1977), most agreements are substantial (0.6-0.8), while some agreements of Friends are moderate (0.4-0.6). In most cases of Table 7, Qadpt outperforms other four models. However, in Friends, Qadpt, Mem-Net, and TAware tie closely. The reason might be the lower agreements of Friends, or only the similar trend with automatic evaluation metrics. There are two extra spots. First, Qadpt wins Mem-Net and TAware less times than winning Seq2Seq and KAware, which aligns with Table 5 and Table 6. Second, Qadpt wins baselines more often by fluency than by information, and much more ties happen in the infomation fields than the fluency fields. This is probably due to the selection of knowledge-contained examples. Hence there is no much difference when seeing the information amount of models. Overall, the human evaluation results can be considered as reference because of the substantial agreement among annotators and the similar trend with automatic evaluation.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
The results demonstrate that MemNet, TAware and Qadpt generally perform better than than the other two baselines, and they excel at different aspects. MemNet can successfully incorporate knowledge graphs and generate sentences with both appropriate knowledge entities and generic words. In contrast, TAware and Qadpt predict more correct knowledge entities but tend to diminish generic words.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
For the scenario of zero-shot adaptation, Mem-Net and TAware show their ability to update responses when the knowledge graphs are largely changed. On the other hand, Qadpt is better to capture minor dynamic changes ( Last1 and Last2) and updates the responses according to the new knowledge graphs. Some examples are given in Appendix. This demonstrates that MemNet and TAware attend on the whole graph instead of focusing on the most influential part.
DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
This paper presents a new task, dynamic knowledge-grounded conversation generation, and a new dataset DyKgChat for evaluation. The dataset is currently provided with a Chinese and an English TV series as well as their correspondent knowledge graphs. This paper also benchmarks the task and dataset by proposing automatic evaluation metrics and baseline models, which can motivate the future research directions.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Open-domain dialogue generation (Shang et al., 2015a;Vinyals and Le, 2015;Sordoni et al., 2015a) intends to produce coherent responses given dialogue history. Nevertheless, it suffers from data insufficiency problem as there may exist many potential responses for a given dialogue history . An ideal way of exploring the potential responses is to train the model by chatting with real users, which is usually time-consuming and labor-intensive in practice. Although replacing a real user with a user simulator could address the issue, the simulator only roughly approximates real user statistics, and its development process is costly (Su et al., 2016).
Counterfactual Off-Policy Training for Neural Dialogue Generation
In contrast, humans could independently reason potential responses based on past experiences from the true environment. Having observed a response, one might naturally ask himself or herself: "What would happen if I respond differently, while everything else in the environment remains the same." Answering the question will result in a potential response (as an example in Figure 1), and it is beneficial for improving future decision making (Roese, 1997). The potential response inferred in hindsight is called a counterfactual response, where the concept "counterfactual" describes the posterior process of reasoning the outcome of alternative actions (i.e., a different responding policy) that could have been taken while keeping everything else unchanged (Buesing et al., 2019).
Counterfactual Off-Policy Training for Neural Dialogue Generation
Motivated by this, we propose a counterfactual off-policy training (COPT) approach to explore potential responses. Building upon the adversarial learning framework, COPT casts a dialogue generator as a structural causal model (SCM), which describes a generation process with two ingredients: scenarios and causal mechanisms (Wright, 1920;Buesing et al., 2019). The scenario is a random noise variable that captures all unobserved yet relevant aspects of the environment, i.e., user profiles. The causal mechanism is a deterministic function that takes a scenario and dialogue history as input and outputs a response. In this way, reasoning a counterfactual response in an observed response's environment can be achieved by feeding the scenario of the observed response into the causal mechanism. After generating the counterfactual response, the generator will receive a reward from a discriminator and optimize itself accordingly.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Intuitively, a counterfactual response is synthesized by grounding the model in the scenario where an observed response occurs, rather than the scenario sampled from scratch as standard adversarial learning-based approaches. This improves the quality of the synthesized responses and subsequently benefits the model that learns from the synthesis. To verify the effectiveness of our approach, we conduct experiments on the public available DailyDialog dataset (Li et al., 2017b). Experimental results show that our approach significantly outperforms previous adversarial learning-based approaches in both automatic and human evaluations. The contributions of this paper are summarized as follows:
Counterfactual Off-Policy Training for Neural Dialogue Generation
• We connect the concept of counterfactual reasoning with the dialogue generation by casting the dialogue generation model as a structural causal model.
Counterfactual Off-Policy Training for Neural Dialogue Generation
• Our counterfactual response is of higher quality than the response synthesized from scratch in standard adversarial learning-based dialogue generation model.
Counterfactual Off-Policy Training for Neural Dialogue Generation
• Our approach is model-agnostic and can be applied to any adversarial learning-based dialogue generation model.
Counterfactual Off-Policy Training for Neural Dialogue Generation
The counterfactual reasoning is a concept derived from psychology. It describes the human capacity to learn from experience by reasoning the outcome of an alternative action that could have been taken (Pearl and Mackenzie, 2018). Combined with the SCM, counterfactual reasoning improves the performance of policy evaluation in reinforcement learning (Buesing et al., 2019;Oberst and Sontag, 2019). In the area of NLP, counterfactual reasoning in previous work is mainly used for data augmentation (Qin et al., 2019;Fu et al., 2020;Kaushik et al., 2020), which rewrites the original data given a counterfactual label or condition. In this paper, we connect the concept of counterfactual reasoning with the dialogue generation and are the first to cast a generation model as an SCM under the adversarial learning framework.
Counterfactual Off-Policy Training for Neural Dialogue Generation
We cast a dialogue generation model as an SCM to explore potential responses by counterfactual reasoning during the training process. We will first review the concept of the SCM (Sec. 3.2), and then introduce our COPT approach (Sec. 3.3).
Counterfactual Off-Policy Training for Neural Dialogue Generation
We use capital letters for random variables (e.g., V ), lowercase letters for instances of random variables (e.g., v), and bold letters for vectors (e.g., V = {V 1 , ..., V N }). During the training process, we denote the response generated by COPT as counterfactual response. In contrast, the response of standard adversarial learning-based dialogue Left: An SCM with random variables V , scenarios U , and causal mechanisms F represented by colored squares. Right: A new SCM after taking an intervention on the left SCM. The original causal mechanism f 2 (V 1 , U 2 ) (denoted by the orange square) is replaced by f T 2 (V 1 , U 2 ) (denoted by the purple square). generation (i.e., REGS Li et al., 2017a) is denoted as standard response.
Counterfactual Off-Policy Training for Neural Dialogue Generation
A structural causal model over random variables (Buesing et al., 2019). U is called scenarios, and F is called causal mechanisms. Figure 2 (Left) shows an example of an SCM. Each random vari-
Counterfactual Off-Policy Training for Neural Dialogue Generation
During the training process, we cast a dialogue generation model as an SCM over two random variables: dialogue history X and response Y . This is achieved by converting the conditional distribution P (Y |X) into a deterministic function Y = f π (X, U ) (for more details see Sec. 3.3). The scenario U is a random noise variable that captures all unobserved yet relevant properties, like user profiles. The causal mechanism is denoted as f π to highlight the role of the policy (parameters) π of the model. The dialogue generation SCM makes it possible to sample counterfactual responses in the scenario where observed responses occur. This improves the quality of synthesized responses and subsequently helps the model to explore the highreward area of the potential response space in the training process.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Intervention in SCM Given an SCM, an intervention T is defined as the replacement of some causal mechanisms. Figure 2 shows an example of intervention. The original causal mechanism f 2 (V 1 , U 2 ) in the left SCM is replaced with f T 2 (V 1 , U 2 ), resulting in a new SCM in the right. Accordingly, intervention in our dialogue gener-ation SCM denotes the update of the policy. For instance, the update from the behavior policy µ that generates observed responses to the target policy π that we aim to learn is the intervention of replacing f µ (X, U ) with f π (X, U ).
Counterfactual Off-Policy Training for Neural Dialogue Generation
Counterfactual Reasoning in SCM Given an SCM and observed a variable V i = v i , counterfactual reasoning answers the question: "What the variable V i would have been if I take an intervention T while remaining everything else unchanged". In this way, generating a counterfactual response can be seen as querying: "Having observed a response Y = y, what the response Y would have been if I take an intervention by following the target policy π, rather than the behavior policy µ that generates the observed responses".
Counterfactual Off-Policy Training for Neural Dialogue Generation
Typically, counterfactual reasoning answers the question by the following steps (as Figure 3):
Counterfactual Off-Policy Training for Neural Dialogue Generation
• Take an intervention by replacing the causal mechanism f µ (X, U ) with f π (X, U ).
Counterfactual Off-Policy Training for Neural Dialogue Generation
• Reason a counterfactual responseŷ = f π (x, u) by the resulting new SCM.
Counterfactual Off-Policy Training for Neural Dialogue Generation
In the following sections, we denote an observed response from the training set as Y and a modelgenerated response asŶ .
Counterfactual Off-Policy Training for Neural Dialogue Generation
Our COPT approach is model-agnostic and can be applied to any adversarial learning-based dialogue generation model. Without loss of generality, we take the combination of COPT and the reward for every generation step (REGS) model (Li et al., 2017a) as an example in this section. It consists of two main components: a generator G and a discriminator D.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Generator The generator G is a sequence to sequence (Seq2Seq) model (Sutskever et al., 2014) equipped with the attention mechanism (Bahdanau et al., 2015;Luong et al., 2015). During the encoding process, G reads the dialogue history into hidden states using an encoder LSTM (Hochreiter and Schmidhuber, 1997):
Counterfactual Off-Policy Training for Neural Dialogue Generation
where X i is the i-th word of the dialogue history, and H i denotes the corresponding hidden state.  Figure 3: The architecture of our COPT approach. π is the target policy that we aim to learn. µ is the behavior policy that generates observed responses. First, we infer the scenario u where the observed response occurs. Then we update the policy from µ to π, which can be seen as an intervention on the left SCM and results in the right SCM. Then, the counterfactual response is reasoned in the inferred scenario u by the causal mechanism Y = f π (X, U ).
Counterfactual Off-Policy Training for Neural Dialogue Generation
At the j-th decoding time step, the hidden states are summarized into a context vector C j by the attention mechanism. Subsequently, G predicts the distribution of the next word over the vocabulary by a decoder LSTM:
Counterfactual Off-Policy Training for Neural Dialogue Generation
where the bracket [·,·] denotes concatenation, and e(·) denotes the embedding of a word. S j is the j-th hidden state of the decoder LSTM.Ŷ j−1 is the word generated in the previous time step. O is the output matrix. We use the superscript in P π j to highlight the role of the policy (parameters of G).
Counterfactual Off-Policy Training for Neural Dialogue Generation
Adversarial learning-based dialogue generation model is optimized according to the reward of responses sampled from P π j (Ŷ j |X,Ŷ 1:j−1 ) ∈ R |V | (abbreviated as P π j in the following), where |V | is the vocabulary size. Using the Gumbel-Max Trick (Luce, 2012), the sampling process can be achieved by:
Counterfactual Off-Policy Training for Neural Dialogue Generation
where the element of U j follows the standard Gumbel distribution. In this way, the generator turns into a Gumbel-Max SCM (Oberst and Sontag, 2019), whose scenarios and causal mechanisms are represented by U j and Equation 4, respectively. From the perspective of the SCM, each response is generated in a scenario. For instance, a standard response is produced in a scenario sampled from scratch. In contrast, the scenario for a counterfactual response is inferred from an observed response y = {y j | y j = arg max y j (log p * j + u j )}, where * is the user's policy that generates the observed response in the true environment. However, the user's policy is not available in practice, which hinders the posterior inference of the scenario. To this end, we introduce a behavior policy µ instead and learn it by minimizing the MLE loss on observed responses. In this way, an observed response can be seen as generating in a scenario u j while following the policy µ: y j = arg max y j (log p µ j + u j ). According to Oberst and Sontag (2019), there are two ways to infer the scenario u j in hindsight from y j = arg max y j (log p µ j + u j ) given y j and µ. One way is the rejection sampling, which samples u j from the standard Gumbel distribution and rejects those where y j = arg max y j (log p µ j + u j ). The other way of the posterior inference makes use of the properties of the shifted Gumbel g = log p µ j + u j : the maximum of g follows the standard Gumbel distribution and is independent with the argmax of g (Maddison et al., 2014). Therefore, g can be obtained by first sampling a maximum and then sampling the remaining elements truncated at the maximum. And u j is subsequently computed by subtracting log p µ j from g. We employ the second method to infer the scenario in COPT because it is more time-efficient than rejection sampling 1 .
Counterfactual Off-Policy Training for Neural Dialogue Generation
Given the scenario inferred from the observed response, COPT reasons the counterfactual response by feeding the dialogue history and the scenario into the SCM (Equation 4). Then the discriminator evaluates the counterfactual response and returns a reward to the generator. Note that the counterfactual response and the SCM are utilized for the training process. During the inference process, responses are generated in the same way as the standard adversarial learning-based dialogue generation (beam search or sampling from P π j , we use the former in our approach) because the observed response is not available.
Counterfactual Off-Policy Training for Neural Dialogue Generation
The discriminator D provides a reward for each generation step. It takes as input the dialogue history X, the wordỸ j produced in the current generation step, and the prefixỸ 1:j−1 in previous steps, whereỸ ∈ {Y ,Ŷ } can be either an observed response or a model-generated response. The output reward D(Ỹ j |X,Ỹ 1:j−1 ) is the probability thatỸ j is human-generated. Concretely, D first reads X andỸ 1:j with an encoder-decoder model. Then, it computes the reward by a Multi-Layer Perceptron (MLP), which takes as input the last hidden state of the decoder.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Adversarial Learning We train G and D under the adversarial learning framework, where G tries to fool D by generating human-like responses while D aims to distinguish between model-generated and human-generated (the observed) responses. Since a response is a sequence of discrete tokens, we pass by the gradient of D to G using the policy gradient algorithm. In this way, G converts into an agent whose partially generated response and parameters define a state and a policy, respectively. At each generation step, the agent takes an action by producing a word and observes a reward from D to update its policy.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Note that there are two policies in COPT: the target policy that we aim to learn and the behavior policy used for the reasoning of scenarios. The behavior policy is pre-trained and then froze during adversarial learning because it aims to maximize the likelihood of a fixed set of observed responses. Introducing the behavior policy makes COPT an off-policy approach because the counterfactual response, from which the target policy learns, is not entirely based on the target policy itself.
Counterfactual Off-Policy Training for Neural Dialogue Generation
The goal of the generator is to minimize the negative expected reward: J G (θ) = −EŶ 1:j ∼G D(Ŷ j |X,Ŷ 1:j−1 ), where θ is the parameters of π. The gradient of θ can be derived by the 
Counterfactual Off-Policy Training for Neural Dialogue Generation
where G π (Ŷ j |X,Ŷ 1:j−1 ) is the probability of gen-eratingŶ j with the policy π given X andŶ 1:j−1 .
Counterfactual Off-Policy Training for Neural Dialogue Generation
The discriminator distinguishes between observed responses and model-generated responses. This is achieved by minimizing the following loss:
Counterfactual Off-Policy Training for Neural Dialogue Generation
where φ is the parameters of D. As a positive instance, Y 1:j is a prefix randomly sampled from observed response set S. A negative instanceŶ 1:j for training D is a prefix of a standard response, rather than a counterfactual response. This is because the latter is of higher quality than the former (as shown in Sec. 4.7).
Counterfactual Off-Policy Training for Neural Dialogue Generation
Pre-training Initialized with different parameters, π and µ are pre-trained on the training set with MLE loss. The pre-training of D depends on the specific model that COPT applied to. For example, REGS pre-trains D on the prefix of a response. In contrast, the discriminator of StepGAN (Tuan and Lee, 2019) is randomly initialized during the adversarial learning process. The overall algorithm of COPT is summarized as Algorithm 1. 
Counterfactual Off-Policy Training for Neural Dialogue Generation
The experiments are conducted on the DailyDialog dataset (Li et al., 2017b). 2 It is a multi-turn dialogue dataset and covers various topics of daily life. The dataset has already been divided into training, validation, and test sets, as shown in Table 1. Given a dialogue that consists of K utterances, we divide it into K-1 instances. Each instance has at most three continuous utterances. The last utterance is the response, and the previous utterances are concatenated as the dialogue history.
Counterfactual Off-Policy Training for Neural Dialogue Generation
We compare COPT with the following dialogue generation models:
Counterfactual Off-Policy Training for Neural Dialogue Generation
• HRED (Serban et al., 2016): The hierarchical recurrent encoder-decoder. An implementation by Park et al. (2018) is available 3 .
Counterfactual Off-Policy Training for Neural Dialogue Generation
• REGS (Li et al., 2017a): Reward for every generation step. Its discriminator is trained on partially generated responses to provide a reward for each generation step.
Counterfactual Off-Policy Training for Neural Dialogue Generation
• DPGAN : The diversitypromoting GAN introduces a language model based discriminator to encourage the generation of informative responses. 4
Counterfactual Off-Policy Training for Neural Dialogue Generation
• StepGAN (Tuan and Lee, 2019): The stepwise GAN trains the discriminator by maximizing the average of state-action values of observed responses. During the adversarial learning process, the discriminator assigns scores for every generation step in the same way as REGS.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Distinct from previous approaches, COPT casts a dialogue generation model as an SCM and trains it  on counterfactual responses. It is model-agnostic and can be applied to any adversarial learningbased dialogue generation model, such as REGS, DPGAN, and StepGAN.
Counterfactual Off-Policy Training for Neural Dialogue Generation
We implement REGS, StepGAN, and their variants with COPT using OpenNMT (Klein et al., 2017), an open-source framework for building sequence to sequence models. We manually tune the parameters according to the perplexity on the validation set. The vocabulary consists of the most frequent 10,000 words. Including more words (up to 17,438, the total number of DailyDialog vocabulary) observes no improvement but takes more time for training. We use 300 dimensional GloVe (Pennington et al., 2014) vectors to initialize word embeddings. Both the encoder and the decoder are a two-layer LSTM in G and a single layer LSTM in D. The number of hidden units is 500. During the adversarial learning process, we use the ADAM algorithm to alternately optimize G and D for one batch and five batches. The batch size is 64. We have tested the learning rate from 1e-6 to 1e-3. REGS+COPT and StepGAN+COPT achieve the best performance on 1e-5. The number of parameters for all the baselines is in a range of 21M to 26M. Equipping an adversarial learning baseline with COPT will introduce extra parameters with the same amount of the generator's parameters. Contributed by the behavior policy, the parameters are learned by pre-training, and COPT will not increase the number of trainable parameters in adversarial learning. Table 2 shows the average training time. COPT may increase the training time due to the posterior inference of scenarios. But it facilitates the exploration of the high-reward area of the potential response space and subsequently improves the quality of responses.  Table 3: Automatic evaluation results of distinct-1 (Dist-1), distinct-2 (Dist-2), and BLEU scores.
Counterfactual Off-Policy Training for Neural Dialogue Generation
Dialogue History A: This is our counter-offer. B: We are sincere to make business with you, but the difference between your counter-offer and our price is too great.  
Counterfactual Off-Policy Training for Neural Dialogue Generation
Automatic Evaluation We evaluate the diversity and the relevance of generated responses using distinct  and BLEU (Papineni et al., 2002), respectively. The distinct-k is the number of distinct k-grams normalized by the number of words of responses. Since BLEU might correlate weakly with human judgments of quality in the single-reference setting (Liu et al., 2016), we use the multi-reference DailyDialog test set (Gupta et al., 2019), where each instance is augmented with four human-written diverse responses. 5
Counterfactual Off-Policy Training for Neural Dialogue Generation
The human evaluation is conducted on 200 instances randomly sampled from the test set. We create a project on Amazon Mechanical Turk (Buhrmester et al., 2016) (AMT) and employ five AMT workers to give a preference between two responses generated by our approach and a baseline. 6 To maintain the quality of the evaluation, the task is visible to workers whose approve rate is greater than 95%, and the number of approved is greater than 500. Table 3 shows the results of automatic evaluation. Both REGS and StepGAN outperform HRED in distinct-1 and distinct-2, indicating that adversarial learning is beneficial for improving the diversity of responses. There is no increase in DPGAN compared with HRED in our experiments. We believe this is because the scale of the DailyDialog dataset is not large enough for sufficiently training the language model based discriminator. For the same reason, COPT is not added to DPGAN. After introducing COPT, both distinct-1 and distinct-2 in REGS and StepGAN further increase, and the improvement is significant (t-test, p <0.01). This suggests that COPT is model-agnostic to adversarial learning-based approaches and helps to promote the diversity. In terms of BLEU in Table 3, both REGS and StepGAN achieve higher BLEU scores with COPT, and the improvements of BLEU-1 and BLEU-2 are significant (p <0.05). This demonstrates the effectiveness of COPT in improving the relevance of responses. The less significant result of BLEU-3 and BLEU-4 is mainly due to the sparsity of tri-grams and four-grams, which are harder to be covered by references than uni-grams and bi-grams.
Counterfactual Off-Policy Training for Neural Dialogue Generation
The human evaluation results are shown in Table 5. Our approach is clearly preferred as it   Table 5: Wins, losses, and ties (in %) of our approach against baselines based on the human evaluation. has more winning instances than losing instances (p <0.01). The results indicate that COPT helps improve the quality of responses. Following Zhou et al. (2018) and Ke et al. (2018), we measure the agreement of annotators using inter-rater consistency. The percentage of instances that at least three annotators have the same preference (3/5 agreement) is 84.18%. The percentage for 4/5 agreement is 46.89%. Table 4 shows an example of responses generated by baselines and our approach. The response of DPGAN sometimes is not fluent and can be very long. We believe this is also because the scale of the DailyDialog dataset is not enough for the language model discriminator. The response of HRED is not as informative as that of our approach. Its first part is generic, and what the pronoun "that" refers to is not clear. The response of StepGAN is not infor-mative enough as well. In contrast, the response of REGS is quite informative, but its content is not entirely relevant to the dialogue history. After introducing COPT, the responses of REGS+COPT and StepGAN+COPT propose offering a discount to address Person B's concern of the price, which is both informative and relevant.
Counterfactual Off-Policy Training for Neural Dialogue Generation
To further analyze COPT's effectiveness in exploring the high-reward area of the potential response space during the training process, we compare the reward of a counterfactual response and a standard response on the same 10,000 randomly sampled training instances. However, the comparison between the two types of responses could be biased if their rewards are computed by different discriminators. Besides, the quality of responses is determined not only by the way they generated (with or without COPT) but also by the generator. To focus on the analysis of COPT and eliminate the bias between generators and discriminators, we generate and evaluate the two types of responses using an identical generator and its corresponding discriminator. Here, we use REGS+COPT and StepGAN+COPT as testbeds because they could generate both the two types of responses. Figure 4 shows the distribution of rewards and the average reward. The percentage of counterfactual responses in the high reward interval (0.66, 1.00] is higher than that of standard responses. Meanwhile, counterfactual responses generated with COPT achieve a higher average than standard responses. The results demonstrate the effectiveness of the counterfactual response in exploring the high-reward area of the potential response space during the training process. Note that the distribution and the average between different epochs are not comparable due to the update of the discriminator as the training processes.
Counterfactual Off-Policy Training for Neural Dialogue Generation
We propose a model-agnostic approach, COPT, that can be applied to any adversarial learning-based dialogue generation models. In contrast to existing approaches, it learns on counterfactual responses inferred from the structural causal model, taking advantage of observed responses. This helps the model to explore the high-reward area of the potential response space. Experiments show that the COPT significantly improves the quality of the generated responses, which demonstrates the effectiveness of this approach.
Deep Reinforcement Learning for Dialogue Generation
Neural response generation Shang et al., 2015;Vinyals and Le, 2015;Li et al., 2016a;Wen et al., 2015;Yao et al., 2015;Luan et al., 2016;Xu et al., 2016;Li et al., 2016b; is of growing interest. The LSTM sequence-to-sequence (SEQ2SEQ) model (Sutskever et al., 2014) is one type of neural generation model that maximizes the probability of generating a response given the previous dialogue turn. This approach enables the incorporation of rich context when mapping between consecutive dialogue turns  in a way not possible, for example, with MT-based dialogue models (Ritter et al., 2011).
Deep Reinforcement Learning for Dialogue Generation
Despite the success of SEQ2SEQ models in dialogue generation, two problems emerge: First, SEQ2SEQ models are trained by predicting the next dialogue turn in a given conversational context using the maximum-likelihood estimation (MLE) objective function. However, it is not clear how well MLE approximates the real-world goal of chatbot development: teaching a machine to converse with humans, while providing interesting, diverse, and informative feedback that keeps users engaged. One concrete example is that SEQ2SEQ models tend to generate highly generic responses such as "I don't know" regardless of the input Li et al., 2016a). This can be ascribed to the high frequency of generic responses found in the training set and their compatibility with a diverse range of conversational contexts. Yet "I don't know" is apparently not a good action to take, since it closes the conversation down.
Deep Reinforcement Learning for Dialogue Generation
Another common problem, illustrated in the two sample conversations on the left of Table 1, is that the system becomes stuck in an infinite loop of repetitive responses. This is due to MLE-based SEQ2SEQ models' inability to account for repetition. In example 2 (bottom left), the dialogue falls into an infinite loop after three turns, with both agents generating dull, generic utterances like i don't know what you are talking about and you don't know what you are saying. Looking at the entire conversation, utterance (4) turns out to be a bad action to take because it offers no way of continuing the conversation. 1 Table 1: Left Column: Dialogue simulation between two agents using a 4-layer LSTM encoder-decoder trained on the OpenSubtitles dataset. The first turn (index 1) is input by the authors. Then the two agents take turns conversing, taking as input the other agent's prior generated turn. The output is generated using the mutual information model (Li et al., 2015) in which an N-best list is first obtained using beam search based on p(t|s) and reranked by linearly combining the backward probability p(s|t), where t and s respectively denote targets and sources. Right Column: Dialogue simulated using the proposed reinforcement learning model. The new model has more forward-looking utterances (questions like "Why are you asking?" and offers like "I'll come with you") and lasts longer before it falls into conversational black holes.
Deep Reinforcement Learning for Dialogue Generation
These challenges suggest we need a conversation framework that has the ability to (1) integrate developer-defined rewards that better mimic the true goal of chatbot development and (2) model the longterm influence of a generated response in an ongoing dialogue.
Deep Reinforcement Learning for Dialogue Generation
To achieve these goals, we draw on the insights of reinforcement learning, which have been widely applied in MDP and POMDP dialogue systems (see Related Work section for details). We introduce a neural reinforcement learning (RL) generation method, which can optimize long-term rewards designed by system developers. Our model uses the encoderdecoder architecture as its backbone, and simulates conversation between two virtual agents to explore the space of possible actions while learning to maximize expected reward. We define simple heuristic approximations to rewards that characterize good conversations: good conversations are forward-looking (Allwood et al., 1992) or interactive (a turn suggests a following turn), informative, and coherent. The parameters of an encoder-decoder RNN define a policy over an infinite action space consisting of all possible utterances. The agent learns a policy by optimizing the long-term developer-defined reward from ongoing dialogue simulations using policy gradient methods (Williams, 1992), rather than the MLE objective defined in standard SEQ2SEQ models.
Deep Reinforcement Learning for Dialogue Generation
Our model thus integrates the power of SEQ2SEQ systems to learn compositional semantic meanings of utterances with the strengths of reinforcement learning in optimizing for long-term goals across a conversation. Experimental results (sampled results at the right panel of Table 1) demonstrate that our approach fosters a more sustained dialogue and manages to produce more interactive responses than standard SEQ2SEQ models trained using the MLE objective.
Deep Reinforcement Learning for Dialogue Generation
Open-Domain Dialogue
Deep Reinforcement Learning for Dialogue Generation
In this section, we describe in detail the components of the proposed RL model. The learning system consists of two agents. We use p to denote sentences generated from the first agent and q to denote sentences from the second. The two agents take turns talking with each other. A dialogue can be represented as an alternating sequence of sentences generated by the two agents: p 1 , q 1 , p 2 , q 2 , ..., p i , q i . We view the generated sentences as actions that are taken according to a policy defined by an encoder-decoder recurrent neural network language model. The parameters of the network are optimized to maximize the expected future reward using policy search, as described in Section 4.3. Policy gradient methods are more appropriate for our scenario than Q-learning (Mnih et al., 2013), because we can initialize the encoder-decoder RNN using MLE parameters that already produce plausible responses, before changing the objective and tuning towards a policy that maximizes long-term reward. Q-learning, on the other hand, directly estimates the future expected reward of each action, which can differ from the MLE objective by orders of magnitude, thus making MLE parameters inappropriate for initialization. The components (states, actions, reward, etc.) of our sequential decision problem are summarized in the following sub-sections.
Deep Reinforcement Learning for Dialogue Generation
An action a is the dialogue utterance to generate. The action space is infinite since arbitrary-length sequences can be generated.
Deep Reinforcement Learning for Dialogue Generation
A state is denoted by the previous two dialogue turns [p i , q i ]. The dialogue history is further transformed to a vector representation by feeding the concatenation of p i and q i into an LSTM encoder model as described in Li et al. (2016a).
Deep Reinforcement Learning for Dialogue Generation
A policy takes the form of an LSTM encoder-decoder (i.e., p RL (p i+1 |p i , q i ) ) and is defined by its parameters. Note that we use a stochastic representation of the policy (a probability distribution over actions given states). A deterministic policy would result in a discontinuous objective that is difficult to optimize using gradient-based methods.
Deep Reinforcement Learning for Dialogue Generation
r denotes the reward obtained for each action. In this subsection, we discuss major factors that contribute to the success of a dialogue and describe how approximations to these factors can be operationalized in computable reward functions.
Deep Reinforcement Learning for Dialogue Generation
Ease of answering A turn generated by a machine should be easy to respond to. This aspect of a turn is related to its forward-looking function: the constraints a turn places on the next turn (Schegloff and Sacks, 1973;Allwood et al., 1992). We propose to measure the ease of answering a generated turn by using the negative log likelihood of responding to that utterance with a dull response. We manually constructed a list of dull responses S consisting 8 turns such as "I don't know what you are talking about", "I have no idea", etc., that we and others have found occur very frequently in SEQ2SEQ models of conversations. The reward function is given as follows:
Deep Reinforcement Learning for Dialogue Generation
where N S denotes the cardinality of N S and N s denotes the number of tokens in the dull response s. Although of course there are more ways to generate dull responses than the list can cover, many of these responses are likely to fall into similar regions in the vector space computed by the model. A system less likely to generate utterances in the list is thus also less likely to generate other dull responses. p seq2seq represents the likelihood output by SEQ2SEQ models. It is worth noting that p seq2seq is different from the stochastic policy function p RL (p i+1 |p i , q i ), since the former is learned based on the MLE objective of the SEQ2SEQ model while the latter is the policy optimized for long-term future reward in the RL setting. r 1 is further scaled by the length of target S.
Deep Reinforcement Learning for Dialogue Generation
We want each agent to contribute new information at each turn to keep the dialogue moving and avoid repetitive sequences. We therefore propose penalizing semantic similarity between consecutive turns from the same agent. Let h p i and h p i+1 denote representations obtained from the encoder for two consecutive turns p i and p i+1 . The reward is given by the negative log of the cosine similarity between them:
Deep Reinforcement Learning for Dialogue Generation
Semantic Coherence We also need to measure the adequacy of responses to avoid situations in which the generated replies are highly rewarded but are ungrammatical or not coherent. We therefore consider the mutual information between the action a and previous turns in the history to ensure the generated responses are coherent and appropriate:
Deep Reinforcement Learning for Dialogue Generation
(3) p seq2seq (a|p i , q i ) denotes the probability of generating response a given the previous dialogue utterances [p i , q i ]. p backward seq2seq (q i |a) denotes the backward probability of generating the previous dialogue utterance q i based on response a. p backward seq2seq is trained in a similar way as standard SEQ2SEQ models with sources and targets swapped. Again, to control the influence of target length, both log p seq2seq (a|q i , p i ) and log p backward seq2seq (q i |a) are scaled by the length of targets. The final reward for action a is a weighted sum of the rewards discussed above:
Deep Reinforcement Learning for Dialogue Generation
where λ 1 + λ 2 + λ 3 = 1. We set λ 1 = 0.25, λ 2 = 0.25 and λ 3 = 0.5. A reward is observed after the agent reaches the end of each sentence.
Deep Reinforcement Learning for Dialogue Generation
The central idea behind our approach is to simulate the process of two virtual agents taking turns talking with each other, through which we can explore the state-action space and learn a policy p RL (p i+1 |p i , q i ) that leads to the optimal expected reward. We adopt an AlphaGo-style strategy (Silver et al., 2016) by initializing the RL system using a general response generation policy which is learned from a fully supervised setting.
Deep Reinforcement Learning for Dialogue Generation
For the first stage of training, we build on prior work of predicting a generated target sequence given dialogue history using the supervised SEQ2SEQ model (Vinyals and Le, 2015). Results from supervised models will be later used for initialization.
Deep Reinforcement Learning for Dialogue Generation
We trained a SEQ2SEQ model with attention (Bahdanau et al., 2015) on the OpenSubtitles dataset, which consists of roughly 80 million source-target pairs. We treated each turn in the dataset as a target and the concatenation of two previous sentences as source inputs.
Deep Reinforcement Learning for Dialogue Generation
Samples from SEQ2SEQ models are often times dull and generic, e.g., "i don't know" (Li et al., 2016a) We thus do not want to initialize the policy model using the pre-trained SEQ2SEQ models because this will lead to a lack of diversity in the RL models' experiences. Li et al. (2016a) showed that modeling mutual information between sources and targets will significantly decrease the chance of generating dull responses and improve general response quality. We now show how we can obtain an encoder-decoder model which generates maximum mutual information responses.
Deep Reinforcement Learning for Dialogue Generation
As illustrated in Li et al. (2016a), direct decoding from Eq 3 is infeasible since the second term requires the target sentence to be completely generated. Inspired by recent work on sequence level learning (Ranzato et al., 2015), we treat the problem of generating maximum mutual information response as a reinforcement learning problem in which a reward of mutual information value is observed when the model arrives at the end of a sequence.
Deep Reinforcement Learning for Dialogue Generation
Similar to Ranzato et al. (2015), we use policy gradient methods (Sutton et al., 1999;Williams, 1992) for optimization. We initialize the policy model p RL using a pre-trained p SEQ2SEQ (a|p i , q i ) model. Given an input source [p i , q i ], we generate a candidate list A = {â|â ∼ p RL }. For each generated candi-dateâ, we will obtain the mutual information score m(â, [p i , q i ]) from the pre-trained p SEQ2SEQ (a|p i , q i ) and p backward SEQ2SEQ (q i |a). This mutual information score will be used as a reward and back-propagated to the encoder-decoder model, tailoring it to generate sequences with higher rewards. We refer the readers to Zaremba and Sutskever (2015) and Williams (1992) for details. The expected reward for a sequence is given by:
Deep Reinforcement Learning for Dialogue Generation
The gradient is estimated using the likelihood ratio trick:
Deep Reinforcement Learning for Dialogue Generation
We update the parameters in the encoder-decoder model using stochastic gradient descent. A curriculum learning strategy is adopted (Bengio et al., 2009) as in Ranzato et al. (2015) such that, for every sequence of length T we use the MLE loss for the first L tokens and the reinforcement algorithm for the remaining T − L tokens. We gradually anneal the value of L to zero. A baseline strategy is employed to decrease the learning variance: an additional neural model takes as inputs the generated target and the initial source and outputs a baseline value, similar to the strategy adopted by Zaremba and Sutskever (2015). The final gradient is thus:
Deep Reinforcement Learning for Dialogue Generation
We simulate conversations between the two virtual agents and have them take turns talking with each other. The simulation proceeds as follows: at the initial step, a message from the training set is fed to the first agent. The agent encodes the input message to a vector representation and starts decoding to generate a response output. Combining the immediate output from the first agent with the dialogue history, the second agent updates the state by encoding the dialogue history into a representation and uses the decoder RNN to generate responses, which are subsequently fed back to the first agent, and the process is repeated.  Figure 1: Dialogue simulation between the two agents.
Deep Reinforcement Learning for Dialogue Generation
Optimization We initialize the policy model p RL with parameters from the mutual information model described in the previous subsection. We then use policy gradient methods to find parameters that lead to a larger expected reward. The objective to maximize is the expected future reward:
Deep Reinforcement Learning for Dialogue Generation
where R(a i , [p i , q i ]) denotes the reward resulting from action a i . We use the likelihood ratio trick (Williams, 1992;Glynn, 1990;Aleksandrov et al., 1968) for gradient updates:
Deep Reinforcement Learning for Dialogue Generation
(9) We refer readers to Williams (1992) and Glynn (1990) for more details.
Deep Reinforcement Learning for Dialogue Generation
A curriculum Learning strategy is again employed in which we begin by simulating the dialogue for 2 turns, and gradually increase the number of simulated turns. We generate 5 turns at most, as the number of candidates to examine grows exponentially in the size of candidate list. Five candidate responses are generated at each step of the simulation.
Deep Reinforcement Learning for Dialogue Generation
In this section, we describe experimental results along with qualitative analysis. We evaluate dialogue generation systems using both human judgments and two automatic metrics: conversation length (number of turns in the entire session) and diversity.
Deep Reinforcement Learning for Dialogue Generation
The dialogue simulation requires high-quality initial inputs fed to the agent. For example, an initial input of "why ?" is undesirable since it is unclear how the dialogue could proceed. We take a subset of 10 million messages from the OpenSubtitles dataset and extract 0.8 million sequences with the lowest likelihood of generating the response "i don't know what you are taking about" to ensure initial inputs are easy to respond to.
Deep Reinforcement Learning for Dialogue Generation
Evaluating dialogue systems is difficult. Metrics such as BLEU (Papineni et al., 2002) and perplexity have been widely used for dialogue quality evaluation (Li et al., 2016a;Vinyals and Le, 2015;, but it is widely debated how well these automatic metrics are correlated with true response quality . Since the goal of the proposed system is not to predict the highest probability response, but rather the long-term success of the dialogue, we do not employ BLEU or perplexity for evaluation 2 .
Deep Reinforcement Learning for Dialogue Generation
Model # of simulated turns SEQ2SEQ 2.68 mutual information 3.40 RL 4.48 Table 2: The average number of simulated turns from standard SEQ2SEQ models, mutual information model and the proposed RL model.
Deep Reinforcement Learning for Dialogue Generation
Length of the dialogue The first metric we propose is the length of the simulated dialogue. We say a dialogue ends when one of the agents starts generating dull responses such as "i don't know" 3 or two consecutive utterances from the same user are highly overlapping 4 .
Deep Reinforcement Learning for Dialogue Generation
The test set consists of 1,000 input messages. To reduce the risk of circular dialogues, we limit the number of simulated turns to be less than 8. Results are shown in Table 2. As can be seen, using mutual information leads to more sustained conversations between the two agents. The proposed RL model is first trained based on the mutual information objective and thus benefits from it in addition to the RL model. We observe that the RL model with dialogue simulation achieves the best evaluation score.
Deep Reinforcement Learning for Dialogue Generation
Diversity We report degree of diversity by calculating the number of distinct unigrams and bigrams in generated responses. The value is scaled by the total number of generated tokens to avoid favoring long sentences as described in Li et al. (2016a). The resulting metric is thus a type-token ratio for unigrams and bigrams.
Deep Reinforcement Learning for Dialogue Generation
For both the standard SEQ2SEQ model and the proposed RL model, we use beam search with a beam size 10 to generate a response to a given input message. For the mutual information model, we first generate n-best lists using p SEQ2SEQ (t|s) and then linearly re-rank them using p SEQ2SEQ (s|t). Results are presented in Table 4. We find that the proposed RL model generates more diverse outputs when com-Since the RL model is trained based on future reward rather than MLE, it is not surprising that the RL based models achieve lower BLEU score. 3 We use a simple rule matching method, with a list of 8 phrases that count as dull responses. Although this can lead to both false-positives and -negatives, it works pretty well in practice. 4 Two utterances are considered to be repetitive if they share more than 80 percent of their words. pared against both the vanilla SEQ2SEQ model and the mutual information model.
Deep Reinforcement Learning for Dialogue Generation
We explore three settings for human evaluation: the first setting is similar to what was described in Li et al. (2016a), where we employ crowdsourced judges to evaluate a random sample of 500 items. We present both an input message and the generated outputs to 3 judges and ask them to decide which of the two outputs is better (denoted as singleturn general quality). Ties are permitted. Identical strings are assigned the same score. We measure the improvement achieved by the RL model over the mutual information model by the mean difference in scores between the models.
Deep Reinforcement Learning for Dialogue Generation
For the second setting, judges are again presented with input messages and system outputs, but are asked to decide which of the two outputs is easier to respond to (denoted as single-turn ease to answer). Again we evaluate a random sample of 500 items, each being assigned to 3 judges.
Deep Reinforcement Learning for Dialogue Generation
For the third setting, judges are presented with simulated conversations between the two agents (denoted as multi-turn general quality). Each conversation consists of 5 turns. We evaluate 200 simulated conversations, each being assigned to 3 judges, who are asked to decide which of the simulated conversations is of higher quality.
Deep Reinforcement Learning for Dialogue Generation
Results for human evaluation are shown in Table 5. The proposed RL system does not introduce a significant boost in single-turn response quality (winning 40 percent of time and losing 36 percent of time). This is in line with our expectations, as the RL model is not optimized to predict the next utterance, but rather to increase long-term reward. The RL system produces responses that are significantly easier to answer than does the mutual information system, as demonstrated by the single-turn ease to answer setting (winning 52 percent of time and losing 23 percent of time), and also significantly higher quality multi-turn dialogues, as demonstrated by the multiturn general quality setting (winning 72 percent of time).
Deep Reinforcement Learning for Dialogue Generation
We show a random sample of generated responses in Table 3 and simulated conversations in Table 1    responses than the other baselines. We also find that the RL model has a tendency to end a sentence with another question and hand the conversation over to the user. From Table 1, we observe that the RL model manages to produce more interactive and sustained conversations than the mutual information model. During error analysis, we found that although we penalize repetitive utterances in consecutive turns, the dialogue sometimes enters a cycle with length greater than one, as shown in Table 6. This can be ascribed to the limited amount of conversational history we consider. Another issue observed is that the model sometimes starts a less relevant topic during the conversation. There is a tradeoff between relevance and less repetitiveness, as manifested in the reward function we define in Eq 4.
Deep Reinforcement Learning for Dialogue Generation
The fundamental problem, of course, is that the manually defined reward function can't possibly cover the crucial aspects that define an ideal conversation. While the heuristic rewards that we defined are amenable to automatic calculation, and do capture  some aspects of what makes a good conversation, ideally the system would instead receive real rewards from humans. Another problem with the current model is that we can only afford to explore a very small number of candidates and simulated turns since the number of cases to consider grow exponentially.
Deep Reinforcement Learning for Dialogue Generation
We introduce a reinforcement learning framework for neural response generation by simulating dialogues between two agents, integrating the strengths of neural SEQ2SEQ systems and reinforcement learning for dialogue. Like earlier neural SEQ2SEQ models, our framework captures the compositional models of the meaning of a dialogue turn and generates semantically appropriate responses. Like reinforcement learning dialogue systems, our framework is able to generate utterances that optimize future reward, successfully capturing global properties of a good conversation. Despite the fact that our model uses very simple, operationable heuristics for capturing these global properties, the framework generates more diverse, interactive responses that foster a more sustained conversation.
Deep Reinforcement Learning for Dialogue Generation
We would like to thank Chris Brockett, Bill Dolan and other members of the NLP group at Microsoft Research for insightful comments and suggestions. We also want to thank Kelvin Guu, Percy Liang, Chris Manning, Sida Wang, Ziang Xie and other members of the Stanford NLP groups for useful discussions. Jiwei Li is supported by the Facebook Fellowship, to which we gratefully acknowledge. This work is partially supported by the NSF via Awards IIS-1514268, IIS-1464128, and by the DARPA Communicating with Computers (CwC) program under ARO prime contract no. W911NF-15-1-0462. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF, DARPA, or Facebook.