tailieunhanh - Báo cáo khoa học: "Minimizing the Length of Non-Mixed Initiative Dialogs"

Dialog participants in a non-mixed initiative dialogs, in which one participant asks questions exclusively and the other participant responds to those questions exclusively, can select actions that minimize 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 special cases of the problem suggest a number of strategies for selecting dialog actions in the intractable general case. . | Minimizing the Length of Non-Mixed Initiative Dialogs R. BryceInouye Department of Computer Science Duke University Durham NC 27708 rbi@ Abstract Dialog participants in a non-mixed initiative dialogs in which one participant asks questions exclusively and the other participant responds to those questions exclusively can select actions that minimize 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 special cases of the problem suggest a number of strategies for selecting dialog actions in the intractable general case. In a simulation involving 1000 dialog scenarios an approximate solution using the most probable rule set least probable question resulted in expected dialog length of questions per dialog as compared to for the optimal case and for a randomly chosen strategy. 1 Introduction Making optimal choices in unconstrained natural language dialogs may be impossible. The difficulty of defining consistent meaningful criteria for which behavior can be optimized and the infinite number of possible actions that may be taken at any point in an unconstrained dialog present generally insurmountable obstacles to optimization. Computing the optimal dialog action may be intractable even in a simple highly constrained model of dialog with narrowly defined measures of success. This paper presents an analysis of the optimal behavior of a participant in non-mixed initiative dialogs a restricted but important class of dialogs. 2 Non-mixed initiative dialogs In recent years dialog researchers have focused much attention on the study of mixed-initiative behaviors in natural language dialogs. In general mixed initiative refers to the idea that control over the content and direction of a dialog may pass from one participant to another. 1 Cohen et al. 1998 provides a good overview of the various definitions .