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

1 Introduction

Automatic human-computer conversation is believed to be one of the most challenging problems in artificial intelligence (AI). For decades, researchers have developed various systems based on human-crafted rules [Webb, 2000; Varges et al., 2009], information retrieval methods [Misu and Kawahara, 2007; Yan et al., 2016], or natural language generators like neural networks [Shang et al., 2015]. In these systems, the computer either searches or synthesizes a reply given an utterance (called query) issued by a user. It is generally presumed that "humans" should play a leading role in human-computer conversation. Hence traditional AI conversation is a passive process: what a computer does is just to "respond."

In human-human conversation, however, both participants have the duty to play a leading role in a continuous dialogue session. The phenomenon is supported by the statistics of conversation data collected from an online forum 1 (Figure 1). Our observation is that, shortly after the conversation begins, both parts are likely to be the stalemate breaker. If only one side keeps finding something to talk while the other side responds in an unmindful way, the conversation becomes less attractive and is likely to end pretty soon. Therefore, in human-computer conversation, the computer side should also be initiative and introduce new content when necessary.

⇤Contribution partially done during internship at Baidu Inc. Corresponding author: Rui Yan (yanrui02@baidu.com).

1 http://www.douban.com

The problem of content introducing is also raised from industry. Although real-world conversation will end sooner or later, industrial conversation systems shall always try to attract users for commercial purposes (except when users explicitly terminate a session). Thus, stalemate breaking is of particular importance to industrial conversation products.

Existing mixed-initiative dialogue systems are typically designed in vertical domains. For example, Ferguson et al. [1996] develop a rule-based system, named TRAINS-95, in the transportation domain; Glas et al. [2015] leverage predefined topics in a museum-guiding system. Such design methodology, however, hardly applies to non-task-specific, chat-style dialogues. Since users are free to say anything, it is virtually impossible to specify rules or design templates for open-domain conversations. Moreover, the content to be introduced is nearly certain in those task- or goal-oriented applications [Seon et al., 2014], whereas the nature of opendomain conversations shows that a variety of replies are plausible, but some are more meaningful, and others are not. Consequently, open-domain conversations are different from task-specific dialogues; the same thing holds for content introducing in these two scenarios.

In this paper, we propose STALEMATEBREAKER, a conversation system that can proactively introduce new content during human-computer conversations. We first detect whether a stalemate occurs by keyword filtering like ". . . " or "Errr," so that our system knows when the stalemate-breaking mechanism should be triggered. To determine what to introduce, we backtrack previous utterances (called context) in a dialogue session and apply named entity recognition in the context. The detected entities are searched for more related entities in a large knowledge graph. All these entities are used to retrieve candidate replies in a conversation database. We believe named entities highly reflect users' interest and provide informative clues for content introducing. We then propose a Bi-PageRank-HITS algorithm to address how to introduce. By matching the relationship between the context and candidate replies (containing the entities) in a reinforced co-ranking manner, we obtain a ranked list, indicating the relevance of each candidate reply. In this way, our system is well aware of when, what, and how to proactively introduce new context in a continuous human-computer conversation.

We build our proactive content-introducing system upon a large conversation database for retrieval (9.8 million candidate query-reply pairs) plus an external knowledge graph (3.7 million tuples). We evaluate our system on conversation logs from real-world users. Our approach outperforms several strong baselines as well as a state-of-the-practice system.

2 RelatedWork

2.1 Dialogue systems

÷ Domain-specific systems. Automatic human-computer conversation has long attracted attention in several vertical domains [Bernsen et al., 1994; Rickel and Johnson, 2000]. In such task- or goal-oriented applications, researchers have developed mixed-initiative systems to more effectively guide users in conversation. Several examples include TRAINS95 for route planning [Ferguson et al., 1996], MIMIC for movie show-time information [Chu-Carroll, 2000], and AutoTutor for learner advising [Graesser et al., 2005]. These systems rely heavily on human-designed rules or templates. Other systems may require intensive domain knowledge to be initiative in conversation, e.g., museum guiders [Glas et al., 2015], children companion systems [Adam et al., 2010; Macias-Galindo et al., 2012], etc.

÷ Open-domain systems. Human-engineered rules may also be applied to the open domain as Han et al. [2015] do, but their generated sentences are subject to 7 predefined forms and hence are highly restricted; they leverage external knowledge bases to enhance content in the responses. Recently, more and more studies and systems are tackling the real challenges of the open domain: great flexibility and diversity. Retrieval-based methods "query" a userissued utterance in a large database of existing dialogues, and return appropriate responses [Higashinaka et al., 2014; Ji et al., 2014]. Generative methods-typically using statistical machine translation techinques [Ritter et al., 2011; Sugiyama et al., 2013; Mairesse and Young, 2014] or neural networks [Shang et al., 2015; Sordoni et al., 2015]-can synthesize new replies, although the generated sentences are not guaranteed to be a legitimate natural language text. Industrial products like Siri of Apple, Xiaobing of Microsoft, and Xiaodu of Baidu, are among state-of-the-practice systems;

