Blackboard-based Dependency Parsing

BLACKBOARD-BASED DEPENDENCY PARSING

Valkonen, K., Jippinen, H. and Lehtola, A. KIELIKONE·project, SITRA Foundation P.O.Box 329, SF-00121 Helsinki Finland

ABSTRACT

This paper presents a blackboard-based computational model for parsing an inflectional free word order language, like Finnish. The structure of sentences is described as partial dependency trees of depth one. Parsing becomes a nondeter111infstfc search problem in the forest of partial parse trees. The search process Is able to solve ambiguities and long-distance dependencies as well. Parsing is controlled by a blackboard system. A working parser for Finnish has been implemented based on the model.

INTRODUCTION

In our first approach, the parsing process is described as a sequence of local decisions (Nelimarkka et al. 1984). A pair of adjacent structures of an input sentence Is connected if valid binary dependency relation exists between them. In that ff rat version of the parser dependency structures were 1110delled procedurally with finite two·way automata (Lehtola et al. 1985). Recently, we have developed a constraint-system for·alism for dependency parsing (Jiippinen et al. 1986). lie also have augmented the model to cover long·distance dependencies. According to the augmented model blackboard-based dependency parser AOP (Augmented Dependency Parser) has been implemented (Valkonen et al . 1987). In this paper we focus on the blackboard· based computet i onal method.

In our model binary dependency relations specify constraints on argument atructuresa In functional schemata the structure of sentences fa described as local dependent environments of regents. The goal is to find a matching local environment description for each word of an Input sentence. As a side effect of the recognition corresponding partial dependency trees are built. The partial dependency trees are linked into a parse tree coverIng the whole sentence (FIgure 1).

BLACKBOARD MODEL FOR DEPENDENCY PARSING

Blackboard is a popular problem-solving model for expert systems (Ni I 1986). lie have adopted that concept and ut il1Zed it for parsing purposes. Our blackboard model application is rather simple (Figure 2) .

There are three main components: a blackboard, a scheduler and knowledge sources. The blackboard contains the active environment description for regents . According to the structural knowledge in that environment descr i ption corresponding partial parse trees are built in the blackboard. Also other changes in the state of computation are marked in the blackboard.

Functional ach..ata and binary dependency relations are independent and separate knowledge sources; no communication happens between them. All data flow takes place through the blackboard. The module of knowledge to be appl led determined dynamically, one step at a time, resulting in Incremental generation of partial solutions. is the

Binary relations are boolean expressions of the morphological and syntactic restrictions defining all the permitted dependency relations between two words in a sentence. In functional schemata grammar writer has described local environments for regents using dependency relations. Only one of the schemata at a time is chosen as an active environment description for the current regent. The activated schema Ia matched with the environment of the regent by binary relation tests. Simultaneously a partial dependency tree Ia buf lt by corresponding dependency function ~~olications. llhen a schema has been fully matched and the -, n i ve regent bound to Its dependents through functIon lInks, :'-e local partial dependency parse tree is complete.

~ scheduler for knowledge sources controls the whole system. lt monitors the changes on the blackboard and decidr; what act ions to take next. The scheduler employs a finite two·way automaton for recognition of the dependents .

2 . 1 The control strategy for dependency parsina

For the formal definition of the parsing process we describe the input sentence as a sequence (c(1),c(2), ··· ,c(i·1), c(i), c(i+1), .·. ,c(n)) of word constituents. With each constituent c(i) set (s(i,1), .·· ,s(i,m)) of functional schemata is associ a ted. The general parsing strategy for each word constituent c(i) can be modelled using a transition network. During parsing there are five possible computational states for each constituent c(i):

• 51 The initial state. One of the schemata associated with c(i) is activated .
• S2 Left dependents are searched for c( i).
• 53 c(i) is waiting for the building of the right context.
• 54 Right dependents are searched for c(i).
• 55 The final state. The schema associated with c(i) has been fully matched and becomes inactive. c(i) is the head of the completed (partial) dependency tree.

At any time, only one schema is active, constituent c(i) may be in state 52 or 54. constituent (one in state 55) is allowed to i.e . only one Only a completed be bound as dependent for a regent. There may be a number of constituents simultaneously in state S3. We call these pending constituents (implemented as a stack PENDING).

Binding is stated as mapping f(c(i),c(j)) c( I) · stands for the regent c( i) after dependent c( j). FunctIon f Is defIned by binary relation. ·> c(i)' where It has bound the the correspond! ng

The parsing process starts with c(1) and proceeds to the right. Initially all constituents c(1), .· ,c(n) are in the state S1. A sentence is well formed if in the end of the parsing process the result is · . single constituent that has reached the state S5 and contains all the other constituents bound in its dependency tree. For each constituent c(i) the parsing process can be described by the following five steps. Parsing begins from step 1 with i,k · 1.

1> A schema candidate s(i,k) associated with c(i) is activated, I .e. the constituent c(i) takes the role of a regent. Following the environment description in s(i,k), dependents for c(i) are searched from its immediate neighbourhood. Go to step 2 with j = 1-1.

2) The search of left dependents. There are two subcases:

2a) There are no left neighbours (j · 0), none is expected for c(i), or c(j) (j < i) exists and is in state S3. Go to step 3 with j = j+1.

2b) c(j) (j < i) exists and is in state 55. Binary relation tests are done. In case of a success the mapping f(c(i), c(j)) ·> c(i)' takes place. Repeat step 2 with j · j - 1 and c ( I ) · c ( I ) · ·

1. Building the right context of the regent. subcases: There are two

3a) There are no right neighbours (j expected for c(i). Go to step 5. n) or none is

3b) c(j) (j > i) exists. Go to step 1 with c(i) · c(i+1) and PENDING · push (C(i), PENDING).

