Automatic optimization of dialog strategies using a theoretical framework for modeling initiative in the missing-axiom theory of dialog

We present a formal definition of the missing axiom theory of dialog, which models task-oriented dialog as a distributed theorem proving process in which completion of the dialog task corresponds to the successful derivation of a proof. Participants in the dialog lack specific pieces of knowledge necessary to complete the proof, the missing axioms from which the theory takes its name.;We extend the missing axiom theory to incorporate probabilistic user models which represent the estimated probabilities that a participant in a dialog will be able to supply a given missing axiom.;We develop a new abstraction for representing the task structure of fixed initiative dialogs in which the knowledge necessary to complete the dialog task is modeled as sets of dialog rule sets, which are sets of missing axioms such that if all of the missing axioms in the set are obtained, a proof of the dialog goal can be generated. Using the dialog rule set abstraction in conjunction with the probabilistic user model, we derive methods for calculating dialog strategies that minimize the expected length of dialog. Polynomial time algorithms are given for several cases of interest, and effective heuristics are developed for the general case.;The methods for dialog strategy optimization can be used in conjunction with a dynamically updated probabilistic user model to implement a spoken dialog system that automatically adapts its strategy to deal with changes in the user population or in individual users' abilities and knowledge. We present results of a simulation that demonstrates the effectiveness of such methods.;The analysis of fixed initiative dialogs can be extended to mixed initiative dialogs if the participants are constrained to be maximally cooperative. We present methods for optimizing dialog strategies in cooperative mixed initiative environments based on an extension of the user model that includes expected costs of obtaining missing axioms. We also develop a formal theory of subdialogs that enables dialog domains to be factored into subdomains that can be solved independently of each other, thus increasing the size of domain for which exact solutions to the dialog strategy optimization problem can be calculated.