SPOKEN LANGUAGE PARSINGBASED ON INCREMENTAL DISAMBIGUATIONyYoshihide Katoz

Shigeki Matsubara

Katsuhiko ToyamayxYasuyoshi Inagaki

Graduate School of Engineering, Nagoya University
Faculty of Language and Culture, Nagoya Universityyz

Center for Integrated Acoustic Information Research, Nagoya Universityyx

Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japanyosihide@inagaki.nuie.nagoya-u.ac.jp

ABSTRACT

Towards a real-time spoken dialogue system, several incremental parsing methods have been proposed so far. Theyconstructs syntactic structures for an initial fragment ofan input sentence. However, they have a problem that thestructures do not necessarily represent the syntactic relation correctly. The problem is caused by the ambiguityof initial fragments. This paper proposes an incremental
disambiguation method, which decides correct structuresat an stage where the entire input is not completed. The
method nds the structures which are correct independently of the remaining input. When correct structures
cannot be decided, the method delays the decision. Since
the disambiguation is executed for every word input, themethod can nd correct structures at an early stage.
1.

INTRODUCTION

It is important for a spoken dialogue system to communicate with the user smoothly. Responding to the user
immediately, the system is required to understand spoken
language at least incrementally [1, 5], that is, to analyze
input sentences from left to right and acquire the semanticcontent.
Several incremental parsing methods have been proposedso far. For example, Matsubara et al. has proposed achart-based parsing for context free grammar[3]. Milward
has proposed a parsing based on categorial grammar[6].
The methods can construct syntactic structures for initial fragments of input sentences. However, they have aproblem that the structures do not necessarily represent
the syntactic relation correctly. The problem is caused by
the ambiguity of initial fragments. It cannot be ignored,
because a dialogue system may misunderstand the user'sutterance if the system interprets the utterance depending on an incorrect structure. Therefore, the system isrequired to make the correctness of structures clear.
This paper proposes an incremental disambiguation
method, which decides correct structures at an stage where
the entire input is not completed. The method nds thestructures which are correct independently of the remaining input. Since the initial fragment does not have theinformation enough to resolve the ambiguity, the method
utilizes a part of the input which follows the fragment.
When correct structures cannot be decided, the method
delays the decision. The disambiguation is executed byutilizing the following two information: undecided partsin syntactic structures and subsumption relation between
structures. Since the disambiguation is executed for everyinput: w1 w2 1 1 1 wn
output: chart
chart := f(0; 0; [?]s )g;for i = 1 to n begin
1)consulting dictionary:
if the category of wi is x
then add (i 0 1; i; [wi ]x ) to chart2)applying grammar rule:for each (i 0 1; i; [1 1 1]x1 ) 2 chart andeach grammar rule a ! x2 y 1 1 1 z
if x1 = x2
then add (i 0 1; i; [[1 1 1]x1 [?]y 1 1 1 [?]z ]a ) to chart3)replacing term:
for each (0; i 0 1;  ); (i 0 1; i; [1 1 1]x ) 2 chart
if the category of lut( ) is x
then add (0; i; rep(; [1 1 1]x )) to chart
end
Figure 1: Algorithm of incremental chart parsing

word input, the method can nd correct structures for an
initial fragment at an early stage.
This paper is organized as follows: The next section explains incremental chart parsing shortly. Section 3 discusses the ambiguity in incremental chart parsing. Section
4 describes the incremental disambiguation method.
2.

INCREMENTAL CHARTPARSING

2.1.

Chart