1. The search of right dependents. Binary relation tests are done. In case of success the mapping f(c(i), c(j)) ·> c(i)' takes place. Repeat step 3 with j · )+1 and c(i) · c(i) 1 ·

5) The final state. There are two subcases:

Sa) The environment description has been matched. If no unbound c(j) 's (j i or . j > i) remain the sentence is parsed. If c(i+1) exists go to the step 1 with i i+1. If c(i+1) doesn't exist or the steps following the previous case returned a failure, go to step 4 with c(i) · pop (PENDING)·.

5b) The environment description has not been matched. tf onother schema for c(l) exists (k < 10), go to step 1 with I.= k+1. Otherwise return a failure.

2.2 The i111ple11entatlon of the control strategy

The control system has two levels: the basic level eMploys a general two- way automaton and the upper level uses a blackboard system. There Is a clear correspondence between the grannar description and the control system: the two-way automaton makes local decisions according to the binary relations. These local decisions are controlled by the blackboard syste11 which utilizes the environment descriptions written In the schemata.

To account for ambl gul tIes there are three kinds of backtracking points In the control syste111. Backtracking 11ay be done In regard to the choice of dependency functions, hoMographic word forms, or uaoclated schemata ( only the last case was expressed in section 2.1 ). Backtracking Ia chronological.

The solution of long-distance dependencies takes place In two phases. First an element which may have moved from the dolllllln of Ita original regent to the do11ain of another one Is recognized (by special CAPTURE functions). Such elements are assigned to · special list of distant elements. Then, In the binding phase, the original regent binds a distant element from the list. For more details, see Valkonen et al. (1987).

The strategy of local decisions controlled by global knowledge of the Input sentence yields a strongly data-driven, left-to-right and bottom-up parae whereby partial dependency trees ore built proceeding from 11fddle to out.

PARSING EXAMPLE

To visualize our discussion, a full trace of parsing the sentence ·llii eksy metsiissli" (Don't get lost In · forest) appears in Figure 4. Parsing starts from the \eft (an arrow). Next line indicates the selected schema and dependents that are tested. The first word ·llii" Is identified as a negative imperative verb with no dependents (schema DUIIIIII)'VP ok). The imperative verb ·eksy· (to get lost) Is then tried by the schema N·lmperlntrVP. The binary relation Negation holds between the two verbs, and the corresponding dependency function adjoins them. The other functions fail. Dependents are searched next fro11 the right context. The control proceeds to the word ·metsiisaii" (forest). For that word no dependents are found and the system returns to the unfinished regent "eksy". The schema N·lmperlntrVP has only two relations re01ainlng: Subject and Adverbial. The word ·metsissii" is bound as an adverb! al. The schema hos been fully matched and the Input sentence Is completely parsed.

> Alj eksy metsAssO

·> (ili) (eksy) (metsissi) Schema: DummyVP () DummyVP ok (ali) ·> (eksy) (metsissi) Schema: N-ImperintrVP (Negation Subject Adverbial) Negation ok Subject failed Adverbial failed ((ali) eksy) · > (metsissi) Schema: TrivialSP (DefPart R) DefPart failed TrivialSP ok returning to unfinished constituent .·· ((ili) eksy) <· (metsissi) Schema: N-ImperintrVP (Subject Adverbial) Subject failed Adverbial ok N-ImperintrVP ok

·> ( (ili) eksy (metsissi)) PARSED

The parse took 0.87 seconds CPU-time on VAX-11/751.

Figure 4. An example of parsing.

COMPARISON

The notion of unification has recently e11erged os a common descriptive device in 11any linguistic theories like FUG, PATR-11 and HPSG (Kay 1985, Shleber 1986). Another popular approach has been to apply attribute grannars originally developed as a theory for formal languages (Knuth 1968). LFG and DCG can be viewed as attribute grannar systems. The trend has been towards strictly declarative descriptions of syntactic structure. Syntactic rules are often expressed in

the form of complex feature seta.

Our ADP system also uses features, but there fa neither unlflcetlon nor correspondence to attribute gra11111ars. Where FUG and the others use unification, there ADP uses a pattern matching via binary relation teats for local decisions. After binding the regent solely represents the constituents hanging below ( however, in some cases certain features must be raised). Functional schemata are Independent, local dependency environment descriptions of regents. Through blackboard approach we have gained a 110re flexible control: the blackboard system can conveniently take Into account

global knowledge of the sentence.

CONCLUS I OMS

According to declarative word envtrorwent descriptions tn schemata partial solutions are built In the blackboard. Local dechtona controlled by global knowledge of the Input sentence hu made It possible to find solutions for problems that are difficult to solve in traditional parsing syatems. ADP finds a II sol ut tons for an e01bl guous sentence. An augmented search process covers long-distance dependencies as well.

ADP has been implemented tn Franzlflp. Expertmenu with non·trtvlal set of Finnish sentence structures has been performed on a VAX 11/751 system. An average time for parsing six word sentence Ia leas than 2.0 seconds for the first parae. At the moment the gra11111ar description covers com.on sentence structures qut te well. There are 66 bt nary relations, 188 functional schemata and 1800 lexicon entries. The lexicon of the morphological analyzer (J.tlpptnen and

Yl t le·t 1986) contains 35 000 word entries.

We argue that our blackboard-based computational model also gtves good b .. fa for parallel parsing. There should be en own processor for each word of the Input sentence. The partial dependency trees would be built parallel and sent to the ··In process that links them into · parse tree covering the whole sentence.

ACKNOWLEDGEMENTS

Thts research has been supported by SITRA Foundation. We also would I tke to thank Matti Ylllannl, who has suggested many lmproveoaents to our parsing model.