Project April --- A Progress Report

PROJECT APRIL -- A PROGRESS REPORT Robin Haigh, Geoffrey Sampson, Eric Atwell Cenlre for Computer Analysis of Language and Speech, University of Leeds, Leeds LS2 9JT, UK ABSTRACT Parsing techniques based on rules defining grammaticality are difficult to use with authentic inputs, which are often grammatically messy. Instead, the APRIL system seeks a labelled tree su~cture which maximizes a numerical measure of conformity to statistical norms derived flom a sample of parsed text. No distinction between legal and illegal trees arises: any labelled tree has a value. Because the search space is large and has an irregular geometry, APRIL seeks the best tree using simulated annealing, a stochastic optimization technique. Beginning with an arbi- Irary tree, many randomly-generated local modifications are considered and adopted or rejected according to their effect on tree-value: acceptance decisions are made probabilistically, subject to a bias against advexse moves which is very weak at the outset but is made to increase as the random walk through the search space continues. This enables the system to converge on the global optimum without getting trapped in local optima. Performance of an early ver- sion of the APRIL system on authentic inputs is yielding analyses with a mean accuracy of 75.3% using a schedule which increases pro- cessing linearly with sentence-length; modifications currently being implemented should eliminate a high proportion of the remaining errors. INTRODUCTION Project APRIL (Annealing Parser for ~al~- tic Input Language) is constructing a software system that uses the stochastic optimization technique known as "simulated annealing'" (Kirkpatnck et al. 1983, van T ~rhoven & Aatts 1987) to parse authentic English inputs by seek- ing labelled trce-su~ctures that maximize a measure of plausibility defined in terms of empirical statistics on parse-tree configurations drawn from a dmahase of mavnolly parsed English toxL This approach is a response to the fact that "real-life" English, such as the m~u,Jial in the Lancaster-Oslo/Bergen Corpus on which our research focuses, does not appear to conform to a fixed set of grammatical rules. (On the LOB Corpus and the research back- ground from which Project APRIL emerged, see Garside et al. (1987). A crude pilot version of the APRIL system was described in Sampson (1986).) Orthodox computational linguistics is heavily influenced by a concept of language according to which the set of all strings over the vocabulary of the language is partitioned into a class of grammatical strings, which possess ana- lyses all parts of which conform to a finite set of rules defining the language, and a class of strings which are ungrammatical and for which the question of their grammatical stntcture accordingly does not arise. Even systems which set out to handle "deviant" sentences com- monly do so by referring them to particular "non-deviant" sentences of which they are deemed to be distortions. In our wcck with authentic texts, however, we find the "gramma- ticality" concept unhelpful. It frequendy hap- pens that a word-sequence occurs which violates some recognized rule of English grammar, yet any reader can understand the passage …

Content truncated to 500 words