Restricted Parallelism in Object-Oriented Lexical Parsing

Restricted Parallelism in Object-Oriented Lexical Parsing Peter Neuhaus Udo Hahn Freiburg University ~} Computational Linguistics Lab Europaplatz 1, D-79085 Freiburg, Germany {neuhaus, hahn}@ coling, uni-freiburg, de Abstract We present an approach to parallel natural language parsing which is based on a con- current, object-oriented model of computa- tion. A depth-first, yet incomplete pars- ing algorithm for a dependency grammar is specified and several restrictions on the de- gree of its parallelization are discussed. 1 Introduction There are several arguments why computational lin- guists feel attracted by the appeal of parallelism for natural language understanding (for a survey, cf. Hahn & Adriaens (1994)): the ubiquitous requirement of en- hanced efficiency of implementations, its inherent po- tential for fault tolerance and robustness, and a flavor of cognitive plausibility based on psycholinguistic ev- idences from the architecture of the human language processor. Among the drawbacks of parallel process- ing one recognizes the danger of greedy resource de- mands and communication overhead for processors running in parallel as well as the immense complexity of control flow making it hard for humans to properly design and debug parallel programs. In this paper, we will consider a framework for par- allel natural language parsing which summarizes the experiences we have made during the development of a concurrent, object-oriented parser. We started out with a rather liberal conception which allowed for al- most unconstrained parallelism. As our work pro- gressed, however, we felt the growing need for restrict- ing its scope as a continuous "domestication process". While still keeping the benefits of parallelism, we have arrived at a point where we argue for a basically se- rial model patched with several parallel phases rather than a basically parallel model with few synchroniza- tion checkpoints. Primarily, this change in perspec- tive was due to large amounts of artificial ambiguities that could be traced to "blind" parallel computations with excessive resource allocation requirements. Con- tinuously taming the parallel activities of the parser and, furthermore, sacrificing highly esteemed theoret- ical principles such as the completeness of the parser, i.e., the guaranteed production of all analyses for a given input, led us to determine those critical portions of the parsing process which can reasonably be pur- sued in a parallel manner and thus give real benefits in terms of efficiency and effectiveness. 2 Design Requirements for the Parser The application framework for the parsing device un- der consideration is set up by the analysis of real- world expository texts (viz. information technology product reviews and medical findings reports). The parser operates as the NLP component of a text knowl- edge acquisition and knowledge base synthesis sys- tem. The analysis of texts (as opposed to sentences in isolation) requires the consideration of discourse phe- nomena. This includes the interaction of discourse en- tities (organized in focus spaces and center lists) with structural descriptions from the parser and conceptual information from the domain knowledge base. Thus, different knowledge sources have to be integrated in the course of an incremental text understanding pro- cess. …

Content truncated to 500 words