Enhancing Dialog Coherence with Event Graph Grounded Content Planning

1 Introduction

One of the key goals of AI is to build a machine that can converse with humans by generating informative, coherent and sustainable open-domain conversations. To achieve this goal, end-to-end neural generative models have been studied [Ritter et al., 2011; Shang et al., 2015]. However, these models tend to produce generic responses. To address this issue, some work propose to generate responses by grounding on external knowledge [Dinan et al., 2019; Ghazvininejad et al., 2018; Zhou et al., 2018].

However these knowledge grounded methods tend to generate less coherent dialogs in the setting of multi-turn conversation generation since they focus on improving response informativeness with little attention on multi-turn dialog coherence. In this paper, we make a step towards coherent and informative multi-turn open-domain conversation generation.

∗ This work was done at Baidu.

† Equal contribution.

‡ Corresponding author.

(c)

Figure 1: A sample dialog grounded on a narrative event chain. Figure (a) shows a sample event chain (green) extracted from a document. Figure (b) provides a graph with the event chain in (a). Figure (c) shows a coherent multi-turn dialog with appropriate content ordering. The red dotted line refers to the process of selecting an appropriate vertex from the graph to guide dialog generation.

To address this challenge, we propose to leverage the knowledge of narrative event chains to facilitate conversation generation. Narrative event chains are partially ordered sets of events centered around a common protagonist [Chambers and Jurafsky, 2008]. Figure 1 provides a sample event chain extracted from a narrative text. We see that this chain consists of partially ordered events about a single topic. Previous study shows that the use of event chains as background knowledge leads to better coherence judgement of real narrative instances in a narrative cloze task [Chambers and Jurafsky, 2008; Li et al., 2018]. It motivates our study of event chains for conversation generation since the chains might help dialog content ordering, and conditioning on the chains makes it easier to generate coherent dialogs. Figure 1 illustrates a sample dialog conditioned on event chains.

To this end, we present a novel event graph grounded RL framework (EGRL). It consists of an event graph, an RL based multi-policy module to conduct explicit high-level response content planning, and a response generator conditioned on the planned content.

First, for event graph construction, we extract event chains from story texts, and connect chains sharing the same events to obtain a directed graph. In this graph, vertices represent events (most simply verb phrases), and edges indicate relations between the events. 1 Then we use this graph to facilitate Algorithm 1 Event extraction from each story sentence

1 Here, relations refer to temporal order, causal relation, etc.

Input: A sentence S

Output: A set of events E from S

• 1: Obtain a dependency parse tree T for S;
• 2: Get all the head words HED that are connected to ROOT node, and all the leaf nodes in T (denoted as L);
• 3: for each leaf node in |L| do
• 4: Extract a phrase consisting of words along the tree from HED to current leaf node, denoted as ei;
• 5: If ei is a verb phrase, then append it into E;
• 6: end for
• 7: return E

In particular, we first perform dependency parsing for each sentence in story texts to obtain its dependency parse tree. 2 With the obtained dependency parse trees, we extract verb phrases as events for each sentence. The detailed extraction process is presented in Algorithm 1. Then the extracted events are connected in the order they occur in the stories to form event chains.

If two events share no less than 80% words, they will be merged into one event. 3 In this way, we can connect the event chains into a directed graph where vertices are events, and edges represent relations between the events. Formally, the event graph is defined as G = {V, E}, where V is the set of all vertices and E is the set of all edges.

2.2 RL BasedMulti-PolicyModule

To foster a coherent and informative dialog, we propose a novel event graph grounded RL based multi-policy method to conduct high-level response content planning. Given a dialog context (previous two utterances), we first link the context to the graph by retrieving the most related top one vertex as the contextual vertex. Specifically, we utilize string matching to obtain five related vertices 4 , and then we retrieve top one vertex from them according to cosine distance in the pretrained embedding space. We represent a vertex or a dialog context as an average of embeddings of its words. Then the RL-based multi-policy module learns to walk along the edges in the graph and then select an appropriate vertex from onehop neighbors of the contextual vertex. The selected vertex

2 https://ai.baidu.com/tech/nlp basic/dependency parsing

3 Here, words refer to noun, verb and adjective words.

4 We first use the user message at current time step for vertex matching. If no vertices are matched, we will use the system response at previous time step for vertex matching.

conversation generation, as shown in Figure 1.

