Controlling Search in Flexible Parsing

1 Introduclien

Most natural language processing systems parse their input by searching through a space of partial parses. They operate this way because, even though complete utterances alone or in context may be quite unambiguous, natural language is highly ambiguous locally. For instance, individual words can be ambiguous in their meaning or part of speech (e.g. "bank") , or components of utterances can fit Iogether in more than one way (e.g. "Iook at the man with the telescope") . A parser's search space for a given input is defined by the relevant set of loca.l ambiguities. A search succeeds if a globally acceptable parse is found that accounts for all the input. There are various techniques to reduce search in parsing, including looking ahead to resolve local ambiguities [5], or ignoring local alternatives that are inconsistent with domain­ specific semantic constraints (2, 4] . However, no techniques can completely eliminate search from naturallanouage parsing.

The search problern becomes much worse if we require a ·parser to cope with extragrammatical input. For practical natural language interface systems, this requirement isareal one [1]. Such interfaces must cantend with the grammatical errors that inevitably arise when people use natural language interactively. Moreover, they also must cope with input that is correct, but outside their domain-restricted grammars. 3 We use the term f/e)( ible parser for a parser that can handle extragrammatical input.

The major search problern in flexible parsing lies in the criterion for identifying failing branches of the search - normally the violation of some syntactic or semantic expectation. While parsers that require grammatical input can employ this constraint to prune the search tree, flexible parsers must act more cautiously. lf a candidate parse violates an expectation, it may mean that the candidate parse is incorrect and should be abandoned, or it may mean that the input really does violate the parser's expectations in the way that has been detected. ln the latter case, the parser should not abandon the branch, but should try to recover from the deviation and complete the parse along that branch.

1 AT& T Bell Laberateries Scholar

2 This research was sponsored in part by the Air Force Office of Scientific Research under Contract AFOSR-82·0219.

One approach to this problern is to abandon a search branch only when the flexible parser has run out of correction techniques to apply. This, in effect, enlarges the grammar of the parser to cover not only the inputs originally considered grammatical, but also those that can be recognized by any combination of available recovery methods. Although straightforward, this approach is unlikely to produce acceptable results. First, given the range of possible recovery techniques [1], the search space will quickly become unmanageably !arge. Second, the recovery techniques may generate spuriously "corrected" pars&s of grammatical input. Finally, the described approach provides no way to distinguish between parses that involve widely varying degrees of correction (e.g. simple spelling corrections versus hypothesization of entire phrasP.s).

What is needed, then, is a control structure that allows the normal criterion of extragrammaticality to cut oft fail ing searches, but also accommodates the application of recovery techniques to reactivate failed search branches if no grammatical parse can be found. Moreover, the recovery techniques should be erdered across all search branches according to the degree of ungrammaticality their use implies, i.e. the simpler ones (like spelling correction) must be tried in all branches of the parse before the more complex and unlikely ones (like missing word insertion) are tried in any branch.

This paper presents a control structure which satisfies these goals. The next section describes the control structure from the point of view of the programmer constr~cting a parser that uses it. Section 3 discusses some efficiency issues that arose in implementing the control structure.

2 A Programmer's View of the Control Structure

The control structure described in this paper was developed in the context of a restricted domain parser consisting of a collection of caseframe instantiation strategies. We have previously used the phrases multi -strategy [3] and entity-oriented [2] to describe this approach. There is no space here to describe this parser, called MUL TIPAR, in detail. The most important characteristic of MULTIPAR from the control structure point of view is that its caseframe interpretation strategies are programmed directly, rather than being driven by a declarative formalism such as a transition network. We will refer to the person who writes strategies as the strategy programmer. ln some sense, the strategy programmer is the user of the control structure.

Each strategy is an expert at parsing certain types of constructs. Strategies cooperate by calling upon each other to parse sections of the input sentence. When a strategy encounters particular difficulties (violated expectations) while parsing its input, several ootions are typically available. The options always include simply reporting failure, but may also include recovery methods to resolve the violated expectation. The MULTIPAR contrql structure provides the programmer witt> a method of specifying the alternative ways of proceeding, and indicating how much of a deviation each option would represent, without requiring him to schedule the investigation of the options explicitly. This scheduling is Iaken care of by the control structure automatically The construct provided 4 by the control structure to specify alternative ways of proceeding in the face of violated expectations is the SPLIT statement. A SPLIT statement splits the computation into parallel branches - one branch for each option. For each branch, the programmer specifies a flexibility increment indicating the degree of grammatical deviation implied by producing a successful parse via that branch. For instance, if a violated expectation could be resolved by a spelling correction or by hypothesizing a missing word, these two options would be specified ·as different branches of a SPLIT. The control structure would then pursue the two Options independently. However, the spelling ·correction option would have a lower flexibility increment than the missing word hypothesization, and so it would be pursued first. II it led to a complete parse, the missing word hypothesization would .never be tried. ·

3 We use the term grammar broadly here to cover the semantic expectations used by many restricted domain systems in addition to syntactic ones.

A stylized example of a split statement is:

(Split (+0 actionA) (+1 actionB) (+3 actionC) . . . . )

Execution of this SPLIT statement produces a three-way branch in the search tree. Action A has a zero flexibility increment, implying no grammatical deviation along this branch. Actions B and C have flexibility increments of 1 and 3 respectively. This means !hat Actions B and C would be scheduled for later investigation, while Action A would be pursued immediately.

The system maintains a global Current-Fiexibility-Level whose value is equal to the flexibility Ievei of the least deviant partial parse !hat remains to be investigated. ln this way, the control structure can guarantee !hat parses are attempted in strict flexibility order and can generate all anC: only parses at the lowest flexibility Ievei at which a global parse succeeds. in particular, if a grammatical parse can be found, then all and only grammatical parses will be generated.

1t is important to note that the flexibility Ievei of a parse is the sum of all flexibility increments of all SPLIT statement branches used to achieve the parse. in terms of the stylized example above, this means that other branches in entirely different parts of the tree may be tried between trying Actions B and C. lt also means !hat Actions Band C may be tried, even if Action A succeeds locally, so long as the parse fragment produced by Action A does not participate in a complete global parse. This global comparison of the sums of the local flexibility increments is crucial in ensuring that recovery techniques are attempted in order of drasticness across the entire search space of a parse. lt also ensures that improbable combinations of recovery techniques are not applied if simoler parses can be found.

Another advantage provided by the SPLIT statement is that recovery actions can be closely integrated with the normal parsing process. Inslead of having a separate recovery phase that occurs independently of normal parsing, recovery actions occur within the local context of strategies. Therefore, only recovery actions appropriate to the context need be applied. This is important for recovery strategies such as spelling correction, where availability of the local context can provide information that constrains the range of possible corrections.

4 MUL Tl PAR is implemented in Common Lisp.

Let us now Iook at a less stylized use of SPLIT. The following algorithm is a simplified version of the strategy MULTIPAR uses for parsing imperative sentences.

Imperative Gaseframe Strategy

1. Find the head verb of the sentence.
2. Retrieve an uninstantiated caseframe for the action associated with this verb.
3. ldentify the semantic type of the syntact{c direct object. Ca// the Nounphrase Strategy to find an object of that type at the beginninn of the unparsed segment.
4. Derermine the untllled marked cases and SPLJT
5. 0 Alternative1: Recognize next word as a case­ marker for an unfilled marked case; attempt to ft/1 that case with the remaining segment.
6. 5 Alternative2: Hypothesize that a case-marker for a_n unfilled marked case is missing; attempt to ft/1 the case with the remaining segment.
7. lf sentence has not been completely parsed, go to 4.

Let us assume !hat MULTIPARis being used as the front-end to a mail system, and that the user has just composed a message to be sent. To parse a .command such as "Mail message to Paui@CMUA", the strategy would first identify "Mail" as the head verb, and SEND as its corresponding action, and then call the Neunphrase Strategy to recognize a potential MSG·OBJECT as the direct object. Assuming this lower Ievei strategy parses "message" correctly, the imperative strategy then reaches the SPLIT statement. At this point, two branches of the search tree are created with flexibility Ieveis equal to the sum of the Current­ Fiexibility-Level (which is 0) and the corresponding flexibility increments. The branch corresponding to Alterriative2 is scheduled by the control structure at flexibility Ievei 5 (0 plus 5) . The branch corresponding to Alternative1 still has flexibility Ievei 0 (0 plus 0) , and so it continues immediately. Alternative1 would successfully recognize "to" as a marker for SEND's destination case, and call a lower-level strategy to parse "Paui@CMUA" as the MSG·DESTINATION. Thus, this branch of the parse succeeds and the other branch spawned by the SPUT is never tried.

A common error in spontaneaus input is to omit case markers, so Iet us suppose now that the input reads "Mail message Paui@CMUA". As before, alter "message" is recognized as the direct object, the SPLIT statement is encountered. However, this time Alternative1 reports failure. II the control structure finds no other branches of the tree suspended at flexibility leve.l 0 (the Current-Fiexibility-Level), it will Iook for suspended branches at higher flexibility Ieveis. in our present example, it will find the branch suspended earlier at Ievei 5. The Current-Fiexibility-Level is set to 5, and computation is restarted at Alternative2. This means !hat the imperative strategy will now hypothesize that a case-marker has been omitted, and will try to parse "Paui@CMUA" as one of the unfilled cases for SEND. When "Paui@CMUA" is recognized as a possible MSG·DESTINATION, the inputwill have been completely accounted for, and the parse would be the same as for the first example. 5 Notice !hat this recovery action is specific to the violated expectation ol linding a case marker. Because the action is context-dependent, it would have been more difficult to achieve in a completely separate recovery phase Even with this simple example, it will be clear that the size ol the search tree can grow rapidly when recovery is attempted. II "Paui@CMUA" qualified as both a MSG-SOURCE and a MSG-DESTINATION, Alternative2 above would have to split again, and two alternative corrected parses would be produced. Then too, Paui@CMUA might be the name ol a misspelled message­ header. Exploring this alternative would be the responsibility ol one ol the strategies called while parsing the direct object. Note that spelling correction can potentially generate many alternatives, especially il words in the parser's lexicon can be considered as potential misspellings ol other words in the lexicon (perhaps the user intended "Make" instead ol "Mail").

5 A complete interface system might want to confirm its interoretation with the user.

These examples may make clearer the importance ol exploring all potential parses at lower flexibility Ieveis belore any ol those at higher Ieveis. Witness the computational expense inherent in recovering a missing case marker, i.e. trying all unlilled cases. II there is still a possibility that branches ol the search requiring less drastic recovery techniques might yet succeed, they must be attempted lirst. For example, the sentence "Mail message should be saved" will be recognized by a strategy lor declarative sentences that is invoked in a branch parallel to the imperative strategy. Since this branch succeeds at Ievei 0, it should be examined in its entirety belore the imperative strategy attempts to hypothesize a missing case marker

This best-lirst order ol exploring the search tree implies that grammatical parses will be discovered relatively quickly. (A disadvantage, ol course, is that ungrammatical, but recoverable parses may be produced signilicantly more slowly.) Equally important, the use ol llexibility Ieveis imposes a partial order on deviant parses, so parses that are highly undesirable will never be discovered il better alternatives exist. For example, a parse with two spelling corrections will not be generated il a parse with a single spelling correction can be lound. At Iimes, the erdering may be rather arbitrary (e.g. is a missing case marker worse than a single spelling mistake?). However, such arbitrary judgments tend to overconstrain the search rather than underconstrain it, which seems appropriate.

31mplementing the Multipar Control Structure Efficiently

ln order lor the control structure outlined in the previous sections to be ol practical use, it must implement the best-lirst search in an efficient manner, and it must be convenient lor the strategy programmer to use. ln this section we outline some of the engineering considerations that proved to be crucial in achieving these goals.

• Usabifity: MULTIPAR consists ol many communicating strategies, each ol which may involve a complex computation. The control structure provides a standard interlace lor one strategy to call upon another and controls the pseudo-parallel exploration ol the search tree. An important attribute ol the control structure is its unobtrusiveness; the strategy writer is provided with a small set ol lacilities lor executing strategy calls and parallel actions
• Efficient Gontext Re-creation: To return to an alternative on the agenda, the local context at the SPLIT statement must be re-created. Rather than saving the complete state of the computation; context re-creation is effected by re-executing the local strategy from its inception. This seemingly inefficient mechanism is quite practical due to two lactors: most scheduled alternatives are nelier attempted during a
• typical parse, and a caching mechanism is used to store substrategy results.
• Sharing Strateqy Resufts: lt is olten the case that parallel branches will duplicate each other's work, since they may differ only in a Iew respects. This is especially true when recovery actions are initiated, since the number of branches tends to grow dramatically as higher llexibility Ieveis are reached. Because ol this, the mechanism lor caching substrategy results has a dual purpose. ln addition to enabling rapid context re-creation, it makes the overall Operation ol the parser more efficient by allowing strategies to share results. 6 For example, to recover lrom a missing case marker, the lower-level case liller strategy has to be called once for each case that could possibly be lilled. Each time it is called it may have to oparate somewhat differently depending on the constraints forthat case (e.g. call a name­ recognizing sub-strategy or check to see whether the input can be lound among current message headers). However, much ol the work may be identical in each instance, and so caching produces considerable savings.

4 Concluslon

All naturallanguage parsers must perform some search, but when a parser is intended to handle ungrammatical as weil as grammatical input, its search space becomes very large. The control structure described in this paper allows a large, complex search space of this kind to be explored in an orderly manner. Elficiency is improved by a caching mechanism that takes advantage of the signilicant amount of redundancy present in the search space. The control structure provides convenient facilities for specifying the search space, while automatically performing the bookkeeping necessary for an efficient search.

We have built a version of MULTIPAR that parses natural language commands to an operating system. Experience with both grammatical and deviant sentences in this domain suggests that the control structure adequately fulfills the requirements for a flexible parser outlined earlier.

5 Acknowledgements

We thank Jaime Garboneil for his help and participation in all phases of this project.