Evolving optimal inspectable strategies for spoken dialogue systems

Dave Toney, Johanna Moore, Oliver LemonNAACL 2006

TL;DR

This paper introduces a novel approach using an evolutionary reinforcement learning algorithm (XCS) to automatically generate dialogue strategies for spoken dialogue systems. The key innovation is that these learned strategies are not only highly performant (achieving 98.9% of optimal) but also significantly more compact and inspectable by human developers compared to traditional methods.

What Problem Does This Paper Address?

Developing effective dialogue management strategies for spoken dialogue systems is a notoriously complex and time-consuming task. This is primarily due to the near-infinite number of ways a user might interact with a system. Traditionally, developers try to anticipate these interactions, a process that can be overwhelming. While reinforcement learning (RL) has shown promise in automating this, existing RL approaches struggle with the large state spaces typical of real-world systems and often produce strategies that are difficult for humans to understand or interpret. This paper aims to bridge this gap by creating dialogue strategies that are both optimal in performance and easily inspectable by human developers.

Methods

The authors employ XCS (X Classifier System), an evolutionary reinforcement learning algorithm. Unlike traditional RL that might learn a value function for every state-action pair, XCS learns a compact set of state-action rules (classifiers). This rule-based representation is the core of the paper's contribution to inspectability. The evolutionary aspect of XCS allows it to search for optimal rule sets, while the reinforcement learning component assigns rewards to these rules. The system is trained using simulated users, which are a practical alternative to human testers for generating a large number of dialogues. The authors experimented with different configurations of dialogue acts and state representations to achieve specific goals like efficient slot-filling and confirmation strategies.

Datasets

The paper does not use traditional datasets in the sense of pre-collected conversational data. Instead, it utilizes two versions of a hand-coded simulated user to generate training and testing dialogues.

  • Simulated User A: Represents a fully cooperative user.
  • Simulated User B: Represents a less cooperative user, introducing a 20% chance of no response. These simulated users allow for controlled experimentation and cross-validation of the evolved strategies.

Key Insights and Ideas

  • Inspectability through Compactness: The use of XCS, which learns a rule-based strategy, dramatically reduces the number of rules needed to represent an optimal policy compared to tabular RL methods. This reduction (e.g., 87% in one experiment) makes the learned strategies much more understandable for human developers.
  • Optimality Maintained with Compactness: The paper demonstrates that achieving this compactness does not come at the cost of performance. The evolved strategies achieve very high performance metrics, suggesting that XCS can find efficient solutions even with a reduced representation.
  • Faster Convergence with More Actions: Interestingly, in experiments where more dialogue actions were introduced (Experiment 4 vs. Experiment 3), the system converged to an optimal policy faster. This suggests that XCS is adept at navigating increased complexity and finding efficient paths.
  • Generalization is Key: The success of XCS in handling large state spaces and producing inspectable strategies is attributed to its generalizing ability through rule-based representations.

Key Results

  • The evolved dialogue strategies achieved a mean performance of 98.9% with respect to a predefined evaluation metric.
  • In one experiment, the evolutionary approach reduced the number of rules by 87% compared to conventional RL techniques, leading to significantly more inspectable strategies.
  • Experiment 4, which introduced more complex dialogue acts, converged to an optimal policy approximately four times faster than Experiment 3.
  • The strategies were robust across different simulated user types (cooperative and less cooperative), achieving high payoffs (e.g., 99.4% and 99.8% for Experiment 1).

Limitations and Future Work

  • Limitations: The current work relies on simulated users. While practical, the authors acknowledge that evaluating against real human users would be the next logical step. The current experiments are focused on a specific, relatively simple slot-filling task (hotel booking).
  • Future Work: The authors plan to further explore the generalization capabilities of XCS for systems with even larger state representations. They also intend to investigate other methods for summarizing learned strategies and will conduct further comparisons against purely RL-based methods.

Summary updated

BibTeX
@inproceedings{toney2006evolving,
  author = {Dave Toney and Johanna Moore and Oliver Lemon},
  title = {{Evolving optimal inspectable strategies for spoken dialogue systems}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure