Traditional generative dialogue models generate responses solely from input queries. Such information is insufficient for generating a specific response since a certain query could be answered in multiple ways. Recently, researchers have attempted to fill the information gap by exploiting information retrieval techniques. For a given query, similar dialogues are retrieved from the entire training data and considered as an additional knowledge source. While the use of retrieval may harvest extensive information, the generative models could be overwhelmed, leading to unsatisfactory performance. In this paper, we propose a new framework which exploits retrieval results via a skeleton-to-response paradigm. At first, a skeleton is extracted from the retrieved dialogues. Then, both the generated skeleton and the original query are used for response generation via a novel response generator. Experimental results show that our approach significantly improves the informativeness of the generated responses. This paper focuses on tackling the challenges to develop a chit-chat style dialogue system (also known as chatbot). Chit-chat style dialogue system aims at giving meaningful and coherent responses given a dialogue query in the open domain. Most modern chit-chat systems can be categorized into two categories, namely, information retrieval-based (IR) models and generative models. The IR-based models (Ji et al., 2014; Hu et al., 2014) directly copy an existing response from a training corpus when receiving a response request. Since the training corpus is usually collected from real-world conversations and possibly post-edited  Work done while DC was interning at Tencent AI Lab. by a human, the retrieved responses are informative and grammatical. However, the performance of such systems drops when a given dialogue history is substantially different from those in the training corpus. The generative models (Shang et al., 2015; Vinyals and Le, 2015; Li et al., 2016a), on the other hand, generate a new utterance from scratch. While those generative models have better generalization capacity in rare dialogue contexts, the generated responses tend to be universal and noninformative (e.g., I don't know, I think so etc.) (Li et al., 2016a). It is partly due to the diversity of possible responses to a single query (i.e., the one-to-many problem). The dialogue query alone cannot decide a meaningful and specific response. Thus a well-trained model tends to generate the most frequent (safe but boring) responses instead. To summarize, IR-based models may give informative but inappropriate responses while generative models often do the opposite. It is desirable to combine both merits. Song et al. (2016) used an extra encoder for the retrieved response. The resulted dense representation, together with the original query, is used to feed the decoder in a standard SEQ 2S EQ model (Bahdanau et al., 2014). Weston et al. (2018) used a single encoder that takes the concatenation of the original query and the retrieved as input. Wu et al. (2019) noted that the retrieved information should be used in awareness of the context difference, and further proposed to construct an edit vector by explicitly encoding the lexical differences between the input query and the retrieved query. However, in our preliminary experiments, we found that the IR-guided models are inclined to degenerate into a copy mechanism, in which the generative models simply repeat the retrieved response without necessary modifications. Sharp performance drop is caused when the retrieved response is irrelevant to the input query. A possible reason is that both useful and useless information is mixed in the dense vector space, which is uninterpretable and uncontrollable. To address the above issue, we propose a new framework, skeleton-to-response, for response generation. Our motivations are two folds: (1) The guidance from IR results should only specify a response aspect or pattern, but leave the query-specific details to be elaborated by the generative model itself; (2) The retrieval results typically contain excessive information, such as inappropriate words or entities. It is necessary to filter out irrelevant words and derive a useful skeleton before use. Our approach consists of two components: a skeleton generator and a response generator. The skeleton generator extracts a response skeleton by detecting and removing unwanted words in a retrieved response. The response generator is responsible for adding query-specific details to the generated skeleton for query-to-response generation. A dialogue example illustrating our idea is shown in Fig. 1. Due to the discrete choice of skeleton words, the gradient in the training process is no longer differentiable from the response to the skeleton generator. Two techniques are proposed to solve this issue. The first technique is to employ the policy gradient method for rewarding the output of the skeleton generator based on the feedback from a pre-trained critic. An alternative technique is to solve both the skeleton generation and the response generation in a multi-task learning fashion. Our contributions are summarized as below: (1) We develop a novel framework to inject the power of IR results into generative response models by introducing the idea of skeleton generation; (2) Our approach generates response skeletons by detecting and removing unnecessary words, which facilitates the generation of specific responses while not spoiling the generalization ability of the underlying generative models; (3) Experimental results show that our approach significantly outperforms other compared methods, resulting in more informative and specific responses. In this work, we propose to construct a response skeleton based on the results of IR systems for guiding the response generation. The skeleton-to-Query : My son loves Disneyland. response paradigm helps reduce the search space of possible responses and provides useful elements missing in the given query. Our model consists of two components, namely, the skeleton generator and the response generator. These components are parameterized by the above two probabilistic models, denoted by  ske and  res respectively. Fig. 2 depicts the overall architecture of our proposed framework. The skeleton generator transforms a retrieved response into a skeleton by explicitly removing inappropriate or useless information regarding the input query q . We consider this procedure as a series of word-level masking actions. Following Wu et al. (2019), we first construct an edit vector by comparing the difference between the original query q and the retrieved query q (cid:48) . In (Wu et al., 2019) the edit vector is used to guide the response generation directly. In our model, the edit vector is used to estimate the probability of being reserved or being masked for every word in a sentence. We define two word sets, namely insertion words I and deletion words D . The insertion words include words that are in the original query q , but not in the retrieved query q (cid:48) , while the deletion words do the opposite. The two bags of words highlight the changes in the dialogue context, corresponding to the changes in the response. The edit vector z is thus defined as the concatenation of the representations of the two bags of words. We use the weighted sum of the apple Do you like banana Retrieval System deletion words insertion words edit vector Skeleton Generator Response Generator Yes , __ is my favorite query memories Decoder Binary Classifier retrieved query retrievedresponse skeleton skeleton memories j o i n t c a s c a d e d skeleton memories Input Query: Generated response : Yes, banana is my favorite Do you like Yes , apple is my favorite Figure 2: The architecture of our framework. word embeddings to get the dense representations of I and D . The edit vector is computed as: z = (cid:88) w 1  I  w 1 ( w 1 )  (cid:88) w 2  D  w 2 ( w 2 ) , (1) where  is the concatenation operation. maps a word to its corresponding embedding vector,  w 1 and  w 2 are the weights of an insertion word w 1 and a deletion word w 2 respectively. The weights of different words are derived by an attention mechanism (Luong et al., 2015). Formally, the retrieved response r (cid:48) = ( r (cid:48) 1 , r (cid:48) 2 . . . , r (cid:48)| r (cid:48) | ) is processed by a bidirectional GRU network (biGRU). We denote the states of the biGRU (i.e. concatenation of forward and backward GRU states) as ( h 1 , h 2 , . . . , h | r (cid:48) | ) . The weight  w 1 is calculated by:  w 1 = exp( s w 1 ) (cid:80) w  I exp( s w ) , s w 1 = v (cid:62) I tanh( WI [( w 1 )  h | r (cid:48) | ]) , (2) where v I and WI are learnable parameters. The weight  w 2 is obtained in a similar way with an-other set of parameters v D and WD . After acquiring the edit vector, we transform the prototype response r (cid:48) to a skeleton t by the following equations: t = (  ( r (cid:48) 1 , h 1 , z ) ,  ( r (cid:48) 2 , h 2 , z ) ,    ,  ( r (cid:48)| r (cid:48) | , h | r (cid:48) | , z )) ,  ( r (cid:48) i , h i , z ) = (cid:40) < blank > if  m i = 0 , r (cid:48) i else , (3) where  m i is the indicator and equals 0 if r (cid:48) i is replaced with a placeholder  < blank >  and 1 otherwise. The probability of  m i = 1 is computed by P (  m i = 1) = sigmoid ( W m [ h i  z ] + b m ) . The response generator can be implemented using most existing IR-augmented models (Song et al., 2016; Weston et al., 2018; Pandey et al., 2018), just by replacing the retrieved response input with the corresponding skeleton. We discuss our choices below. Encoders Two separate bidirectional LSTM (biLSTM) networks are used to obtain the distributed representations of the query memories and the skeleton memories, respectively. For biLSTM, the concatenation of the forward and the backward hidden states at each token position is considered a memory slot, producing two memory pools: M q = { h 1 , h 2 , . . . , h | q | } for the input query, and M t = { h (cid:48) 1 , h (cid:48) 2 , . . . , h (cid:48)| t | } for the skeleton. 1 Decoder During the generation process, our decoder reads information from both the query and the skeleton using attention mechanism (Bah-danau et al., 2014; Luong et al., 2015). To query the memory pools, the decoder uses the hidden state s t of itself as the searching key. The matching score function is implemented by bilinear functions:  ( h k , s t ) = h kT W q s t ;  ( h (cid:48) k , s t ) = h (cid:48) kT W t s t , (5) where W q and W t are trainable parameters. A query context vector c t is then computed as a weighted sum of all memory slots in M q , where the weight for a memory slot h k is exp(  ( h k , s t )) / ( (cid:80) | q | i =1 exp(  ( h i , s t ))) . A skeleton context vector c (cid:48) t is computed in a similar spirit by using  ( h (cid:48) k , s t ) 's. The probability of generating the next word r t is then jointly determined by the decoder's state s t , the query context c t and the skeleton context c (cid:48) t . We first fuse the information of s t and c t by a linear transformation. For c (cid:48) t , a gating mechanism is additionally introduced to control the information flow from skeleton memories. Formally, the probability of the next token r t is estimated by y t followed by a softmax function over the vocabulary: y t = ( W c [ s t  c t ])  g t + c (cid:48) t  (1  g t ) , (6) where g t = f g ( s t , c t , c (cid:48) t ) is implemented by a single layer neural network with sigmoid output layer. Given that our skeleton generator performs nondifferentiable hard masking, the overall model cannot be trained end-to-end using the standard maximum likelihood estimate (MLE). A possible solution that circumvents this problem is to treat the skeleton generation and the response generation as two parallel tasks and solve them jointly 1 Note the skeleton memory pool M t could contain multiple response skeletons, further discussed in the experiment section. in a multi-task learning fashion. An alternative is to bridge the skeleton generator and the final response output using reinforcement learning (RL) methods, which can exclusively inform the skeleton generator with the ultimate goal. The latter option is referred as cascaded integration while the former is called joint integration . Recall that we have formulated the skeleton generation as a series of binary classifications. Nevertheless, most of the dialogue datasets are end-to-end query-response pairs without explicit skeletons. Hence, we propose to construct proxy skeleton s to facilitate the training. Definition 1 Proxy Skeleton: Given a training quadruplet ( q, q (cid:48) , r, r (cid:48) ) and a stop word list S , the proxy skeleton for r is generated by replacing some tokens in r (cid:48) with a placeholder  < blank > . A token r (cid:48) i is kept if and only if it meets the following conditions 1. r (cid:48) i /  S 2. r (cid:48) i is a part of the longest common subsequence (LCS) (Wagner and Fischer, 1974) of r and r (cid:48) . The proxy skeletons are used in different man-ners according to the integration method, which we will introduce below. To avoid breaking the differentiable computation, we connect the skeleton generator and the response generator via a shared network architecture rather than by passing the discrete skeletons. Concretely, the last hidden states in our skeleton generator (i.e, the hidden states that are utilized to make the masking decisions) are used as the skeleton memories in response generation. The training objective is the sum of the proxy skeleton labels likelihood L (  ske ) and the response likelihood L (  res ) : L (  res   ske ) = L (  res ) + L (  ske ) , (7) where  is a harmonic weight, and it is set as 1 . Policy gradient methods (Williams, 1992) can be applied to optimize the full model while keeping it running as cascaded process. We regard the skeleton generator as the first RL agent, and the response generator as the second one. The final output generated by the pipeline process and the intermediate skeleton are denoted by  r and  t respectively. Given the original query q and the generated response  r , a reward R ( q,  r ) for generating  r is calculated. All network parameters are then optimized to maximize the expected reward by the policy gradient. The reward function R should convey both the naturalness of the generated response and its relevance to the given query q . A pre-trained critic is utilized to make the judgment. Inspired by comparative adversarial learning in (Li et al., 2018), we design the critic as a classifier that receives four inputs every time: the query q , a human-written response r , a machine-generated response  r and a random response r (yet written by human). The critic is trained to pick the human-written response r among others correctly. Formally, the following objective is maximized: log D ( r | q,  r, r, r ) = log exp( h r TMD h q ) (cid:80) x {  r,r,r } exp( h x TMD h q ) , (8) where h x is a vector representation of x , produced by a bidirectional LSTM (the last hidden state), and MD is a trainable matrix. 2 4 Related Work Multi-source Dialogue Generation Chit-chat style dialogue system dates back to ELIZA (Weizenbaum, 1966). Early work uses handcrafted rules, while modern systems usually use data-driven approaches, e.g., information retrieval techniques. Recently, end-to-end neural approaches (Vinyals and Le, 2015; Serban et al., 2016; Li et al., 2016a; Sordoni et al., 2015) have attracted increasing interest. For those generative models, a notorious problem is the safe re-sponse problem: the generated responses are dull and generic, which may attribute to the lack of suf-ficient input information. The query alone cannot specify an informative response. To mitigate the issue, many research efforts have been paid to introducing other information source, such as unsupervised latent variable (Serban et al., 2017; Zhao et al., 2018; Cao and Clark, 2017; Shen et al., 2017), discourse-level variations (Zhao et al., 2017), topic information (Xing et al., 2017), speaker personality (Li et al., 2016b) and knowl-2 Note the classifier could be fine-tuned with the training of our generators, which falls into the adversarial learning setting (Goodfellow et al., 2014). edge base (Ghazvininejad et al., 2018; Zhou et al., 2018). Our work follows the similar motivation and uses the output of IR systems as the additional knowledge source. Combination of IR and Generative models To combine IR and generative models, early work (Qiu et al., 2017) tried to re-rank the output from both models. However, the performance of such models is limited by the capacity of individual methods. Most related to our work, Song et al. (2016); Weston et al. (2018) and Wu et al. (2019) encoded the retrieved result into distributed representation and used it as the additional conditionals along with the standard query representation. While the former two only used the target side of the retrieved pairs, the latter took advantages of both sides. In a closed domain conversation setting, Pandey et al. (2018) further proposed to weight different training instances by context similarity. Our model differs from them in that we take an extra intermediate step for skeleton generation to filter the retrieval information before use, which shows the effectiveness in avoiding the erroneous copy in our experiments. Multi-step Language Generation Our work is also inspired by the recent success of decomposing an end-to-end language generation task into several sequential sub-tasks. For document summarization, Chen and Bansal (2018) first select salient sentences and then rewrite them in parallel. For sentiment-to-sentiment translation, Xu et al. (2018) first use a neutralization module to remove emotional words and then add sentiment to the neutralized content. Not only does their decomposition improve the overall performance, but also makes the whole generation process more interpretable. Our skeleton-to-response framework also sheds some light on the use of retrieval memories. We use the preprocessed data in (Wu et al., 2019) as our test bed. The total dataset consists of about 20 million single-turn query-response pairs collected from Douban Group 3 . Since similar contexts may correspond to totally different responses, the training quadruples ( q, r, q (cid:48) , r (cid:48) ) for 3 https://www.douban.com/group IR-augmented models are constructed based on response similarity. All response are indexed by Lucene. 4 For each ( q, r ) pair, top 30 similar responses with their corresponding contexts are retrieved { ( q (cid:48) i , r (cid:48) i ) } 30 i =1 . However, only those satisfying 0 . 3  Jaccard ( r, r (cid:48) i )  0 . 7 are leveraged for training, where Jaccard measures the Jaccard distance. The reason for the data filter is that nearly identical responses drive the model to do simple copy while distantly different responses make the model ignore the retrieval input. About 42 million quadruples are obtained afterward. For computational efficiency, we randomly sample 5 million quadruples as training data for all experiments. The test set consists of 1,000 randomly selected queries that are not in our training data. 5 For a fair comparison, when training a generative model without the help of IR, the quadruples are split into pairs. We implement the skeleton generator based on a bidirectional recurrent neural network with 500 LSTM units. We concatenate the hidden states from both directions. The word embedding size is set to 300. For the response generator, the encoder for queries, the encoder for skeletons and the decoder are three two-layer recurrent neural networks with 500 LSTM units, where both encoders are bidirectional. We use dropout (Sri-vastava et al., 2014) to alleviate overfitting. The dropout rate is set to 0.3 across different layers. The same architecture for the encoders and the decoder is shared across the following baseline models, if applicable. Seq2Seq the standard attention-based RNN encoder-decoder model (Bahdanau et al., 2014). MMISEQ 2S EQ with Maximum Mutual Information (MMI) objective in decoding (Li et al., 2016a). In practice, an inverse (response-to-query) SEQ 2S EQ model is used to rerank the N -best hypothesizes from the standard SEQ 2S EQ model ( N equals 100 in our experiments). EditVec the model proposed by Wu et al. (2019), where the edit vector z is used directly at each decoding step by concatenating it to the word embeddings. IR the Lucene system is also used a benchmark. 6  IR+rerank rerank the results of IR by MMI . Besides, We use JNT to denote our model with joint integration, and CAS for our model with cascaded integration. To validate the usefulness of the proposed skeletons. We design a response generator that takes an intact retrieval response as its skeleton input (i.e., to completely skip the skeleton generation step), denoted by SKP . 7 5.4 Evaluation Metrics Our method is designed to improve the informativeness of the generative model and alleviate the inappropriateness problem of the retrieval model. To measure the performance effectively, we use 6 Note IR selects response candidates from the entire data collection, not restricted to the filtered one. 7 There are some other IR-augmented models using standard SEQ 2 SEQ models as SKP. Weston et al. (2018) used a rule to select either the generated response or the retrieved response as output, while we would like to focus on improving the quality of generated responses. Pandey et al. (2018) concentrated on closed domain conversations, their hierarchical encoder is not suitable for our open domain setting. We thus omit the empirical comparison with them. human evaluation along with two automatic evaluation metrics. Human evaluation We asked three experienced annotators to score the group of responses (the best output of each model) for 300 test queries. The responses are rated on a five-point scale. A response should be scored 1 if it can hardly be considered a valid response, 3 if it is a valid but not informative response, 5 if it is an informative response, which can deepen the discussion of the current topic or lead to a new topic. 2 and 4 are for decision dilemmas. dist-1 & dist-2 It is defined as the number of unique uni-grams ( dist-1 ) or bi-grams ( dist-2 ) dividing by the total number of tokens, measuring the diversity of the generated responses (Li et al., 2016a). Note the two metrics do not necessarily reflect the response quality as the target queries are not taken into consideration. The results are depicted in Table 1. Overall, both of our models surpass all other methods, and our cascaded model (CAS) gives the best performance according to human evaluation. The contrast with the SKP model illustrates that the use of skeletons brings a significant performance gain. According to the dist-1&2 metrics, the generative models achieve significantly better diversity by the use of retrieval results. The retrieval method yields the highest diversity, which is consistent with our intuition that the retrieval responses typically contain a large amount of information though they are not necessarily appropriate. The model of MMI also gives strong diversity, yet we find that it tends to merely repeat the words in queries. By removing the words in queries, the dist-2 of MMI and CAS become 0.710 and 0.751 respectively. It indicates our models are better at generating new words. To further reveal the source of performance gain, we study the relation between response quality and query similarity (measured by the Jaccard similarity between the input query and the retrieved query). Our best model (CAS) is compared with the strong IR system (IR-rerank) and the previous state-of-the-art (EditVec) in Fig. 3. The CAS model significantly boosts the performance when query similarity is relatively low, which indicates that introducing skeletons can alleviate erroneous copy and keep a strong generalization ability of the underlying generative model. Generated Skeletons Although generating skeletons is not our primary goal, it is interesting to assess the skeleton generation. The word-level precision (P), recall (R), F 1 score (F 1 ) and accuracy (Acc.) of the well-trained skeleton generators are reported in Table 2, taking the proxy skeletons as golden references. Table 3 shows some skeleton-to-response examples of the CAS model and a case study among different models. In the leftmost example in Table 3, the MMI and the EditVec simply repeat the query while the retrieved response is weakly related to the query. Our CAS model extracts a useful word 'boy' from the retrieved response and generates a more interesting response. In the mid-dle example, the MMI response makes less sense, and some private information is included in the retrieved response. Our CAS model removes the privacy without the loss of informativeness, while the outputs by other models are less informative. The rightmost case shows that our response generator is able to recover the possible mistakes made by the skeleton generator. Retrieved Response v.s. Generated Response To measure the extent that the generative models are copying the retrieval, we compute the edit distances between generated responses and retrieved 8 We merge the ranges [0 . 6 , 0 . 8] and [0 . 8 , 1 . 0] due to the sparsity of highly similar pairs. responses. As shown in Fig. 4, in the comparison between the SKP and other models, the use of skeletons makes the generated response deviate more from its prototype response. Ideally, when the retrieved context is very similar to the input query, the changes between the generated response and the prototype response should be minor. Conversely, the changes should be drastic. Fig. 4 also shows that our models can learn this intuition. Single v.s. Multiple Retrieval Pair(s) For a given query q , the retrieval pair set R q could contain multiple query-response pairs. We investigate two ways of using it under the CAS setting. Single For each query-response pair ( q (cid:48) i , r (cid:48) i )  R q , a response  r i is generated solely based on q , and ( q (cid:48) i , r (cid:48) i ) . The resulted responses are re-ranked by generation probability. Multiple The whole retrieval set R q is used in a single run. Multiple skeletons are generated and concatenated in the response generation stage. The results are shown in Table 4. We attribute the failure of Multiple to the huge variety of the retrieved responses. The response generator receives many heterogeneous skeletons, yet it has no idea which to use. It remains an open question on how to effectively use multiple retrieval pairs for generating one single response, and we leave it for future work. In this paper, we proposed a new methodology to enhance generative models with information retrieval technologies for dialogue response generation. Given a dialogue context, our methods generate a skeleton based on historical responses that respond to a similar context. The skeleton serves as an additional knowledge source that helps specify the response direction and complement the response content. Experiments on real world data validated the effectiveness of our method for more informative and appropriate responses. We thank the anonymous reviewers for their helpful comments. The work described in this paper is partially supported by a grant from the Research Grant Council of the Hong Kong Special Administrative Region, China (Project Code: 14203414).
abstain abstain abstain abstain abstain objective abstain abstain result objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain objective objective abstain abstain abstain abstain result abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain method abstain abstain method method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain other method abstain abstain abstain abstain abstain abstain abstain other method abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain other abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain method result method abstain result method method abstain method abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method abstain abstain other other