Alternative Parsers for Conceptual Dependency: Getting There is Half the Fun

1. INTRODUCTION

An important trend in natural language proces­ sing which emerged in the early 1970's was the use of case-based language-independent notation to represent the conceptual content of segments of text (3,5,7). Although there is much over­ lap among the theories of different research teams working in this area, there appea r to be fundamental differences in the ways in which these theories specify the actual processing of text. But which differences are deep theoreti­ cal ones, and which are merely artifacts of implementation? I address this question by look­ ing at the processes underlying two parsers which were influential during the 1970's: Riesbeck's parser (4) for Schank's conceptual dependency formalism ( 5); and the 'LNR' parser for Norman and Rumelhart's active semantic net­ work formalism (3). The actual internal repre­ sentation of text i s not the main focus of this paper. Rather, it is the parsing process itself which is under scrutiny.

To carry out this analysis, I have implemented vers ions of both parsers using Kaplan's General Syntactic Processor, GSP (1). I will first des­ cribe the GSP versions of each parser, and then the way in which their best features can be combined.

2. RIESBECK 1 S PARSER

2.1 Overview

The intent of Riesbeck's parser is to build a conceptual dependency r epr esenta t i on of a seg­ ment of t ext. In operation, the main verb of each segment (phrase) of t ext i s loca ted, and a representa tion of its 'meaning' ( its decomposi­ tion) is constructed in memory. The surrounding text, primarily noun-phrases, is then systemati­ cally mapped onto vacant slots within the memor y representation of the decomposed verb. The parser's ·expectations ' arc repr esented by active packets of production rules . Impor tant phrase boundaries and slot-filler ( case ) i nformation are s i gnpost ed by words which may (a ) satisfy exi sting expectations of t he parser (by matching the condition s ide of a production rule) or (b) generate new expec t a t ions f or the parser (by activating a new packet of product ion rules) .

2. 2 The ~ version

In GSP t erms , Ri esbeck's 'ac t i ve' produc t i on rules are represented by s t andard ATN- s tyl e arcs in the grammar (6). The interrupt s which activate new packets of rul es are modelled i n GSP by storing in the lexi con the code which causes control to shift to a new gr amma r s t ate (since any change in t he va lue of global var i ­ ables, such as Riesbeck's 'request list' , i s formally equivalent t o a new GSP-machine stat e).

For exampl e, the l exical entry f or t he verb 'give ' includes , amon~ other t hings , t he f ollow­

ing :

