Paper: Minimizing The Length Of Non-Mixed Initiative Dialogs

ACL ID P04-2002
Title Minimizing The Length Of Non-Mixed Initiative Dialogs
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2004

Dialog participants in a non-mixed ini- tiative dialogs, in which one participant asks questions exclusively and the other participant responds to those questions exclusively, can select actions that min- imize the expected length of the dialog. The choice of question that minimizes the expected number of questions to be asked can be computed in polynomial time in some cases. The polynomial-time solutions to spe- cial cases of the problem suggest a num- ber of strategies for selecting dialog ac- tions in the intractable general case. In a simulation involving 1000 dialog sce- narios, an approximate solution using the most probable rule set/least proba- ble question resulted in expected dialog length of 3.60 questions per dialog, as compared to 2.80 for the optimal case, and 5.05 for a rand...