they are increasingly affecting people's everyday life.

To the best of our knowledge, existing open-domain chatbot-like conversation are a passive process: the computer only needs to "respond" to human inputs and does not take the role of conversation leading. Instead, we propose a proactive system, which can determine when, what, and how to be proactive and to introduce new content into the conversation.

2.2 RandomWalk-Based Ranking

Our system follows a retrieval-and-reranking schema to select replies from a candidate pool. In this part, we briefly review (re)ranking algorithms like PageRank and its variants.

In the field of information retrieval, research shows that random walks over hyper-link graphs, i.e., PageRank, can reflect the relationship between different web pages and rank high important ones [Page et al., 1999]. Many studies are devoted to the application and extention of PageRank [Haveliwala, 2002; Jeh and Widom, 2003]. Random walks over bipartite graphs can model two heterogeneous types of items, e.g., the HITS algorithm for queries and documents in a click-though graph [Kleinberg, 1999; Deng et al., 2009]. Its variants have been widely used for ranking tasks in the information retrieval community [Cao et al., 2008; Song et al., 2012]. In our scenario, the matching between user utterances and candidate replies can also be modeled as a bipartite graph; to enhance their interaction, we extend existing models and propose Bi-PageRank-HITS, which is a novel algorithm for reranking.

3 The Proposed Approach

3.1 Architecture

Figure 2 shows the overall architecture of our STALEMATEBREAKER system; Figure 3 further illustrates the process flow of content introducing. Our system comprises mainly four steps:

Stalemate detection. The system is built upon a conventional retrieval-based conversation system, which is typically passive. The proactive content introducing starts from stalemate detection. We apply keyword matching of meaningless expressions like ". . . " or "Errr." In total, we have nearly a hundred filters. Although simple, the approach works in a pragmatic way and is not the main focus of this paper. In future work, we would like to apply learning-based sentence modeling (e.g., Mou et al. [2015]) for stalemate detection.

Named entity detection. Once the content-introducing mechanism is triggered, our system backtracks previous utterances in the current conversation session, and detects all named entities within a window. Currently, we keep four utterances, i.e., two turns, as context. We believe recently mentioned named entities highly reflect users' interest; hence we search related entities in a knowledge base for introducing new content. Concretely, the knowledge base is composed of tuples like he1↪ e2↪ wi, indicating the entity e1 is correlated to e2 with a weight of w. Notice that the relation between e1 and e2 in this tuple is directed because weights are asymmetric. For each entity in the current context, we search it in the knowledge base and keep top (highest weighted) five returned entities for further processing.

entity C

containing C

Figure 3: Process flow of triggering content introducing.

In our work, the knowledge base we used was constructed from query logs of an information retrieval system. Without loss of generality, we can also exploit similar resources, e.g., ontologies [Xu et al., 2014] or information networks [Cao et al., 2014]. Leveraging knowledge bases for content introducing, in fact, is also applied in Han et al. [2015]. However, they plug related entities to several predefined templates for response generation, whereas we have further developed complicated retrieval-and-reranking approaches.

It should be mentioned that if the conversation is not in a stalemate or we could not recognize any named entity in previous several utterances, our system will return to the general conversation mode. In other words, the proactive contentintroducing method can be viewed as an "add-on" mechanism to a mature conversation system.

Candidate reply retrieval. We then use the entities and conversation context to retrieve up to fifty candidate replies from a large pool of collected dialogue data. A candidate reply contains at least one entity. This process is accomplished by standard keyword-based retrieval methods, similar to the Lucene system.

Selection by reranking. Finally, the candidate replies are reranked by a random walk-like algorithm. To enhance interaction between conversation utterances and candidate replies, we further propose Bi-PageRank-HITS, a novel algorithm that combines PageRank and HITS into a single framework. (See next subsection.) The highest (re)ranked candidate is selected as the reply.

3.2 Reranking Algorithm

In this part, we describe in detail the proposed Bi-PageRankHITS algorithm, which is a combination of PageRank [Page et al., 1999] and HITS [Kleinberg, 1999; Deng et al., 2009]. 2

