MATHEMATICAL ANALYSIS OF DIALOGUE CONTROLSTRATEGIES
Yasuhisa Niimi and Takuya Nishimoto

Kyoto Institute of Technology
Matsugasaki, Sakyo-ku, Kyoto, 6068585 Japanf niimi, nishi g@dj.kit.ac.jp
ABSTRACTIn this paper we describe a quantitative relation between the eciency of dialogue control strategies, wemeasure by the average number of exchanges taken
during a dialogue, and the performance of a speech
recognition system used in a spoken dialogue system.
We consider four dialogue control strategies: (1) direct con rmation, (2) indirect con rmation, (3) multiple item answer followed by direct con rmations,and (4) multiple item answer followed by multiple
item con rmations. If n information items are necessary to execute a task, a status of a dialogue is represented by a triplet (u; k; c) (u + k + c = n), whereu, k and c are the numbers of unknown, known not
yet con rmed, and con rmed items respectively. The
mathematical analyses of the strategies are based on
the fact that the state transition of a dialogue can berepresented by a Markov process in which a space ofstates are a set of triplets (u; k; c), and state transition probabilities are decided by a speech recognition
rate and user's behaviors.
1. INTRODUCTION

A number of studies on spoken dialogue systems havebeen carried out using HMM-based speech recognition systems. It is, however, still dicult to correctly
recognize casual utterances often observed in humanconversations. To remedy this diculty, several interactive methods have been reported for recoveringfrom speech recognition errors, but most of these approaches were empirical and did not involve mathematical analyses [1,2]. We have studied quantitative
relations between dialogue control strategies and theperformance of a speech recognizer under the assumption that the reliability in recognizing utterances or
keywords can be evaluated [3,4]. However, it is oftendicult to uniformly evaluate such reliability independently of the content of utterances or keywords.
In this paper we will quantify the performanceof four dialogue control strategies to relieve speech
recognition errors, which are not based on the reliability, but on the con rmation only.
We consider it possible to evaluate the performance of thedialogue control strategy by the average of numbersof those exchanges which are taken between the dialogue system and the user to collect and con rm
necessary items. Using this de nition, we will derivea mathematical relation between the performance ofa dialogue control strategy and the performance of aspeech recognizer.
The remainder of the paper is constructed as follows. Section 2 introduces a model describe dialogue
control strategies and gives a brief descriptions of thefour dialogue control strategies we will consider. Section 3 derives a mathematical expression for the performance of each strategy. Finally section 4 compares
the performances of those strategies numerically.
2. OUTLINES OF DIALOGUECONTROL STRATEGIESThis section outlines the dialogue control strategies tobe considered in this paper. First a model to describe
the dialogue control strategies, which was proposed in[1], is introduced. Suppose n information items, forexample, values of attributes necessary for a database
query, are needed to attain some task or subtask. At
the current state of the art in speech recognition, eachitem must be con rmed explicitly or implicitly. Thus
each item takes one of three states, unknown to thedialogue system, known but not yet con rmed, andcon rmed. So the state of a dialogue will be represented by a triplet (u; k; c) of three parameters, whereu, k and c are the numbers of unknown, known but
not yet con rmed and con rmed items respectively.
However, the number of independent parameters is
two because there is a constraint, u + k + c = n,among u, k and c. Thus a triplet (u; k; c) can bemapped on a grid point in the 2-dimensional space(k; c) as shown in Fig. 1(a).
In this representation the purpose of a dialogue isto transfer the state of a dialogue from state (n; 0; 0)
to state (0; 0; n). Thus dialogue control strategies canbe described by specifying how to achieve this statetransition, and their eciency can be evaluated by
the average number of exchanges of turns which thedialogue system and its user take to achieve this statetransition. State transitions are induced by actionsof the system and the user. An example of suchactions is user's response to system's con rmation
on a known item. This changes the state of a dialogue by (0; 01; +1) if user's response is 'yes', and by(+1; 01; 0) if it is 'no', while nothing changes if it isa corrective answer. Thus a dialogue control strategy and user's actions constitute a Markov process inwhich the state space is a set of triplets (u; k; c) andstate transition probabilities are decided the probability that an item be correctly recognized.
Based on this fact we will derive quantitative relations between the performance of dialogue control
strategies and the performance of a speech recognizer.
In this paper we will consider following dialogue control strategies.

 ananswer of n items,A(item1 ; item2 ; :::itemn ),

