Grammatical Relations as the Basis for Natural Language Parsing and Text Understanding

ABSTRACT

The KING KONG parser described by this pa­ per attempts to apply the principles of rela­ tional grammar to the parsing of English in ord­ er to overcome the problems encount~red by syn­ tactic and semantic parsers. Specif~cally, this Earser uses relational categories such as sub­ Ject~ direct 9bject, and instrume~t to map _ sy~­ tact~c const~tuents onto semant~c roles w~th~n CD-like structures. Thus, the parser makes use of both syntactic and semant~c information to guide its parse.

I BACKGROUND

A. Syntactic Parsing

During the 1970's, Woods, and Bresnan and Kaplan among others developed syntax driven parsers based on various kinds of ATNs, whose theoretical base derived more or less from transformational grammar and its offshoots. A more recent approach to syntax driven parsing is represented by the Marcus parserJ which, unlike ATN's, does no backtracking and ouilds permanent structure. One of the principal difficulties with the type of parser represented by Woods's work and Marcus's work, and also to a lesser ex­ tent of Bresnan's and Kaplan's, is illustrated by the problems associated with garden path sen­ tences. which require extended backtracking, or, in the case of tlie Marcus parser, more look­ ahead than his theory permits.

Prepositional phrase attachment represents another problem for syntactic parsers. since this phenomenon is primarily semantic and as such does not lend itself to syntactic solu­ tions. More abstractly one can say that syn­ tactic parsers generaily have trouble deal~ng with sentences w~th multiple interpretationsl where the ambiguity involves the placement ot constituents. Marcus uses a related problem, that of locating the source of a moved WH­ phra~e, ~o argue . tha~ semantic as well as syn­ tact~c ~nformat~on ~s necessary for an accurate syntactic parse and appeals to the procedure in (Woods 1973) of Selective Modifier Placement, although he does not formally incorporate it.

One syntactic parser, the CHART parser developed by Kay for the MIND system, dealt ex­ tensively with this type of problem. The solu­ tion chosen was to keep several possibilities open at once by building constituents and 1 in effectJ treat~ng them as building blocks which could oe put together in a variety of ways. The final parse would be the result not only of the identif~cation and analysis of the constituents but also of the choice of how to put them to­ gether. The CHART parser relied on some seman­ tic knowledge to make this choice and was in a way a hybrid o; syntactic and semantic ap­ proaches to pars~ng.

*This research was sponsored by Rome Air Eorce Development Center under Contract Fl962884-C-001, prO]eCt #6070.

GRAMMATICAL RELATIONS AS THE BASIS FOR NATURAL LANGUAGE PARSING AND TEXT UNDERSTANDING*

Samual Bayer, Leonard Joseph. Candace Kalish

A045 Mitre Corporation Bedford. MA 01730

B- Semantic Parsing

Another approach to ambiguity is offered by members of the semantic school of parsing. among them the developers of CDs: Schank. Abelson, and their students. The developers of such parsers recognized multiple senses of of a word from the start. Attachment problems were resolved either by refer~nce to larger.meaning str~ctures such as a scr~ots or bv lex~cal expectat~ons.

The ability to handle ambiguity is the great advantage of semantic parsers, but this ability comes at a high price. Such a parser has great difficulty capturing generalizations between transformationally related sentences, and it also has to work barder in dealing with problems that are better analyzed in terms of constituent structure, such as gapping. Furth­ ermore, there is no graceful way to retarge~ a word-based parser to another language, s~nce such parsers ignore cross-linguistic generaliza­ tions. Finally, error handl~ng is often easier in a syntactic parser both because knowledge of constituent structure can often aid in correc­ tion and because syntactically based error mes­ sages are far more intelligible to the user.

II THE NEED FOR RELATIONAL GRAMMAR

The parser being devel9ped at M~TRE differs from most pa·rsers in that ~t recogn~zes not two but three levels of representation: the level of structure, the level of meaqing. and the lev­ el of grammatical relations (suoject, object, indirect object)t which mediates between the first two for the purpose of identification of semantic roles. This notion is based mainly on work in (Bayer 1984), although a similar ap­ proach in a differ~nt framework bas been sug­ gested in (Wasow 1978J. The premise of this ap­ proach is that there is no Straightforward map­ ping between structural information (which, ~n typ~cal CD approaches 1 s~~s to amount to ~o more than appeals to pos~t~on) and semant~c roles. Thu is clear even in English 1 a language whose structure is quite r~gid and yields more clues than most languages about the mapping between structure and semantic roles.

An approach in terms of grammatical rela­ tions may be justified by i) simplification of ~ynta~t;c g~neralizations, ii) simplifi~~~ion of ~aent~f~cat~on of semant~c roles, and ~~~J gen­ erality with respect to complex sentences.