INTERRUPT: (SETR CONCEPT (GETF DECOMPOSITION»

(NEWSTATE GIVE¢)

GSP's controlling executive knows to look at the 'interrupt' code stored in the lexicon. In this case, the code says to set the CONCEPT register to the structure found for this entry under the indicator DECOMPOSITION (i.e. its conceptual dependency representation), and to advance the grammar to the state labelled GIVE¢. State GIVE¢ is the one which initiates the actions corresponding to Riesbeck's setting up of new expectations, and is bas ically an entire sub-grammar devoted to the verb 'give'. This sub-grammar asks specific questions about the attributes of incoming noun phrases, and assigns these phrases to case slots accordingingly, e.g. the surface pattern HUMAN give HUMAN PHYSOBJ results in the second HUMAN getting placed in

the RECIPient slot.

Although conceptual dependency emphasises the role of 'deep conceptual cases', the parser itself is necessarily a hybrid beast - it builds conceptual representation the instant a verb is encountered, but it fills vacant case slots on the basis of purely surface syntactic consid­ erations, combined with relatively simple Katz & Fodor-type selectional restrictions (although Riesbeck does allow the restrictions to be re­ laxed if nothing else makes more sense). Riesbeck's parser could in fact build some other kind of internal representation, based on any one of several linguistic theories of lexical decomposition, without any effect on the course of parsing.

Riesbeck's parser discovers noun phrases when a signalling word, such as 'a', interrupts proces­ sing and passes control to a noun-phrase sub­ grammar. Active production rules which were pending before the 'a' was discovered are saved on a special 'hold' list, and restored when a 'phrasebreak' (e.g. a verb or a period) is en­ countered. At that point, an EVAL-PHRASE routine (not unlike an ATN BUILDQ) constructs an intern& representation of the just-parsed noun-phrase. In GSP terms, this activity is almost identical to the standard ATN 'PUSH NP', except that the potentially expensive aspects of a PUSH and POP (namely, saving return states and building pos­ sibly incomplete NP structures) are not carried out until it is virtually certain that they will succeed. This variation is handled in the GSP version by having the appearance of an item such as a determiner (which would normally be sought at the beginning of an NP sub-grammar) initiate a PUSH 'safely' after that key item is encount­ ered in the text:--This is done . by having the 'interrupt' code for determiners pass control directly to state NP in the grammar. Then, instead of performing a tentative POP when the NP sub-grammar thinks it is finished, the

'interrupt' code of verbs (and other items which signal a 'phrasebreak' in various contexts) initiates the equivalent of a 'safe' POP directly when it is appropriate.

Of course 'safe' doesn't always mean 'guaran­ teed'. It is clear that there are all sorts of examples which would cause Riesbeck's parser to go astray. However, Riesbeck is concerned mainly about the fundamental operating principles, rather than performance on a specific case. The assumption is that these principles could be applied to more elaborate examples. This remains to be demonstrated for a so-called 'conceptually­ based' parser, although a related theme under­ lying the workings of Marcus' parser(2) indicates that 'safe' PUSHes and POPs indeed make powerful parsing tools. The advantages of lookahead in parsing are significant only when such lookahead is relatively cheap and reasonably accurate. The GSP implementation of Riesbeck's parser allows one to automatically incorportate fairly simple lookahead within the framework of other, more well established parsing mechanisms (e.g.

the PUSH NP of ATNs).

3· THE LNR PARSER ----

3.1 Overview

The LNR parser is designed to map sentences onto a surface case frame. This case frame is an n-ary predicate which contains a pointer to the appropriate code responsible for decomposing the predicate into a canonical 'meaning' represent­ tation. The case frame of each verb is stored in a memory network, and is referred to by the parser for guidance in picking up arguments to go with the main predicate. Aside from the subject and object slots, which typically surround the verb, other (arbitrary) case slots are signalled by the appearance of key prepositions.

3.2 The GSP version

The LNR parser is implemented as a fairly straightforward ATN, with the PUSH NP and PUSH PP arcs augmented with extra tests which must be passed for the transitions to be allowed. These tests are simply checks to see whether, say, the current prepositional phrase is consistent with the 'surface frame' stored in the lexical entry for the current verb, and whether the relevant case slot is still vacant. For example, the lexical entry for the verb 'give' includes the following:

SURFACE-FRAME: NP1: AGENT NP2: OBJ

'TO': RECIP

The slots 'NP1' and 'NP2' are signposts for the parser, saying that the NPs preceding andfollow­ ing the verb should be placed into the AGENT and OBJ registers, -espectively. The 'to' slot is a signpost saying that a prepositional phrase beginning with 'to' is acceptable, and that its (nested) noun phrase should be placed in the RECIP register.

The LNR parser only decomposes the main verb after the surface case frame is entirely filled ~Since the parser consults only the surface­ frame for guidance during processing, the final internal representation has no effect on the actual course of parsing, and could have been based on any of several theories of lexical de­ composition, including conceptual dependency.

Selectional restrictions are not included at all in the LNR parsing process - this must be done as part of the code which is executed during de­ composition. The problem with this approach is that it is not clear how total failure of such selectional tests would influence the course of parsing itself. A method of incorporating Riesbeck-style tests is described below.

4. A SYNTHESIS

Many of the differences between the LNR and Riesbeck parsers are apparent rather than real. LNR's use of a surface frame as a signpost to guide a general procedure (e.g. PUSH NP) to work on a specific verb is isomorphic to Riesbeck's branching off to an entirely separate sub-gram­ mar following the verb. Also, LNR' s test for a 'vacant slot' is equivalent to Riesbeck' use of self-deleting production rules. Neither the final decomposed representation of the main verb nor the time at which decomposition occurs have any effect on the actual course of parsing for either Riesbeck or LNR.

The two parsers do, however, differ in terms of whether they use interrupts and selectional re­ strictions to guide parsing. Riesbeck's parser uses both, and is on these counts computational­ ly superior to the LNR parser. The main strength of the LNR parser is its notational clarity, which derives from its description as an ATN. This makes it an ideal starting point for a hybrid parser made by augmenting it with Riesbeck's use of interrupts and selectional re­ strictions.

Beginning with an ATN specification of the LNR parser, Riesbeck-style interrupts are added by splicing into the lexicon the 'interrupt' code for items which can initiate 'safe' PUSHes (e.g. determiners) and items which can initiate 'safe' POPs (e.g. verbs). The old PUSHes and POPs then become redundant, and can be eliminated.

Selectional restrictions of the simplicity of Riesbeck's (i.e. looking for features such as HUMAN, PHYSOBJ, etc.) are then easily added. This simply involves augmenting LNR's surface­ frame slots with selectional information, e.g. 'TO': RECIP/HUMAN,

and then conjoining a general test onto the PUSH PP arc so that it tes ts whether the noun phrase following the preposition is an instance of the class named after the '/'.

Preliminary results with my own hybrid LNR/ Riesbeck Parser (implemented in my POP-2 version of GSP) indicate that the combination is cost­ effective for simple sentences, where the occurrence of obviously ill-fated PUSHes (e.g. testing for non-existing prepositional phrases) can be totally avoided . The selectional re­ strictions provide an extra heuristic for case slot-filling purposes , but can be easily fooled by counterexamples, so are better treated as 'preferences' to be followed tentatively. The most promising line for future development is the use of 'safe' PUSHes and POPs to handle multi-constituent lookahead, as in (2). I am currently working on a GSP version of Marcus' parser. Insights gained from placing his parser in a common framework with that of Riesbeck and LNR will be described in a forth­ coming paper.