A State-Transition Grammar for Data-Oriented Parsing

A State-Transition Grammar for Data-Oriented Parsing David Tugwell* Centre for Cognitive Science, University of Edinburgh 2, Buccleuch Place, Edinburgh EH8 9LW, Scotland davidt~cogsci.ed.ac.uk Abstract This paper presents a grammar formalism de- signed for use in data-oriented approaches to lan- guage processing. It goes on to investigate ways in which a corpus pre-parsed with this formalism may be processed to provide a probabilistic lan- guage model for use in the parsing of fresh texts. Introduction Recent years have seen a resurgence of interest in probabilistic techniques for automatic language analysis. In particular, there has arisen a dis- tinct paradigm of processing on the basis of pre- analyzed data which has taken the name Data- Oriented Parsing. "Data Oriented Parsing (DOP) is a model where no abstract rules, but language experi- ences in the form of an analyzed corpus, con- stitute the basis for language processing." 1 There is not space here to present full justification 1. for adopting such an approach or to detail the ad- vantages that it offers. The main claim it makes is that effective language processing requires a con- sideration of both the structural and statistical as- 2. pects of language, whereas traditional competence grammars rely only on the former, and standard statistical techniques such as n-gram models only on the latter. DOP attempts to combine these two traditions and produce "performance grammars", which: "... should not only contain information on the structural possibilities of the general 3. language system, but also on details of actual language use in a language community... ''2 *This research was funded by a research studentship from the ESRC. My thanks also for discussion and com- ments to Matt Crocker, Chris Brew, David Milward and Anna Babarczy. 1Bod, 1992. 4. 2ibid. This approach entails however that a corpus has first to be pre-analyzed (ie. hand-parsed), and the question immediately arises as to the formalism to be used for this. There is no lack of compet- ing competence grammars available, but also no reason to expect that such grammars should be suited to a DOP approach, designed as they were to characterize the nature of linguistic competence rather than performance. The next section sets out some of the properties that we might require from such a "performance grammar" and offers a formalism which attempts to satisfy these requirements. A Formalism for DOP Given that we are attempting to construct a for- malism that will do justice to both the statistical and structural aspects of language, the features that we would wish to maximize will include the following: The formalism should be easy to use with prob- abilistic processing techniques, ideally having a close correspondence to a simple probabilistic model such as a Markov process. The formalism should be fine-grained, ie. re- sponsive to the behaviour of individual words (as n-gram models are). This suggests a radi- cally lexiealist approach (cf. Karttunen, 1990) in which all rules are encoded in the lexicon, there being no phrase structure rules which do not introduce lexical items. …

Content truncated to 500 words