PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System

M. Kearns, D. Litman, S. Singh, M. Walker

arXiv:1106.0676v1cs.LGcs.AI

TL;DR

Hand-designing spoken-dialogue policies involves a large, unsettled search space. This paper develops reinforcement-learning methods to optimize NJFun with limited human interactions and finds that optimization improves system performance, particularly for experts.

  • Problem

    Spoken-dialogue policy design is typically hand-crafted despite a large search space and no prevailing consensus on the best policy.

  • Method

    The paper develops a reinforcement-learning methodology for optimizing a dialogue policy using limited interactions with human users.

  • Results

    Among experts, completed dialogues increased from 46% during training to 69% during testing (p<.001), while novices showed nonsignificant degradation.

  • Takeaways & Limitations

    The NJFun study demonstrates that reinforcement learning can optimize a dialogue policy in a working spoken-dialogue system with human users.

  • Takeaways & Limitations

    The paper does not provide a general methodology for reducing the dialogue policy’s state space.

Abstract

from arXiv · show

Designing the dialogue policy of a spoken dialogue system involves many nontrivial choices. This paper presents a reinforcement learning approach for automatically optimizing a dialogue policy, which addresses the technical challenges in applying reinforcement learning to a working dialogue system with human users. We report on the design, construction and empirical evaluation of NJFun, an experimental spoken dialogue system that provides users with access to information about fun things to do in New Jersey. Our results show that by optimizing its performance via reinforcement learning, NJFun measurably improves system performance.

1. In tro du tion

The paper presents reinforcement learning as a data-efficient approach for optimizing dialogue policies despite the many design choices and practical constraints of spoken interaction with human users. It develops and evaluates this methodology in NJFun, showing improved task completion and substantial quantitative performance gains when properly applied.

  • Motivation: Dialogue-policy design involves many nontrivial choices whose effects depend on users, ASR robustness, task difficulty, and the preceding dialogue.The choice between user and system initiative illustrates this recurring design problem.
  • Motivation: Traditional iterative design explores only a handful of policies, although NJFun has thousands of reasonable policy possibilities.Human-user experimentation makes broader policy exploration costly.
  • Approach: Applying reinforcement learning to spoken dialogue is technically challenging because human interaction limits training data and exploration must preserve a functioning system.Available actions must also make sense in context from the user’s perspective.
  • Contribution: The paper details a methodology for learning dialogue policies from limited human interactions and demonstrates it in the NJFun spoken dialogue system.The methodology includes reward selection, dialogue-state estimation, exploratory data collection, MDP construction, and redeployment of the learned policy.
  • Results: The NJFun results show that the learned policy improves task completion rate and provide evidence that reinforcement learning can substantially improve spoken-dialogue-system performance.The evaluation also establishes the validity of the learned MDP and compares the learned policy with standard hand-designed policies.

2. Dialogue Managemen t in Sp ok en Dialogue Systems

The paper focuses on automating two dialogue-policy decisions influenced by automatic speech recognition: how much initiative the system should allow the user and how conservatively it should confirm its understanding. Because these choices lack prevailing consensus, the authors aim to determine them empirically and in a principled way.

  • Initiative: The first decision is whether the system should use user initiative or system initiative when prompting.User initiative is relatively open-ended, whereas system initiative is relatively restrictive.
  • Confirmation: The second decision is whether to explicitly confirm the user’s perceived utterance or continue the dialogue without confirmation.The appropriate choice may depend on ASR confidence, previous exchanges, and the system’s measure of success.
  • Motivation: These choices lack prevailing consensus among dialogue-system designers, motivating their automation on the basis of empirical data.The paper characterizes initiative and confirmation as choices over which there is genuine debate.

3. Reinfor emen t Learning F or Dialogue P oli y Design

The paper formulates dialogue-policy design as learning action choices in a carefully designed state space from representative human interactions. These interactions define an MDP whose optimal policy maximizes expected reward and can be computed efficiently, enabling empirical validation of the methodology in NJFun.

  • State representation: The approach represents each dialogue with a compact state containing information relevant to the system’s next action.The state space is application-dependent and must preserve decision-relevant information while compressing the dialogue history into a small feature set.
  • Policy learning: Rather than relying on designer intuition, reinforcement learning learns action choices for dialogue choice-states.A dialogue policy maps states to actions; some states have multiple reasonable choices, such as initiative and confirmation.
  • Exploration: Exploratory training data must try many allowed actions from many states, while random choices are restricted to actions that keep dialogues sensible for human users.Actions in non-choice states remain fixed, and NJFun uses random exploration at choice-states with carefully designed allowable actions.
  • Contribution: The paper empirically validates a practical methodology for using reinforcement learning to optimize dialogue behavior from human-computer training data.The proposed implementation works directly in a small, carefully designed state space, greatly reducing value-iteration computation for the learned MDP.