Incremental chart parsing records parsing results in agraph called a chart [2]. The edge is labeled a syntactic
structure called a term, which is denoted by [ ]x , where x
is a category and is a word, a special symbol `?' or a listof terms. The term [?]x is called an undecided term andrepresents that the part has not been inputed yet. The
leftmost occurrence of an undecided term in a term  iscalled a leftmost undecided term in , which is denotedby lut(). If an edge is labeled a term which includes anundecided term, it is called active, otherwise inactive.

s ! np vp $np ! pronnp ! det n
np1 ! det n pp
pp ! p np
vp ! vi
vp ! vt np pp
vp ! vt np1

pron ! I / her
det ! the / hern! aunt / telescope
p! withvi ! saw
vt ! saw
$!.

I
#1

saw
#2

her

#4

Figure 1 shows the incremental parsing algorithm[3]. Here,an edge with a label  between nodes j and k is denotedby (j; k;  ). The result of replacing the leftmost undecided
term in  with  is denoted by rep(;  ). The incrementalchart parsing introduces two new operations to the standard bottom-up chart parsing[2]. One is the applicationof grammar rules to an active edge and the other is the replacement of the leftmost undecided term with the term ofan active edge. The operations enable the parsing to necessarily construct syntactic structures of initial fragments
of input sentences.
As an example, let us consider parsing the following sentence using context free grammar shown in Figure 2:(1)

Table 1 shows the process of chart construction for thesentence (1).
When \saw" is inputed, by consulting a dictionary andapplying grammar rules, the following terms for \saw" areconstructed:[[saw]vi ]vp(2)[[saw]vt [?]np [?]pp ]vp(3)[[saw]vt [?]np1 ]vp(4)
The parsing replaces the leftmost undecided term in #2
with the terms (2), (3) and (4) respectively, so that it constructs terms #3, #4 and #5 for the initial fragment \Isaw". These terms, at least, represent the relation thata pronoun \I" is the subject of the verb \saw". This example shows that the incremental chart parsing is capableof constructing terms of initial fragments for every word
input.
3.

thetelescope .

#6
#7

#9

#11

#13

#15

#17

#8

#10

#12

#14

#16

#18

#5

Parsing Algorithm

I saw her aunt with the telescope.

with

#3

Figure 2: Grammar
2.2.

auntAMBIGUITY IN

INCREMENTAL PARSING

Before describing the ambiguity of initial fragments, wegive some de nitions about terms.

De nition 1 (subsumption relation) Let  and  beterms. Then we write  >  , if rep(; ) =  , for someterm .
Let >3 be the re exive transitive closure of >. We saythat  subsumes  , if  >3  .
2That  subsumes  means that  is constructed by application of replacement operation to  . Figure 3 shows thesubsumption relation between the terms constructed forthe sentence (1).

Figure 3: subsumption relation between terms
I
#1

saw
#2

heraunt

withthetelescope .

#3
#4

#6
#7

#9

#11

#13

#15

#17

#8

#10

#12

#14

#16

#18

#5

correct term

Figure 4: correct terms
If a term for an initial fragment represents syntactic relation correctly, the term subsumes some nal completeterms. We call such a term correct. The correctness of aterm is de ned as follows:

De nition 2 (correct term) Let  be a term andw1 1 1 1 wn be an input sentence. We say that  is correct for
w1 1 1 1 wn if some term  satis es the following conditions:1.  is a term for w1 1 1 1 wn .
2.  does not include undecided terms.
3.  >3  ．

2For example, the term #4 is correct for the sentence (1),because the term #17 for the sentence (1) does not includes undecided terms and #4 >3 #17. On the otherhand, the term #3 is not correct for (1). Figure 4 shows
the correct terms for the sentence (1).
The previous section has illustrated the construction ofterms for initial fragment in incremental chart parsing.
Here, note that the constructed terms are not necessarilycorrect. It is caused by the syntactic ambiguity of initialfragments.
As an example, let us consider the fragment \I saw her".
A word \her" is syntactically ambiguous in the sense thatit has two part-of-speeches. The incremental chart parsing
constructs the terms #6 #7 and #8 for the fragment \Isaw her". #6 is the term in which \her" is \pron" and#7 and #8 are the ones in which \her" is \det". The
ambiguity of the fragment \I saw her" produces the incorrect term. For instance, the term #6 is not correct,
when the entire input sentence is \I saw her aunt with thetelescope.".

Table 1: Incremental parsing process of \I saw her aunt with the telescope ."wordIsaw
heraunt
withthetelescope.
4.

#12345678
910111213141516
1718

loc
0-0
0-1
0-2
0-2
0-2
0-3
0-3
0-3
0-4
0-4
0-5
0-5
0-6
0-6
0-7
0-7
0-8
0-8

chart
term
[?]s
[[[I ]pron ]np [?]vp [?]$ ]s[[[I ]pron ]np [[saw]vi ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [?]np [?]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [?]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]pron ]np [?]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [?]n ]np [?]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [?]n [?]pp ]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n ]np [?]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n [?]pp ]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n ]np [[with]p [?]np ]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n [[with]p [?]np ]pp ]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n ]np [[with]p [[the]det [?]n ]np ]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n [[with]p [[the]det [?]n ]np ]pp ]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n ]np [[with]p [[the]det [telescope]n ]np ]pp ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n [[with]p [[the]det [telescope]n ]np ]pp ]np1 ]vp [?]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n ]np [[with]p [[the]det [telescope]n ]np ]pp ]vp [:]$ ]s[[[I ]pron ]np [[saw]vt [[her]det [aunt]n [[with]p [[the]det [telescope]n ]np ]pp ]np1 ]vp [:]$ ]s

INCREMENTALDISAMBIGUATION

Our purpose is to develop a disambiguation framework to
make the correctness of terms clear at an early stage.
In general, it is impossible to know whether a term for afragment is correct or not, from only the fragment. Because the correctness of the terms depends on the entire
input sentence. For example, in the case where the entire
input sentence is \I saw her.", #6 is correct and #7 and#8 are not correct. On the other hand, if the entire input
sentence is \I saw her aunt with the telescope.", #6 is notcorrect but #7 and #8 are correct.
By utilizing a part of the input which follows the fragment,
it becomes possible to decide correct terms. For example,
it turns out that a word \her" in the fragment \I saw her"is \det", if the next word is \aunt". It means that theterm #6 is not correct.
Our method delays the decision to utilize a part of theinput which follows an initial fragment, if necessary. Only
if a term is correct independently of the remaining input,
the method decides the term to be correct.
4.1.

The Algorithm

Our method utilizes the terms constructed in incremental parsing. The terms have the syntactic information of
the fragment which has been already inputed. They canbe obtained for every word input. Therefore, the disambiguation is easy to be executed at an early stage. For
every word input, our method decides whether the terms
constructed before the input is correct, if possible.
The method utilizes an undecided part of a term and subsumption relation between terms. First, we describe an
undecided part of a term.

De nition 3 (undecided part of term)
Let 1 ; : : : ; m be undecided terms which occur in a term
 in this order. Furthermore, let Xi be the category of i .

Table 2: undecided part of terms
wordIsaw
heraunt
withthetelescope.

term
#1
#2
#3
#4
#5
#6
#7, #8#9, #10#11, #12#13, #14#15, #16#17, #18

upt

svp $
$

np pp $
np1 $pp $n pp $
pp $
np $
n$
$

We call the sequence X1 1 1 1 Xm an undecided part of  anddenote it by upt( ).
2Let w1 1 1 1 wn be an input sentence and  be a term for
an initial fragment w1 1 1 1 wi (i  n). upt() = X1 1 1 1 Xmmeans that  becomes correct in the case where wi+1 1 1 1 wn
3satis es X1 1 1 1 Xm ) wi+1 1 1 1 wn . 1 For example,
3upt(#4) =\np pp $" and \np pp $")\her aunt with thetelescope.". Therefore, #4 is correct for the sentence (1).
Table 2 shows the undecided part of the terms constructed
for the sentence (1).
Furthermore, let 0 be a term for the initial fragment
0w1 1 1 1 w
i . When upt( ) = upt( ), the correctness of and 0 is identical. Becauseboth and 0 are correct
3if and only if upt( ) ) wi+1 1 1 1 wn . For example, sinceupt(#7) = upt(#8) =\n pp $", the correctnessof #7 and
#8 is identical. When upt( ) = upt(0 ), we write    0 .
Now, we describe the disambiguation method proposed in)3

1 The de nition ofis as follows: Let and be sequencesof categories and words. Furthermore, let A be a category. If a3grammar rule A
exists, then we write A.
isthe re exive and transitive closure of .

!

)))

w1

...

...

wj

wiTi...

Iwn1στpττq#8...

rFigure 6: Finding correct term #4

Table 3: correct terms

This example shows that the proposed method can ndcorrect terms at an early stage.

...

Figure 5: Decision of correct term

However, it turns out that the term #4 is correct. Because#4 satis es the condition in Theorem 4, as shown in Figure
6. When \aunt" is inputed, the terms #9 and #10 areconstructed. #9  #10 and #9 >3 #9. Therefore, theterm #9 is correct. In the same way, the term #10 iscorrect.

*ττstwordIsaw
heraunt
withthetelescope.

correct term
#1
#2
#4
#5, #7, #8, #9, #10#11, #12#13, #14#15, #16#17, #18

this paper.

Theorem 4 Let w1 1 1 1 wn be an input sentence and  bea term for an initial fragment w1 1 1 1 wj (j  n). Furthermore, let Ti be a set of terms for an initial fragment
w1 1 1 1 wi (j  i  n).  is correct for w1 1 1 1 wn if  satis es
the following condition for all  2 Ti :

 Thereexists a term  0 2 Ti such that  >3  0 and0  .
2When  satis es the condition as shown in Figure 5,  iscorrect for w1 1 1 1 wn . The proof is as follows: Some term
c 2 Ti is correct for wi+1 1 1 1 wn (otherwise wi+1 1 1 1 wn is
not accepted by the grammar). When  satis es the condition, there exists some term  0 2 Ti such that  >3  0and  0  c . Since c is correct and  0  c ,  0 is correct.
Therefore,  is also correct, because  >3  0 .
Furthermore, it should be noted that the correctness of is independent of wi+1 1 1 1 wn . It means that correct terms
can be decided when the word wi is inputed.
4.2.

#6
#7

...

...

*

her#4

τ
*

saw

An Example

This section gives an example of the disambiguation. Table
3 shows the correct terms, which are found by the proposed
method, for the sentence (1).
When \saw" is inputed, the terms #3, #4 and #5 areconstructed for the initial fragment \I saw". It cannot
be decided whether the terms are correct or not. When\her" is inputed, the parsing constructs terms #6, #7 and#8. upt(#6) =\pp $" and upt(#7) = upt(#8) =\n pp $".
The correctness of the terms #6, #7 and #8 is not clear.

5.

CONCLUSION

This paper has proposed a method of deciding correct
syntactic structures, which are constructed in incremental parsing. The method can decide correct structures at
an early stage. We can expect that the disambiguation
method enables a dialogue system to interpret the user'sutterance correctly at an early stage.
We intend to apply the method proposed in this paper toincremental spoken language translation [4].

Acknowledgment: This work is partially supported by
Grant-in-Aid for COE Research of the Ministry of Education, Science, Sports and Culture Japan and by The
Telecommunications Advancement Foundation.
6.

REFERENCES

1. Inagaki, Y. and Matsubara, S.: Models for Incremental Interpretation of Natural Language, Proc. of 2nd
Symposium on Natural Language Processing, pp.51-60(1995).
2. Kay, M : Algorithm Schemata and Data Structures
in Syntactic Processing, Technical Report CSL-80-12,
Xerox PARC (1980).
3. Matsubara, S., Asai, S., Toyama, K. and Inagaki, Y.:
Chart-based Parsing and Transfer in Incremental Spoken Language Translation, Proc. of 4th Natural Language Processing Paci c Rim Symposium, pp.521-524(1997).
4. Matsubara, S. and Inagaki, Y.: Incremental Transfer in English-Japanese Machine Translation, IEICE Trans. on Inf. & Sys, E80-D(11), pp.1122-1129(1997).
5. Milward, D. and Cooper, R.: Incremental Interpretation : Applications, Theory, and Relationship toDynamic Semantics, Proc. of 15th Int. Conf. on Computational Linguistics, pp.748-754 (1994).
6. Milward, D.: Incremental Interpretation of Categorial
Grammar, Proc. of 7th Conf. of European Chapter ofthe Assoc. for Computational Linguistics, pp.119-126(1995).