Second, we present a novel event graph grounded RL based multi-policy method to conduct high-level content planning. Given a dialog context, it first links the context to the graph to obtain the contextual vertex. Then it learns to walk along graph edges and identifies an appropriate vertex from onehop neighbors of the contextual vertex as response content. In this way, our method can utilize event chains directly. Furthermore, to foster a coherent dialog with appropriate content ordering and high contextual relevance, we devise a novel multi-policy decision making mechanism for the RL policy. It consists of three sub-policies: (1) the first sub-policy uses reward signals from a storytelling model [Li et al., 2019] to make the overall structure of multiple responses being consistent with event ordering; (2) the second sub-policy uses reward signals from a topic model [Ramage et al., 2009] to guarantee global response relevance; (3) the third sub-policy uses reward signals from a semantic matching model [Kadlec et al., 2015] to improve local response relevance. Then these sub-policies are fed into a policy-fusion gate for a final decision on content planning. Notice that to avoid "one-sided conversation", we employ two sub-policies (the second one and the third one) to guarantee response content relevance to user message.

Finally, the response generator produces a response conditioned on the planned content and the dialog context.

In summary, this paper makes the following contributions:

• We leverage an event graph to determine a sketch of a multi-turn dialog by RL based content planning, which makes it easier to generate a more coherent dialog.
• To ensure appropriate content ordering and high contextual relevance for content planning, we devise a novel multi-policy decision making mechanism for RL policy.
• Our study indicates that both the event graph and the multi-policy decision making mechanism are crucial to our superior performance in dialog coherence.

2 Our Approach

As shown in Figure 2, the overall architecture of our framework consists of three main parts: an event graph, an RL based multi-policy module and a response generator. Next, we elaborate the details for each of them.

2.1 Event Graph Construction

To obtain the event graph, we first extract event chains from story texts in ROCStories [Mostafazadeh et al., 2016] and then construct the graph based on the extracted chains.

will be fed into the response generator to obtain a response. In this way, our method can utilize event ordering information directly. Next we elaborate the main components of RL: state and action, a multi-policy decision making mechanism and reward.

State and action. The current state st consists of three parts: svt to represent the contextual vertex and selected vertices at all previous time steps, sut to represent the user message at all previous time steps, and slt to represent current user message. The candidate action set Ast = {ai}Ni=1 consists of all outgoing one-hop neighbors of the contextual vertex, where N is the number of candidate actions. All states and actions are encoded by Transformers [Vaswani et al., 2017] to obtain their vector representations.

Multi-policy decision making mechanism and rewards. To foster a coherent dialog with appropriate content ordering and high contextual relevance, we first devise a novel multi-policy decision making mechanism that uses different rewards to train three sub-policies. Then three sub-policies are fed into a policy-fusion gate to obtain the final policy and we also design another three rewards to train the final policy.

In particular, to ensure appropriate dialog content ordering, we first employ reward signals from a storytelling model (named as content ordering reward) to train the first subpolicy, named as content ordering sub-policy. It helps our policy to make full use of the event ordering information between events in narrative texts for content planning. The subpolicy is formalized as follows:

where esvt and eai denote the vector representations of svt and the action ai respectively. The reward value is the prediction probability of a storytelling model [Li et al., 2019].

Second, to improve global relevance (at topic level) of generated responses, we use reward signals from a topic model (named as global relevance reward) to train the second subpolicy, named as global relevance sub-policy:

where esut is the vector representation of sut . For the global relevance reward, we first use a topic model [Ramage et al., 2009] to obtain the topics of the user message at all previous time steps and candidate actions respectively. Then we compute the embedding distances between the topic word embedding of those user message and that of each candidate action as reward values.

Third, to improve local relevance between current response and current user message (single-turn), we employ reward signals from a semantic matching model (named as local relevance reward) to train the third sub-policy, named as local relevance sub-policy, presented as follows:

where eslt is the vector representation of slt . We use a BiLSTM-based semantic matching model [Kadlec et al., 2015] to calculate the local relevance. Finally, these three sub-policies are fed into a policy-fusion gate to make a final decision on content planing, which is computed as follows:

Here, α1, α2 and α3 denote the weight coefficients of the three sub-policies. Each of them is computed as follows:

where e1, e2, e3 denote esvt , esut , eslt respectively.

Rewards

We design three rewards to train the final policy. Specifically, following previous work [Tang et al., 2019; Yao et al., 2018; Zhao et al., 2019], we consider utterance-based rewards shown as follows:

Repetition penalty. The reward is 1 when a generated response shares more than 60% words with one of contextual utterances, otherwise 0.

Moreover, to fully leverage the event graph in policy learning, we employ another two event graph based reward factors:

Global coherence. We calculate the average cosine distance between current selected vertex and all previously selected vertices (or contextual vertex) in TransE based embedding space [Bordes et al., 2013] as global coherence reward. We see that vertices from the same highly connected sub-graph are more likely to constitute coherent dialog and it leads to obtain high global coherence reward.

Sustainability. It is reasonable to give priority to vertices with a large number of neighboring vertices to foster a longlasting dialog. In particular, we calculate sustainability reward as a PageRank score of the selected vertex. The scores are calculated on the full event graph.

For the final policy, we define its reward as a weighted sum of the above-mentioned three factors with weights whose default values are set as [-0.5, 4, 7000].

At each time step, we sample vertices from the three subpolicies and the final policy by Gumbel-Softmax [Jang et al., 2016] respectively. The vertex sampled by the final policy is utilized to guide response generation.

2.3 Response Generator

The generator produces a response conditioned on the event vertex selected by the policy module and the context. In this work, we use a RNN decoder with a copy mechanism to suit our generation task. In particular, we first build a dataset that suits the settings of our generator by modifying our experimental datasets (Weibo or Twitter Corpus) as follows: (1) sampling an phrase from each gold response as its corresponding event vertex; (2) replacing the sampled phrase with a special symbol, "[event]" in each response. Then we train the response generator with user message and corresponding event vertices as inputs and responses as ground truth.

2.4 Training

To make the RL based training process more stable, we employ the A2C method [Sutton and Barto, 2018] for model optimization. The three sub-policies and the fusion gate are trained simultaneously. Moreover, we only update parameters of the policy module, and parameters of the response generator stay intact during RL training.

3 Experiment

3.1 Datasets

Weibo Corpus. [Shang et al., 2015] The Weibo corpus contains 2.6Mmessage-response pairs for training, 10k pairs for validation and 10k pairs for test.

Twitter Corpus. [Ritter et al., 2011] The corpus contains 1.3M dialogs for training, 10k for validation and 10k for test.

Narrative Event Graph. The ROCStories corpus contains 98,161 five-sentence stories. For the Weibo corpus, we translate the ROCStories corpus into Chinese by Baidu Translate API. 5 Meanwhile, the topic overlap between ROCStories and Weibo (or Twitter) is 98.1% ( or 98.5%). 6 Our constructed narrative event graph contains 1,011,547 vertices and 13,668,796 edges. Moreover, to evaluate the quality of the graph, we conduct human evaluation by randomly sampling 500 edges from the graph and then calculate the proportion of edges which are suitable for chatting. The results show that 73.6% of edges are appropriate to dialog.

3.2 Baselines

S2S. It is the widely-used seq2seq model with attention mechanism [Luong et al., 2015].

CCM. It is a commonsense knowledge based conversation model [Zhou et al., 2018], which leverages commonsense knowledge from ConceptNet through two graph attention mechanisms to facilitate informative response generation. 7

CMR. It is a document augmented neural conversation model [Qin et al., 2019] that jointly models response generation and on-demand machine reading. For fair comparison, we use the ROCStories corpus as the document of CMR.

LaRL. It is a latent variable driven RL based dialog model [Zhao et al., 2019]. We choose the multivariate categorical latent variables as RL actions since it performs the best.

Notice that CCM leverages ConceptNet for generation and CMR uses ROCStories, and we rerun original source codes for CCM 8 , CMR 9 and LaRL 10 .

We adopt pre-trained Tencent AI Lab Embedding 11 (for Weibo) and Glove 12 (for Twitter) with the size of 200. The vocab size is 50000 and the dimension of all the representations is set to 512. Dropout rate is 0.3. The optimizer adopts Adam and the learning rate is set to 0.002. The discounting weight for reward is 0.95. 13

5 http://fanyi-api.baidu.com/api/trans/product/prodinfo.The translate accurary is 95% by human evaluation.

6 Here, we use the LDA model [Ramage et al., 2009] to obtain topics of stories and datasets, and the total number of topics is 200.

7 https://conceptnet.io

8 https://github.com/tuxchow/ccm

9 https://github.com/qkaren/converse reading cmr

10 https://github.com/snakeztc/NeuralDialog-LaRL

11 https://ai.tencent.com/ailab/nlp/embedding.html

12 https://nlp.stanford.edu/projects/glove/

3.3 Experimental Settings

Conversation with user simulator. Following the experimental settings in previous work [Li et al., 2016b; Tang et al., 2019], we use a user simulator to play the role of human and let each of the models chat with the same simulator. The user simulator is a pre-trained sequence-to-sequence model with attention mechanism to produce user-side utterances. During the experiments, we use the same user simulator for RL training of our model and baselines. Specifically, given a model to be evaluated, we randomly select an utterance from test set (as the starting position of sessions) to start the conversations with the simulator. Moreover, to avoid infinite conversation, we set maximum number of dialog turns to 8 (i.e. in total, 16 utterances are generated by the simulator and the model) in our experiment. Finally, for each model, we collect 100 model-simulator dialogs to perform multi-turn level evaluation. Meanwhile, for each model, we randomly sample 200 message-response pairs from the model-simulator dialogs for single-turn level evaluation.

Conversation with human. Given a model to be evaluated, we randomly select an utterance from test set for the model to start the conversations with a human turker. Then the human is asked to converse with the model till 8 turns are reached. Finally, we obtain 50 model-human dialogs for multi-turn level evaluation. For single-turn level evaluation, we also randomly sample 200 message-response pairs from model-human dialogs for each model.

3.4 EvaluationMetrics

We define six human evaluation metrics and two automatic metrics. Since the proposed system does not aim at predicting the highest-probability response at each turn, but rather the long-term success of a dialog (e.g., coherence), we do not employ BLEU or perplexity for automatic evaluation [Li et al., 2016b]. (1) Content ordering (Content-Order.) for coherence: The metric is used to evaluate whether the ordering of dialog content is appropriate. In practice, we first manually segment a dialog by topics and then conduct evaluation on each sub-topic fragment. 14 A fragment will be rated "1" if the ordering is appropriate, otherwise "0". Finally we compute the average of the scores of all sub-topic fragments over the dialog as content ordering value. (2) Global relevance (Global-Rele.) for coherence: Global relevance is used to count the number of incoherent errors within a topic of a dialog. Common incoherence errors in a topic include anaphora errors across utterances and information inconsistency. Similarly,we also perform global relevance evaluation on the above segmented sub-topic fragments. "0" means that there are more than two incoherence errors in a sub-topic fragment,. "1" means that there are one error. "2" means that there are no errors. Finally, we compute the average score of all sub-topic fragments over the dialog as global relevance value. (3) Local relevance or Appropriateness (Appr.) for coherence: "0" if a response is inappropriate as an reply, otherwise "1". (4) Informativeness (Info.): "0" if a response is a "safe" response, e.g. "I don't know", or it repeats most of the context (more than 80%), otherwise "1". (5) Distinct (Dist.): Dist-i calculates the ratio of distinct i-gram in generated responses [Li et al., 2016a]. We use Dist-1 and Dist-2 to measure the diversity of generated responses. (6) Engagement (Enga.) for overall quality: This metric measures the overall quality of a dialog. "1" if the dialog has appropriate content ordering, no more than one incoherent errors and responds appropriately to users, otherwise "0". (7) Length-ofdialog (Length) for overall quality: Here, we say a dialogue ends when two consecutive utterances from the same agent are highly overlapping [Li et al., 2016b]. (8) User-interests consistency (User-Cons.) for overall quality: The metric is used to evaluate if a model can follow a new topic mentioned by a user. A dialog will be rated "1" if the model follows the user's new topic, otherwise "0".

13 We optimize these values by grid search.

14 Each conversation session contains no more than 4 topics.

3.5 Experiment Results

We invite three annotators to evaluate each dialog from each model. System identifiers are masked during evaluation.

Results on Weibo Corpus