We formulate the utterances in context (called queries) and candidate replies as a bipartite graph. Following the notations in HITS, we denote queries as "hubs" and replies as "authorities." Then our random walk-style algorithm alternately ranks either side in the query-candidate graph (PageRank step) and interacts between the two sides (HITS step).

2 "HITS" is the acronym of hyperlink-induced topic search.

Our intuition is that a high hub score indicates the query is important, providing a clue for content introducing; the interaction between two sides assesses the appropriateness of a reply to all queries (reweighted by query importance). Then another PageRank over authorities suggests high-quality replies; such information is propagated back to queries in a similar way. So on and so forth, the hub and authority scores are iteratively computed in a reinforced fashion. After convergence, we obtain an overall ranking list for candidate replies. Because PageRank applies to both hubs and authorities, the model in this paper extends our previous work [Yan et al., 2012b; 2015], and we name the algorithm Bi-PageRankHITS. In the rest of this subsection, we present individual PageRank and HITS steps and then describe how they are combined.

PageRank step. For either side (e.g., queries) of the queryreply bipartite graph, we use PageRank [Page et al., 1999] for scoring. We do not consider the other side (e.g., replies) in this step.

Considering the set of all queries (utterances in the conversation context), we define a random walk over an undirected graph Gq = (Vq↪ Eq), whose nodes are the queries and edges are the relationships between a query-query pair. The weight of an edge i ! j is defined to be the "similarity" between queries i and j, i.e., Mq↪ij = sim(qi↪ qj), where we use the cosine measure as similarity based on two queries' tf·idf vectors.

To incorporate a prior distribution x over queries, we follow Yan et al. [2012a] and define the PageRank formula as

Likewise, for the set of candidate replies, we have

where [·] denotes column normalization, that is to say, each column is the transition probability of its corresponding node. Superscripts indicate the number of iterations in a particular PageRank step (called local iteration).

PageRank is inspired by the following intuition. A candidate reply is important if it is "voted" by many other candidates. The prior (x for queries or y for replies) is initialized as a uniform distribution, but may change to emphasize particular nodes suggested by the HITS step during interaction between queries and replies.

HITS step. After the above step, we obtain PageRank scores for either queries or candidate replies. To propagate such information to the other side in the query-reply bipartite graph, we perform another random walk with links between queries and replies representing the structural information of hubs and authorities.

