Eliminative Parsing with Graded Constraints

Eliminative Parsing with Graded Constraints Johannes Heinecke and Jiirgen Kunze (heinecke I kunze@compling.hu-berlin.de ) Lehrstuhl Computerlinguistik, Humboldt-Universit~t zu Berlin Schiitzenstraf~e 21, 10099 Berlin, Germany Wolfgang Menzel and Ingo Schrtider (menzel I ingo.schroeder@informatik.uni-hamburg.de ) Fachbereich Informatik, Universit~t Hamburg Vogt-Kblln-Stra~e 30, 22527 Hamburg, Germany Abstract Resource adaptlvity" Because the sets of struc- Natural language parsing is conceived to be a pro- cedure of disambiguation, which successively re- duces an initially totally ambiguous structural rep- resentation towards a single interpretation. Graded constraints are used as means to express well- formedness conditions of different strength and to decide which partial structures are locally least pre- ferred and, hence, can be deleted. This approach facilitates a higher degree of robustness of the ana- lysis, allows to introduce resource adaptivity into the parsing procedure, and exhibits a high potential for parallelization of the computation. 1 Introduction Usually parsing is understood as a constructive pro- cess, which builds structural descriptions out of ele- mentary building blocks. Alternatively, parsing can be considered a procedure of disambiguation which starts from a totally ambiguous structural repre- sentation containing all possible interpretations of a given input utterance. A combinatorial explosion is avoided by keeping ambiguity strictly local. Al- though particular readings can be extracted from this structure at every time point during disam- biguation they are not maintained explicitly, and are not immediately available. Ambiguity is reduced successively towards a single interpretation by deleting locally least preferred par- tial structural descriptions from the set of solutions. This reductionistic behavior coins the term elimina- tire parsing. The criteria which the deletion deci- sions are based on are formulated as compatibility constraints, thus parsing is considered a constraint satisfaction problem (CSP). Eliminative parsing by itself shows some interest- ing advantages: Fail soft behavior: A rudimentary robustness can be achieved by using procedures that leave the last local possibility untouched. More elabo- rated procedures taken from the field of partial constraint satisfaction (PCSP) allow for even greater robustness (cf. Section 3). tural possibilities are maintained explicitly, the amount of disambiguation already done and the amount of the remaining effort are immediately available. Therefore, eliminative approaches lend themselves to the active control of the pro- cedures in order to fulfill external resource lim- itations. Parallelization: Eliminative parsing holds a high potential for parallelization because ambiguity is represented locally and all decisions are based on local information. Unfortunately even for sublanguages of fairly modest size in many cases no complete disambigua- tion can be achieved (Harper et al., 1995). This is mainly due to the crisp nature of classical constraints that do not allow to express the different strength of grammatical conditions: A constraint can only al- low or forbid a given structural configuration and all constraints are of equal importance. To overcome this disadvantage gradings can be added to the constraints. Grades indicate how seri- ous one considers a specific constraint violation and allow to express a range of different types of condi- tions including preferences, defaults, and strict re- strictions. Parsing, then, is modelled …

Content truncated to 500 words