DOI: 10.1017/S000000000000000 Printed in the United Kingdom A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies <s> Statistical User Models for Simulating Dialogue <s> Statistical methods useful in automatic recognition of continuous speech are described. They concern modeling of a speaker and of an acoustic processor, extraction of the models' statistical parameters and hypothesis search procedures and likelihood computations of linguistic decoding. Experimental results are presented that indicate the power of the methods. <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> Statistical User Models for Simulating Dialogue <s> 1. Fundamentals of Speech Recognition. 2. The Speech Signal: Production, Perception, and Acoustic-Phonetic Characterization. 3. Signal Processing and Analysis Methods for Speech Recognition. 4. Pattern Comparison Techniques. 5. Speech Recognition System Design and Implementation Issues. 6. Theory and Implementation of Hidden Markov Models. 7. Speech Recognition Based on Connected Word Models. 8. Large Vocabulary Continuous Speech Recognition. 9. Task-Oriented Applications of Automatic Speech Recognition. <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> Statistical User Models for Simulating Dialogue <s> We present two server-initiated protocols to improve the performance of distributed information systems (e.g. WWW). Our first protocol is a hierarchical data dissemination mechanism that allows information to propagate from its producers to servers that are closer to its consumers. This dissemination reduces network traffic and balances load amongst servers by exploiting geographic and temporal locality of reference properties exhibited in client access patterns. Our second protocol relies on "speculative service", whereby a request for a document as serviced by sending, in addition to the document requested, a number of other documents that the server speculates will be requested in the near future. This speculation reduces service time by exploiting the spatial locality of reference property. We present results of trace-driven simulations that quantify the attainable performance gains for both protocols. <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> Statistical User Models for Simulating Dialogue <s> A dialogue agent is one that can interact and communicate with other agents, in a coherent manner, not just with one-shot messages, but with a sequence of related messages all on the same topic or in service of an overall goal. Following the basic insights of speech act theory, these communications are seen not just as transmitting information but as actions which change the state of the world. Most of these changes will be to the mental states of the agents involved in the conversation, as well as the state or context of the dialogue. As such, speech act theory allows an agent theorist or designer to place agent communication within the same general framework as agent action. In general, though, communicative action requires a more expressive logic of action than is required for something like the single-agent blocks world, familiar in classical AI planning. For one thing, there are multiple agents, and there is also a possibility of simultaneous and fallible action. <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> Statistical User Models for Simulating Dialogue <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> 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> Statistical User Models for Simulating Dialogue <s> In this paper, a complete development of computer-aided analysis and design approaches for spoken dialogue systems based on quantitative simulations is presented. With this approach the various performance metrics of a dialogue system can be flexibly defined and numerically evaluated, such that the behavior and performance of the dialogue system can be well predicted and efficiently analyzed before the implementation of the real spoken dialogue system is completed. How the different dialogue performance measures vary with respect to each of the many very complicated factors, regardless of whether it is caused by an individual component, by the overall system design, or by users' response patterns, can be separately identified, because all such factors can he precisely controlled in the simulation. Several analysis examples are presented to show how the approach can be used, including selection and tuning of the speech understanding front end, system strategy design considering query factors and confirmation factors, and objective estimates of user's degree of satisfaction. This approach is therefore very useful for the analysis and design of spoken dialogue systems, although the online test, corpus-based analysis and user survey can always follow after the system is online. <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> Statistical User Models for Simulating Dialogue <s> In recent years, a question of great interest has been the development of tools and techniqnes to facilitate the evaluation of dialogue systems. The latter can be evaluated from various points of view, such as recognition and understanding rates, dialogue naturalness and robustness against recognition errors. Evaluation usually requires compiling a large corpus of words and sentences uttered by users, relevant to the application domain the system is designed for. This paper proposes a new technique that makes it possible to reuse such a corpus for the evaluation and to check the performance of the system when different dialogue strategies are used. The technique is based on the automatic generation of conversations between the dialogue system, together with an additional dialogue system called user simulator that represents the user's interaction with the dialogue system. The technique has been applied to evaluate a dialogue system developed in our lab using two different recognition front-ends and two different dialogue strategies to handle user confirmations. The experiments show that the prompt-dependent recognition front-end achieves better results, but that this front-end is appropriate only if users limit their utterances to those related to the current system prompt. The prompt-independent front-end achieves inferior results, but enables front-end users to utter any permitted utterance at any time, irrespective of the system prompt. In consequence, this front-end may allow a more natural and comfortable interaction. The experiments also show that the re-prompting confirmation strategy enhances system performance for both recognition front-ends. <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> Statistical User Models for Simulating Dialogue <s> In this paper we propose a number of principles and conjectures for mixed-initiative collaborative dialogs. We explore some methodologies for managing initiative between conversational participants. We mathematically analyze specific initiative-changing mechanisms based on a probabilistic knowledge base and user model. We look at the role of negotiation in managing initiative and quantify how the negotiation process is useful toward modifying user models. Some experimental results using computer–computer simulations are presented along with some discussion of how such studies are useful toward building human–computer systems. <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> Statistical User Models for Simulating Dialogue <s> This paper experimentally shows that mixed-initiative dialogue is not always more efficient than non-mixed initiative dialogue in route finding tasks. Based on the dialogue model proposed in Conversation Analysis and Discourse Analysis a lá the Birmingham school and Whittaker and Stenton's definition of initiative, we implement dialogue systems and obtain experimental results by making the systems interact with each other. Across a variety of instantiations of the dialogue model, the results show that with easy problems, the efficiency of mixed-initiative dialogue is a little better than or equal to that of non-mixed-initiative dialogue, while with difficult problems mixed-initiative dialogue is less efficient than non-mixed- initiative dialogue. <s> BIB009 </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> Statistical User Models for Simulating Dialogue <s> This paper presents a probabilistic method to simulate task-oriented human-computer dialogues at the intention level, that may be used to improve or to evaluate the performance of spoken dialogue systems. Our method uses a network of hidden Markov models (HMMs) to predict system and user intentions, where a "language model" predicts sequences of goals and the component HMMs predict sequences of intentions. We compare standard HMMs, input HMMs and input-output HMMs in an effort to better predict sequences of intentions. In addition, we propose a dialogue similarity measure to evaluate the realism of the simulated dialogues. We performed experiments using the DARPA communicator corpora and report results with three different metrics: dialogue length, dialogue similarity and precision-recall <s> BIB010 </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> Statistical User Models for Simulating Dialogue <s> The Lumiere Project centers on harnessing probability and utility to provide assistance to computer software users. We review work on Bayesian user models that can be employed to infer a user's needs by considering a user's background, actions, and queries. Several problems were tackled in Lumiere research, including (1) the construction of Bayesian models for reasoning about the time-varying goals of computer users from their observed actions and queries, (2) gaining access to a stream of events from software applications, (3) developing a language for transforming system events into observational variables represented in Bayesian user models, (4) developing persistent profiles to capture changes in a user's expertise, and (5) the development of an overall architecture for an intelligent user interface. Lumiere prototypes served as the basis for the Ofice Assistant in the Microsoft Office '97 suite of productivity applications. <s> BIB011
The recent work on user modelling for strategy learning with a simulated user differs in many respects from traditional work on user modelling in SDS and NLP. The purpose of the user model in this new context is not to capture the individual characteristics of a specific user, but to form the basis of a user simulation tool which is representative of a diverse user population and which takes the role of a synthetic dialogue partner for the learning dialogue manager during the development phase of a new system. As such, the user model must be able to predict user responses that a real user might give in the same dialogue context and it must also represent the statistical distribution over all types of user behaviour and user responses. These requirements clearly favour a statistical approach to user modelling. Most importantly, the probabilistic nature of statistical models allows for a degree of "lifelike" randomness in user behaviour. Very early research on dialogue system design and evaluation has explored the use of deterministic user models for simulating dialogues  BIB008 BIB009 BIB006 ), but these cannot naturally account for the variability in real human user behaviour. The second advantage of statistical models is that the model parameters can be estimated using real human-computer dialogue data. Hand-coded models require a very careful choice of parameter values, which is difficult because human user behaviour is poorly understood and system-specific factors or user population-dependent aspects are hard to estimate using "common sense". The statistical, data-driven approach of learning appropriate parameter values from training data rather than relying on heuristics or empirical principles is less likely to introduce a bias in user behaviour. The user model is also likely to be more robust, more scalable and easier to port to a different domain or dataset. Statistical predictive user models in the context of dialogue strategy learning have been explored by a number of research groups over the last decade. It is possible to classify the different approaches with regard to the level of abstraction at which they model dialogue. This can be at either the acoustic level, the word level or the intention-level. The latter is a particularly useful compressed representation of human-computer interaction. Intentions cannot be observed, but they can be described using speech-act and dialogue-act theory   BIB004 . In recent years, simulation on the intention-level has been most popular. This approach was first taken by  and has been adopted in later work on user simulation by most other research groups BIB005   BIB010 . Modelling interaction on the intention-level avoids the need to reproduce the enormous variety of human language on the level of speech signals or word sequences. Examples of user simulation on the word-level   or acoustic level BIB007  are rare and their robustness, portability and scalability is somewhat limited. Several different statistical user modelling techniques have been applied to the problem of simulationbased learning. All of them exploit the Markov assumption that the next user action can be predicted based on some representation of the current state of the dialogue. The state representation typically includes the previous system action, but may also cover longer dialogue histories and other variables representing the user goal, user memory, and so forth. In general, Markov Models are based on the assumption that the likelihood of occurrence of an event depends only on a fixed number of previous events and hence the relevant history can always be encoded in a finite state space. Given a sequence of events x n , x n−1 , ..., x n−m+1 , a probability distribution can be estimated over all events following this sequence in a set of training data. The likelihood that a certain event x n+1 follows the given sequence can then be computed using the conditional probability p(x n+1 |x n , x n−1 , ..., x n−m+1 ). Outside the field of spoken dialogue systems research, Markov Models are a commonly used statistical user modelling technique. A typical application is the prediction of documents a user is most likely to request next when browsing web-pages BIB003 BIB011 . In the field of speech recognition and spoken dialogue systems, n-grams are a popular form of Markov Model and well-known for their use in predicting the likelihood of different word sequences in statistical language modelling BIB001 BIB002 .