k1
2(1)

3

4

to DC (item1 ; item2 ; :::; itemn ) when all the items
to be con rmed are correct.
p1-pq(*,1(q),*)

(3)
(4)

k(b)

Figure 1: (k,c)-plane and the state transitions of thefour strategies.
(1) Strategy 1 | Direct con rmation. This strategy tries to change the state of an item from unknown
to known and then from known to con rmed, in otherwords, tries to transfer the state of a dialogue along
the path (1) shown in Fig. 1(b).
(2) Strategy 2 | Indirect con rmation. A known
item is embedded in the question of the next unknown
item. This strategy tries to transfer the state of a
dialogue along the path (2) shown in Fig. 1(b).
(3) Strategy 3 | This strategy rst requires a user
to input all the necessary items, and then makes adirect con rmation on each of these known items. It
strategy tries to transfer the state of a dialogue along
the path (3) in Fig. 1(b).
(4) Strategy 4 | This strategy rst collects all thenecessary items in an exchange, and then tries to conrm all of the known items in an exchange. In thisstrategy the transition of the state of a dialogue isintended to occur along the path (4) in Fig. 1(b).
3. ANALYSIS OF THE DIALOGUECONTROL STRATEGIES
3.1 Actions of the system and the user

In a spoken dialogue system considered in this paper,
we suppose dialogues are composed of the following
actions taken by the system and its user.
Actions taken by the system are : a question on n information items, denoted by
Q(?item1 ; ?item2 ; :::; ?itemn ), a direct con rmation on n items, denoted by
DC (item1 ; item2 ; :::; itemn ), and an indirect con rmation, that is, a question

on an unknown item newitem including a conrmation on a known item item, denoted by
IDC (item; ?newitem).

Actions taken by the user are :(*,0,*+1)

c(2)

(a)

by

 a response 'yes', denoted by Y es, which is returned(*,1(p),*)c0123400 400 301 202 103 004
01 310 211 112 013
12 220 121 022
23 130 031
34 0404denoted

1-q

Figure 2: The state transition diagram for DCsubdialogue.
3.2 Subdialogues

