Conversational Exploratory Search via Interactive Storytelling

09/15/2017 ∙ by Svitlana Vakulenko, et al. ∙ WU (Vienna University of Economics and Business) University of Amsterdam 0




There are no comments yet.


page 1

page 2

page 3

page 4

This week in AI


1. Introduction

Exploratory search systems provide guidance for users who are exploring unfamiliar information landscapes (Marchionini, 2006; White and Roth, 2009). White and Roth (2009) differentiate two main activities within the exploratory search paradigm: exploratory browsing and focused searching. Exploratory browsing is an initial step that provides necessary domain understanding required for focused searching activities. It is related to Radlinski and Craswell (2017)’s system revealment property: “The system reveals to the user its capabilities and corpus, building the user’s expectations of what it can and cannot do.”

Lately, conversational agents and conversational search systems are becoming increasingly popular

(Thomas et al., 2017). So far, however, such systems mainly focus on question answering and simple search tasks, those that are to a large extent solved by web search engines. We argue that conversational agents and search systems should also support exploratory search. While exploratory search is a challenging task in itself, conversational exploratory search raises unique research and practical issues, which we discuss in this position paper.

In particular, we argue that the core of conversational exploratory search is interactive storytelling, where the document collection underlying a conversational search system is first converted into a set of stories and then a user interactively navigates within a story and between stories by means of a dialogue with the system.

There have been several recent position statements on conversational agents and search. One, by Radlinski and Craswell (2017), focuses on a theoretical model of conversational search systems. Another, by Kiseleva and de Rijke (2017), focuses on evaluation. In contrast, we focus on solution strategies for a specific conversational search scenario, viz. exploratory search.

Below, we first provide motivating examples in Section 2. In Section 3 we present our view of a conversational exploratory search system. The research agenda associated with this system is presented in Section 4. The paper is concluded in Section 5.

2. Motivating Examples

The literature is full of arguments motivating computational support for exploratory search (White, 2016). Exploratory search is an important enabler for educational purposes that aim to broaden the knowledge of a user and understanding of the domain by enhancing learning processes. Serendipitous discoveries are very important in less structured and content rich domains such as music, videos, design etc., where users often look for inspiration, surprises and novel ideas (Zhang et al., 2012). Furthermore, the potential benefits of conversational exploratory search for e-commerce applications should not be underestimated. In particular, it can be combined with personal recommendations and persuasion techniques for marketing purposes (Munigala et al., 2017).

For us, one of the main motivations behind conversational exploratory search comes from the results of analyzing the conversation log of a chatbot demo that some of the authors were involved with (Neumaier et al., 2017a).111 This chatbot demo exposes search functionality over an aggregated open data repository (Neumaier et al., 2017b) via a conversational interface. Manual inspection of the conversation log of the digital assistant revealed that the majority of users experience difficulties formulating adequate queries to the system, i.e., queries that return any matches. This effect is, to a large extent, due to a misconception of the underlying collection of documents, which can potentially be retrieved using a search system.

The observation of a user’s mistaken internal representation of a document collection is not new. The information seeking literature is full of examples to this effect and the information retrieval community has proposed a range of technological solutions to help address such mismatches, ranging from algorithms that help recover from possibly empty search engine result pages using query suggestions and rewrites (Li et al., 2017) to information visualization techniques to help steer users in possibly useful regions of a document collection (Hearst, 2009).

However, visualization approaches may vary significantly and be hard to understand without an animated explanation in natural language or even specialized training. While such methods may be effective in traditional keyboard or touch-based exploratory search scenarios, by and large they are inappropriate to support exploratory search in a conversational setting on mobile devices. Instead, we argue that an approach based on interactive storytelling is called for to support conversational exploratory search.

3. Conversational Exploratory Search

Figure 1. Communicating knowledge via an interactive storytelling process.

Our view of a conversational exploratory search system is represented in Figure 1. It has a number of key components: Document Collection, Knowledge Model, Story Space, Dialog System and User. These components are connected through the Reader, Composer, and Guide modules. The interplay of the system components and modules happens at different stages.

Knowledge Representation

Knowledge representation consists of the Reader

module that extracts concepts and relations from the Document Collection and embeds them into a single Knowledge Model. The Knowledge Model integrates different elements (words, concepts or entities) and describes relations between them. The knowledge can be explicitly modeled by means of a taxonomy or ontology (knowledge graph) but it can also be embedded into a latent (hidden) structure.

Story Generation

Story generation consists of the Composer module that is able to generate stories by combining elements of the Knowledge Model. To create a story, the Composer has to select elements (characters, words, facts, concepts, relations), choose their ordering, arrange selected elements in time and/or space. The set of all possible stories constitutes the Story Space.

Interactive Storytelling

Interactive storytelling consists of the Guide module that helps the User to navigate through the Document Collection via the Story Space. The Guide can change the current position within a single story or traverse the space across different stories. Interactive storytelling integrates the Dialogue System to communicate a story to the User and to receive an input from the User. Supporting such a conversation with the User requires natural language (utterance) generation and understanding. Note that the input/output modalities do not have to be restricted to text and speech only and may include images, videos, interactive visualization, virtual reality interactions, etc.

