MRF -Chat: Improving Dialogue with M arkov Random Fields (2021)

Abstract: Recent state-of-the-art approaches in open-domain dialogue include training end-to-end deep-learning models to learn various conversational features like emotional content of response, symbolic transitions of dialogue contexts in a knowledge graph and persona of the agent and the user, among others. While neural models have shown reasonable results, modelling the cognitive processes that humans use when conversing with each other may improve the agent’s quality of responses. A key element of natural conversation is to tailor one’s response such that it accounts for concepts that the speaker and listener may or may not know and the contextual relevance of all prior concepts used in conversation. We show that a rich representation and explicit modeling of these psychological processes can improve predictions made by existing neural network models. In this work, we propose a novel probabilistic approach using Markov Random Fields (MRF) to augment existing deep-learning methods for improved next utterance prediction. Using human and automatic evaluations, we show that our augmentation approach significantly improves the performance of existing state-of-the-art retrieval models for open-domain conversational agents.

## introduction with advances in deep learning, the natural language understanding community has seen a recent proliferation of open-domain dialogue systems such as @xcite ; @xcite ; @xcite as well as competitions such as the amazon alexa prize @xcite and convai @xcite . existing approaches can be classified into two main categories: generative models and retrieval models. while the former produce responses from a generative language model @xcite , retrieval * equal contribution models aim to select the best response from a set of candidate responses given a conversation history. this paper focuses on retrieval-based models. most of the prior work in retrieval-based models has focused on training end-to-end models using different architectures (eg. key-value memory networks @xcite , gated self-attention @xcite , poly-encoder @xcite on specific datasets to statistically learn various conversational features like emotional content of response @xcite , symbolic transitions of dialogue contexts in a knowledge graph @xcite and even the persona of the agent and the user @xcite ). in natural conversations, while humans often view each other as cognitive agents, we observe that prior work has not focused on the cognitive processes that humans use when conversing with each other. we posit that explicitly modeling these cognitive processes and using these models alongside existing statistical approaches can improve state-of-the-art. in conversational inference, the cognitive theory of mutual knowledge proposes that speakers and listeners maintain mental models of the knowledge and beliefs they share with each other to find common ground for communication @xcite . it follows that in a two-person conversation, each speaker maintains both (i) a model of their partner's knowledge and (ii) a model of the knowledge they have communicated to their partner. these models provide information about their mutual knowledge and help in deciding the next utterance. further, as the conversation continues, each speaker updates their mental model as they gain new information from and provide new information to their partner. consider the following example of a conversation between two speakers: sp 1: did you see the avenger's movie? (u 1 ) sp 2: yes, i loved thor's character in it. (u 2 ) sp 1: do you like superhero movies? (u 3 ) in u 1 , speaker 1 offers "avengers" and "movie" as context for the conversation. speaker 2 observes that speaker 1 knows about "avengers", so they must also know the related concept "thor". consequently, speaker 2 offers "thor" as context with u 2 . now, from u 1 and u 2 , speaker 1 infers that the concept "superhero movies" has the highest "mutual knowledge" and says u 3 . along with mutual knowledge, humans also account for contextual relevance of concepts, as conversation flows from one topic to another. that is, even though a concept may be familiar to both people at one point during the conversation, it may not remain relevant when they discuss another topic. while the theory of mutual knowledge forms the basis of grounding in conversation and contextual relevance plays a vital role in conversations, to the best of our knowledge, there hasn't been an attempt to explicitly model these processes. based on these theories, we propose a novel probabilistic approach using markov random fields (mrf) to model mutual knowledge and contextual relevance. we augment existing deep-learning methods with our model for improved next utterance prediction. in this paper, we refer to deep-learning models as base models and to our algorithm as mrf-chat. our primary contribution is an algorithm (mrf-chat) to augment existing statistical deep-learning methods to improve the performance of conversational agents. mrf-chat is model agnostic, easy to implement and independent of the base model. our augmentation approach achieves strong results on human and automatic evaluations in predictions made by state-of-the-art models on two widely used datasets (personachat and blendedskilltalk). poly-encoder (convai2 dataset). the con-vai2 dataset is based on persona-chat and involves conversations between pairs of human speakers who are each given a persona, with the goal of getting to know one another. recently, @xcite introduced poly-encoder architectures which use self-attention to learn context features at a global rather than token level. they showed that poly-encoders are more accurate than bi-encoders and faster (at test time) than cross-encoders. knowledge prediction from partial information. for an algorithm to compute mutual knowledge, a person's knowledge of related concepts from partial information must be inferred. if a person talks about "avengers", the algorithm should infer the probability of them also knowing "superhero". we build upon our prior work @xcite where we experimentally validated a model for predicting children's vocabulary from partial information of their existing knowledge. the model made assumptions based on the psycholinguistic theory of semantic learning which states that humans learn new words by forming semantic associations with words they already know. more specifically, the model was based on the following assumption: if it is observed that a child knows a given word, the child must have learned it by forming semantic associations with words they already knew. thus, it is likely that if a child knows a given word, they also know words semantically related to it. the steps for model construction are as follows: thus, we can find the probability of a person knowing any target concept given their knowledge about some concepts. ## preliminaries a markov random field (mrf) is an undirected graphical model of a joint distribution, specified by a graph @xmath0, e) and a set of random variables an edge e ij between nodes x i and x j captures dependencies between nodes. these dependencies are represented by potential functions φ(x). potential functions may be defined over pairs or cliques of nodes. when they are defined for pairs of nodes, the mrf is called a pairwise mrf. when φ c (x c ) > 0, the probability distribution can also be expressed by a corresponding gibbs field. for a given mrf: inference on mrf gives marginal probabilities of each node. while exact inference on mrfs is computationally intractable, approximate inference algorithms such as belief propagation and markov chain monte carlo are often used in practice. in this paper, we use sum-product belief propagation. ## mrf-chat we consider the setting where a user and conversational agent take turns interacting. we wish to incorporate the following features for the agent. more formally, for a prior agent utterance u agent and a prior user utterance u user , a set of candidate response utterances u candidates and a base model b, we are interested in selecting a response utterance u @xmath1. we now discuss the steps to incorporate p1 and p2 separately and then discuss a method to combine them to generate a response. ## experiments for our experiments, we compare the performance of state-of-the-art models in 2 settings: (i) base models augmented with mrf-chat (base+mrf) and (ii) base models alone (base) foot_2 . baseline models. we used poly-encoders and kv-mem as the current state-of-the-art baselines. humeau et al. (2019) show that poly-encoders outperform bi-encoders and all models submitted to the convai2 competition including transfer-transfo @xcite , obtaining new stateof-the-art. additionally, poly-encoders are based on bert pretraining. hence, we believe that polyencoders provide not only a reasonable but also a challenging baseline to improve upon. further, key-value memory networks are a common standard baseline used in prior work. datasets. (i) kv memory: pre-trained on persona-chat (10,907 dialogues) and evaluated on persona-chat validation (1000 dialogues) and test (968 dialogues) sets. (ii) poly-encoder: pre-trained on the convai2 dataset and evaluated on validation (1,009 conversations) and test sets (980 conversations) from the blendedskilltalk dataset (bst) @xcite . we do not use the convai2 test set because it is not publicly available, and the validation set alone does not have enough conversations to statistically evaluate our model. bst has twice as many conversations for evaluation and was specifically collected to evaluate models on their ability to be engaging, knowledgeable and empathetic as opposed to a single metric that previous datasets targeted. we believe this dataset provides an independent and robust test bed to evaluate our model's performance. multi-turn conversations. for each conversation in the dataset, we used the first 4 turns as context, processing each utterance as described in section 4 to update marginal probabilities and contextual relevance after each turn-pair. we then produced a response to follow as the next utterance using both, the base model+mrf-chat and the base model alone. we repeated the same experiments using the first 6 turns as context to evaluate our model with increasing conversation length. sensitivity to λ. we also repeat this response selection process for each value of λ ∈ {0, 0.3, 0.6} (λ = 0 means that only the most recent user-agent utterance pair is used, ignoring previous turns). we exclude conversations in which mrf-chat and the base model select the same response. hyperparameters. we used top @xmath2. for building the semantic network, we used pre-trained common crawl glove word embeddings (300 dimensional) @xcite with a @xmath3.6 for adding an edge between nodes, only considering the 100,000 most common words. to exclude frequent words, we use word frequencies from the subtlex-us database @xcite , excluding words with a zipf value of greater than 5.75 based on empirical observation. runtime considerations. in each turn, graph augmentation runs in o(n 2 + n r) where n is the number of new and related concepts in the current turn and r is the number of prior related concepts. there is also an added cost for performing inference. however, in our experiments, we found this runtime to be computationally acceptable and suitable for deployment in real-time systems. ## conclusion in this work, we approach open-domain dialogue through a new lens of modelling cognitive behavior with probabilistic methods. we present a novel algorithm, mrf-chat to improve performance of retrieval-based deep-learning models without requiring the collection of new datasets or retraining. our method is model agnostic, easy-to-implement and independent of the base model. using human evaluations, we present statistically significant results showing that responses produced by base models augmented with mrf-chat were rated as better and more on-topic by human annotators when compared to those produced by base models alone. further, using automatic metrics, we show that base+mrf outperforms base alone (kv-mem/poly-encoder) on hits@1 and mrr metrics for all considered values of λ across different conversation lengths. finally, we provide a detailed analysis of the algorithm's sensitivity to the hyperparameter λ and suggest future avenues of research. figure 3: example responses from base+mrf-chat and base only