Commonsense Knowledge Aware Conversation Generation with Graph Attention

1 Introduction

Semantic understanding, particularly when facilitated by commonsense knowledge or world facts, is essential to many natural language processing tasks [Wang et al., 2017; Lin et al., 2017], and undoubtedly, it is a key factor to the success of dialogue or conversational systems, as conversational interaction is a semantic activity [Eggins and Slade, 2005]. In open-domain conversational systems, commonsense knowledge is important for establishing effective interactions, since socially shared commonsense knowledge is the set of background information people intended to know and use during conversation [Minsky, 1991; Markov´a et al., 2007; Speer and Havasi, 2012; Souto, 2015].

∗Corresponding author: Minlie Huang.

Recently, a variety of neural models has been proposed for conversation generation [Ritter et al., 2011; Shang et al., 2015]. However, these models tend to generate generic responses, which are unable to respond appropriately and informatively in most cases, because it is challenging to learn semantic interactions merely from conversational data [Ghazvininejad et al., 2017] without deep understanding of user input, and the background knowledge and the context of conversation. A model can understand conversations better and thus respond more properly if it can access and make full use of large-scale commonsense knowledge. For instance, to understand a post-response pair "Don't order drinks at the restaurant , ask for free water" and "Not in Germany. Water cost more than beer. Bring you own water bottle", we need commonsense knowledge such as (water, AtLocation, restaurant), (free, RelatedTo, cost), etc.

Some prior studies have been conducted to introduce external knowledge in conversation generation [Han et al., 2015; Ghazvininejad et al., 2017; Zhu et al., 2017]. The knowledge used in these models is either unstructured texts [Ghazvininejad et al., 2017] or domain-specific knowledge triples [Zhu et al., 2017]. Therefore, such models face with two issues when they are applied to open-domain, open-topic conversation generation. First, they are highly dependent on the quality of unstructured texts or limited by the small-scale, domain-specific knowledge. Second, they usually make use of knowledge triples (entities) separately and independently, instead of treating knowledge triples as a whole in a graph. Thus, they are unable to represent the semantics of a graph via linked entities and relations.

To address the two issues, we propose a commonsense knowledge aware conversational model (CCM) to facilitate language understanding and generation in open-domain conversational systems. We use a large-scale commonsense knowledge [Speer and Havasi, 2012] to help understand the background information of a given post, and to facilitate response generation with such knowledge. The model retrieves a few knowledge graphs for each post and then use the graphs to respond more informatively and appropriately, as shown in Figure 1. To fully leverage the retrieved graphs in conversation generation, two novel graph attention mechanisms are designed. A static graph attention mechanism encodes Moonlight lacks the ultraviolet rays of sunlight.

I'm not sure what you're saying.

Figure 1: (Better viewed in color) Two response examples by our model (the first line) and Seq2Seq (second) with/without considering commonsense knowledge, respectively.

the retrieved graphs for a post to augment the semantic representation of the post, which can help understand the post. A dynamic graph attention mechanism attentively reads the knowledge graphs and the triples in each graph, and then uses the semantic information from the graphs and triples for better response generation.

In summary, this paper makes the following contributions:

• This work is the first attempt that uses large-scale commonsense knowledge in neural conversation generation. Supported by such knowledge, our model can understand the dialogue better and thus respond more appropriately and informatively.
• Instead of treating knowledge triples (or entities) separately and independently, we devise static and dynamic graph attention mechanisms to treat the knowledge triples as a graph, from which we can better interpret the semantics of an entity from its neighboring entities and relations.

2 RelatedWork

Open-domain Conversational Models

Recently, sequence-to-sequence models [Sutskever et al., 2014; Bahdanau et al., 2014] have been successfully applied to large-scale conversation generation, including neural responding machine [Shang et al., 2015], hierarchical recurrent models [Serban et al., 2015], and many others [Sordoni et al., 2015]. These models developed various techniques to improve the content quality of generated responses, including diversity promotion [Li et al., 2016; Shao et al., 2017], considering additional information [Xing et al., 2017; Mou et al., 2016], and handling unknown words [Gu et al., 2016]. However, generic or meaningless responses are still commonly seen in these models due to the inability of good understanding of the user input or other context.