A. Simplification of Syntactic Generalization

In English, .as in other languages, various syntactic facts are best expressed in terms of grammatical relations. The facts of verb agree­ ment, for example 1 are most elegantly captured through appeals to the categories subject, ob­ ject, and ~~dire~t object (~n English as well ~s languages w~th r~cher case mark~ng). Semant~c subcategorization facts, such as tlie requirement that the verb ''walk" be predicated of an animate being, are also most easily expressed in terms of grammatical relations. S~nce final grammatical relations are deduced from surface structure almost solely by ~ositional and morphological information~ one m1ght claim that a statemen~ of the facts or verb ag;eement an4 subca~egor1za­ tion in terms of tn1s sort of 1nformat1on would be adequate. While it is true that this sort of description can be made its aw~wardness c~lls its intuitiveness and usefulness 1nto quest1on. The term "subject" in English is isomorphic with the phrase "tne NP directly precedins the verb in an uninverted clause, or the NP d1rectly fol­ lowing the initial verb in an inverted clause", but the fact that this disjunction must be em­ p,loyed in all those references where the word 'subject" would be n~tur~lly l!sed s~J&gestf! that an im~ortant general1zat1on 1s b~1ng ~1ssedJ even 1n a language where structure 1s str1ct an fairly unambiguous; in a lansuage ~ere. case­ marking and word-order comb1ne to 1dent1fy the subject, the description of th~ above phenomena in structural and morpholog1cal terms becomes much harder.

B. Simplification of Identification of Seman­ t1c Roles

Analosously, the explicit identification of subject a1ds in the identification of semantic roles. Generalizations or defaults. such as the ma~ping into the ACTOR slot, can be greatly sim­ pl1fied by referring to the notion of subject rather than to the positions the NP in question may occupy. The mapping properties of classes of exceptwns can also be descr ibed eas ily, when the sroup of np's conveni~ntly labeled "subject" map 1nto the OBJECT slot 1nstead, for example.

C. Generality with Respect to Complex Sen-~

We referred earlier to the notion of final grammatical relations. This phrase hints at the 1dea that grammatical relations may CHANGE. This is why, in the passive sentence "John was struck by Mary", the su;face sub j ect is . mapped into the same semant1c slot tnat rece1ves the direct object of an active sentence such as "Mary struck Jo~n". The _operatic;m of Passiye makes a direct obJect a subJ~C~ 1 w1th. conc~m1tant displacement of the or1g1nal subJect (1nto the "by"-phras~ in Englif!h 1 for ex{llllple). In order to 1dent1fy the or1g1nal relat1ons, we ap~ ply the operation BACKWARD in order to "un4o' the appl1cation of Passiye. Although Engl1~h has relatively few rules wh1ch change grammat1cal relations, these few rules interact to derive complicated multi-clause sentences which positional approaches . are hard-pressed to analyze elegantly or eas1ly.

Consider two more of these relation­ changing rules: .subject-to-Subjec~ Rais;ng, which makes the subJect of a clause 1n subJect position the subject of the dominating clause, relating "That John will so is like~y" and. "~ohn is likely to go", al!d SubJect-to-ObJeC~ Ra1~1ng, which makes the sub J ect of a clause 1n duect object position tne direct object of the dom­ inating clause 1 relating "I beheve that John left" and "I oelieve John to have left". These two rules, combined with the rule of Passive above, may cooperate in their application to yield quite complex sentences. For example,

John is believed by Mary to be likely to have left.

is derived by Subject-to-Subject Raising_in the most embedded clause, followed by SubJec~-to­ Object Raising in the next clause up, and f1nal­ ly Passive in the matrix clause. While a rela­ t1onal approach can, having identified and ex­ tracted those NPs which bear the relevant g;am­ matical relations, simply change the grammat1cal relations of the NPs involved when they undo these operations, a positional/structural approach must physically move the NPs or try to develop a set of com~l1cated conditions which alter the slot-mapp1ngs for a verb. These ap­ proaches are unwieldy alternatives to the rela­ tional approach; the intuitive appeal of gram­ matical relations is demonstrated even in the names of the raising Operations just described, names which were coined not by relational gram­ marians but by the classical transformat1onal grammarians of the '50's and '60's, notably Noam Chomsky 1 for whom grammatical relations were (and st1ll are) derivative.

III Implementation of the KING KONG Parser

The current implementation of the KING KONG parser contains a Marcus-type syntactic parser coupled with mechanisms for manipuiating gram­ mat1cal relations and semantic roles. It also relies on a semantic representation scheme in which CD type structures are embedded in a se­ mantic net. As the parse progresses, the gram­ matical relations of the terms in the sentence are identified, and the changes in grammatical relations are undone. Once the in1tial rela­ tions have been reached 1 the function FILL-CD takes the relational network, along with a set of slot-mappings (which are produced by modify­ ing a set of global defaults, such as SUBJ -> ACTOR DOBJ -> OBJECT, with whatever verb­ specific mappings are appropriate) and maps in the values for the CD,

(defkong fly (make-word newform 'fly semantics (make-kernel , part-of-speech v cd fly-family) features (copilist *VERB-DEFAULT*) gr<->slots 't ~subject actor command)) intrans-subject obj)) trans-subject instr instrumentality)) ((trans-subject obj neither) (dobj instr instrumentality))) slot-completions '((qbj instr . ) 1nstrumentahty (instr actor control)) ) )

