DECISION LISTS FOR LEXICAL AMBIGUITY RESOLUTION: Application to Accent Restoration in Spanish and French

DECISION LISTS FOR LEXICAL AMBIGUITY RESOLUTION: Application to Accent Restoration in Spanish and French David Yarowsky* Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 yarowsky©unagi, cis. upenn, edu Abstract This paper presents a statistical decision procedure for lexical ambiguity resolution. The algorithm exploits both local syntactic patterns and more distant collo- cational evidence, generating an efficient, effective, and highly perspicuous recipe for resolving a given ambigu- ity. By identifying and utilizing only the single best dis- ambiguating evidence in a target context, the algorithm avoids the problematic complex modeling of statistical dependencies. Although directly applicable to a wide class of ambiguities, the algorithm is described and eval- uated in a realistic case study, the problem of restoring missing accents in Spanish and French text. Current accuracy exceeds 99% on the full task, and typically is over 90% for even the most difficult ambiguities. INTRODUCTION This paper presents a general-purpose statistical deci- sion procedure for lexical ambiguity resolution based on decision lists (Rivest, 1987). The algorithm considers multiple types of evidence in the context of an ambigu- ous word, exploiting differences in collocational distri- bution as measured by log-likelihoods. Unlike standard Bayesian approaches, however, it does not combine the log-likelihoods of all available pieces of contextual evi- dence, but bases its classifications solely on the single most reliable piece of evidence identified in the target context. Perhaps surprisingly, this strategy appears to yield the same or even slightly better precision than the combination of evidence approach when trained on the same features. It also brings with it several ad- ditional advantages, the greatest of which is the abil- ity to include multiple, highly non-independent sources of evidence without complex modeling of dependencies. Some other advantages are significant simplicity and ease of implementation, transparent understandability *This research was supported by an NDSEG Fellowship, ARPA grant N00014-90-J-1863 and ARO grant DAAL 03- 89-C0031 PRI. The author is also affiliated with the Lin- guistics Research Department of AT&T Bell Laboratories, and greatly appreciates the use of its resources in support of this work. He would like to thank Jason Eisner, Libby Levison, Mark Liberman, Mitch Marcus, Joseph Rosenzweig and Mark Zeren for their valuable feedback. of the resulting decision list, and easy adaptability to new domains. The particular domain chosen here as a case study is the problem of restoring missing accents 1 to Spanish and French text. Because it requires the res- olution of both semantic and syntactic ambiguity, and offers an objective ground truth for automatic evalua- tion, it is particularly well suited for demonstrating and testing the capabilities of the given algorithm. It is also a practical problem with immediate application. PROBLEM DESCRIPTION The general problem considered here is the resolu- tion of lexical ambiguity, both syntactic and seman- tic, based on properties of the surrounding context. Accent restoration is merely an instance of a closely- related class of problems including word-sense disam- biguation, word choice selection in machine translation, homograph and homophone disambiguation, and capi- talization …

Content truncated to 500 words