EFFICIENT INCREMENTAL DEPENDENCY PARSING
Yoshihide Katoy
Shigeki Matsubaraz
Katsuhiko Toyamayx
Yasuyoshi Inagakiy
Graduate School of Engineering, Nagoya University yFaculty of Language and Culture, Nagoya University z
Center for Integrated Acoustic Information Research, Nagoya University x
Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japanfyosihide,matu,toyama,inagakig@inagaki.nuie.nagoya-u.ac.jp

Abstract
This paper describes an ecient method of incremental dependency parsing based on phrase structure
grammar with the dependency relation. The reachability relation between syntactic categories is utilized
for connecting a head word with a dependent word simultaneously with the inputs. The method does
not need to construct the whole parse tree of an initial fragment on the word-by-word basis, and thus
can be expected to be usable for simultaneous spoken language processing. An experiment on the ATIS
corpus has shown the technique of utilizing the reachability to be e ective for reducing processing timeof the incremental dependency parsing.

1

Introduction

Dependency grammar has a long tradition in natural language theories. In recent years, great attention
has been paid to the concept of dependency, as the importance of relations between words is recognizedin the eld of language parsing. Dependency parsing techniques of written language has been studied sofar, on the other hand, few investigations has been done for that of spoken language. In particular, suchspoken language processing systems as real-time dialogue system, simultaneous machine interpretingsystem, etc. are being studied, and thus dependency parsing needs to be discussed from the viewpointof incrementality.
An approach based on context-free phrase structure grammars is known as one of the dependency
parsing techniques. In this approach, dependency grammar is described as a set of phrase structurerules with head-dependent relations between syntactic categories, and the dependencies are extracted
from parse trees according to Collins' structures mapping procedure [1]. This means that we can notacquire the dependency structures before getting parse tree completely. If such the technique is used
for incremental spoken language processing, it is strongly required not to damage the incrementality.
This paper describes an ecient method of incremental dependency parsing based on CFG withthe dependency relation. In order to connect a head word with a dependent word simultaneously with
the inputs, the reachability relation between syntactic categories is utilized. Our method, which isdi erent from the standard one of incremental parsing such as incremental chart parsing [4], does notnecessarily construct the whole parse tree for an initial fragment, and can be therefore expected to besuitable for incremental spoken language processing. To evaluate the performance of our method, anexperiment on the ATIS corpus has been made. The experimental result has shows the technique ofutilizing the reachability to be e ective for reducing parsing time.

S ! NP V P 3
V P ! V P 13 ADV / V P 13 P P

NP ! DET N 3 / DET ADJ N 3
V P 1 ! V 3 NP / V 3 NP NP

Figure 1: Grammar

procedure dependency
input: [[1 1 1]C1 1 1 1 [1 1 1]Ci 1 1 1 [1 1 1]Cm ]X
output: D