Formally, the bipartite graph G = (V↪E) has vertexes V = ¶Vq [ Vr♦, where Vq are queries and Vr are replies. We define the weight matrix by a relevance scoring function φ(q↪ r) between queries and replies. φ(·↪ ·) was learned via a learning-to-rank model similar to Burges et al. [2005] with rich features including textual similarity, translation models, as well as word2vec word embeddings [Mikolov et al., 2013]. In other words, φ(·↪ ·) returns the relatedness between a query and a reply in the range (0↪ 1).

Moreover, since we would like to make use of PageRank scores for queries or replies, the HITS links are judged by not only the static relevance score φ(·↪ ·), but also the information given by PageRank. To be concrete, the (unnormalized) weight matrix is given by either

Here, qi and ri are the i-th element in the vectors q and r, which are obtained in the PageRank phase by Equations 1-2. If information is propagated from queries to replies, we use the former equation for weight update, and vice versa.

The mutual-reinforcing relationship of hub and authority scores can be expressed in matrix representation as follows.

where x is query scores, y reply scores; superscripts denote the number of local iterations in HITS update. Each column of the weights is normalized to be a valid probability. Moreover, to compute the weight for y, the matrix ˜W> should be first row-normalized (given by [ ˜W]>); otherwise, the effect of the prior qi in Equation 3 is ruled out by column normalization. Notice that the transition matrix is fixed in one step of HITS, but they may also change as our algorithm proceeds like the PageRank step.

In the above equations, the first term is the standard HITS, which is entirely determined by the linkage structure between hubs and authorities. The second term indicates that, with a certain probability, the hub and authority scores will be influenced by their prior scores ˆx and ˆy. Such idea of combining additional information of hubs and authorities is proposed in Deng et al. [2009] and called Co-HITS. 3

We define the prior score of a query to be proportional to the averaged relevance (textual similarity) score to all replies, i.e., ˆxi / 1 #r0 Pr0 sim(qi↪ r0 ). Likewise, ˆ yi / 1 #q0 Pq0 sim(q0 ↪ ri). The vectors ˆx and ˆy are also selfnormalized so as to be valid probabilities.

Iteration over PageRank and HITS. After performing PageRank over one side (e.g., queries) of the bipartite queryreply graph and propagating the information with HITS, we shall perform another PageRank on the other side (e.g.,

3 Precisely, our model uses the Co-HITS variant. But for simplicity, we denote it as HITS, if not confused, for notational purposes.

Algorithm 1: Bi-PageRank-HITS

Input: Queries (utterances) and candidate replies Output: Ranking list of replies for content introducing begin

//Global iteration in Bi-PageRank-HITS

repeat

Update query priors

repeat

PageRank update over queries by Eqn. 1 until Local convergent;

Update HITS weights by Eqn. 3 (query!reply) repeat

HITS update over query-reply bipartite graph until Local convergent;

Update reply priors

repeat

PageRank update over replies by Eqn. 2 until Local convergent;

Update HITS weights by Eqn. 4 (reply!query)

repeat

HITS update over query-reply bipartite graph until Local convergent;

replies). As mentioned, we use the results x or y obtained by HITS as the prior information, and recompute the transition weights in PageRank (Equation 1 or 2). Then, the information is propagated back by HITS, and PageRank is applied again for a better estimation.

As depicted in Algorithm 1, our Bi-PageRank-HITS algorithm performs PageRank and HITS steps alternately and computes the importance of a query/reply in a reinforced way. Note that the transition matrix in each step of PageRank or HITS is fixed, but they change dynamically during global iterations. Thus our model is different from the original PageRank or HITS.

For convergence concerns, we have normalized all prior distributions and all columns in transition matrices. Therefore, the convergence of PageRank and HITS is guaranteed. For alternation between the two steps, we shall empirically analyze its convergence in Section 4.4. In practice, we terminate our algorithm when the mean square difference between two successive HITS scores in global iteration is less than a threshold (10-6 in our study).

After convergence, we use replies' HITS scores y for final reply selection. Compared with PageRank scores r, HITS scores convey more structural information between queries and replies. A higher score indicates the reply is more appropriate for content introducing.

4 Evaluation

4.1 Datasets and Experimental Setups

Our content-introducing open-domain conversation system is built upon a large database of conversation data for retrieval. We collected massive resources from (Chinese) forums, microblog websites, and community question-answering platforms including Baidu Zhidao, Baidu Tieba, Douban forum, Sina Weibo, etc. 4 In total, we extracted nearly 10 million query-reply pairs. Besides, we leveraged a knowledge graph mined from Baidu search logs.

To evaluate the proposed STALEMATEBREAKER, we resorted to human evaluation, following Ritter et al. [2011] and Shang et al. [2015]. Objective scores like BLEU and traditional evaluation for dialogue systems (e.g., accuracy of template classification) are less applicable to our scenario, because open-domain conversation is highly diverse-one query can have a lot of suitable replies that appear different to each other. Human evaluation, on the other hand, conforms to the ultimate goal of open-domain conversation systems. In our experiments, we used 180 sessions from real-world user conversation logs. For each entity in the context (4 previous utterances in the session), we sought 5 most related entities in the knowledge graph, and for each related entity, we retrieved top-10 candidate replies (containing the entity).

We hired workers on a Chinese crowdsourcing platform to annotate all retrieved results with 1 Point (appropriate) or 0 Point (inappropriate). A candidate reply was annotated by 3 workers in an independent and blind fashion. We regarded the majority voting as the "ground truth" indicating whether the reply is appropriate for content introducing. We also evaluated the kappa score:  = 0▷768, showing high inner-annotator agreement [Fleiss, 1971].

Our website 5 provides additional data statistics and rating criterion.

4.2 CompetingMethods

We compared the proposed proactive content-introducing method with passive conversation systems. As our work is an "add-on" mechanism to a deployed system, we presumed that a stalemate had been detected in our evaluation. In other cases, our proposed method does not corrupt the existing system.

For fairness, our baselines (passive conversation systems) were also aware of context information for candidate reply retrieval, since an utterance like "Errr" itself contains little substance. We also performed data cleaning like Pitler et al. [2010] by removing candidates of low linguistic quality such as extremely short ones or meaningless babblings.

Regarding ranking algorithms, we compared the proposed Bi-PageRank-HITS with the following methods:

• ÷ Textual similarity. This method ranks candidate replies according to textual similarity, predicted by a regression model with human engineered features. It is a stateof-the-practice system 6 which our experimental environment was built upon.

4 http://¶zhidao.baidu♣tieba.baidu♣douban♣weibo♦.com

5 https://sites.google.com/site/stalematebreaker/

6 http://duer.baidu.com

• ÷ Reply PageRank. PageRank is a widely used ranking algorithm [Page et al., 1999], and is, actually, a component of the Bi-PageRank-HITS model.
• ÷ HITS. HITS is a link analysis algorithm suitable for modeling bipartite graphs like web click-through data [Kleinberg, 1999].
• ÷ Co-HITS. Co-HITS [Deng et al., 2009], a variant of HITS, is another component of our Bi-PageRank-HITS model. Details are described in Section 3.2.

4.3 Overall Performance

We first evaluated the performance using the p@1 metric, which is believed to be the most direct judgment of conversation systems [Wang et al., 2013; Shang et al., 2015]. It reflects exactly the "accuracy" of the highest-ranked reply. Further, we applied mean average precision (MAP) and normalized discounted cumulative gain (nDCG), as both our system and baselines return a ranking list containing multiple candidates. For details of our metrics, we refer interested readers to J¨arvelin and Kek¨al¨ainen [2002] and Kishida [2005]. Formulas are also listed on our website.

Table 1 shows the performance of our STALEMATEBREAKER system as well as a variety of baselines.

The main result is that proactive entity-based content introducing is generally better (higher p@1) than passive conversation systems regardless of the ranking algorithm. Although passive systems can reply to important previous utterances in the current conversation session to some extent (because the baselines are also context-aware), they are more likely to repeat existing topics and be stuck in the stalemate.

By contrast, our STALEMATEBREAKER proactively seees a knowledge base, retrieves candidate replies that contain related entities, and reranks more appropriate ones. Thus, entity-based content introducing methods yield higher scores in terms of p@1, i.e., accuracy of the top-ranked reply.

Regarding the Bi-PageRank-HITS ranking algorithm, it outperforms its base models, PageRank and HITS/Co-HITS, as well as a feature-rich regression model based on textural similarity. The results are conservative in all metrics (p@1, MAP, and nDCG) and in both introducing and nonintroducing groups, showing that our ranking algorithm is potentially applicable to other tasks.

To sum up, the experimental results show that both our entity-based content introducing and Bi-PageRank-HITS are effective. When a stalemate occurs, the full STALEMATEBREAKER yields a +14▷4% boost of accuracy (p@1) compared with a state-of-the-practice system which our model is built upon.

4.4 Analysis and Discussion

Parameter Settings. In our Bi-PageRank-HITS model, we have three main parameters, θ in the PageRank phase, and ↵x↪ ↵y in the HITS phase. θ was set to 0.15 following Yan et al. [2012a] and not tuned in our experiment. For ↵x and ↵y, we tried different values with a granularity of 0.1. The results are shown in Figure 4. If ↵ is set to 0, the HITS update vanishes (the first term in Equations 5-6), and the system solely depends on "prior" information. The result is worse than using HITS update.

When ↵ increases, we observe an interesting phenomenon: queries and replies respond differently. For queries, i.e., context utterances, the performance peaks when ↵x is small (Figure 4a). This suggests that textual information ˆx (based on query-reply similarity) does recommend important queries. On the contrary, textual information ˆy for replies is inimical: the highest performance was achieved when ↵y = 1, where ˆy was discarded. One plausible explanation is that, based on textual similarity, the algorithm is likely to recommend similar replies to the queries and be stuck in stalemate. In summary, the parameters we used were ↵x = 0▷3 and ↵y = 1.

Convergence. In our Bi-PageRank-HITS, the convergence of each local step (either PageRank or HITS) is guaranteed because we have properly normalized the transition matrices. We further empirically analyze the global convergence by plotting the root mean square error between two successive HITS scores. Figure 5 shows the curves of 10 randomly

Table 2: Examples obtained by STALEMATEBREAKER.

chosen samples; the results indicate that Bi-PageRank-HITS typically converges quickly in 3-5 global iterations. It works well in practice.

Case Study. We illustrate two examples in Table 2 obtained by Bi-PageRank-HITS. As seen, the (human) user doen not know waht to say by "Err. . . ," but our system can introduce new content (entities like "WALL-E" and the TW play "Marriage of the Fairy Princess") to attract users.

5 Conclusion

In this paper, we addressed the problem of content introducing for stalemate breaking in open-domain conversation systems. We proposed a pipeline of content introducing based on an external knowledge graph. To enhance the interaction between queries (utterances in the conversation) and candidate replies (retrieved from a massive database), we further proposed the random walk-style Bi-PageRank-HITS reranking approach. Experiments show the effectiveness of both our content-introducing method and the ranking algorithm.

Acknowledgments

This paper is partially supported by the National Natural Science Foundation of China (Grant Nos. 61272343 and 61472006), the Doctoral Program of Higher Education of China (Grant No. 20130001110032), and the National Basic Research Program (973 Program No. 2014CB340405 and No. 2014CB340505).