4. The NJF un System

NJF un is a real-time spoken dialogue system for finding things to do in New Jersey, built with standard speech and dialogue-management modules. Its policy operates over attribute acquisition and confirmation choices, while reinforcement learning explores this space to obtain an approximately optimal policy.

  • System architecture: NJF un provides real-time spoken access to New Jersey activity information through ASR, spoken-language understanding, TTS, database access, and dialogue management.Its database covers activity type, location, and time of day.
  • Dialogue operation: The dialogue manager sequentially acquires activity, location, and time attributes, repeating unsuccessful requests and querying the database with wildcards for missing values.Multiple database matches can be returned for a given attribute binding.
  • Policy choices: Learning is restricted to difficult policy choices: initiative type when asking or reasking for an attribute and whether to confirm an obtained value.Obvious policy choices are specified in advance, while the optimal actions may vary with dialogue state.
  • Initiative and confirmation: The initiative options combine open or directive prompts with restrictive or non-restrictive grammars, yielding user, system, and mixed initiative.System initiative is always used for the third attribute because the user can only provide the time of day at that point.
  • Learning representation: An approximately optimal policy is obtained in the large policy class through reinforcement learning applied to exploratory behavior.The learning state space is simplified to 7 variables because of data-sparsity concerns.

5. Exp erime n tally Optimizing a P oli y

NJFun’s policy was optimized by collecting human dialogues under random exploration, constructing an empirical MDP, and computing an optimal dialogue policy. The experimental design supported policy learning while limiting data sparsity, and subsequent testing evaluated improvements in task completion.

  • Policy optimization: The logged dialogues were used to build an empirical MDP and compute the optimal dialogue policy, with Binary Completion as the optimized binary reward.Binary Completion equals 1 when NJFun queries the database using exactly the task-specified attributes and -1 otherwise.
  • Policy optimization: Testing the learned policy showed improved task completion rates, the performance measure selected for optimization.The supplied passage identifies task completion as the reported performance outcome but provides no numerical improvement value.
  • Experimental design: Subjects completed six application tasks through free-form phone conversations with NJFun and then provided post-task feedback through a web survey.The tasks covered activities such as museums, cruises, historical sites, wineries, theaters, and parks.
  • Training data: 311 complete training dialogues were logged as state-action sequences for constructing the empirical MDP.The shortest and longest dialogues contained 3 and 11 user utterances, respectively.
  • Training data: Random action selection produced a fairly balanced action distribution, while the small state space and two allowed actions per state prevented a data-sparseness problem.The paper notes that reinforcement-learning policies are unreliable at infrequently visited states, making this coverage important.

6. Exp erime n tally Ev aluating the Optimized P oli y

Testing the learned deterministic policy on 124 dialogues improved Binary Completion from 52% in training to 64% in testing. Improvements also appeared for related objective measures, while several non-optimized subjective measures showed no statistically significant change.

  • Binary Completion: 52% to 64%: Binary Completion increased from training to testing under the learned policy.The test set comprised 124 dialogues, compared with 311 training dialogues.
  • Subjective measures: No statistically significant changes were found for several non-optimized subjective measures, although responses shifted toward the middle effect.The reported interpretation was that optimizing task completion shifted weight away from the tails of subjective measures.

7. Dis ussion

The paper presents a practical reinforcement-learning methodology that optimizes spoken-dialogue policies by searching a much larger policy space than traditional methods. Experiments with NJFun showed improved performance, while identifying remaining challenges in state-space design, partial observability, and reward specification.

  • Methodology: The methodology computes an apparent optimal policy from relatively few exploratory dialogues across a policy space of perhaps thousands of policies.This avoids sequentially implementing only a handful of particular policies.
  • Empirical results: NJFun showed empirically improved performance after reinforcement-learning optimization, including significant improvements in the optimized reward measure.The controlled human-user experiment also found significant improvements for several other objective reward measures, but not for a set of subjective measures.
  • Empirical results: The learned policy outperformed both the non-deterministic EIC policy class and other fixed choices proposed in the literature.Its decisions used ASR confidence with other features and varied initiative and confirmation at a finer grain than previous work.
  • Practical challenges: The work addresses practical RL challenges by balancing random exploration with user experience and keeping the state space small while retaining decision-relevant information.The resulting learned policy included a complex back-off policy for initiative when reasking.
  • Limitations and future work: The methodology does not provide a general way to reduce the state space, and its approximate learned MDP model may introduce hidden state or partial observability.Future work includes automating state-space and reward selection, studying subjective-measure results, comparing expert and novice users, learning reward functions, and using more informative non-terminal rewards.

A kno wledgmen ts

The authors acknowledge contributors who implemented NJFun, provided technical assistance, commented on the paper, and participated in helpful conversations. The section also introduces Appendix A and identifies NJFun as the New Jersey Place-to-go Recommender.

  • The authors thank Fan Jiang for substantial effort implementing NJFun.
  • The authors acknowledge Wieland Eckert, Esther Levin, Roberto Pieraccini, and Mazin Rahim for technical help.
  • The authors thank Julia Hirschberg for comments on a draft and David M. Allester, Richard Sutton, Esther Levin, and Roberto Pieraccini for helpful conversations.
  • Appendix A is titled “Experimental Instructions” and identifies NJFun as the New Jersey Place-to-go Recommender.

General Des ription

NJFUN is an experimental spoken dialogue system accessed by telephone that provides information about things to do in New Jersey. Participants complete six tasks with potentially varying system versions and behavior, then provide task-level feedback and survey responses.

  • System description: NJFUN provides telephone access to a database of things to do in New Jersey.The system is an experimental spoken dialogue system.
  • Experiment procedure: Participants are instructed to complete six different tasks as efficiently as possible.Each phone call may use a different NJFUN version, and system behavior may vary within a call.
  • Feedback procedure: At the end of each task, participants rate the call as “good,” “so-so,” or “bad.”Participants must provide this feedback before hanging up.
  • Feedback procedure: After hanging up, participants answer brief survey questions and continue even if NJFUN aborts before task completion.The instructions explicitly require finishing the survey before proceeding to the next task.

T ask S enarios

The experiment presents six tasks to be completed one at a time in a prescribed order. Participants provide feedback and complete a survey after each task, then submit final comments after all six tasks.

  • Per-task procedure: After each task, participants provide feedback, hang up the phone, and complete that task’s survey.The task procedure requires these steps before proceeding to the next task.
  • Final feedback: After completing ALL of the tasks, participants provide any final comments.A separate prompt is provided for final comments.

Referen es

The references span reinforcement learning foundations, spoken-dialogue management, dialogue evaluation, speech recognition, and mixed-initiative interaction. They also include applications to email, robots, web-based agents, and telephone services.

  • Reinforcement learning: Reinforcement-learning foundations include surveys, textbooks, neuro-dynamic programming, temporal-difference learning, and delayed reinforcement-learning models.Key references include Kaelbling, Littman, and Moore; Sutton and Barto; Bertsekas and Tsitsiklis; Tesauro; and Watkins.
  • Dialogue evaluation: The references cover dialogue evaluation and system assessment, including metrics, PARADISE, response strategies, and evaluations of web-based and timetable-information agents.These works include Danieli and Gerbino; Walker et al.; Litman, Pan, and Walker; and Sanderman et al.
  • Dialogue interaction and applications: The bibliography also covers mixed-initiative and collaborative interaction, intelligent telephone dialogues, spoken dialogue management for robots, and user interfaces for voice applications.Related references include Walker and Whittaker, Haller and McRoy, Jack et al., Roy et al., and Kamm.
  • Speech recognition and robustness: Other references examine speech-recognition reliability, poor-recognition detection, selective verification, and adaptation to recognition errors in spoken dialogue.The bibliography includes work by Niimi and Kobayashi, Litman and Pan, Litman, Walker, and Kearns, and Smith.
  • Spoken dialogue strategy learning: Several works address reinforcement learning and strategy selection for spoken dialogue systems, including applications to email and broader dialogue-policy learning.The bibliography cites Singh et al., Walker, and Walker, Fromer, and Narayanan on learning dialogue strategies.
Loading 1106.0676v1…