MRF-Chat: Improving Dialogue with Markov Random Fields

Ishaan Grover, Matthew Huggins, Cynthia Breazeal, Hae Won ParkEMNLP 2021 · DOI

Abstract

Modern retrieval-based dialogue systems often struggle to maintain a coherent "mental model" of a conversation, leading to responses that lack contextual relevance or ignore established common ground. We present MRF-Chat, a model-agnostic framework that layers Markov Random Fields (MRF) onto existing neural architectures to simulate human cognitive processes like mutual knowledge tracking. By constructing a semantic network of conversation concepts and performing probabilistic inference, MRF-Chat significantly improves the topicality and quality of agent responses. Evaluations on the Persona-Chat and BlendedSkillTalk datasets demonstrate substantial gains in both automatic metrics and human preference scores.

Introduction

While deep-learning models such as Poly-encoders have achieved high performance in dialogue tasks, they primarily rely on statistical pattern matching. They often lack the linguistic concept of mutual knowledge—the shared information that speakers assume to be known by all parties to ensure successful communication. Without this "common ground," agents may produce responses that are technically fluent but contextually "stale" or irrelevant to the current state of the interaction.

MRF-Chat addresses this by introducing a probabilistic layer that explicitly models what the user and agent likely know at any given point. This approach allows the system to prioritize responses that align with the established context while penalizing those that introduce disconnected or irrelevant topics.

Methodology: The MRF-Chat Pipeline

MRF-Chat functions as a "plugin" for existing retrieval models, requiring no retraining of the underlying neural network. The system processes candidate responses through a four-stage pipeline:

  1. Concept Extraction: Key concepts (keywords) are extracted from the dialogue history and candidate responses using automated tools like Yake.
  2. Semantic Network Construction: A graph is built where nodes represent words and edges represent semantic similarity, typically derived from pre-trained GloVe embeddings.
  3. Markov Random Field Inference: The semantic graph is transformed into a factor graph. The model performs inference to estimate the probability that both participants "know" a concept based on the conversation history.
  4. Contextual Decay: To account for topic drift, an exponential decay parameter ($\lambda$) is applied to older concepts, ensuring the model remains focused on the most recent and relevant information.
The MRF-Chat pipeline: from concept extraction to final scoring.

The final MRF-Chat score is combined with the base model's score using a Bayesian approach, assuming conditional independence between the two models. This hybrid scoring mechanism leverages both the deep-learning patterns of the base model and the explicit cognitive modeling of the MRF layer.

Experimental Evaluation

The authors evaluated MRF-Chat using two primary benchmarks: Persona-Chat, which focuses on consistent personality-driven dialogue, and BlendedSkillTalk (BST), which tests a variety of conversational skills.

Automatic Metrics

In automatic evaluations on the Persona-Chat dataset, the addition of the MRF layer led to dramatic improvements in retrieval accuracy. For instance, when the base Poly-encoder and the MRF-augmented version disagreed on the best response, the MRF-augmented model achieved significantly higher Hits@1 and Mean Reciprocal Rank (MRR).

Automatic evaluation results comparing Poly+MRF against the base Poly-encoder across different conversation lengths and decay values.

As shown in Figure 6, the MRF-augmented model consistently outperforms the baseline across different conversation lengths (4 vs. 6 turns) and various $\lambda$ settings. Notably, the Hits@1 score for the augmented model is often double that of the base model in these comparative scenarios.

Human Evaluation

Crowdsourced evaluations on Amazon Mechanical Turk further validated these results. Human judges consistently rated responses from MRF-Chat as "better" and "more on-topic" compared to those from base models like Key-Value Memory Networks (KV-Mem) and Poly-encoders ($p < 0.05$). These results suggest that the "common ground" heuristic effectively captures human-like conversational relevance.

Discussion and Key Insights

A critical finding of this work is the importance of the decay hyperparameter $\lambda$. In shorter dialogues, focusing on the immediate preceding turn ($\lambda=0$) is often sufficient. However, as conversations progress, retaining a weighted history of concepts becomes more beneficial, mirroring the way humans build deeper shared context over time.

Furthermore, the model's agnosticism is a significant advantage; it can be applied to any retrieval-based system without the need for expensive retraining. While the MRF inference adds some computational overhead, the authors found the latency to be well within the limits for real-time interaction.

Conclusion

MRF-Chat demonstrates that explicit cognitive modeling can significantly enhance the performance of neural dialogue systems. By tracking mutual knowledge and managing contextual relevance through a Markov Random Field framework, agents can engage in more grounded and human-like conversations. Future work will explore learning the decay rate dynamically and incorporating more sophisticated, evolving semantic knowledge bases.

Summary updated

BibTeX
@inproceedings{grover2021mrf,
  author = {Ishaan Grover and Matthew Huggins and Cynthia Breazeal and Hae Won Park},
  title = {{MRF-Chat: Improving Dialogue with Markov Random Fields}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  doi = {10.18653/v1/2021.emnlp-main.403},
}
Figure