Combinatorial Disambiguation

COMBINATORIAL DISAMBIGUATION P. S. Newman IBM Los Angeles Scientific Center 11601 Wilshire Boulevard Los Angeles, CA 90025-1738 Abstract The disambiguation of sentences is a combinatorial problem. This paper describes a method for treating it as such, directly, by adapting standard combinatorial search optimizations. Traditional disambiguation heu- ristics are applied but, instead of being embedded in individual decision procedures for specific types of ambiguities, they contribute to numerical weights that are considered by a single global optimizer. The result is increased power and simpler code. The method is being implemented for a machine translation projecl, but could be adapted to any natural language system. 1. Introduction The disambiguation of sentences is a combinatorial problem. Identification of one word sense interacts with the identification of other word senses, (I) lie addressed the chair and with constituent attachment, (2) He shot some bucks with a rifle Moreover, the attachment of one constituent interacts with the attachment of other constituents: (3) She put the vase on the table in the living room This paper describes a method of addressing the prob- lem directly, by adapting standard searctl optimization techniques, in the first section we describe the core of the method, which applies a version of best-.first search to a uniform representation of the set of possibilities. In the second section we relate the work to other approaches to preference-based disambiguation. "l"he final sections describe how the representation may he obtained from a lexicon. 2. The Search Method In the machine translation project for which this tech- nique is being developed, disambiguation begins after a parser, specifically the PLNI.P English Grammar by Jensen (1986), has identified one or more parses based primarily on syntactic considerations (including subcategorization). Words are disambiguated up to part-of-speech, but word senses are not identified. In- dividual parses may indicate alternative attachments of many kinds of constituents including prepositional phrases and relative clauses. Beginning disambiguation only after a general parse has the advantage of making clear what all the possi- bilities are, thus allowing their investigation in an ef- ficient order. Perlbrming a full parse before disamblguatlon need not consume an inordinate amount of space or time; techniques such as those used by Jensen (default rightmost prepositional phrase attachment), and "l'omita (1985) (parse forests) ade- quately control resource requirements. The parser output is first transfi)rmed so that it is represented as a set of of semantic choice points. Each choice point generally represents a constituent, it con- rains a group of weighted semantic alternatives that represent the different ways in which word-senses of tile constituent head can he associated semantically with word-senses of a higher level head. This allows word-sense and attachment alternatives to be treated uniformly. Combinatorial disamhiguation then selects the consis- tent combination of alternatives, one from cat'h choice point, that yields tile highest total weight. "1,~ illustrate the method, we use tile exlension of the classic example mentioned above: (2) lie shot some bucks with a rifle A decomposition of tile sentence into choice points el, c2, and …

Content truncated to 500 words