Automatic Optimization of Dialogue Management

Diane J. Litman, Michael S. Kearns, Satinder Singh, Marilyn A. WalkerCOLING 2000

TL;DR

This paper tackles the challenge of automatically designing effective dialogue strategies for spoken dialogue systems, moving beyond manual, iterative design. By framing dialogue management as a reinforcement learning problem and applying it to a real-world system (NJFun), they demonstrate a significant improvement in task completion rates, showcasing the power of learning from user interactions.

What Problem Does This Paper Address?

Designing the "brain" of a spoken dialogue system – the dialogue manager – is a complex and often manual process. Experts must make numerous design choices about how the system should interact with users, such as when to ask for clarification or how to confirm information. These choices heavily influence how well the system helps users achieve their goals. Traditionally, improving these strategies involves building multiple versions of a system, collecting extensive dialogue data with human users, and statistically comparing performance. This is costly and limits the exploration of the vast space of possible dialogue strategies. This paper addresses the need for a more automated and efficient way to discover optimal dialogue strategies, especially in the face of challenges like speech recognition errors and varying user behavior.

Methods

The core of this paper's contribution lies in applying Reinforcement Learning (RL) to dialogue strategy optimization. The authors frame the problem as a Markov Decision Process (MDP), where the dialogue system's state summarizes the conversation so far, and actions are the system's utterances or database queries.

Here's a breakdown of their approach:

  • State Representation: They define a simplified, yet informative, state space for the dialogue manager. This is crucial to avoid the "curse of dimensionality" and data sparsity issues common in RL. The state captures key information like whether the system has greeted the user, which attribute it's currently seeking, confidence levels from the Automatic Speech Recognizer (ASR), and dialogue history.
  • Exploratory Dialogue Strategy (EIC): To gather training data, they deploy an initial system with a hand-designed "Exploratory for Initiative and Confirmation" (EIC) strategy. This strategy involves making random choices between a few pre-defined actions in certain states, encouraging exploration of different dialogue paths.
  • MDP Construction: Dialogue data collected using the EIC strategy is used to empirically estimate the transition probabilities between states and the reward function. This empirical data forms the basis of the MDP model.
  • Value Iteration: Standard RL algorithms, specifically value iteration, are then used to compute the optimal policy (dialogue strategy) for this learned MDP. This policy dictates the best action to take in each state to maximize expected rewards.
  • Deployment: The learned optimal strategy is then deployed in the system, replacing the EIC strategy.

This approach contrasts with traditional methods by allowing for the exploration of a much larger search space of strategies and learning directly from real user interactions.

Datasets

The paper describes experiments conducted with human subjects.

  • Training Data: Collected from 54 employees not directly involved with the NJFun project. These subjects engaged in free-form conversations to complete six application tasks. This phase resulted in 311 complete dialogues.
  • Testing Data: Collected from 21 different test subjects, performing the same six tasks, resulting in 124 complete test dialogues.

The paper does not introduce a new benchmark dataset but rather uses data collected from their experimental setup to train and evaluate their RL-based dialogue strategy.

Key Insights and Ideas

  • RL for Dialogue is Practical: The paper demonstrates that RL can be practically applied to optimize dialogue strategies in a working system with human users, not just in simulated environments.
  • Simplified State Space is Key: The success hinges on carefully designing a minimal state space that captures essential information without leading to insurmountable data sparsity issues.
  • Learning Fine-Grained Distinctions: The learned strategy exhibits a sophisticated understanding of user interactions, making nuanced decisions about initiative and confirmation based on ASR confidence and dialogue history, which would be difficult to hand-code.
  • Exploration is Crucial for Learning: The EIC strategy, with its random choices, is vital for gathering diverse data that allows for the construction of a robust MDP model.
  • Optimizing for Task Completion Works: Focusing the RL reward on a clear performance measure like "Strong Comp" (task completion) leads to measurable improvements in that specific metric.

Key Results

The primary quantitative result is a significant improvement in task completion rates:

  • Strong Comp (Task Completion): Increased from 52% with the initial EIC strategy during training to 64% with the learned strategy during testing (p<.06).
  • Weak Comp (Relaxed Task Completion): Average reward increased from 1.75 to 2.19 (p < 0.02).
  • ASR (Speech Recognition Quality Measure): Average reward increased from 2.5 to 2.67 (p < 0.04).

Qualitatively, the learned strategy showed a more sophisticated approach to initiative and confirmation, often confirming attributes only at lower confidence levels, and exhibiting complex back-off strategies for initiative when re-asking for attributes.

Limitations and Future Work

  • Expert vs. Novice Users: The learned strategy showed a significant improvement for "expert" users (tasks 3-6) but a slight degradation for "novice" users (tasks 1-2). This suggests the learned strategy might be slightly optimized for expert users, and future work could explore optimizing for different user types.
  • Subjective Measures: While objective performance improved, subjective measures like user satisfaction did not significantly differ between the EIC and learned strategies. The authors note that test users tended to give less extreme answers, and explaining these subjective results is an area for future work.
  • State Space Automation: The authors suggest automating the choice of state space for dialogue systems as a future research direction.
  • Learned Reward Function: Investigating the use of a learned reward function (instead of a fixed one) is also proposed.
  • Non-Terminal Rewards: Exploring more informative non-terminal rewards (rewards given during the dialogue, not just at the end) is another avenue for future research.

Summary updated

BibTeX
@inproceedings{litman2000automatic,
  author = {Diane J. Litman and Michael S. Kearns and Satinder Singh and Marilyn A. Walker},
  title = {{Automatic Optimization of Dialogue Management}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure