Improving Search Strategies An Experiment in Best-First Parsing

hnproving Search Strategies An Experiment in BesbFirst Parsing Hans ItAUGENEI)ER Manfl'ed GEHRKE Siemens AG ZT ZTI INF 23 Otto-Hahn-Ring 6 8000 Mtinchen 83 W. Germuny Abstract Viewing the syntactic analysis of natural language as a search problem, the right choice of parsing strategy plays an important role in the performance of natural language [arsers. After a motivatim: of the use of various heuristic criteria, a fl'amework for defining and testing par:;[ng strategies is presented. On this basis systematic tests on different parsing strategies have been performed, the results of which are dicussed. Generally ;hese tests show that a "guided" depth- oriented strategy gives a considerable reduction of search effort eompared to the classical depth.first strategy. ~.. Introduction Parsing natural language utterances can be considered a search t,roblem, which is characterized by the application of a set of operators (i.e. the grammar rules) onto the input data (phrase to be processed) in order to yield a ~)nal state (derivation tree). In practical applications which are characterized by grammars with a large eow.,rage and a non-trlvial complexity of the input {mea,';ured e.g. in sentence length and lexieal ambiguity) one is confronted with difficulties that seem quite common to various search problems, namely the size of the search space and the selection among multiple solutions, Two (iuite opposite approaches to these problems have been proposed. In tile one approach, the brute force of exhaustive .,~earch has been used, possibly augmented with some ranking scheme tbr the set of parses. In the other approach, the parsing of natural language utterances is considered a deterministic process [Mar80], where a "wait and set.'" strategy makes the tlavour of searching through the alternative application of different grammar rules disappear, at least for grammars w{th limited coverage. The approach we are taking to this problem lies between these two ext('emes: ConC'el)tually, it takes the first view, considering natural language parsing a nondeterministic process; fi'om a performance point of view, it is :tirected towards the approximation of deterministic behaviour. Thus our aim is to develop a best-first parsing strategy which enables tile parser by means of heuristic criteria and information to limit the overall search space as much as possible to arrive at tile first parse at low costs achieve the most plausible analysis as the first one. With these aims in mind - at present mainly concentrating on the first one - we still want to maintain tile ability of our nleehanism to find t'm'~her solutions, since we do not assume the order of the analyses to be correct all the time. Thus "hem'isties" is understood as improving the problem solving perfornlance without affecting the competence [Min63]. What we propose is a practically oriented approach to these problems; it is practical in the sense that our primary focus is not to model the human sentence processing meehanisn~ or specify the human parsing strategy. We are rather aiming towards the development of parsing strategies, that are based on heuristic information, enabling the parser to choose the right paths in …

Content truncated to 500 words