Fast Parsing Using Pruning and Grammar Specialization

FAST PARSING USING PRUNING AND GRAMMAR SPECIALIZATION Manny Rayner and David Carter SRI International Suite 23, Millers Yard Cambridge CB2 1RQ United Kingdom manny@cam, sri. com, dmc~cam, sri. com Abstract We show how a general grammar may be automatically adapted for fast parsing of utterances from a specific domain by means of constituent pruning and grammar specialization based on explanation-based learning. These methods together give an order of magnitude increase in speed, and the coverage loss entailed by grammar spe- cialization is reduced to approximately half that reported in previous work. Experi- ments described here suggest that the loss of coverage has been reduced to the point where it no longer causes significant perfor- mance degradation in the context of a real application. 1 Introduction Suppose that we have a general grammar for En- glish, or some other natural language; by this, we mean a grammar which encodes most of the impor- tant constructions in the language, and which is in- tended to be applicable to a large range of different domains and applications. The basic question at- tacked in this paper is the following one: can such a grammar be concretely useful if we want to process input from a specific domain? In particular, how can a parser that uses a general grammar achieve a level of efficiency that is practically acceptable? The central problem is simple to state. By the very nature of its construction, a general grammar allows a great many theoretically valid analyses of almost any non-trivial sentence. However, in the context of a specific domain, most of these will be ex- tremely implausible, and can in practice be ignored. If we want efficient parsing, we want to be able to focus our search on only a small portion of the space of theoretically valid grammatical analyses. One possible solution is of course to dispense with the idea of using a general grammar, and sim- ply code a new grammar for each domain. Many people do this, but one cannot help feeling that something is being missed; intuitively, there are many domain-independent grammatical constraints, which one would prefer only to need to code once. In the last ten years, there have been a number of attempts to find ways to automatically adapt a general grammar and/or parser to the sub-language defined by a suitable training corpus. For exam- ple, (Briscoe and Carroll, 1993) train an LR parser based on a general grammar to be able to distin- guish between likely and unlikely sequences of pars- ing actions; (Andry et al., 1994) automatically infer sortal constraints, that can be used to rule out oth- erwise grammatical constituents; and (Grishman et al., 1984) describes methods that reduce the size of a general grammar to include only rules actually use- ful for parsing the training corpus. The work reported here is a logical continuation of two specific strands of research aimed in this gen- eral direction. The first is the popular idea of sta- tistical tagging e.g. (DeRose, 1988; …

Content truncated to 500 words