Sequence to Backward and Forward Sequences: A Content-Introducing Approach to Generative Short-Text Conversation

Introduction

Automatic human-computer conversation is a hot research topic in natural language processing (NLP). In past decades, researchers have developed various rule- or template-based systems, which are typically in vertical domains, e.g., transportation [Ferguson et al. (1996] and education [Graesser et al. (2005]. In the open domain, data-driven approaches play an important role, because the diversity and uncertainty make it virtually impossible for humans to design rules or templates. ?) and ?) use information retrieval methods to search for a reply from a pre-constructed database; ?) formalize conversation as a statistical machine translation task.

Recently, the renewed prosperity of neural networks brings new opportunities to open-domain conversation [Vinyals and Le (2015, Shang et al. (2015, Serban et al. (2016a, Li et al. (2016a]. In these studies, researchers leverage sequence-to-sequence (seq2seq) models to encode a query (user-issued utterance) as a vector and to decode the vector into a reply. In both encoders and decoders, an RNN keeps one or a few hidden layers; at each time step, it reads a word and changes its state accordingly. RNNs are believed to be well capable of modeling word sequences, benefiting machine translation [Sutskever et al. (2014], abstractive summarization [Rush et al. (2015] and other tasks of natural language generation. Contrary to retrieval methods, neural network-based conversation systems are generative in that they can synthesize new utterances; results in the literature also show the superiority of seq2seq to phrase-based machine translation for dialogue systems [Shang et al. (2015]. In our study, we focus on neural network-based generative short-text conversation, where we do not consider context information, following ?) and ?).

Despite these, neural networks’ performance is far from satisfactory in human-computer conversation. A notorious problem is the universal reply: the RNN prefers to generate safe, universally relevant sentences with little meaning, e.g., “something” [Serban et al. (2016a] and “I don’t know” [Li et al. (2016a]. One problem may lie in the objective of decoding. If we choose a reply with the maximal estimated probability (either greedily or with beam search), it is probable to obtain such universal replies, because they do appear frequently in the training set. Another potential problem is that, the query may not convey sufficient information for the reply, and thus the encoder in seq2seq is less likely to obtain an informative enough vector for decoding.

In this paper, we propose a content-introducing approach to generative short-text conversation systems, where a reply is generated in a two-step fashion: (1) First, we predict a keyword, that is, a noun reflecting the main gist of the reply. This step does not capture complicated semantic and syntactic aspects of natural language, but estimates a keyword with the highest pointwise mutual information against query words. The keyword candidates are further restricted to nouns, which are not as probable as universal words (e.g., I and you), but can introduce substantial content to reply generation. (2) We then use a modified encoder-decoder model to synthesize a sentence containing the keyword. In traditional seq2seq, the decoder generates the reply from the first word to the last in sequence, which prevents introducing certain content (i.e., a given word) to the reply. To tackle this problem, we propose seq2BF, a novel “sequence to backward and forward sequences” model, based on our previous work of backward and forward language modeling [Mou et al. (2015]. The seq2BF model decodes a reply starting from a given word, and generates the remaining previous and future words subsequently. In this way, the predicted keyword can appear at an arbitrary position in the generated reply.

The rest of this paper is organized as follows. Section 2 describes the proposed approach; Section 3 presents experimental results. Section 4 briefly reviews related work in the literature. Finally we conclude our paper and discuss future work in Section 5.

Our Approach

In this section, we present our content-introducing generative dialogue system in detail. Subsection 2.1 provides an overview of our approach, Subsection 2.2 introduces the keyword predictor, and Subsection 2.3 elaborates the proposed seq2BF model. We describe training methods in Subsection 2.4.

Figure 1 depicts the overall architecture of our approach, which comprises two main steps:

We first use PMI to predict a keyword for the reply, as shown in Figure 1a.

After keyword prediction, we generate a reply conditioned on the keyword as well as the query. More specifically, we propose the seq2BF model, which generates the backward half of the sequence (Figure 1b) and then the forward half (Figure 1c).

Notice that, the RNNs in Step II do not share parameters (indicated by different colors in the figure) because they differ significantly from each other. Moreover, the encoder and decoder do not share parameters either, which is standard in seq2seq. For clarity, we do not assign different colors for encoders and decoders, but separate them with a long arrow in Figures 1b and 1c.

2 Keyword Prediction

In this step, we use pointwise mutual information (PMI) to predict a keyword for the reply. We leverage such surface statistics because this step outputs a single keyword, which does not capture complicated syntax and semantics of queries and replies. Our goal of content introducing is to suggest a word that is especially suited to the query, instead of predicting a most likely (common) word. Hence, the pointwise mutual information is an appropriate statistic for keyword prediction.

Formally, we compute PMI of a query word $w_{q}$ and a reply word $w_{r}$ using a large training corpus by

When predicting, we choose the keyword $w_{r}^{*}$ with the highest PMI score against query words $w_{q_{1}},\cdots w_{q_{n}}$, i.e., $w_{r}^{*}=\operatorname*{argmax}_{w_{r}}\operatorname{PMI}(w_{q_{1}}\cdots w_{q_{n}},w_{r})$, where

The approximation is due to the independency assumptions of both the prior distribution $p(w_{q_{i}})$ and posterior distribution $p(w_{q_{i}}|w_{r})$. While the two assumptions may not be true, we use them in a pragmatic way so that the word-level PMI is additive for a whole utterance. Experiments show that this treatment generally works well.

Different from choosing the most likely word, PMI penalizes a common word by dividing its prior probability; hence, PMI prefers a word that is most “mutually informative” with the query. Moreover, we manually restrict keyword candidates to nouns, so that this step can introduce substantial content to reply generation, which will be discussed in the next part.

3 The seq2BF Model

To insert the predicted keyword into sequence generation, we cannot use the traditional seq2seq model. In existing approaches, we usually decompose the probability of an output sentence $\bm{r}=r_{1}r_{2}\cdots r_{m}$ given an input sentence $\bm{q}=q_{1}q_{2}\cdots q_{n}$ by

The output sentence is thus predicted in sequence from $r_{1}$ up to $r_{m}$ either greedily or with beam search. I personally believe such decomposition is mainly inspired by the observation that humans always say a sentence from the beginning to the end.

However, in our content-introducing approach to generative dialogue systems, the predicted keyword could appear at the beginning ($r_{1}$), the middle ($r_{2}$ to $r_{m-1}$), or the end ($r_{m}$) of the reply. It is then natural to decompose the probability starting from the given word. In particular, the predicted keyword $k$ splits a reply into two (sub-)sequences:

and the joint probability of remaining words can be written as

where $p(\text{-\ -\ -}|r_{k},\bm{q})$ refers to the probability of the backward and forward subsequences given the split word $r_{k}$ and an encoded query $\bm{q}$. Notice that both the backward and forward sequence generators include a wildcard allowing rich inner-subsequence and/or inter-subsequence dependencies. In our previous study of backward-and-forward (B/F) language modeling [Mou et al. (2015], we propose three variants: (1) sep-B/F: The backward and forward sequences are generated separately. (2) syn-B/F: The backward and forward sequences are generated synchronously using a single RNN, two output layers at each time step for the two sequences. (3) asyn-B/F: The two sequences are generated asynchronously, that is, we first generate the backward “half” sequence, conditioned on which we then generate the forward “half.” Our previous experiments show the asyn-B/F is the most natural way of modeling backward and forward sequences, and thus we adopt this variant in seq2BF.

Specifically, our seq2BF model works as follows. A seq2seq neural network encodes a query and decodes a “half” reply, that is, the first set of factors in Equation 7 becomes $p^{\text{(bw)}}(r_{k-i}|r_{k},\bm{q},\cdot)=p^{\text{(bw)}}(r_{k-i}|r_{k}\cdots r_{k-i+1},\bm{q})$, where $1\leq i\leq k-1$. The decoder here outputs words in a reversed order from $r_{k-1}$, $r_{k-2}$ to $r_{1}$, so that the reversed “half” sequence is fluent with respect to the given word, at least from a mathematical perspective. (Please see Figure 1b.)

Then another seq2seq model encodes the query again, but decodes the entire reply, provided that the first half of the reply is given (Figure 1c), i.e., $p^{\text{(fw)}}(r_{k+i}|r_{k},\bm{q},\cdot)=p^{\text{(fw)}}(r_{k+i}|r_{1}\cdots r_{k}\cdots r_{k+i-1},\bm{q})$, $(1\leq i\leq m-k)$. Here, the forward generator is aware of the backward half sequence $r_{1}\cdots r_{k-1}$, where the word order is reversed again, so that they are in a normal order for fluent forward generation.

In both backward and forward seq2seq models, we use RNNs with gated recurrent units (GRUs) for information processing [Cho et al. (2014], given by

where $W$’s and $U$’s are weights and $\bm{b}$’s are bias terms. $\bm{w}_{t}$ is the word embedding; $\bm{h}_{t}$ is the hidden state at the time step $t$. “$\circ$” denotes element-wise product.

4 Model Training

Training (i.e., parameter estimation) is always a most important thing in the neural network regime, and oftentimes, problems arise when we prepare the dataset.

Fortunately, the seq2BF model can be trained without additional labels. We randomly sample a word in a reply as the split word, take the first half, and reverse its word order; in this way, we obtain the training data for the backward sequence generator. The forward sequence generator is essentially a seq2seq encoder and decoder from queries to replies. The difference between the pure seq2seq and the forward generator of seq2BF lies in the inference stage: in our scenario, we ignore the query-reply seq2seq generator’s output at the beginning steps, but feed it with the “half” reply obtained by our backward sequence generator as well as the predicted keyword (red and green words in Figure 1c); then we let the seq2seq model generate remaining future words (blue words in Figure 1c).

It should be emphasized that the backward sequence generator requires “half” replies starting from the split word as training data, and that we cannot train the model with a full reversed sentence. Otherwise, the backward part will undesirably generate an entire reversed reply, and the forward part cannot add much to it.

Experiments

We evaluated our approach on a Chinese dataset of human conversation crawled from the Baidu Tiebahttp://tieba.baidu.com forum. We used 500,000 query-reply pairs to train the seq2BF model. We had another unseen 2000 and 27,871 samples for validation and testing, respectively. To obtain PMI statistics in the first step (Figure 1a) of our method, we use a much larger dataset containing 100M query-reply pairs.

Chinese language is different from English in that a Chinese character carries more semantics than an alphabet. For example, the characters 黑 and 板 mean “black” and “board” in English, respectively; the term 黑板 means “blackboard.” Because we have far more Chinese terms than English words, our seq2BF is trained in the character level out of efficiency concerns. But we train the keyword predictor with noun phrases (Chinese terms), by noticing that blackboard is different from board, despite some subtle relations. Fortunately, the two granularities can be integrated together straightforwardly: during backward sequence generation, we only need to condition the model on the character sequence in the key term instead of a single keyword, that is, we have several green inputs in Figure 1b. In our study, we kept 2.5k noun terms as candidate keywords and 4k characters for seq2BF generation.

2 Hyperparameters

In our experiments, word embeddings and recurrent layers were 500d. We used rmsprop to optimize all parameters except embeddings, with initial weights uniformly sampled from $[-.08,.08]$, initial learning rate $0.002$, moving average decay $0.99$, and a damping term $\epsilon=10^{-8}$. Because word embeddings are sparse in use [Peng et al. (2015], we optimized embeddings asynchronously by stochastic gradient descent with the learning rate divided by $\sqrt{\epsilon}$. We set the mini-batch size to 50. These values were mostly chosen empirically by following ?) and ?); they generally work well in our scenarios. We did not tune the hyperparameters in this paper, but are willing to explore their roles in dialogue generation as future work.

The validation set (containing 2k query-reply samples) was used for early stop only. We chose the parameters yielding the highest character-level BLEU-2 score on our validation set.

3 Performance

We evaluated our results in terms of the following criteria:

Human Evaluation. We had six volunteersAll volunteers are well-educated native speakers of Chinese and have received a Bachelor’s degree or above. to annotate the results of our content-introducing seq2BF and baselines. To ensure the quality of human evaluation, we randomly sampled 200 queries and replies in the test set. The samples and volunteers were further split into two equal-sized groups of different annotation protocols:

Pointwise annotation. The volunteers were asked to annotate a score indicating the appropriateness of a reply to a given query: 0 = bad reply, 2 = good reply, and 1 = borderline.

Pairwise annotation. Given a certain query, the volunteers were asked to judge whether pure seq2seq is better than, equal to, or worse than seq2BF (with content introducing). If they could not understand both replies, they were asked to choose “equal.”

All our human evaluation were conducted in a random, blind fashion, i.e., we randomly shuffled the samples and volunteers did not know which system generated a particular reply. Notice that we did not define what a “good” or “bad” reply is; otherwise, the annotation may be biased towards certain systems. Rather, annotators had their own subjective discretion. While criteria may differ from person to person, the ranking of average scores reflects the comparison of different dialog systems. (In our study, the ranking is consistent among all six annotators.)

Length. The length of an utterance is an objective, surface metric that reflects the substance of a generated reply.

Entropy. Entropy is another objective metric, which shows the serendipity of a reply by measuring the amount of information contained in the utterance. We computed the average character-level entropy, given by

where $R$ refers to all replies, $|R|$ is the number of words in all replies, and $p(\cdot)$ is the unigram probability of a character in the training set.

The latter two metrics are “intrinsic,” by which we mean no reference (groundtruth reply) is needed to compute the metric. They are used in ?).The entropy equation in ?, v3) has a minor error. We confirmed this with Serban via personal emails. In our experiments, objective metrics were assessed with all test samples.

We do not include BLEU scores as our evaluation criteria, which are used in ?). As a pilot study, we also asked two volunteers to write their own replies to 50+ queries. One obtained 1.69 BLEU-4 score. (The result is lower than 1.74 obtained by an automatic dialogue system in ?); this may be caused by different datasets and languages.) What surprises us is that the other volunteer obtained 0 BLEU-2 score, indicating that no bi-gram overlaps between his replies and the references. This result provides evidence of the diversity among human replies, and thus we abandoned BLEU scores as evaluation criteria. We reported this case study in our paper so as to shed more light on the research of evaluation metrics in dialogue systems.

Table 1 compares our content-introducing seq2BF with the seq2seq baseline. Also included is the seq2BF model without content introducing, that is, we slacked the keyword constraint in the backward sequence generator (Figure 1b), and let it generate a reversed half reply freely.

As seen in Table 1a, the content-introducing seq2BF model yields the highest pointwise human annotation result. For seq2BF without content introducing, we obtain low scores, showing that artificially splitting a sequence into two parts itself is not a fancy way of modeling natural language sentences. However, given a keyword predicted by PMI statistics, the backward and forward sequence generation can significantly improve the dialogue system in comparison with pure seq2seq. In the pairwise annotation protocol, the content-introducing seq2BF model also outperforms traditional seq2seq to a large extent. We computed standard deviation (0.33) and discrete-class Fleiss’ $\kappa$ scores (0.27–0.29), showing fair annotator agreement [Fleiss (1971]. While the agreement is comparable to previous results, e.g., 0.2–0.4 reported in ?), we find the disagreement mainly comes from the discretion of the “goodness” of a reply (so that the annotation complies with the subjective nature of human evaluation). All annotators yielded the same system-level ranking order, providing consistent evidence of the effectiveness of our approach.

Regarding intrinsic metrics, our seq2BF with a predicted keyword generates slightly shorter replies than seq2seq, but contains far richer information, as the entropy increases by 30%. The results verify that content introducing is particularly useful in generative human-computer dialogue systems.

4 Case Studies and Discussion

We provide case studies in Table 2.Due to Chinese-English translation, some characteristics cannot be fully presented in the English text, e.g., the position of the given word, the length of the reply, and even the part-of-speech of a word. Nevertheless, we present the predicted keyword and its translated counterpart in bold and thus the aforementioned characteristics can be visually demonstrated to some extent. As we see, the seq2seq responder prefers safe, universally relevant utterances like “me too.” In these examples, the replies generally match the queries in meaning, but such universal replies are too boring and thus undesirable in real applications. In the seq2BF model with content introducing, we predict a keyword of the reply with PMI. This yields meaningful words/terms like rumor and score, serving as the gist of the reply. Then the seq2BF model generates previous and future words to obtain a more complete utterance (maybe not a whole sentence because of the casualness in human conversation). The proposed “backward and forward sequences” mechanism ensures that the predicted keyword can appear at an arbitrary position in the utterance.

We delve deep into the question: why seq2seq models (or variants) tend to generate universal replies? We may have two conjectures: (1) The seq2seq model cannot capture rich enough semantics other than “yes,” “me too,” etc. (2) The sequence generator is able to capture rich semantics, but starting from a high-level universal word at the beginning, it is unlikely to fall into concrete concepts.

We present in Table 3 the average character-level entropy of keywords and non-keywords. We find that, provided with a noun term, seq2BF can generate meaningful remaining words (keyword excluded) with an entropy of 7.422, higher than 6.971 given by seq2BF without keywords. Noticing that the seq2BF model is exactly the same in content-introducing and non-content-introducing settings, we believe the second conjecture holds. Choosing the most likely reply yields universal utterances; moreover, RNN sequence generators are reluctant to introduce concrete concepts, provided with one or a few universal words/terms (like I and you) that are greedily chosen at the beginning.

Fortunately, our content-introducing seq2BF works in an opposite fashion. We first predict a meaningful but not that probable noun term as the keyword; then we feed seq2BF with such concrete keyword that provides substantial content. In this way, our approach significantly outperforms pure seq2seq generation in short-text conversation systems.

Related Work

Automatic human-computer conversation has long attracted the attention of researchers. In early decades, people design rule- or template-based systems, but they are mainly in vertical domains [Ferguson et al. (1996, Misu and Kawahara (2007]. Although such approaches can also be extended to the open domain [Han et al. (2015], their generated sentences are subject to 7 predefined forms and thus are highly restricted. For open dialogues, researchers have applied data-driven approaches, including retrieval methods [Isbell et al. (2000, Wang et al. (2013], phrase-based machine translation [Ritter et al. (2011], and recurrent neural networks [Sordoni et al. (2015, Shang et al. (2015].

A hot research topic in human-computer conversation is mixed-initiative systems, for example, the TRAINS-95 system for route planning [Ferguson et al. (1996] and AutoTutor for learner advising [Graesser et al. (2005]. ?) propose a proactive dialogue system that can introduce new content when a stalemate occurs. The system is chatbot-like and in the open domain; an external knowledge base is used for searching related entities as new content. They propose a random walk-like reranking algorithm based on retrieval results. Different from ?)’s work, our paper addresses the problem of content introducing in open-domain generative dialogue systems.

2 Neural Networks for Sentence Generation

?) propose seq2seq for machine translation; the idea is to encode a source sentence as a vector by a recurrent neural network (RNN) and to decode the vector to a target sentence by another RNN. ?) enhance it with an attention mechanism. These approaches largely benefit natural language generation tasks such as abstractive summarization [Rush et al. (2015], question answering [Yin et al. (2016], and poetry generation [Wang et al. (2016].

For neural network-based dialogue systems, ?) summarize a query and context as bag-of-words features, based on which an RNN decodes the reply. ?) generate replies for short-text conversation by seq2seq-like neural networks with local and global attention. ?) and ?) design hierarchical neural networks for multi-turn conversation.

To address the problem of universal replies, ?) propose a mutual information training objective. ?) apply a variational Bayes approach that imposes a probabilistic distribution on the hidden variables and encodes the parameters of the posterior distribution. A very recent study similar to ours is ?), where replies are augmented with topic information. In a dialogue-like question-answering system, ?) query a knowledge base and insert a selected triple into an answer sentence by a soft logistic unit. In such approach, however, the answer may not actually appear in the generated sentence, especially when the test patterns are different from training ones. Unlike existing work, our seq2BF model guarantees the predicted keyword can appear in the reply at an appropriate position.

Conclusion and Future Work

In this paper, we proposed a content-introducing approach to generative short-text conversation systems. Instead of generating a reply sequentially from the beginning word to the end as in existing approaches, we used pointwise mutual information to predict a keyword, i.e., a noun term, for the reply. Then we proposed a “sequence to backward and forward sequences” (seq2BF) model to generate a reply containing the predicted keyword. The seq2BF mechanism ensures the keyword can appear at an arbitrary position in the reply, but the generated utterance is still fluent. Experimental results show that our approach consistently outperforms the pure seq2seq model in dialogue systems in terms of human evaluation and the entropy measure.

In future work, we would like to apply different keyword prediction techniques (e.g., neural sentence models) to improve the performance; the proposed seq2BF model can also be extended to other applications like generative question answering, where the answer may be given by searching an external database or knowledge base.

Acknowledgments

We thank Jiexiu Zhai, Hao Meng, Siqi Wang, Zhexi Hong, Junling Chen, and Zhiliang Tian for evaluating our dialogue systems. We also thank all reviewers for their constructive comments. This research is supported by the National Basic Research Program of China (the 973 Program) under Grant No. 2015CB352201 and the National Natural Science Foundation of China under Grant Nos. 61232015, 91318301, 61421091, 61225007, and 61502014.

References