DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> As the DARPA spoken language community moves towards developing useful systems for interactive problem solving, we must explore alternative evaluation procedures that measure whether these systems aid people in solving problems within the task domain. In this paper, we describe several experiments exploring new evaluation procedures. To look at end-to-end evaluation, we modified our data collection procedure slightly in order to experiment with several objective task completion measures. We found that the task completion time is well correlated with the number of queries used. We also explored log file evaluation, where evaluators were asked to judge the clarity of the query and the correctness of the response based on examination of the log file. Our results show that seven evaluators were unanimous on more than 80% of the queries, and that at least 6 out of 7 evaluators agreed over 90% of the time. Finally, we applied these new procedures to compare two systems, one system requiring a complete parse and the other using the more flexible robust parsing mechanism. We found that these metrics could distinguish between these systems: there were significant differences in ability to complete the task, number of queries required to complete the task, and score (as computed through a log file evaluation) between the robust and the non-robust modes. <s> BIB001 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> The paper presents a consolidated set of 24 principles of cooperative spoken human machine dialogue which are based on the development and controlled user testing of the dialogue component of the Danish dialogue system as well as on comparison with human human dialogue theory. Potentially, the principles could be used as effective and systematic dialogue development and evaluation tools both during early design and in later phases of dialogue evaluation. <s> BIB002 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> From the Publisher: ::: This comprehensive state-of-the-art book is the first devoted to the important and timely issue of evaluating NLP systems. It addresses the whole area of NLP system evaluation, including aims and scope, problems and methodology. The authors provide a wide-ranging and careful analysis of evaluation concepts, reinforced with extensive illustrations; they relate systems to their environments and develop a framework for proper evaluation. The discussion of principles is completed by a detailed review of practice and strategies in the field, covering both systems for specific tasks, like translation, and core language processors. The methodology lessons drawn from the analysis and review are applied in a series of example cases. The book also refers NLP system evaluation to the neighbouring areas of information and speech processing, and addresses issues of tool and data provision for evaluation. A comprehensive bibliography and subject index are included as well as a term glossary. This monograph will be a valuable source of inspiration in research, practice, and teaching. <s> BIB003 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> We are interested in providing automated services via natural spoken dialog systems. By natural, we mean that the machine understands and acts upon what people actually say, in contrast to what one would like them to say. There are many issues that arise when such systems are targeted for large populations of non-expert users. In this paper, we focus on the task of automatically routing telephone calls based on a user's fluently spoken response to the open-ended prompt of How may I help you?. We first describe a database generated from 10,000 spoken transactions between customers and human agents. We then describe methods for automatically acquiring language models for both recognition and understanding from such data. Experimental results evaluating call-classification from speech are reported for that database. These methods have been embedded within a spoken dialog system, with subsequent processing for information retrieval and form-filling. <s> BIB004 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> 1. Interactive Speech Systems.- 1.1 Introduction.- 1.2 Background and Scope of This Book.- 1.3 State of the Art.- 1.4 Unsolved Problems.- 2. Speech Interaction Theory.- 2.1 Introduction.- 2.2 Elements of Interactive Speech Theory.- 2.3 Context.- 2.4 Interaction Control.- 2.5 Language.- 2.6 Speech.- 2.7 Performance.- 2.8 Characterizing Systems.- 3. Developing Interactive Speech Systems.- 3.1 Introduction.- 3.2 The Development and Evaluation Process.- 3.3 Supporting Completeness and Consistency of Requirement Specifications.- 3.4 Representing Design Space and Design Reasoning.- 3.5 Speech Functionality.- 4. Interaction Model Analysis and Design.- 4.1 Introduction.- 4.2 Guidelines for Co-operative Interaction Design.- 4.3 Guidelines Illustrated and Explained.- 4.4 Development and Justification of the Guidelines.- 5. Wizard of Oz Simulation.- 5.1 Introduction.- 5.2 Wizard of Oz for Interaction Model Development.- 5.3 Planning Wizard of Oz Simulations.- 5.4 Developing the First Interaction Model.- 5.5 Iterating the Interaction Model.- 5.6 Uses of WOZ.- 6. Implementational Issues.- 6.1 The Overall Dialogue System.- 6.2 Dialogue Control.- 6.3 Debugging.- 7. Corpus Handling.- 7.1 Introduction.- 7.2 Transcription.- 7.3 Mark-up.- 7.4 Coding.- 7.5 Corpus Tools.- 8. Evaluation.- 8.1 Introduction.- 8.2 Performance Evaluation.- 8.3 Diagnostic Evaluation.- 8.4 A By-product: User Errors.- 8.5 Adequacy Evaluation.- 9. Next Steps in Interactive Speech Systems.- 9.1 Introduction.- 9.2 Advanced Mixed Initiative Interactive Speech Systems.- 9.3 Intelligent Multimodal Systems Using Advanced Interactive Speech.- References. <s> BIB005 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> This paper describes a novel method by which a dialogue agent can learn to choose an optimal dialogue strategy. While it is widely agreed that dialogue strategies should be formulated in terms of communicative intentions, there has been little work on automatically optimizing an agent's choices when there are multiple ways to realize a communicative intention. Our method is based on a combination of learning algorithms and empirical evaluation techniques. The learning component of our method is based on algorithms for reinforcement learning, such as dynamic programming and Q-learning. The empirical component uses the PARADISE evaluation framework (Walker et al., 1997) to identify the important performance factors and to provide the performance function needed by the learning algorithm. We illustrate our method with a dialogue agent named ELVIS (EmaiL Voice Interactive System), that supports access to email over the phone. We show how ELVIS can learn to choose among alternate strategies for agent initiative, for reading messages, and for summarizing email folders. <s> BIB006 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> In this paper, we describe the evaluation of the dialog management and response generation strategies being developed for retrieval of touristic information, selected as a common domain for the ARC AUPELF-B2 action. A large number of spoken dialog systems have been reported in the literature making use of different strategies for dialog management. Comparing and evaluating different strategies is a difficult task, which often remains unexplored, because in most cases evaluation approaches require a unified database structure and efficient integration of data from several disparate sources and forms. To avoid this problem, we implemented two dialog strategy versions within the same general platform. We investigate qualitative and quantitative criteria for evaluation of these dialog control strategies: in particular, by testing the efficiency of our system with and without automatic mechanisms for guiding the user via suggestive prompts. An evaluation phase has been carried out to assess the utility of guiding the user with 32 subjects. We report performance comparisons for naive and experienced subjects and also describe how experimental results can be placed in the PARADISE framework for evaluating dialog systems. The experiments show that user guidance is appropriate for novices and appreciated by all users. <s> BIB007 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> Recent technological advances have made it possible to build real-time, interactive spoken dialogue systems for a wide variety of applications. However, when users do not respect the limitations of such systems, performance typically degrades. Although users differ with respect to their knowledge of system limitations, and although different dialogue strategies make system limitations more apparent to users, most current systems do not try to improve performance by adapting dialogue behavior to individual users. This paper presents an empirical evaluation of TOOT, an adaptable spoken dialogue system for retrieving train schedules on the web. We conduct an experiment in which 20 users carry out 4 tasks with both adaptable and non-adaptable versions of TOOT, resulting in a corpus of 80 dialogues. The values for a wide range of evaluation measures are then extracted from this corpus. Our results show that adaptable TOOT generally outperforms non-adaptable TOOT, and that the utility of adaptation depends on TOOT’s initial dialogue strategies. <s> BIB008 </s> DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Empirical and Statistical Approaches to Dialogue Strategy Design <s> We propose a quantitative model for dialog systems that can be used for learning the dialog strategy. We claim that the problem of dialog design can be formalized as an optimization problem with an objective function reflecting different dialog dimensions relevant for a given application. We also show that any dialog system can be formally described as a sequential decision process in terms of its state space, action set, and strategy. With additional assumptions about the state transition probabilities and cost assignment, a dialog system can be mapped to a stochastic model known as Markov decision process (MDP). A variety of data driven algorithms for finding the optimal strategy (i.e., the one that optimizes the criterion) is available within the MDP framework, based on reinforcement learning. For an effective use of the available training data we propose a combination of supervised and reinforcement learning: the supervised learning is used to estimate a model of the user, i.e., the MDP parameters that quantify the user's behavior. Then a reinforcement learning algorithm is used to estimate the optimal strategy while the system interacts with the simulated user. This approach is tested for learning the strategy in an air travel information system (ATIS) task. The experimental results we present in this paper show that it is indeed possible to find a simple criterion, a state space representation, and a simulated user parameterization in order to automatically learn a relatively complex dialog behavior, similar to one that was heuristically designed by several research groups. <s> BIB009
Over the last decades, numerous research papers have attempted to develop recommendations and guidelines for dialogue management. Examples of empirically obtained design principles can be found in BIB002 BIB005  and many further references are listed in BIB006  . Yet, the process of designing dialogue management strategies is still often driven by "trial and error" BIB009 and remains an "art rather than a science" BIB003 . Typically, a small number of strategies are hand-crafted by a group of expert designers. A spoken dialogue system is then built that explores each of these alternative strategies. The system is then tested on real users and conclusions are drawn as to which strategy performs best for the given task BIB004 BIB001  BIB008 . A large number of subjects is usually needed to obtain results of statistical significance, leading to high development costs and slow cycles of iterative refinements. Interpretation of the results is also often difficult since user satisfaction or dissatisfaction with a dialogue system or strategy may be due to many different factors. The results can be biased through subtle influences such as the order in which the strategies are presented to the subjects BIB007 ) and often do not necessarily provide a clear guide to further improvements. As the process of designing, implementing and testing dialogue management strategies is becoming increasingly complex, the focus of scientific research is increasingly turning from empirical methods to data-driven techniques. Statistical approaches which model processes probabilistically and estimate parameters from corpora of real human-computer dialogues are gaining popularity and have affected all areas of SDS research over the past decade (Young, 2002b,a) . The motivation for training models on real data rather than relying on traditional linguisticallymotivated techniques is clear. The latter approach of observing and analysing user phenomena and then manually constructing rules to cover them incurs significant development and maintenance costs. Moreover, the approach is inherently suboptimal because no guarantee can be given, that the hand-crafted set of rules does in fact optimally cover all possible aspects of user behaviour. Especially as systems become more complex, it is nearly impossible to test whether the system will perform well in all possible dialogue scenarios and whether the given set of rules is indeed optimal. Statistical models, in contrast, can be trained on corpora of real human-computer dialogue and they explicitly model the variance in user behaviour that hand-written rules cannot cover. While model construction and parameterization is of course still dependent on expert knowledge, the hope is to build systems which offer more robust performance, improved portability, better scalability and greater scope for adaptation. The success of statistical approaches, however, is of course naturally tied to the quality of the models and the quality of the data.