Unstructured Texts Enhanced Conversational Models Several studies incorporated unstructured texts as external knowledge into conversation generation [Ghazvininejad et al., 2017; Long et al., 2017]. [Ghazvininejad et al., 2017] used memory network which stores unstructured texts to improve conversation generation. [Long et al., 2017] applied a convolutional neural network to extract knowledge from unstructured texts to generate multi-turn conversations. However, these models largely depend on the quality of unstructured texts, which may introduce noise in conversation generation if the texts are irrelevant.

Structured Knowledge Enhanced Conversational Models There exist some models that introduced high-quality structured knowledge for conversation generation [Han et al., 2015; Zhu et al., 2017; Xu et al., 2017]. [Xu et al., 2017] incorporated a structured domain-specific knowledge base into conversation generation with a recall-gate mechanism. [Zhu et al., 2017] presented an end-to-end knowledge grounded conversational model using a copy network [Gu et al., 2016]. However, these studies are somehow limited by the small domain-specific knowledge base, making them not applicable for open-domain, open-topic conversation generation. By contrast, our model applies a large-scale commonsense knowledge base to facilitate both the understanding of a post and the generation of a response, with novel graph attention mechanisms.

3 Commonsense Conversational Model

3.1 Background: Encoder-decoder Framework

First of all, we introduce a general encoder-decoder framework which is based on sequence-to-sequence (seq2seq) learning [Sutskever et al., 2014]. The encoder represents a post sequence X = x1x2 · · · xn with hidden representations H = h1h2 · · · hn 1 , which is briefly defined as below:

where e(xt) is the embedding of the word xt, and GRU is gated recurrent unit [Cho et al., 2014].

The decoder takes as input a context vector ct and the embedding of a previously decoded word e(yt-1), and updates its state st using another GRU:

where [ct-1; e(yt-1)] is the concatenation of the two vectors, serving as input to the GRU network. The context vector ct-1 is an attentive read of H, which is a weighted sum of the encoder's hidden states as ct-1 = ∑nk=1 αt-1 k hk, and αt-1 k measures the relevance between state st-1 and hidden state hk. Refer to [Bahdanau et al., 2014] for more details.

The decoder generates a token by sampling from the output probability distribution which can be computed as follows:

where y<t = y1y2 · · · yt-1, the words already generated.

1 Throughout the paper, a normal letter denotes a discrete symbol while a bolded letter denotes a vector.

3.2 Task Definition and Overview

Our problem is formulated as follows: Given a post X = x1x2 · · · xn and some commonsense knowledge graphs G = {g1, g2, · · · , gNG }, the goal is to generate a proper response Y = y1y2 · · · ym. Essentially, the model estimates the probability: P(Y |X,G) = ∏mt=1 P(yt|y<t,X,G). The graphs are retrieved from a knowledge base using the words in a post as queries, and each word corresponds to a graph in G 2 . Each graph consists of a set of triples gi = {τ1, τ2, · · · , τNgi } and each triple (head entity, relation, tail entity) is denoted as τ = (h, r, t).

We adopt TransE [Bordes et al., 2013] to represent the entities and relations in the knowledge base. In order to bridge the representation gap between knowledge base and unstructured conversational texts, we adopt a MLP for the purpose: a knowledge triple τ is represented by k = (h, r, t) = MLP(TransE(h, r, t)), where h/r/t are the transformed TransE embeddings for h/r/t respectively.