Conversation with simulators. As shown in Table 1, EGRL significantly outperforms all baselines in terms of all the metrics except for length-of-dialog (sign test, p-value < 0.01). It demonstrates that EGRL can effectively foster a more coherent, informative, engaging conversation. In terms of coherence, our model outperforms baselines by a large margin in terms of content ordering, global relevance and appropriateness. It indicates that event ordering information and reward signals from a storytelling model can help our model guarantee content ordering. And the use of the global and local relevance rewards can help keep responses globally and locally relevant with users. Meanwhile, our model also significantly surpasses baselines in terms of informativeness and Dist-1/2. In terms of overall quality of dialogs, our model obtains the highest scores in terms of engagement and length-of-dialog. In addition, our model obtains the best user-interests consistency result compared with baselines. It indicates that with EGRL, our model avoids one-sided conversation while focusing on dialog coherence. We also observe that S2S tends to generate generic and dull responses, achieving relatively low scores of informativeness and Dist1/2. CCM amd CMR obtain better informativeness scores than S2S, indicating that incorporating external knowledge into dialog generation can enhance response informativeness. LaRL tends to generate informative but incoherent dialogs, since LaRL's latent variables can not provide sufficient information to accurately guide response generation. The Kappa value for inter-annotator agreement is above 0.4, showing moderate agreement among three annotators.

Conversation with human. As shown in Table 2, EGRL significantly outperforms baselines in terms of all the metrics except for length-of-dialog (sign test, p-value < 0.01), which is consistent with the results in Table 1. We observe that scores of most of metrics on Table 2 have been improved in comparison with Table 1. The possible reason is that human can produce higher quality utterances compared with the simulator, e.g., humans rarely fall into a "dead cycle" during conversation, which is helpful for models to produce a longer dialog. Here, the Kappa value is above 0.4.

Ablation Study. We conduct an ablation study in the setting of model-simulator conversation. First, to evaluate the contribution of the event graph, we remove the event graph from EGRL, denoted as EGRL w/o EG, where we cannot use Table 3: Results for dialogs with user simulator on Twitter corpus. * denotes human evaluation metrics and # denotes automatic metrics.

graph information for action space pruning and reward design. Moreover, we replace ConceptNet with the event graph to augment the CCM model, denoted as CCM w/ EG. As shown in Table 1, the performance of EGRL w/o EG drops dramatically in terms of dialog coherence and informativeness. Furthermore, the event graph can improve the performance of CCM in terms of all the metrics, especially for content ordering and user-interests consistency. It demonstrates the effectiveness of event graph for appropriate dialog content ordering. Second, to verify the effectiveness of multi-policy decision making mechanism, we replace multi-policy mechanism with a single-policy module (merging the inputs of all sub-policies as its input, and all reward items as its reward), denoted as EGRL w/o MP. Results show that the scores of content ordering and appropriateness drop sharply. It confirms that multi-policy mechanism can enhance coherence.

Results on Twitter Corpus

As shown in Table 3, our model significantly outperforms the baselines in terms of dialog coherence, engagement and informativeness except for length-of-dialog (sign test, p-value < 0.01). It is consistent with Table 1.

Case Study

Figure 3 presents an example generated by EGRL. We see that our model can generate more coherent and informative responses. In particular, the ordering of the dialog content by our model is more appropriate, e.g., "tooth decay" → "emergency surgery" → "recover".

4 RelatedWork

Knowledge-grounded Conversation Generation. There are growing interests in leveraging external knowledge for generation of more informative responses [Ghazvininejad et al., 2018; Moghe et al., 2018; Zhou et al., 2018; Bao et al., 2019; Moon et al., 2019; Liu et al., 2019; Dinan et al., 2019; Xu et al., 2020]. Different from those work, we put more efforts on dialog coherence in the setting of multi-turn dialogs. In particular, we care about the ordering of selected knowledge, which is less studied in previous work.

RLbasedModels forConversationGeneration. Previous work adopt RL based frameworks to learn dialog strategies merely from dialog corpora, which fall into two categories: (1) word-level methods with words as RL actions [Li et al., 2016b; Zhang et al., 2018]; (2) utterance-level methods with high-level utterance representations as RL actions, e.g., latent

variables or keywords [Zhao et al., 2019; Yao et al., 2018]. In this work, we investigate how to leverage external knowledge to explicitly plot a dialog by RL based content planning.

5 Conclusion

In this paper, we present an event graph grounded RL framework (EGRL) to demonstrate how the knowledge of event chains can help plan a multi-turn open-domain dialog. Experimental results on two datasets show that EGRL can generate a more coherent dialog with appropriate content ordering when compared with baselines.

Integrating text knowledge directly for modeling multiturn dialog logic paves the way for developing models in lowresource domains that lack sufficient dialog corpus. In the future, we will adapt EGRL for low-resource domains.

Acknowledgments

We thank the anonymous reviewers for their helpful comments and suggestions. This work is supported by the National Key Research and Development Project of China (No.2018AAA0101900) and the National Natural Science Foundation of China (NSFC) via grant 61976072.