Experience with an Easily Computed Metric for Ranking Alternative Parses

Experience with an Easily Computed Metric for Ranking Alternative Parses George E. Heidorn Computer Sciences Department IBM Thomas J. Watson Research Center Yorktown Heights, New York 10598 Abstract This brief paper, which is itself an extended abstract for a forthcoming paper, describes a metric that can be easily com- puted during either bottom-up or top-down construction of a parse tree for ranking the desirability of alternative parses. In its simplest form, the metric tends to prefer trees in which constituents are pushed as far down as possible, but by appro- priate modification of a constant in the formula other behavior can be obtained also. This paper includes an introduction to the EPISTLE system being developed at IBM Research and a discussion of the results of using this metric with that system. Introduction Heidorn (1976) described a technique for computing a number for each node during the bottom-up construction of a parse tree, such that a node with a smaller number is to be preferred to a node with a larger number covering the same portion of text. At the time, this scheme was used primarily to select among competing noun phrases in queries to a program explanation system. Although it appeared to work well, it was not extensively tested. Recently, as part of our research on the EPISTLE system, this idea has been modified and extend- ed to work over entire sentences and to provide for top-down computation. Also, we have done an analysis of 80 sentences with multiple parses from our data base to evaluate the per- formance of this metric, and have found that it is producing very good results. This brief paper, which is actually an extended abstract for a forthcoming paper, begins with an introduction to the EPISTLE system, to set the stage for the current application of this metric. Then the metrie's computation is described, fol- lowed by a discussion of the results of the 80-sentence analy- sis. Finally, some comparisons are made to related work by others. The EPISTLE System In its current form, the EPISTLE system (Miller, Heidorn and Jensen 1981) is intended to do critiquing of a writer's use of English in business correspondence, and can do some amount of grammar and style checking. The central compo- nent of the system is a parser for assigning grammatical struc- tures to input sentences. This is done with NLP, a LISP-based natural language processing system which uses augmented phrase structure grammar ~APSG) rules (Heidorn 1975) to specify how text is to be converted into a network of nodes consisting of attribute-value pairs and how such a network can be converted into text. The first process, decoding, is done in a bottom-up, parallel processing fashion, and the inverse proc- ess, encoding, is done in a top-down, serial manner. In the current application the network which is constructed is simply a decorated parse tree, rather than a meaning representation. Because EPISTLE must deal with unrestricted input (both in terms of vocabulary and syntactic constructions), we are …

Content truncated to 500 words