Here we will de ne two subdialogues using the actions
introduced in the previous section.
(1) Direct con rmation subdialogue (abbreviatedas DC subdialogue below). This can be described interms of the following C-like program.
DC subdialogue(item)fDC (item); if ( item is correct ) Y es;
elsefA(item0 ); DC subdialogue(item0 ); ggHere we assume that an item in user's responseA(item) to Q(?item) and an item in user's corrective response A(item0) to DC (item) be recognizedcorrectly with the probabilities p and q respectively.
In general p is greater than or equal to q . Under
these assumptions a state transition diagram for theDC subdialogue can be illustrated as in Fig. 2. Here
rectangles indicate the state of a dialogue, arcs correspond to an exchange of turns, a symbol 3 means a
positive integer and a string 1(p) represents a known
item in that state is correctly recognized with theprobability p.
(2) Indirect con rmation subdialogue (abbreviatedas IDC subdialogue below). This can be describedby the following C-like program.
I DC subdialogue(item; ?newitem)fI DC (item; ?newitem);if ( item is correct ) A(newitem);elsefA(item0 ; newitem); DC subdialogue(item0 ); gg
Here we assume for simplicity that an item included in A(item) and each of two items includedin A(item0 ; newitem) be correctly recognized withthe probabilities p and q respectively. When entering this subdialogue under these assumptions, theprobability that a known item to be con rmed becorrect is p. Hence the action A(newitem) will
be taken with the probability p after the action
IDC (item; ?newitem). In this situation the stateof a dialogue changes from state (3; 1(p); 3) to state(3 0 1; 1(p); 3 + 1), in other words, a known item is
implicitly con rmed and an unknown item newitem
becomes known by A(newitem), thus the probability for newitem to be correct being p. On the otherhand, A(item0; newitem) will occur with the probability 1 0 p after IDC (item; ?newitem). In this situation a known item is corrected as item0 and an unknown item becomes known, the probability for each
item to be correct being q by the assumption. Thus
the state of a dialogue changes from state (3; 1(p); 3)
to state (3 0 1; 2(qq); 3). Since A(item0 ; newitem) isfollowed by DC subdialogue(item'), the state of a dialogue nally reaches state (30 1; 1(q); 3 + 1). Thus astate transition diagram for this subdialogue can beillustrated as in Fig. 3.
p(*,1(p),*)(*-1,1(p),*+1)

1-pq(*-1,2(qq),*)(*-1,1(q),*+1)

1-qp(*-1,2(pq),*)

1-pFigure 3: The satate transition diagram for IDCsubdialogue.
3.3 Analysis of the Strategy 1

Using the notations de ned in the previous sections,
we can describe how a dialogue proceeds based on thestrategy 1, as follows.
for(k = n; k > 0; k 0 0)
fQ(?itemk ); A(itemk ); DC subdialogue(itemk ); g
Now we will derive a mathematical expression forthe performance of the strategy 1. Let N (u; k ) be
the average of numbers of exchanges taken to movefrom any state s = (u; k; c) to the state (0; 0; n) whichmeans the end of a dialogue. Referring to the statetransition diagram shown in Fig. 2, we have the following recursive equation.
N (k; 0) = N (k0 1; 0) + 2 + (1 0 p)=q

We will denote N (n; 0)
N (0; 0) = 0, we haveby N (n), Noting that

N (n) = (2 + (10 p)=q)n(1)The second term in the righthand side of this equation represents an increase of exchanges due to speech
recognition errors.
3.4 Analysis of the Strategy 2

We can describe how a dialogue proceeds based on
the strategy 2 as follows.

Q(?itemn ); A(itemn );f or(k = n; k > 1; k)
I DC subdialogue(itemk ; ?itemk01 );DC subdialogue(item1 );00

We have already shown in Fig. 3 the state transition diagram for IDC subdialogue. Noting that statetransitions from state (3; 1(q); 3) are quite same as
those from state (3; 1(p); 3), and denoting N (k; 1(p))
and N (k; 1(q )) by ak and bk respectively, we have thefollowing equations.
ak = 1 + pak01 + (1 0 p)N (k 0 1; 2(qq ))(2)
bk = 1 + qak01 + (1 0 q )N (k 0 1; 2(qq ))(3)
Using the same computation as explained in theprevious section, we can compute N (k 0 1; 2(qq )) as
bk01 + 1 + (1 0 q)=p. Moreover, we have a0 = 1=p andb0 = 1 + (1 0 q )=p as the initial conditions.
From these considerations we can derive an explicit
expression on ak as follows.
k+12(1 0 p)p
p(1 0 pk )ak =+k0(4)pp(1 0 p)
1 0 pwhere p = p 0 q , Using eq. (4) we can reach thenal result.
N (n) = an01 + 1:
In particular, since if p = q the second term of therighthand side of eq. (4) vanishes, we havehiN (n) = 1 + n=p:
3.5 Analysis of the Strategy 3

We can describe how a dialogue proceeds based on
the strategy 3 as follows.
Q(?item1 ; ?item2 ; :::; ?itemn );A(item1 ; item2 ; :::; itemn );f or(k = n; k > 0; k 0 0)DC subdialogue(itemk );Here we assume that only replacements of items occur in recognition of A(item1 ; item2 ; :::; itemn ) while
insertions and omissions do not occur, and denoteby q the probability that each item be correctly recognized. Note that this probability depends on thenumber of items. Since each of known items is conrmed one by one using a DC subdialogue, the transition from state (0; k; n0k) to state (0; k 01; n0k +1)
can be described by the diagram shown in Fig. 2.
Noting that p and q respectively correspond to q andp in Fig. 2, we have
N (n) = 1 + N (0; n(q n )) = 1 + n(1 + (10 q)=p):

3.6 Analysis of the Strategy 4

A dialogue based on the dialogue control strategy 4
can be described as follows.
Q(?item1 ; ?item2 ; :::; ?itemn );A(item1 ; item2 ; :::; itemn );DC (item1 ; item2 ; :::; itemn );A(item11 ; item12 ; :::);::::::::

DC (itemk1 ; itemk2 ; :::);Y es;

From the previous considerations we can see that

Here we will put on the same assumptions on
speech recognition errors as those made in the previous section, and denote by qm the probability thateach item be correctly recognized in recognition ofA(item1 ; :::; itemm ). Suppose the state of a dialogue
be on state (0; m; n 0 m). According to the de nition,
the probability that k out of m items be incorrect ism0k(1 0 qm )k (0  k  m). In this situation them Ck qm
user will make a response A(item01 ; item02 ; :::; item0k ),which changes the state of a dialogue from state(0; m; n 0 m) to state (0; k; n 0 k). Denoting N (0; m)by am , thus we have the following equation on am .
am = 1 +Xm

0k (1 0 qm )k akmm Ck q m

k =00
X
1+(1  m  n)

Since a0 = 0, we havem

1k =1am =mm Ck qm

0k (1 0 qm)k ak(1  m  n)

1 0 (1 0 qm )mN(5)16St1St4
St2&3

P=0.8

12

P=0.95St3

P=0.8

10St38St2

P=0.95

St26420ponential as seen from the curve(st4) shown in Fig.
4.
Finally we will investigate numerically the e ectsof the second parameter q on N (n) in the strategies
2 and 3. Fig. 4 also shows the relations of N (5) to q
in the cases that p = 0:95 and p = 0:8. These curvesindicate that the dependency of N (5) on q is small
and the strategy 2 is slightly better than the strategy
3 in the range of practical values of p and q.
5. CONCLUSION

which is followed byN (n) = N (0; n) + 1 = an + 1:

14

N (n)'s of the strategies 1, 2 and 3 are linearly dependent on n and their coecients are greater thanone. Computing numerically N (n) of the strategy
4 for p = 0:9, we have N (1) = 2:11, N (2) = 2:21,N (3) = 2:30, N (4) = 2:39 and N (5) = 2:46, whichshow its dependency on n is small. For the strategies 1,2 and 3 their dependencies on p are 1=p, while
the dependency of the strategy 4 on p looks like ex-

In this paper we have addressed the quantitative relation between the eciency of dialogue control strategies, we measure by the average number of exchanges
taken during a dialogue, and the performance of aspeech recognizer. The dialogue control strategies wehave considered allow the user to produce multiple
items in an utterance and the system to con rm them
directly or indirectly.
This study is of much importance in establishing
the theoretical foundation for the optimal choice ofdialogue control strategies given the performance ofa speech recognizer and for the dynamic adaptationof the strategy in real elds in which the performanceof a speech recognizer changes dynamically.
In this paper we have assumed only the replacement error of items occur in speech recognition forsimplicity, but this is not the case. So it is left as
future work to entend the analysis of dialogue control
strategies so as to include these recognition errors.
References

00.2

0.4

0.6

0.8

1.0
p or qFigure 4: N(5)'s of the four dialogue control strategies.
4. NUMERICAL COMPARISONSOF THE FOUR STRATEGIESIn this section we will make comparisons among thefour dialogue control strategies. Since these strategies include multiple parameters, we rst assume thatq be equal to p in the strategies 1, 2 and 3, and qi 's
be all equal to p in the strategy 4. N (n)'s, calculatedon this condition, mean the lower bound of N (n)'s,
in other words, the best performance of each strategy given the value of p. N (5) of each strategy isgraphically illustrated in Fig. 4.

[1] Cozannet, A. and Siroux, J., "Strategies for oraldialogue control," Proc. of ICSLP, pp.963-966(1994).
[2] Waterworth, J. A., \Interactive strategies for conversational computer system," in Structure ofMultimodal Dialogue, ed. by Taylor, M. M., etal., pp.331-340, North Holland (1988).
[3] Niimi, Y. and Kobayashi, Y.,"Modeling dialogue
control strategies to relieve speech recognition errors," Proc. of EUROSPEECH'95, pp.1177-1180(1995).
[4] Niimi, Y., Nishimoto, T., and Kobayashi, Y.,"Analysis of interactive strategy to recover frommisrecognition of utterances including multiple
information items," Proc. of EUROSPEECH'97,pp.2251-2254 (1997).