We also argue that a conversational exploratory search system should support the following types of the user-system interactions:

  • Navigation Control – a user chooses a direction (branch) for exploration and is also able to influence and change the current direction of the narrative at any point in time;

  • Feedback – a user may provide feedback to the system (positive, neutral, negative) that may help to correct and steer the direction of the story that shall maximize the user satisfaction with the system;

  • Question – a user may pose questions to the system, e.g., a request for a definition, look up query, etc.

A sample dialogue with interactions of all these types is provided in Figure 2. In this example the dialogue agent provides concise natural language descriptions of the information space structure, suggestions for possible exploration directions, and further support and guidance along the chosen direction for exploration.



I am here to help you explore open data! This collection includes more than 18,000 open datasets from countries such as Italy, Ireland, Mexico, Austria, etc.


What data do you have about Austria?


Jobs, healthcare, population statistics, education, environment… Are you interested in anything from the above?


What else?


Traffic data, sports, agriculture, tourism.


Traffic sounds interesting! What kind of data is there?


There is data for different cities in Austria: Vienna, Linz, Salzburg, Innsbruck.




For example, pedestrian zones in Vienna, bridges locations, Electronic timetable information for Linz.


Great! Show me something else.


There are 96 datasets about Education and Research in Austria. One of them is a List of all driving schools in Burgenland.


What is Burgenland?


Burgenland is the easternmost and least populous state of Austria [Wikipedia].

Figure 2. Sample dialog for exploratory search based on the Open Data Assistant chatbot use case and the faceted-search interface of the Austrian Government Open Data portal

4. Research Agenda

We identify the following research questions with respect to the components and interaction types described in the previous section:


Reader: How to model the information space structure, represent documents and relations between them for the purpose of story generation?


Composer: How to generate a coherent narrative (story) that efficiently describes a knowledge model?


Guide: How to efficiently traverse/navigate a story space?


Dialogue system: How to provide support for the following three types of the system-user interactions:


Storytelling: How to communicate a story to a user?


Question generation: How to verify user understanding, satisfaction and preferences?


Response analysis: How to interpret and correctly react to natural language utterances (or other signals), such as the ones expressing user satisfaction (feedback), communicating the desired directions for traversing the information space (navigation control), checking the terminology and asking other types of questions?

In the following, we organize these research questions into two subtasks, namely, story generation and interactive storytelling.

4.1. Story Generation

In the context of conversational AI we are primarily interested in developing an operational knowledge model (RQ1), i.e., the structure that the system can act upon, e.g., to answer questions or generate stories. Story generation (RQ2) requires accomplishing the following three tasks: (1) select elements of the knowledge model; (2) choose an order in which to present these elements; and (3) communicate the story to the user using the modalities available to the system, e.g., natural language and/or visualization (RQ4.1).

Computational narrative intelligence, the ability to craft, tell, understand and respond appropriately to narratives, is a core component of a strong AI system (Riedl, 2016; Li, 2015). So far, it has mostly been developed with applications to fiction, in the context of computational creativity. We propose to put it to work for conversational exploratory search. To this end, we first recall some core concepts from the area and then sketch our ideas for putting it to work for conversational exploratory search.

McIntyre and Lapata (2010)

use genetic algorithms (GAs) to generate children stories from a corpus of fairy tales. They extract schemas from natural language texts using dependency parsing and co-reference resolution tools, then generate a single plot graph by merging these schemas. The plot graph constitutes the story space, where each path is a different story. The algorithm then searches the story space for the best story candidates using a coherence function learned from training data 

(Barzilay and Lapata, 2008). The produced stories are readable but short and uninformative, and can be considered as a proof-of-concept for the story generation approach.

Martin et al. (2017)

generate stories in natural language using two sequence-to-sequence recurrent neural networks (RNNs):

(1) event representations are extracted from text using dependency parsing, stemming and topic modeling; (2) event2event RNN chains the extracted events together into stories; (3) event2sentence RNN translates the generated story representation into natural language sentences. This approach is applied to a corpus of movie plot summaries extracted from Wikipedia (Bamman et al., 2013). It is reported to achieve plausible and human-readable sentences.

Huang et al. (2016) establish a new task of visual storytelling, in which the system is to generate a story in natural language given a sequence of images as an input. The baseline model for story generation is trained using sequence-to-sequence RNNs.

In our view, the work on algorithms for story generation is sufficiently mature so that it can be successfully used in the context of conversational exploratory search, especially to support dialogue management in conversational exploratory search, thereby offering the potential to address RQ1, RQ2 and part of RQ4, namely, RQ4.1.

4.2. Interactive Storytelling

