Statistical Agenda Parsing

Statistical Agenda Parsing Robert J. Bobrow BBN Systems and Technologies 10 Moulton Street. Cambridge, MA 02138 ABSTRACT This paper presents the results of converting a standard Greham/Harrison/Ruzzo (GHR) parser for a unification grammar into an agenda-driven parsing system. The agenda is controlled by statistical measures of grammar-rule likelihood obtained from a training set. The techniques in the agenda parser lead to substantial reductions in chart size and parse time, and can be applied to any chart-based parsing algorithm without hand-tuning. INTRODUCTION In a Graham/Harrison/Ruzzo (GHR) parser, the chart is used to maintain a record of syntactic constituents that have been found (terms) and grammatical rules that have been partially matched (dotted rules). Parsing strategies such as GHR, CKY and other algorithms can be viewed as methodical ways of filling the chart which guarantee to explore all possible extensions of dotted rules by terms. An agenda is an alternative chart-filling algorithm with the goal of finding some term covering the entire input without necessarily filling in all of the chart. If terms can be ranked by "goodness" and the grammar can produce multiple analyses of a given string, then one goal for an agenda is to produce the "best" parse first. The alternative goal we have chosen for DELPHI is to use the agenda mechanism to reduce the search necessary to produce ACCEPTABLE (see below) parses. This results in sparsely populated charts, approaching the extreme (and probably unattainable) goal of deterministic parsing, in which the only terms and dotted rules entered into the chart are those which appear as parts of the final parse. The techniques involved in statistical agenda parsing allow "low probability" rules to be added to a grammar without significant cost in terms of either erroneous parses or increased parse time. These low probability rules greatly increase the coverage and robustness of the system by accounting for unusual or marginal constructions. DELPHI AGENDA PARSING Most techniques for search splice reduction involve careful tuning of the grammar or the parsing mechanism. This is very labor intensive and can place limits on the grammatical coverage of the system (Abney 1990). Our approach is to use an automated statistical technique for ranking rules based on their use in parsing a training set with the same grammar (under the control of an all-paths GHR parser without human supervision). This approach also allows us to include grammatical rules that are of use only rarely, or in specialized domains, and to learn how applicable they are to a body of sentences. To take into account general linguistic tendencies, we augment the statistical ranking by a small number of general agenda ordering strategies. The DELPHI agenda mechanism is based on three "scbedulable" action types: 1. the insertion of a term into the chart, 2. the insertion of a dotted rule into the chart, and 3. the (conditional) "pair extension" of a dotted rule by a term. In principle one would like to order those actions in terms of the probability that they lead to a …

Content truncated to 500 words