StalemateBreaker: A Proactive Content-Introducing Approach to Automatic Human-Computer Conversation

Xiang Li, Lili Mou, Rui Yan, Ming Zhang

Abstract

Existing open-domain human-computer conversation systems are typically passive: they either synthesize or retrieve a reply provided with a human-issued utterance. It is generally presumed that humans should take the role to lead the conversation and introduce new content when a stalemate occurs, and that computers only need to "respond." In this paper, we propose STALEMATEBREAKER, a conversation system that can proactively introduce new content when appropriate. We design a pipeline to determine when, what, and how to introduce new content during human-computer conversation. We further propose a novel reranking algorithm, Bi-PageRank-HITS, to enable rich interaction between conversation context and candidate replies. Experiments show that both the content-introducing approach and the reranking algorithm are effective. Our full STALEMATEBREAKER model outperforms a state-of-the-practice conversation system by +14.4% p@1 when a stalemate occurs.

Introduction

Most open-domain chatbots are fundamentally passive, waiting for user input and attempting to generate a relevant response. However, natural human conversation is a shared responsibility. When one participant stops contributing new ideas, the dialogue hits a "stalemate." Traditional AI systems often respond to such dead-ends with generic, meaningless phrases like "..." or "I see," which fails to sustain engagement. StalemateBreaker addresses this by shifting the AI's role from a passive responder to a proactive participant that shares the duty of leading the conversation.

System Architecture

The authors propose a multi-stage pipeline to handle the "when, what, and how" of proactive conversation. The system monitors the dialogue flow and intervenes only when a stalemate is detected.

The StalemateBreaker pipeline architecture, showing the transition from detection to content introduction.
  1. Stalemate Detection: A keyword-based filter identifies "meaningless" user expressions (e.g., "Errr") signaling a stall.
  2. Named Entity Detection: The system identifies key entities from the last four utterances to maintain context.
  3. Knowledge Base Expansion: Using a massive knowledge graph, the system finds entities related to the detected context. For example, mentioning "WALL-E" might trigger related entities like "EVE" or "Pixar."
  4. Candidate Retrieval: The system retrieves up to 50 candidate replies from a database of 9.8 million query-reply pairs that contain these new, related entities.
  5. Selection by Reranking: The final reply is chosen using a novel algorithm that balances context relevance with the novelty of the introduced content.

Bi-PageRank-HITS Reranking

The core algorithmic contribution is the Bi-PageRank-HITS algorithm. It models the relationship between the conversation context (queries) and candidate replies as a bipartite graph.

The content-introducing process leveraging a Knowledge Base and the Bi-PageRank-HITS ranking algorithm.

This approach combines PageRank, to determine the intrinsic importance of specific queries or replies, and HITS (Hyperlink-Induced Topic Search), to model the "mutual reinforcement" between queries (hubs) and replies (authorities). This iterative process ensures that the selected reply is not only similar to the immediate context but also structurally sound within the broader conversation.

Experimental Results

The system was evaluated using 180 real-world conversation logs and a massive database of 9.8 million query-reply pairs crawled from Chinese social media (Baidu Zhidao, Tieba, Douban, and Sina Weibo). Human evaluators scored the appropriateness of the replies on a 0/1 scale.

  • Performance Gain: StalemateBreaker achieved a 14.4% improvement in p@1 (precision at top-1) compared to standard textual similarity baselines during stalemates.
  • Proactivity Impact: Systems that introduced new entities scored significantly higher (0.550 p@1) than passive models (0.483 p@1).
  • Algorithm Superiority: The hybrid Bi-PageRank-HITS algorithm outperformed standalone PageRank or HITS implementations, proving that modeling mutual reinforcement is critical for high-quality dialogue reranking.

Conclusion

StalemateBreaker demonstrates that AI can effectively share the responsibility of leading a conversation. By pivoting on named entities via a knowledge graph, the system introduces new information while remaining contextually relevant. Future work includes developing more sophisticated, learning-based stalemate detection and expanding the diversity of the retrieval database to move beyond the constraints of existing human-generated replies.

Summary updated

Abstract

Existing open-domain human-computer conversation systems are typically passive: they either synthesize or retrieve a reply provided with a humanissued utterance. It is generally presumed that humans should take the role to lead the conversation and introduce new content when a stalemate occurs, and that computers only need to "respond." In this paper, we propose STALEMATEBREAKER, a conversation system that can proactively introduce new content when appropriate. We design a pipeline to determine when, what, and how to introduce new content during human-computer conversation. We further propose a novel reranking algorithm Bi-PageRank-HITS to enable rich interaction between conversation context and candidate replies. Experiments show that both the content-introducing approach and the reranking algorithm are effective. Our full STALEMATEBREAKER model outperforms a state-of-the-practice conversation system by +14.4% [email protected] when a stalemate occurs.
BibTeX
@inproceedings{li2016stalematebreaker,
  author = {Xiang Li and Lili Mou and Rui Yan and Ming Zhang},
  title = {{StalemateBreaker: A Proactive Content-Introducing Approach to Automatic Human-Computer Conversation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=Sy4-CGM_-H},
}
Figure