Conversational exploratory search is not a one way traffic. Hence, our perspective on using story generation for the purposes of conversational exploratory search needs to be complemented with conversational aspects. Interactive storytelling is a conversation, in which a storyteller aims to convey a fraction of a knowledge model to a listener (RQ4.1), and the listener can actively influence the direction, flow and manner of the story being told (responsive by design, RQ4.3). Ability of the storyteller to ask questions and expose possible directions for exploration (RQ4.2) aims at encouraging listener’s active engagement with the story and avoiding lengthy monologues in favor of a more balanced dialogue-based interaction with the content.

Approaches developed within the goal-oriented dialogue framework (Dialog State Tracking Challenge (Williams et al., 2016)) are likely to be useful for dialogue management in the interactive storytelling settings as well. Within this framework the dialogue system is supported by a task-specific domain ontology. The ontology enumerates all concepts and attributes (slots) that a user can specify or request information for (Mrksic et al., 2017)

. The dialogue management model is trained to correctly classify user intents by matching user utterances to the elements in the domain ontology. It can also learn to use the distribution over intents to decide whether to execute an action or request a clarification from the user 

(Mrksic et al., 2017).

The results of the Dialog State Tracking Challenge show advantages of end-to-end dialog systems that employ discriminative models and embed a dialog directly as a sequence (Williams et al., 2016). Bordes and Weston (2016) show how to train such an end-to-end dialog system using the Memory Network architecture. Dhingra et al. (2017)

use RNNs and reinforcement learning to train a dialogue system that can interactively retrieve items from a single table.

Mrksic et al. (2017)

avoid the limitations of the exact word matching by loading pre-trained word vectors and composing them into intermediate representations to be able to scale to larger and more complex domains. They carry out an evaluation for a single domain (restaurants), which is described by an ontology with three attributes specifying the goal (information need) and eight attributes available for retrieval. While very promising for the task of conversational exploratory search, the question remains whether the proposed interactive storytelling approaches can scale up from the toy examples considered so far to support meaningful conversations using the full-sized knowledge graphs.

With the fraction of the knowledge model involved in communication getting bigger the major design challenges arise with respect to the balanced composition of the story space (RQ2) that allows efficient traversal and communication taking into account cognitive limitations of the human brain (RQ3). In addition, the ability to adopt useful shortcuts across the story space will reduce the traversal time and, thereby, improve the experience by avoiding linear search in favor of random access, when it is applicable (RQ3).

In addition to scale, another important challenge arises from the fact that interactive storytelling is different from a common conversational search task, where an agent tries to pin-point an item or an information subspace relevant to the user’s query (Radlinski and Craswell, 2017). In this respect, interactive storytelling is hard to optimize, since there is no single correct answer. We propose to measure the results of the interactive storytelling process with respect to: (1) the learning outcomes, which constitute the fraction of the knowledge model gained on the listeners’ side; and (2) user satisfaction. The datasets available for learning dialogue representations are currently limited to two types of tasks: general chit-chat and goal-oriented dialogues, such as restaurant reservation (Kenter et al., 2017; Miller et al., 2017).

There are a few new datasets of conversation transcripts covering more general search scenarios (Trippas et al., 2017; Thomas et al., 2017), which focus primarily on analyzing different task complexity levels and user experience during the dialogue interactions. To the best of our knowledge, there is currently no publicly available dataset of conversation logs recorded for learning conversational exploratory browsing behavior and evaluation of successful knowledge transfer interactions.

5. Conclusions

In this paper we introduced the idea of enabling conversational exploratory search by means of interactive storytelling. We presented our vision of such a system, its components and modules. We also outlined directions for future research towards development of the computational narrative intelligence, as an enabler of conversational AI, and its application in the exploratory search scenarios, which go beyond the discrete look-up requests towards continuous interaction sessions with the goal of knowledge transfer, that we refer to as interactive storytelling.

The insights gained in the fields of story generation and dialogue systems suggest that it is feasible to develop a computational model able to learn natural language generation and communication from crowd-sourced examples. We see our task in developing this idea further by adopting it in the context of exploratory search. To begin in this direction, the research community requires a collection of new datasets of dialogue interactions that can be used for evaluation of successful knowledge transfer. Next, evaluation of existing approaches to story generation and learning dialogue policies in this new settings will help to form the baselines for developing novel approaches.


The work of Svitlana Vakulenko has received funding from the EU H2020 programme under the MSCA-RISE agreement 645751 (RISE_BPM) and the Austrian Research Promotion Agency (FFG) under the project CommuniData (grant no. 855407). Ilya Markov and Maarten de Rijke were supported by Ahold Delhaize, Amsterdam Data Science, the Bloomberg Research Grant program, the Criteo Faculty Research Award program, Elsevier, the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement nr 312827 (VOX-Pol), the Microsoft Research Ph.D. program, the Netherlands Institute for Sound and Vision, the Netherlands Organisation for Scientific Research (NWO) under project nrs 612.001.116, HOR-11-10, CI-14-25, 652.002.001, 612.001.551, 652.001.003, and Yandex. All content represents the opinion of the authors, which is not necessarily shared or endorsed by their respective employers and/or sponsors.