Efficient Dialogue Strategy to Find Users’ Intended Items from Information Query Results

Kazunori Komatani, Tatsuya Kawahara, Ryosuke Ito, Hiroshi G. OkunoCOLING 2002

TL;DR

This paper proposes a dialogue strategy to help users efficiently find specific items from a large set of search results, particularly useful for speech interfaces where presenting many options is impractical. The core innovation lies in using information-theoretic criteria and, for structured knowledge like appliance manuals, leveraging hierarchical structures to ask targeted questions that quickly narrow down possibilities.

What Problem Does This Paper Address?

Information retrieval systems, especially those accessed via speech interfaces like telephones, often return a large number of potential matches. Presenting all these results to the user is infeasible due to screen limitations and cognitive load. Existing dialogue systems often rely on pre-defined semantic slots, which are rigid and require well-structured databases. This paper addresses the challenge of efficiently guiding users to their intended item from a broad set of search results when the underlying knowledge might not be perfectly structured, and when speech recognition errors can further complicate the process. The goal is to make spoken dialogue interfaces more flexible and user-friendly for information seeking.

Methods

The paper presents two main approaches:

  1. General Information Query Task: For tasks where knowledge isn't strictly structured (like a restaurant database), the system uses an information-theoretic criterion to select the most informative "yes/no" question. This question is designed to maximally reduce the uncertainty about the user's intended item. Keywords are extracted from user utterances, and a confidence measure is assigned based on speech recognition. The system calculates the expected information gain for potential questions and selects the one that offers the highest gain. If the user finds the proposed question irrelevant, the system can offer a second-best option.
  2. Appliance Manual Query Task: When structured task knowledge is available, such as a hierarchical manual for an appliance, the system leverages this tree structure. The manual's table of contents is used to build a tree, and each node (representing a section or sub-section) is assigned a likelihood score based on the matching keywords from the user's query. The dialogue strategy then focuses on asking questions about nodes that are most ambiguous (likelihood close to 0.5) or that offer the best balance between reducing uncertainty and the estimated number of future dialogue turns. Three different heuristic cost functions are proposed and compared for selecting the optimal question node.

Datasets

The paper describes experiments conducted using:

  • A restaurant query task (example provided, but no specific dataset details given).
  • A VTR (Video Tape Recorder) manual, which served as the structured knowledge base. This manual comprised 111 pages and 47 items, with a derived tree structure of three levels.
  • Evaluation data was collected from 14 subjects who made 10 queries each based on scenarios, plus several spontaneous queries, totaling 195 query utterances.

Key Insights and Ideas

  • Information Theory for Dialogue: Using information gain as a criterion for selecting dialogue questions is a powerful way to efficiently narrow down search results, especially in spoken interfaces.
  • Leveraging Structure: For structured knowledge (like manuals), exploiting hierarchical relationships is crucial for efficient dialogue management. It allows for more targeted and less ambiguous questions.
  • Handling Ambiguity: The system's ability to offer a second-best option when the primary suggestion is not preferred makes the interaction more cooperative and less frustrating for the user.
  • Speech Recognition Robustness: The proposed dialogue strategy aims to minimize reliance on complex speech understanding by using simple "yes/no" questions, which are less prone to recognition errors.
  • Cost Functions for Decision Making: Developing and comparing different heuristic cost functions for selecting dialogue questions highlights the trade-offs between immediate information gain and the overall dialogue length.

Key Results

  • Reduced Dialogue Turns: The proposed dialogue strategy significantly reduced the average number of dialogue turns compared to a baseline method (confirming candidates in order of matching score).
  • For text input, turns were reduced from an average rank of 3.2 to 2.4 (using the best heuristic).
  • For speech input, turns were reduced from an average rank of 3.3 to 2.5 (using the best heuristic).
  • Efficiency Improvement: The system demonstrated an improvement in finding intended items more efficiently, particularly in speech-based interactions where initial matching accuracy can be lower due to recognition errors.
  • Confidence Measure Impact: The evaluation showed that using confidence measures from speech recognition improved the performance, and the proposed dialogue strategy effectively handled the inherent uncertainty.

Limitations and Future Work

  • Heuristic Function Performance: The paper notes that the performance difference between the three proposed heuristic cost functions was not substantial, suggesting that as long as the heuristics are reasonable, the framework is effective. However, the reason why the "apparently most accurate" function (h1) did not perform best is not fully identified.
  • Threshold 'a': The parameter 'a' (threshold for the number of remaining nodes) was set to 3, and its impact on performance is not deeply explored.
  • Future Work: The authors suggest that further research could explore more complex dialogue strategies and potentially incorporate user modeling to further personalize the interaction. The robustness of the system to speech recognition errors is a key advantage, and further exploration of this aspect could be beneficial.

Summary updated

BibTeX
@inproceedings{komatani2002efficient,
  author = {Kazunori Komatani and Tatsuya Kawahara and Ryosuke Ito and Hiroshi G. Okuno},
  title = {{Efficient Dialogue Strategy to Find Users’ Intended Items from Information Query Results}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure