Efficient model learning for dialog management

ABSTRACT

Intelligent planning algorithms such as the Partially Observable Markov Decision Process (POMDP) have succeeded in dialog management applications [10, 11, 12] because they are robust to the inherent uncertainty of human interaction. Like all dialog planning systems, however, POMDPs require an accurate model of the user (e.g., what the user might say or want). POMDPs are generally specified using a large probabilistic model with many parameters. These parameters are difficult to specify from domain knowledge, and gathering enough data to estimate the parameters accurately a priori is expensive.In this paper, we take a Bayesian approach to learning the user model simultaneously with dialog manager policy. At the heart of our approach is an efficient incremental update algorithm that allows the dialog manager to replan just long enough to improve the current dialog policy given data from recent interactions. The update process has a relatively small computational cost, preventing long delays in the interaction. We are able to demonstrate a robust dialog manager that learns from interaction data, out-performing a hand-coded model in simulation and in a robotic wheelchair application.

REFERENCES

• 1: R. Dearden, N. Friedman, and D. Andre. Model based bayesian exploration. pages 150--159, 1999.
• 2: G. J. Gordon. Stable function approximation in dynamic programming. In Proceedings of the Twelfth International Conference on Machine Learning, San Francisco, CA, 1995. Morgan Kaufmann.
• 3: R. Jaulmes, J. Pineau, and D. Precup. Learning in non-stationary partially observable markov decision processes. Workshop on Non-Stationarity in Reinforcement Learning at the ECML, 2005.
• 4: Diane Litman , Satinder Singh , Michael Kearns , Marilyn Walker, NJFun: a reinforcement learning spoken dialogue system, ANLP/NAACL 2000 Workshop on Conversational systems, p.17-20, May 04-04, 2000, Seattle, Washington [doi>10.3115/1117562.1117566]
• 5: A. Nilim and L. Ghaoui. Robustness in markov decision problems with uncertain transition matrices, 2004.
• 6: J. Pineau, G. Gordon, and S. Thrun. Point-based value iteration: An anytime algorithm for pomdps, 2003.
• 7: J. Pineau, N. Roy, and S. Thrun. A hierarchical approach to pomdp planning and execution. In Workshop on Hierarchy and Memory in Reinforcement Learning (ICML), June 2001.
• 8: L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257--286, 1989.
• 9: M. Ravishankar. Efficient Algorithms for Speech Recognition. PhD thesis, Carnegie Mellon, 1996.
• 10: Nicholas Roy , Joelle Pineau , Sebastian Thrun, Spoken dialogue management using probabilistic reasoning, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.93-100, October 03-06, 2000, Hong Kong [doi>10.3115/1075218.1075231]
• 11: J. Williams and S. Young. Scaling up pomdps for dialogue management: The lhsummary pomdpla method. In Proceedings of the IEEE ASRU Workshop, 2005.
• 12: J. D. Williams, P. Poupart, and S. Young. Partially observable markov decision processes with continuous observations for dialogue management. In Proceedings of SIGdial Workshop on Discourse and Dialogue 2005, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Human Factors

Keywords:
decision-making under uncertainty, human-robot interaction, model learning