The overview of our commonsense conversational model (CCM) is presented in Figure 2. The knowledge interpreter takes as input a post X = x1x2 · · · xn and retrieved knowledge graphs G = {g1, g2, · · · , gNG } to obtain knowledgeaware representations at each word position, by concatenating a word vector and its corresponding knowledge graph vector. A knowledge graph vector represents a knowledge graph for the corresponding word in X through a static graph attention mechanism. The knowledge aware generator generates a response Y = y1y2 · · · ym with our dynamic graph attention mechanism. At each decoding position, it attentively reads the retrieved graphs and the entities in each graph, and then generates a generic word in the vocabulary or an entity in the knowledge graphs. The entity is selected by attending on the graphs and the triples within each graph.

2 For a word without any match, there is a special graph denoted as Not A Fact.

3.3 Knowledge Interpreter

The knowledge interpreter is designed to facilitate the understanding of a post. It augments the semantics of a word by including the corresponding graph vector for the word, as shown in Figure 3. The knowledge interpreter uses each word xt in a post as the key entity to retrieve a graph gi = {τ1, τ2, · · · , τNgi } (the yellow parts) from the entire commonsense knowledge base. Each retrieved graph consists of a key entity (the red dots), its neighboring entities (the blue dots) and relations between entities. For common words (e.g., of) which match no entity in the commonsense knowledge graph, a knowledge graph that contains a special symbol Not A Fact (the grey dots) is used. Then, the knowledge interpreter computes the graph vector gi of the retrieved graph using the static graph attention mechanism. After concatenating the word vector w(xt) and the knowledge graph vector gi, the concatenated vector e(xt) = [w(xt); gi] is obtained and fed to the GRU cell of the encoder (see Eq. 1).

Static Graph Attention

The static graph attention mechanism is designed to generate a representation for a retrieved knowledge graph, inspired by [Velickovic et al., 2017]. The major difference to [Velickovic et al., 2017] lies in that our graph attention encodes more structured semantic information by considering not only all nodes in a graph but also relations between nodes.

The static graph attention generates a static representation for a graph, which will be used to augment the semantics of a word in a post.

Formally, the static graph attention mechanism takes as input the knowledge triple vectors K(gi) = {k1, k2, · · · , kNgi } in the retrieved knowledge graph gi, to produce a graph vector gi as follows:

where (hn, rn, tn) = kn, Wh,Wr,Wt are weight matrices for head entities, relations, and tail entities, respectively. The attention weight measures the association of a relation rn to a head entity hn and a tail entity tn.

Essentially, a graph vector gi is a weighted sum of the head and tail vectors [hn; tn] of the triples contained in the graph.

3.4 Knowledge Aware Generator

The knowledge aware generator is designed to generate a response through making full use of the retrieved knowledge graphs, as shown in Figure 4. The knowledge aware generator plays two roles: 1) attentively reading the retrieved graphs to obtain a graph-aware context vector, and using the vector to update the decoder's state; 2) adaptively choosing a generic word or an entity from the retrieved graphs for word generation.Formally, the decoder updates its state as follows:

where e(yt) is the concatenation of the word vector w(yt) and the previous knowledge triple vector kj from which the previous word (yt) is selected,

ct is the context vector as used in Eq. 2, cgt and ckt are context vectors attended on knowledge graph vectors {g1, g2, · · · , gNG } and knowledge triple vectors {K(g1),K(g2), · · · ,K(gNG )} respectively.

Dynamic Graph Attention

The dynamic graph attention mechanism is a hierarchical, top-down process. It first attentively reads all the knowledge graphs and then attentively reads all the triples in each graph for final word generation. Given the decoder state st, it first attends on the knowledge graph vectors {g1, g2, · · · , gNG } to compute the probability of using of each graph gi, which is defined as below:

where Vb/Wb/Ub are parameters, and αg ti is the probability of choosing knowledge graph gi at step t. The graph context vector cgt is a weighted sum of the graph vectors, and the weight measures the association between the decoder's state st and a graph vector gi.

The model then attends on the knowledge triple vectors K(gi) = {k1, k2, · · · , kNgi } within each graph gi to calculate the probability of selecting a triple for word generation, formally as follows:

where βk tj can be viewed as the similarity between each knowledge triple vector kj and the decoder state st, αk tj is the probability of choosing triple τj from all triples in graph gi at step t.