The dictionary entries for KING KONG, although based on CD-like kernels, look quite different from standard CD's. Figure 1 contains an example of a typical verb entry~ for the word "fly", The "part-of-speech" slot ror the verb conta1ns subcategorization information, and the "features" slot specifies syntactic and morpho­ logical properties. The two fields "gr<->slots" and "slot'-completions" contain crucial informa­ tion which ties the semantic properties of "fly" to its syntactic properties. The former maps from relationa1 categories to semantic slots; the latter fills empty semantic slots based on already filled slots. Each can rely on the functional/ semantic notions of "command" and "instrumentality" to guide the slot-~ illil).g. An actor must be able to command an act1on 1n the sense that he must be able to cause the action to occur; an instrument must be a tool useable by the commander to accomplish the action; an object is the entity primarily affected by the action. An example may clarify this.

The various senses of "fly" are illustrated in Table 1; we consider the semantic roles of these sentences to be as in Table 2.

1. The businessmau flew the plane to Cairo. - The businessmau was a passenger.
2. The pilot flew the plane to Cairo. - The pilot actually manipulated the plane's controls.
3. The mummy flew to Cairo. - The mummy was cargo.
4. The plane flew to Cairo. - T~e plane was the instrument of its own mo­ tl.On.
5. The pigeon flew to Cairo. - The bird was both the instrument and com­ mander of the action.

Table 1.

1. fly: actor nil object businessmau
2. fly: instrument plane actor pilot qbject plane
3. fly: 1.nstrument plane actor nil qbject mummy 1.nstrument
4. fly: actor nil qbject plane 1.nstrument plane
5. fly: act;or pigeon qbJect p1.feo~ 1.nstrumen p1.geon

Table 2.

IV TESTING AND RESULTS

The parser, with a dictionary of 72 words, was tested on a set of 120 sentences to verify that it recognized the morphology of the words and syntactic constructions of the clauses prop­ erly, and that the mapping from structure to g~ammatical re1~tions and from grammatical rela­ tl.ons to semant1.c roles was correct.

KING KONG worked correctly under the full range of tenses, voices, and under many transformations on sentence structure including unbounded movement rules like WH movement, relation-changing rules like Passive, Dative Movement and Raising, deletion rules such as Equi, and insertion rules ~uch as There­ insertion and Extraposition tsee a sam~ling in Tab1e 3). However 1 there were some lim1.tat1.ons on the capabilit1.es of the parser arising from its insufficient handling of coordination. We are currently implementing KING KONG as an ex­ pert systems a~proach to parsing in order better to handle dec1.sions about ambiguity. Even with these limitations, the range of sentence con­ structions it could parse was very wide. Most crucially, KING KONG successfully recognized grammatical relations. It was always able to 1.dentify the subject, object and indirect object of each verb, even when these were shifted away from the verb by transformations of the base sentence.

Finally, within the restrictions im~osed by lack of context and only the most rud1.mentary suggestions of a semantic component, KING KONG w~s always .a~le to map from grammatical rel~­ tl.ons of ent1.t1.es to act1.ons, to the semant1.c roles of actor, instrument, and object.

A pilot flew the plane.

The good plane could quickly be flown by a good pilot.

Who flew the plane?

What plane is the pilot flying?

Are planes destroying boxes?

He gave the box to John.

Refuel the plane at the airbase.

I am trying to believe that John seemed to promise me to want the ecm to jam the ra­ dar.

Does John go quickly?

Table 3.

V CONCLUSION

We have demonstrated that the use of rela­ tional. grammar as a mapping between syntax and semant1.cs overcomes many of the weaknesses asso­ ciated with other pars1.ng strategies. We real­ ize. of course, that a parser is only one com­ ponent . of an interfa~e; we are currently develop1.ng a representat1.on of context using scripts and semantic networks. The latter s~ould provide a ca~ability . for understanding s;mp~e word ext~ns1.qns, Wh1.le the former will ~1.d 1.n understand1.ng 1.11-;-formed but ''meaningful" 1.nput. A last hope 1.s that by making use of un1.versal relational categories we can attempt the retargetting of KING KONG to another language.