D := [Cj (1j m) dependency ([1 1 1]Cj )if a rule X ! C1 1 1 1 Ci3 1 1 1 Cm exists then add hh([1 1 1]Cj ); h([1 1 1]Ci )i to D (1  j  m; j 6= i)

Figure 2: Dependency extraction procedure

2

Incremental Extraction of Word Dependencies

An orthodox and typical method of incremental dependency parsing based on context free grammar
with the dependency relation could be as follows: When an input word is produced, (i) the partial
parse trees of the initial fragment are constructed by incremental CFG parsing such as incremental
chart parsing [4], (ii) the dependencies between words are extracted from the parse trees according to
the structure mapping procedure [1]. This section describes such the method shortly.
Dependency is a kind of relations between words, and represents that a word modi es anotherword. The modi ed word is called a head and the modifying word is called a dependent. We write thedependency, in which wd is dependent and wh is head, as wd ; wh . Dependencies can be extracted
from a parse tree by identifying the head-child in each rule [1]. Just one category in the right-handside of each rule is called head-child, which is annotated with a special symbol * as shown in Fig.
1. A parse tree has a head-word, which represents a main meaning of the parse tree. We denote thehead-word of a term  by h( ). Head-words propagate up through the tree, each parent receiving its
head-word from its head-child. The dependency extraction procedure is de ned in Fig. 2.
Incremental chart parsing produces the partial parse trees for initial fragments [4]. The partial parsetree is called a term, which is denoted by [ ]X where X is a category and is a word, a special symbol? or a list of terms. We denote the category of [ ]X by cat([ ]X ). The term [?]X is called undecided
term and corresponds to the part not inputed yet. The leftmost occurrence of an undecided term in aterm  is called leftmost undecided term in  , which denoted by lut( ). The incremental chart parsing
introduces two new operations to the standard bottom-up chart parsing [2]. One is the application ofrules to the term including undecided terms and the other is the replacement of the leftmost undecidedterm with the term including undecided terms. As an example, let us consider the parse of thefragment \The boy saw". The standard chart parsing produces terms: (1)[[[the]DET [boy ]N ]NP [?]V P ]S ,(2)[saw]V , (3)[[saw]V [?]NP ]V P 1 and so on. However, it produces no term for \The boy saw". On theother hand, the incremental chart parsing applies the rule V P
V P 1 ADV for (3) to produce aterm (4)[[[saw]V [?]NP ]V P 1 [?]ADV ]V P and the leftmost undecided term of (1) is replaced with (4) sothat it produces the term (5)[[[the]DET [boy ]N ]NP [[[saw]V [?]NP ]V P 1 [?]ADV ]V P ]S for \The boy saw".
Dependencies for initial fragments can be extracted from the terms produced in incremental chartparsing by applying the dependency extraction procedure. For example, the dependencies for \Theboy saw" is computed from the term (5) as shown in Fig. 3.

hi!

3

Incremental Dependency ParsingThe method described in Sect.2 can compute the dependencies for initial fragments. However, wecan not say the eciency is enough, because it may produce a lot of terms which have the samedependencies. If it is possible to extract the dependencies correctly, all the terms are not necessary to(a)S(saw)(b)

NP(boy)DET(the) N*(boy)Theboyextraction

VP*(saw)

V*(saw)

TheADV(?)

VP1*(saw)
NP(?)

wd

whboysaw

means a dependency <wd,wh>sawFigure 3: An example of computing dependencies for initial fragments
procedure dependency2
input: 1 1 1 1 moutput: D

D := dependency (m )for i := 0 to m 0 2
h 3 cat(lut(if cat(m0i )m0i01 )) then h(lut(m0i01 )) := h(m0i )D := D [ dependency(m0i01 );Figure 4: Algorithm of extracting dependencies from connected terms
produce so that the eciency is increased. We accomplish this by utilizing the reachability relation.
Before describing our proposed method, we give a de nition of reachability. Let X and Y becategories. We write X ; Y , if a rule Y
X exists for some categories sequence . Let ;3 be there exive transitive closure of ;. We say that Y is reachable from X , if X ;3 Y . The relation that
Y is reachable from X means that a parse tree whose root is Y may have the leftmost descendant X .
To compute dependencies, we classify the reachability relation.
h Y if a rule Y
De nition 1 Let X and Y be categories. We write X ;X 3 exists for somedcategories sequence . We write X ; Y if a rule Y
X Z 3 exists for some categories sequences!

!

!

Z.
2
33hdh
When Y is reachable from X , X and Y satisfy X ; Y or X ;3 ;;3 Y . X ; Y means that thed 3Y
head-word of leftmost descendant X propagates up to the ancestor Y . In contrast, X ;3 ;;means that the head-word of X does not propagate up to Y .
andand some category

For initial fragments, the proposed parsing (i) produces terms according to the standard chartparsing, (ii) connects terms by utilizing reachability and (iii) extracts dependencies from the connectedterms. The same dependencies as the one described in Sect. 2 can be obtained by the method.
The method connects a term  with another term  , if cat(lut( )) is reachable from cat( ). We
represent connected terms by a list of terms. The adjacent terms  and  in the list mean that they areconnected by reachability. Fig. 4 illustrates
the procedure of extracting dependencies from connected
3hterms. By utilizing the relation ; , the procedure propagates a head-word of a term to another term.
d 3 is satis ed, the head-word is not propagated. This enables the parsing toIf the relation ;3 ;;compute the dependencies for fragments without applying rules to terms including undecided terms.
As an example, let us consider the incremental parsing process of the fragment \The boy saw".
When \saw" is processed, the parsing produces the terms (1) and (2) according to the standard chartparsing fashion. The category of (2) is V and the one of the leftmost undecided term of (1) is V P .
h 3 V P and the head-word of (2) isSince V ;3 V P , (1) and (2) are connected. Moreover, since V ;\saw", the head-word of the leftmost undecided term of (1) becomes \saw" (see Fig. 5.). For \Theboy saw", the dependencies the; boy and boy; saw are obtained by the procedure in Fig. 4. The
dependencies are the same as the ones extracted from the term (5).

hihi

S(saw)NP(boy)VP*(saw)hDET(the) N*(boy)Theboy*V*(saw)
sawTheboysawFigure 5: An example of propagation of head-wordaverage parsing time(sec)
10001001010.1
0.01
0.001
0.00012464usual method
our method810
12sentence length(word)
Figure 6: Parsing time per sentenceExperimental Result

In order to evaluate the performance of our technique, an parsing experiment has been made. Theparsing was implemented in GNU Common Lisp on a Linux PC with Pentium III 1GHz processor
and 1GB main memory. We used the ATIS corpus of Penn Treebank [3]. The corpus contains 578
sentences with CFG parse tree tags, and 509 phrase structure rules in them are used for the test.
The parsing time has been compared between the technique explained in Sect. 2 (i.e. usual method)
and the one utilizing the reachability relation in Sect. 3 (i.e. our method). Fig. 6 shows the relation
between the sentence length and the processing time1 . The average time of our method is 0.03 sec.,
while that of the usual method is 23.49 sec. This result shows the technique of utilizing the reachability
to be e ective for reducing processing time.

5

Concluding Remarks

This paper has described an ecient method of incrementally computing the dependencies between
words. We have pointed out that the reachability relation between syntactic categories is related
to the head-dependent relation between words. We provided a simple algorithm for acquiring thelexical dependencies based on the reachability relation. An experimental result has demonstrated
that our method is e ective for reducing processing time. Therefore, the method can be expected tobe applicable to a simultaneous speech interpreting system which we are studying.
In this method, the lexical dependencies of the natural language sentence have been extracted fromthe CFG parse tree. From the point of view of only the eciency, however, the parsing with only
syntactic constraints on dependency grammar might also be available. For the comparison with suchthe technique, further experiments will be made in the future.

References[1] Collins, M. J.: A New Statistical Parser Based on Bigram Lexical Dependencies, Proc. of the34th Annual Meeting of the Assoc. for Computational Linguistics, pp.184-191 (1996).
[2] Kay, M.: Algorithm Schemata and Data Structures in Syntactic Processing, Technical Report
CSL-80-12, Xerox PARC (1980).
[3] Marcus, M. P., Santorini, B. and Marcinkiewicz, M. A. : Building a Large Annotated Corpus ofEnglish: the Penn Treebank, Computational Linguistics, Vol.19, No.2, pp.310-330 (1993).
[4] Matsubara, S., Asai, S., Toyama, K. and Inagaki, Y.: Chart-based Parsing and Transfer in
Incremental Spoken Language Translation, Proc. of NLPRS-97, pp.521-524 (1997).
1 We terminated the parsing when the processing time per word was over 60 sec. The result is for 154 sentences forwhich the usual method did not terminate the parsing.