Finally, the knowledge aware generator selects a generic word or an entity word 3 with the following distributions:

where γt ∈ [0, 1] is a scalar to balance the choice between an entity word we and a generic word wc, Pc/Pe is the distribution over generic/entity words respectively. The final distribution P(yt) is a concatenation of two distributions.

3.5 Loss Function

The loss function is cross entropy between the predicted token distribution ot and the reference distribution pt in the training corpus. Additionally, we apply supervised signals on the knowledge aware generator layer to teacher-force the selection of an entity or a generic word. The loss on one sample < X, Y > (X = x1x2 · · · xn, Y = y1y2 · · · ym) is defined as:

3 Entity words are taken from the neighboring entities of the knowledge triples.

where γt is the probability of selecting an entity word or a generic word, and qt ∈ {0, 1} is the true choice of an entity word or a generic word in Y . The second term is used to supervise the probability of selecting an entity word or a generic word.

4 Experiments

4.1 Dataset

Commonsense Knowledge Base

ConceptNet 4 is used as the commonsense knowledge base. It contains not only world facts such as "Paris is the capital of France" that are constantly true, but also informal relations between common concepts that are part of daily knowledge such as "A dog is a pet". This feature is desirable in our experiments, because the ability to recognize the informal relations between common concepts is necessary in the open-domain conversation setting. For simplicity, we removed triples containing multi-word entities, and 120,850 triples were retained with 21,471 entities and 44 relations.

Commonsense Conversation Dataset

We adopted 10M reddit single-round dialogs from the site 5 . Since we target at using commonsense knowledge to facilitate language understanding and generation, we filtered the original corpus with the knowledge triples. If a post-response pair can not be connected by any triple (that is, one entity appears in the post and the other in the response), the pair will be removed. The statistics can be seen in Table 1.

We randomly sampled 10,000 pairs for validation. To test how commonsense knowledge can help understand common or rare concepts in a post, we constructed four test sets: highfrequency pairs in which each post has all top 25% frequent words, medium-frequency pairs where each post contains at least one word whose frequency is within the range of 25%- 75%, low-frequency pairs within the range of 75%-100%, and OOV pairs where each post contains out-of-vocabulary words. Each test set has 5,000 pairs randomly sampled from the dataset 6 .

4.2 Implementation Details

Our model was implemented with Tensorflow 7 . The encoder and decoder have 2-layer GRU structures with 512 hidden cells for each layer and they do not share parameters. The word embedding size is set to 300. The vocabulary size is limited to 30,000. We used TransE [Bordes et al., 2013] to obtain entity and relation representations. The embedding size of entities and relations is set to 100.

4 https://conceptnet.io

5 https://www.reddit.com/r/datasets/ comments/3bxlg7/i_have_every_publicly_ available_reddit_comment/

6 Our data are available at: http://coai.cs.tsinghua. edu.cn/hml/dataset/#commonsense

7 https://github.com/tensorflow/tensorflow

We used the Adam optimizer with a mini-batch size of 100. The learning rate is 0.0001. The models were ran at most 20 epoches, and the training stage of each model took about a week on a Titan X GPU machine. Our code is available at: https://github.com/tuxchow/ccm.

4.3 Baselines

We chose several suitable baselines:

• A seq2seq model (Seq2Seq) [Sutskever et al., 2014], which is widely used in open-domain conversational systems.
• A knowledge-grounded model (MemNet) adapted from [Ghazvininejad et al., 2017], where the memory units store TransE embeddings of knowledge triples.
• A copy network (CopyNet) model [Zhu et al., 2017], which copies a word from knowledge triples or generates a word from the vocabulary.

4.4 Automatic Evaluation

Metrics: We adopted perplexity [Serban et al., 2015] to evaluate the model at the content level (whether the content is grammatical and relevant in topic). We also calculated the number of entities per response to measure the model's ability to select the concepts from the commonsense knowledge

