Minimizing the Length of Non-Mixed Initiative Dialogs
R. Bryce Inouye
Department of Computer Science
Duke University
Durham, NC 27708
rbi@cs.duke.edu
Abstract
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 randomly chosen strategy.
1 Introduction
Making optimal choices in unconstrained natural
language dialogs may be impossible. The diffi-
culty of defining consistent, meaningful criteria
for which behavior can be optimized and the infi-
nite number of possible actions that may be taken
at any point in an unconstrained dialog present
generally insurmountable obstacles to optimiza-
tion.
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 ini-
tiative 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 gen-
eral, mixed initiative refers to the idea that con-
trol 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 vari-
ous definitions of dialog initiative that have been
proposed. Our work adopts a definition similar to
Guinn (1999), who posits that initiative attaches to
specific dialog goals.
This paper considers non-mixed-initiative di-
alogs, which we shall take to mean dialogs with
the following characteristics:
1. The dialog has two participants, the leader
and the follower, who are working coopera-
tively to achieve some mutually desired dia-
log goal.
2. The leader may request information from the
follower, or may inform the follower that the
dialog has succeeded or failed to achieve the
dialog goal.
1There is no generally accepted consensus as to how ini-
tiative should be defined.
3. The follower may only inform the leader of a
fact in direct response to a request for infor-
mation from the leader, or inform the leader
that it cannot fulfill a particular request.
The model assumes the leader knows sets of ques-
tions a0a2a1a4a3
a5a7a6 a8 a9a10a0a7a6a11a6a2a12a13a0a14a6a16a15a14a12a18a17a18a17a18a17a2a12a13a0a14a6a11a19a20a22a21a24a23
a5a10a15 a8 a9a10a0a10a15a25a6a2a12a13a0a2a15a11a15a14a12a18a17a18a17a18a17a2a12a13a0a2a15a25a19a20a7a26a10a23
...
a5a2a27 a8 a9a10a0a2a27a28a6a2a12a13a0a18a27a29a15a14a12a18a17a18a17a18a17a10a12a13a0a18a27a30a19a20a32a31a28a23
such that if all questions in any one set a5a14a1 are
answered successfully by the follower, the dia-
log goal will be satisfied. The sets will be re-
ferred to hereafter as rule sets. The leader’s
task is to find a rule set a5 whose constituent
questions can all be successfully answered. The
method is to choose a sequence of questions
a0a18a1a33a21a34a19a3a35a21a25a12a13a0a18a1 a26 a19a3 a26 a12a18a17a18a17a18a17a36a12a13a0a18a1a38a37a25a19a3a39a37 which will lead to its dis-
covery.
For example, in a dialog in a customer service
setting in which the leader attempts to locate the
follower’s account in a database, the leader might
request the follower’s name and account number,
or might request the name and telephone num-
ber. The corresponding rule sets for such a di-
alog would be a9a10a40a42a41a32a43a45a44a46a40a48a47a50a49a51a12a13a40a42a41a32a43a45a52a54a53a56a55a32a57a58a49a10a44a59a55a22a23 and
a9a10a40a45a41a36a43a45a44a46a40a48a47a50a49a51a12a13a40a42a41a32a43a45a60a62a61a25a61a25a63a34a44a59a55a22a23 .
One complicating factor in the leader’s task is
that a question a0 a1a64a19a3 in one rule set may occur in
several other rule sets so that choosing to ask a0a14a1a33a19a3
can have ramifications for several sets.
We assume that for every question a0a36a1a33a19a3 the leader
knows an associated probability a65
a1a33a19a3 that the fol-
lower has the knowledge necessary to answer a0a32a1a33a19a3 .2
These probabilities enable us to compute an ex-
pected length for a dialog, measured by the num-
ber of questions asked by the leader. Our goal in
selecting a sequence of questions will be to mini-
mize the expected length of the dialog.
The probabilities may be estimated by aggregat-
ing the results from all interactions, or a more so-
phisticated individualized model might be main-
tained for each participant. Some examples of
how these probabilities might be estimated can be
2In addition to modeling the follower’s knowledge, these
probabilities can also model aspects of the dialog system’s
performance, such as the recognition rate of an automatic
speech recognizer.
found in (Conati et al., 2002; Zukerman and Al-
brecht, 2001).
Our model of dialog derives from rule-based
theories of dialog structure, such as (Perrault and
Allen, 1980; Grosz and Kraus, 1996; Lochbaum,
1998). In particular, this form of the problem mod-
els exactly the “missing axiom theory” of Smith
and Hipp (1994; 1995) which proposes that di-
alog is aimed at proving the top-level goal in a
theorem-proving tree and “missing axioms” in the
proof provide motivation for interactions with the
dialog partner. The rule sets a5a32a1 are sets of missing
axioms that are sufficient to complete the proof of
the top-level goal.
Our format is quite general and can model other
dialog systems as well. For example, a dialog sys-
tem that is organized as a decision tree with a ques-
tion at the root, with additional questions at suc-
cessor branches, can be modeled by our format.
As an example, suppose we have top-
level goal a63a66a6 and these rules to prove it:
(a63a34a15 AND a0a14a6a16a15 ) implies a63a66a6
(a0a14a6a11a6 OR a0a10a15a25a6 ) implies a63a11a15 .
The corresponding rule sets are
a5a7a6 = a9a10a0a14a6a11a6a2a12a13a0a7a6a16a15a10a23
a5a10a15 = a9a10a0a2a15a25a6a2a12a13a0a7a6a16a15a10a23 .
If all of the questions in either a5 a6 or a5 a15 are
satisfied, a63a66a6 will be proven. If we have values for
the probabilities a65 a6a11a6a18a12 a65 a6a16a15 , and a65 a15a25a6 , we can design
an optimum ordering of the questions to minimize
the expected length of dialogs. Thus if a65
a6a11a6 is
much smaller than a65 a15a25a6 , we would ask a0 a15a25a6 before
asking a0a7a6a11a6 . The reader might try to decide when
a0a14a6a16a15 should be asked before any other questions in
order to minimize the expected length of dialogs.
The rest of the paper examines how the leader
can select the questions which minimize the over-
all expected length of the dialog, as measured by
the number of questions asked. Each question-
response pair is considered to contribute equally
to the length. Sections 3, 4, and 5 describe
polynomial-time algorithms for finding the opti-
mum order of questions in three special instances
of the question ordering optimization problem.
Section 6 gives a polynomial-time method to ap-
proximate optimum behavior in the general case of
a57 rule sets which may have many common ques-
tions.
3 Case: One rule set
Many dialog tasks can be modeled with a single
rule set a5 a8 a9a10a0a7a6a18a12a13a0a2a15a14a12a18a17a18a17a18a17a2a12a13a0a18a20 a23 . For example, a
leader might ask the follower to supply values for
each field in a form. Here the optimum strategy is
to ask the questions first that have the least proba-
bility of being successfully answered.
Theorem 1. Given a rule set a5 a8 a9a10a0 a6 a12a18a17a18a17a18a17a36a12a13a0 a20 a23 ,
asking the questions in the order of their prob-
ability of success (least first) results in the min-
imum expected dialog length; that is, for a1 a8
a2
a12a18a17a18a17a18a17a10a12a11a57a4a3
a2
a12
a65
a1a6a5
a65
a1a8a7 a6 where
a65
a1 is the probability
that the follower will answer question a0a36a1 success-
fully.
A formal proof is available in a longer version
of this paper. Informally, we have two cases; the
first assumes that all questions a0a36a1 are answered
successfully, leading to a dialog length of a57 , since
a57 questions will be asked and then answered.
The second case assumes that some a0a36a1 will not
be answered successfully. The expected length
increases as the probabilities of success of the
questions asked increases. However, the expected
length does not depend on the probability of suc-
cess for the last question asked, since no questions
follow it regardless of the outcome. Therefore, the
question with the greatest probability of success
appears at the end of the optimal ordering. Simi-
larly, we can show that given the last question in
the ordering, the expected length does not depend
upon the probability of the second to last question
in the ordering, and so on until all questions have
been placed in the proper position. The optimal or-
dering is in order of increasing probability of suc-
cess.
4 Case: Two independent rule sets
We now consider a dialog scenario in which the
leader has two rule sets for completing the dialog
task.
Definition 4.1. Two rule sets a5a22a6 and a5a10a15 are inde-
pendent if a5a51a6a10a9a59a5a10a15 a8a12a11 . If a5a7a6a10a9a50a5a10a15 is non-empty,
then the members of a5a48a6a10a9a46a5a10a15 are said to be com-
mon to a5a51a6 and a5a10a15 . A question a0 is unique to rule
set a5 if a0a14a13 a5 and for all a5a16a15a18a17a8 a5 , a0a20a19a13 a5a21a15
In a dialog scenario in which the leader has
multiple, mutually independent rule sets for ac-
complishing the dialog goal, the result of asking a
question contained in one rule set has no effect on
the success or failure of the other rule sets known
by the leader. Also, it can be shown that if the
leader makes optimal decisions at each turn in the
dialog, once the leader begins asking questions be-
longing to one rule set, it should continue to ask
questions from the same rule set until the rule set
either succeeds or fails. The problem of select-
ing the question that minimizes the expected dia-
log length a22a24a23a26a25a28a27 becomes the problem of selecting
which rule set should be used first by the leader.
Once the rule set has been selected, Theorem 1
shows how to select a question from the selected
rule set that minimizesa22a24a23a26a25a28a27 .
By expected dialog length, we mean the usual
definition of expectation
a22a29a23a26a25a30a27
a8a32a31a34a33
a23a65
a5a7a55a16a35a36a17a10a55a16a36a38a37
a27a39a23a26a25
a49a18a57a41a40a48a63a11a53 a55a21a36a42a37
a27
a17
Thus, to calculate the expected length of a dialog,
we must be able to enumerate all of the possible
outcomes of that dialog, along with the probability
of that outcome occurring, and the length associ-
ated with that outcome.
Before we show how the leader should decide
which rule set it should use first, we introduce
some notation.
The expected length in case of failure for an
ordering a55 a8 a0a7a6a18a12a18a17a18a17a18a17a10a12a13a0a2a20 of the questions of a
rule set a5 is the expected length of the dialog that
would result if a5 were the only rule set available to
the leader, the leader asked questions in the order
given by a55 , and one of the questions in a5 failed.
The expected length in case of failure is
a43
a43a45a44a4a46a38a47a48a50a49
a21a52a51
a48
a47
a53
a48a50a49
a21a16a54a28a55
a48a8a56
a21
a57
a58
a49
a21
a51
a58a60a59
a55
a43a45a44
a51
a48
a59a62a61
The factor
a6
a6a64a63a66a65
a47a67
a49
a21a69a68a16a70a50a71
a67a52a72 is a scaling factor that ac-
counts for the fact that we are counting only cases
in which the dialog fails. We will let a36 a1 represent
the minimum expected length in case of failure for
rule set a5a10a1 , obtained by ordering the questions of a5a14a1
by increasing probability of success, as per Theo-
rem 1.
The probability of success a41 of a rule set
a5 a8 a9a10a0a7a6a2a12a13a0a2a15a32a12a18a17a18a17a18a17a10a12a13a0a18a20 a23 is
a73
a20
a1a75a74 a6
a65
a1 . The definition
of probability of success of a rule set assumes that
the probabilities of success for individual ques-
tions are mutually independent.
Theorem 2. Let a0 a8 a9a2a5a51a6a2a12a11a5a36a15a10a23 be the set of mutu-
ally independent rule sets available to the leader
for accomplishing the dialog goal. For a rule set
a5 a1 in
a0 , let
a41 a1 be the probability of success of a5 a1 , a57 a1
be the number of questions in a5a32a1 , anda36a32a1 be the min-
imum expected length in case of failure. To mini-
mize the expected length of the dialog, the leader
should select the question with the least probabil-
ity of success from the rule set a5a32a1 with the least
value of a57 a1a2a1 a36a32a1a23
a6
a3
a48
a3
a2
a27 .
Proof: If the leader uses questions from a5a42a6 first,
the expected dialog lengtha22a24a23a26a25a6 a27 is
a41a51a6a34a57 a6a4a1
a23
a2
a3a62a41a7a6
a27
a41a36a15
a23
a36a22a6a5a1 a57 a15
a27
a1
a23
a2
a3 a41a7a6
a27a39a23
a2
a3 a41a36a15
a27a39a23
a36a22a6a6a1 a36a14a15
a27
The first term, a41a48a6a11a57 a6 , is the probability of success
for a5a7a6 times the length of a5a48a6 . The second term,
a23
a2
a3 a41a7a6
a27
a41a36a15
a23
a36a22a6a7a1 a57 a15
a27 , is the probability that a5a48a6 will
and a5 a15 will succeed times the length of that dialog.
The third term, a23a2 a3 a41a48a6 a27a39a23a2 a3 a41a36a15 a27a39a23a36a22a6a8a1 a36a14a15 a27 , is the
probability that both a5a48a6 and a5a36a15 fail times the asso-
ciated length. We can multiply out and rearrange
terms to get
a9
a55a11a10
a21
a59a13a12 a14
a21a16a15 a21a2a17
a55
a43a45a44
a14
a21
a59
a55a19a18
a21a20a17
a14
a26 a15 a26 a17
a55
a43 a44
a14
a26
a59
a18
a26
a59
a12 a14
a21a16a15 a21a2a17
a18
a21 a44
a14
a21
a18
a21a21a17
a14
a26 a15 a26 a44
a14
a21
a14
a26 a15 a26 a17
a18
a26
a44
a14
a21
a18
a26 a44
a14
a26
a18
a26a22a17
a14
a21
a14
a26
a18
a26
If the leader uses questions from a5a14a15 first,a22a24a23a26a25
a15
a27 is
a23a25a24
a47
a24a20a26a28a27a25a24
a56
a23a29a24a30a27a25a24a31a26a28a23a33a32
a47
a32
a56
a23a25a24a34a23a33a32
a47
a32a35a26a8a27a33a32
a56
a23a25a24a36a27a33a32
a56
a23a33a32a34a27a33a32a37a26a28a23a25a24a30a23a16a32a38a27a33a32
Comparinga22a24a23a26a25a6 a27 anda22a24a23a26a25a15 a27 , and eliminating any
common terms, we find that a23a5 a6 a12a11a5 a15 a27 is the correct
ordering if
a9
a55a11a10
a21
a59a40a39
a9
a55a11a10
a26
a59
a44
a14
a21
a14
a26a34a15a22a26 a44
a14
a21
a18
a26a41a17
a14
a21
a14
a26
a18
a26
a39
a44
a14
a26
a14
a21 a15 a21 a44
a14
a26
a18
a21 a17
a14
a26
a14
a21
a18
a21
a14
a21
a55
a44
a14
a26 a15 a26 a44
a18
a26 a17
a14
a26
a18
a26
a59a40a39 a14
a26
a55
a44
a14
a21a16a15 a21 a44
a18
a21a2a17
a14
a21
a18
a21
a59
a14
a21
a55
a44
a18
a26a42a17
a14
a26
a55a19a18
a26 a44 a15a22a26
a59a30a59a40a39 a14
a26
a55
a44
a18
a21 a17
a14
a21
a55a19a18
a21 a44 a15 a21
a59a30a59
a44
a18
a26 a17
a14
a26
a55a19a18
a26 a44 a15 a26
a59
a14
a26
a39
a44
a18
a21a21a17
a14
a21
a55a19a18
a21 a44 a15 a21
a59
a14
a21
a15a22a26a41a17
a18
a26
a55
a43
a14
a26
a44 a43
a59a40a43
a15 a21 a17
a18
a21
a55
a43
a14
a21
a44 a43
a59
Thus, if the above inequality holds, thena22a24a23a26a25a6 a27a45a44
a22a24a23a26a25
a15
a27 , and the leader should ask questions from
a5a7a6 first. Otherwise,
a22a24a23a26a25
a15
a27
a5
a22a29a23a26a25
a6
a27 , and the leader
should ask questions from a5a32a15 first.
We conjecture that in the general case of a47 mu-
tually independent rule sets, the proper ordering of
rule sets is obtained by calculating a57 a1a46a1 a36a32a1a23
a6
a3
a48
a3
a2
a27
for each rule set a5a36a1 , and sorting the rule sets by
those values. Preliminary experimental evidence
supports this conjecture, but no formal proof has
been derived yet.
Note that calculating a41 and a36 for each rule set
takes polynomial time, as does sorting the rule sets
into their proper order and sorting the questions
within each rule set. Thus the solution can be ob-
tained in polynomial time.
As an example, consider the rule sets a5 a6 a8
a9a10a0a14a6a11a6a2a12a13a0a14a6a16a15a32a23 and a5a36a15 a8 a9a10a0a2a15a25a6a2a12a13a0a2a15a11a15a36a23 . Suppose that we
assign a65 a6a11a6 a8 a47a45a17a49a48 a12 a65 a6a16a15 a8 a47a45a17a51a50a42a12 a65 a15a25a6 a8 a47a45a17a51a52a42a12 and
a65
a15a11a15 a8a53a47a45a17a51a54 . In this case, a57 a8a56a55 and a41 a8a53a47a45a17a51a55a57a48 are
the same for both rule sets. However, a36 a6 a8 a2 a17a51a55 a2
and a36a7a15 a8 a2 a17a58a47a59a54 , so evaluating a57 a1a60a1 a36a32a1 a23
a6
a3
a48
a3
a2
a27 for
both rule sets, we discover that asking questions
from a5 a15 first results in the minimum expected dia-
log length.
5 Case: Two rule sets, one common
question
We now examine the simplest case in which the
rule sets are not mutually independent: the leader
has two rule sets a5a51a6 and a5a10a15 , and a5a7a6a10a9a59a5a10a15 a8 a9a10a0a62a61a25a23 .
In this section, we will use a22a24a23a26a25a29a63a48a27 to denote the
minimum expected length of the dialog (computed
using Theorem 1) resulting from the leader using
only a5a2a1 to accomplish the dialog task. The notation
a22a24a23a26a25a63a36a64
a48
a27 will denote the minimum expected length
of the dialog resulting from the leader using only
the rule set a5a10a1 a3 a9a10a0a62a61a25a23 to accomplish the dialog task.
For example, a rule set a5a48a6a29a8 a9a10a0a14a6a18a12a13a0a2a15a32a12a13a0a62a61a25a23 witha65 a6a29a8
a47a45a17a51a52a42a12
a65
a15 a8a65a47a45a17a51a66 and
a65
a61 a8a67a47a45a17a51a68 , has
a22a24a23a26a25a19a63
a21
a27
a8
a2
a17a49a48a35a66 and
a22a24a23a26a25a63a36a64
a21
a27
a8
a2
a17a51a52 .
Theorem 3. Given rule sets a5a22a6 a8 a9a10a0a62a61a24a12a13a0a14a6a18a12a18a17a18a17a18a17a10a12a13a0a18a20 a23
and a5a36a15 , such that a5a51a6 a9 a5a10a15a30a8 a9a10a0a69a61a25a23 , if the leader asks
questions from a5a48a6 until a5a51a6 either succeeds or fails
before asking any questions unique to a5a14a15 , then the
ordering of questions of a5 a6 that results in the min-
imum expected dialog length is given by ordering
the questions a0a2a1 by increasing a70 a1 , where
a70
a1a58a8
a71
a72a49a73
a68a75a74
a7
a68a75a74a30a76a6a70a78a77 a37
a64
a26
a72a63
a76a6a70a79a77
a37
a26
a72
a6a62a7
a68 a74 a76 a70a78a77 a37
a64
a26
a72a63
a76a6a70a79a77
a37
a26
a72
a12a13a0 a1 a8 a0 a61
a65
a1a42a55a32a63a11a53 a49a2a5a57a80
a1
a41a32a49a7a17
The proof is in two parts. First we show that
the questions unique to a5a22a6 should be ordered by
a9
a55a11a10
a59 a12
a43 a17
a1
a53
a48a49
a21
a48
a57
a58
a49
a21
a51
a58
a17
a51 a74
a47
a56
a21
a53
a48a49
a1
a48
a57
a58
a49
a21
a51
a58
a17
a9
a55a11a10
a37
a24
a59
a55
a43a45a44
a1
a57
a48a50a49
a21
a51
a48
a59
a17
a51 a74
a9
a55a11a10
a37a3a2
a24
a59
a55
a1
a57
a48a50a49
a21
a51
a48
a44
a47
a57
a48a50a49
a21
a51
a48
a59
Figure 1: A general expression for the expected di-
alog length for the dialog scenario described in section
5. The questions of a4 a21 are asked in the arbitrary order
a5
a21a7a6
a61a61a61
a6
a5
a1
a6
a5
a74
a6
a5
a1 a26
a21a8a6
a5
a47 , where
a5
a74 is the question common to
a4
a21 and
a4
a26 . a9
a55a11a10
a26
a59 and
a9
a55a11a10
a64
a26
a59 are defined in Section 5.
increasing probability of success given that the po-
sition of a0a69a61 is fixed. Then we show that given
the correct ordering of unique questions of a5a42a6 ,
a0a62a61 should appear in that ordering at the position
where
a68 a74
a7
a68 a74 a76a6a70a78a77 a37
a64
a26
a72a63
a76a6a70a78a77
a37
a26
a72
a6a62a7
a68 a74 a76a6a70a78a77 a37
a64
a26
a72a63
a76 a70a78a77
a37
a26
a72 falls in the correspond-
ing sequence of questions probabilities of success.
Space considerations preclude a complete listing
of the proof, but an outline follows.
Figure 1 shows an expression for the expected
dialog length for a dialog in which the leader
asks questions from a5a48a6 until a5a51a6 either succeeds
or fails before asking any questions unique to a5 a15 .
The expression assumes an arbitrary ordering a55a54a8
a0a14a6a18a12a18a17a18a17a18a17a2a12a13a0
a71
a12a13a0a62a61a24a12a13a0
a71
a7 a6a2a12a18a17a18a17a18a17a2a12a13a0a18a20 . Note that if a question
occurring before a0a69a61 fails, the rest of the dialog has
a minimum expected lengtha22a29a23a26a25a29a63
a26
a27 . If a0a69a61 fails, the
dialog terminates. If a question occurring after a0 a61
fails, the rest of the dialog has minimum expected
lengtha22a29a23a26a25a63a36a64a26 a27 .
If we fix the position of a0 a61 , we can show that the
questions unique to a5a48a6 must be ordered by increas-
ing probability of success in the optimal ordering.
The proof proceeds by showing that switching the
positions of any two unique questions a0 a71 and a0a10a9 in
an arbitrary ordering of the questions of a5 a6 , where
a0
a71 occurs before
a0a11a9 in the original ordering, the
expected length for the new ordering is less than
the expected length for the original ordering if and
only if a65 a9 a44 a65 a71 .
After showing that the unique questions of a5a42a6
must be ordered by increasing probability of suc-
cess in the optimal ordering, we must then show
how to find the position of a0 a61 in the optimal or-
dering. We say that a0 a61 occurs at position a40 in or-
dering a55 if a0a69a61 immediately follows a0 a71 in the or-
dering. a22a29a23a26a25a71a27 is the expected length for the or-
dering with a0a69a61 at position a40 . We can show that if
a22a24a23a26a25
a71
a27 a44a32a22a29a23a26a25
a71
a7 a6
a27 then
a68 a74
a63
a76 a70a78a77
a37
a26
a72a7
a68 a74 a76a6a70a78a77 a37
a64
a26
a72
a6a64a63
a76a6a70a79a77
a37
a26
a72a7
a68 a74 a76a6a70a78a77 a37
a64
a26
a72
a44 a65
a71
a7 a6
by a process similar to that used in the proof of
Theorem 2. Since the unique questions in a5a42a6 are
ordered by increasing probability of success, find-
ing the optimal position of the common question
a0 in the ordering of the questions of a5 a6 corre-
sponds to the problem of finding where the value
of
a68
a63
a76 a70a78a77
a37
a26
a72a7
a68a62a76a6a70a79a77 a37
a64
a26
a72
a6a64a63
a76a6a70a79a77
a37
a26
a72a7
a68a62a76a6a70a79a77 a37
a64
a26
a72 falls in the sorted list of proba-
bilities of success of the unique questions of a5 a6 . If
the value immediately precedes the value of a65 a1 in
the list, then the common question should imme-
diately precede a0a2a1 in the optimal ordering of ques-
tions of a5a51a6 .
Theorem 3 provides a method for obtaining the
optimal ordering of questions in a5a22a6 , given that a5a51a6
is selected first by the leader. The leader can use
the same method to determine the optimal order-
ing of the questions of a5a32a15 if a5a10a15 is selected first. The
two optimal orderings give rise to two different ex-
pected dialog lengths; the leader should select the
rule set and ordering that leads to the minimal ex-
pected dialog length. The calculation can be done
in polynomial time.
6 Approximate solutions in the general
case
Specific instances of the optimization problem can
be solved in polynomial time, but the general case
has worst-case complexity that is exponential in
the number of questions. To approximate the op-
timal solution, we can use some of the insights
gained from the analysis of the special cases to
generate methods for selecting a rule set, and se-
lecting a question from the chosen rule set. Theo-
rem 1 says that if there is only one rule set avail-
able, then the least probable question should be
asked first. We can also observe that if the dialog
succeeds, then in general, we would like to min-
imize the number of rule sets that must be tried
before succeeding. Combining these two observa-
tions produces a policy of selecting the question
with the minimal probability of success from the
rule set with the maximal probability of success.
Method Avg. length
Optimal 2.80
Most prob. rule set/least prob. question 3.60
Most prob. rule set/random question 4.26
Random rule set/most prob. question 4.26
Random rule set/random question 5.05
Table 1: Average expected dialog length (measured in num-
ber of leader questions) for the optimal case and several sim-
ple approximation methods over 1000 dialog scenarios. Each
scenario consisted of 6 rule sets of 2 to 5 questions each, cre-
ated from a pool of 9 different questions.
We tested this policy by generating 1000 dialog
scenarios. First, a pool of nine questions with ran-
domly assigned probabilities of success was gen-
erated. Six rule sets were created using these nine
questions, each containing between two and five
questions. The number of questions in each rule
set was selected randomly, with each value being
equally probable. We then calculated the expected
length of the dialog that would result if the leader
were to select questions according to the following
five schemes:
1. Optimal
2. Most probable rule set, least probable question
3. Random rule set, least probable question
4. Most probable rule set, random question
5. Random rule set, random question.
The results are summarized in Table 1.
7 Further Research
We intend to discover other special cases for
which polynomial time solutions exist, and inves-
tigate other methods for approximating the opti-
mal solution. With a larger library of studied spe-
cial cases, even if polynomial time solutions do
not exist for such cases, heuristics designed for use
in special cases may provide better performance.
Another extension to this research is to extend
the information model maintained by the leader to
allow the probabilities returned by the model to be
non-independent.
8 Conclusions
Optimizing the behavior of dialog participants can
be a complex task even in restricted and special-
ized environments. For the case of non-mixed ini-
tiative dialogs, selecting dialog actions that mini-
mize the overall expected dialog length is a non-
trivial problem, but one which has some solutions
in certain instances. A study of the characteristics
of the problem can yield insights that lead to the
development of methods that allow a dialog par-
ticipant to perform in a principled way in the face
of intractable complexity.
Acknowledgments
This work was supported by a grant from SAIC,
and from the US Defense Advanced Research
Projects Agency.
References
Robin Cohen, Coralee Allaby, Christian Cumbaa,
Mark Fitzgerald, Kinson Ho, Bowen Hui, Celine
Latulipe, Fletcher Lu, Nancy Moussa, David Poo-
ley, Alex Qian, and Saheem Siddiqi. 1998. What is
initiative? User Modeling and User-Adapted Inter-
action, 8(3-4):171–214.
C. Conati, A. Gerntner, and K. Vanlehn. 2002. Us-
ing bayesian networks to manage uncertainty in user
modeling. User Modeling and User-Adapted Inter-
action, 12(4):371–417.
Barbara Grosz and Sarit Kraus. 1996. Collaborative
plans for complex group action. Artificial Intelli-
gence, 86(2):269–357.
Curry I. Guinn. 1999. An analysis of initiative
selection in collaborative task-oriented discourse.
User Modeling and User-adapted Interaction, 8(3-
4):255–314.
K. Lochbaum. 1998. A collaborative planning model
of intentional structure. Computational Linguistics,
24(4):525–572.
C. R. Perrault and J. F. Allen. 1980. A plan-based
analysis of indirect speech acts. Computational Lin-
guistics, 6(3-4):167–182.
Ronnie. W. Smith and D. Richard Hipp. 1994. Spo-
ken Natural Language Dialog Systems: A Practical
Approach. Oxford UP, New York.
Ronnie W. Smith and D. Richard Hipp. 1995. An ar-
chitecture for voice dialog systems based on prolog-
style theorem proving. Computational Linguistics,
21(3):281–320.
I. Zukerman and D. Albrecht. 2001. Predictive statis-
tical models for user modeling. User Modeling and
User-Adapted Interaction, 11(1-2):5–18.