base in generation. This metric is denoted by entity score. Results: As shown in Table 2, CCM obtains the lowest perplexity on all the test sets, indicating that CCM can understand users' posts better and generate more grammatical responses. Moreover, CCM selects the most entities from the commonsense knowledge among the models during generation, demonstrating that commonsense knowledge can truly

facilitate response generation.

More interestingly, commonsense knowledge is more frequently used by CCM in low-frequency posts than in highfrequency ones (entity score: 1.196 vs. 1.156 ). This is in line with our intuition that rare concepts need more background knowledge to understand and respond. For the perplexity, the score for high-frequency posts is lower than low-frequency ones (35.36 vs. 40.67) since the probabilities for the common words can be more sufficiently trained.

4.5 Manual Evaluation

We resorted to a crowdsourcing service, Amazon Mechanical Turk, for manual annotation. 400 posts were randomly sampled for manual annotation. We conducted pair-wise comparison between the response generated by CCM and the one by a baseline for the same post. In total, there are 1,200 pairs since we have three baselines. For each response pair, seven judges were hired to give a preference between the two responses, in terms of the following two metrics. Tie was allowed. Notice that system identifiers were masked during annotation.

Metrics: We defined two metrics: appropriateness at the content level (whether the response is appropriate in grammar, topic, and logic); and informativeness at the knowledge level (whether the response provides new information and knowledge in addition to the post).

Annotation Statistics: We calculated the agreements to measure inter-rater consistency. For appropriateness, the percentage of the pairs that at least 4 judges gave the same label (4/7 agreement) amounts to 96.3%, and the percentage for at least 5/7 agreement is 60.2%. For informativeness, the percentage for at least 4/7 agreement is 90.4% and that for at least 5/7 agreement is 55.1%.

Results: The results are shown in Table 3. The score is the percentage that CCM wins a baseline after removing "Tie" pairs. CCM outperforms all the baselines significantly in terms of both metrics (sign test, p-value < 0.005) on all the test sets. Furthermore, CCM has about 60% chances to win the strongest baseline, CopyNet, which makes use of knowledge triples (entities) separately and independently. This demonstrates the effectiveness of our graph attention mechanisms.

Noticeably, the probabilities that CCM wins Seq2Seq on the OOV dataset are remarkably higher than those on the high-frequency dataset (0.673 vs. 0.605 in appropriateness, and 0.716 vs. 0.656 in informativeness). This further indicates that commonsense knowledge is more useful in understanding rare concepts in post since Seq2Seq has no ability to use such knowledge. For MemNet and CopyNet, we did not observe such differences because the two baselines have the ability of using knowledge more or less.

4.6 Case Study

A sample conversation is shown in Table 4. The red-colored word "breakable" in the post is an entity word in the knowledge base as well as an out-of-vocabulary word for all the models. Without the access to commonsense knowledge, the Seq2Seq model is unable to understand the post because of the out-of-vocabulary word, "breakable", thereby generating OOV words. MemNet can generate some meaningful words as it reads the triple embeddings in its memory, but still outputs OOV. CopyNet can read and copy words from knowledge triples. However, CopyNet generated fewer entity words than ours (see Table 2), as it only deals with separate knowledge triples. Instead, CCM treats the knowledge graph as a whole and encodes more structured, connected information via linked entities and relations. It thus generates more reasonable responses through better use of knowledge. This simple example shows that CCM can generate more appropriate and informative responses than the baselines.

5 Conclusion and FutureWork

In this paper, we present a commonsense knowledge aware conversational model (CCM) to demonstrate how commonsense knowledge can facilitate language understanding and generation in open-domain conversational systems. Automatic and manual evaluation show that CCM can generate more appropriate and informative responses than state-of-theart baselines.

As future work, our graph attention mechanisms may inspire other tasks to use commonsense knowledge.

Acknowledgments

This work was partly supported by the National Science Foundation of China under grant No.61272227/61332007 and the National Basic Research Program (973 Program) under grant No. 2013CB329403.