Boosting Applied to Tagging and PP Attachment

Boosting Applied to Tagging and PP Attachment Steven Abney {abney, Robert E. Schapire AT&T Labs - Research 180 Park Avenue Florham Park, NJ 07932 schapire, Yoram Singer singer}@research.att.com Abstract Boosting is a machine learning algorithm that is not well known in computational linguistics. We ap- ply it to part-of-speech tagging and prepositional phrase attachment. Performance is very encourag- ing. We also show how to improve data quality by using boosting to identify annotation errors. 1 Introduction Boosting is a machine learning algorithm that has been applied successfully to a variety of problems, but is almost unknown in computational linguis- tics. We describe experiments in which we apply boosting to part-of-speech tagging and prepositional phrase attachment. Results on both PP-attachment and tagging are within sampling error of the best previous results. The current best technique for PP-attachment (backed-off density estimation) does not perform well for tagging, and the current best technique for tagging (maxent) is below state-of-the-art on PP- attachment. Boosting achieves state-of-the-art per- formance on both tasks simultaneously. The idea of boosting is to combine many sim- ple "rules of thumb," such as "the current word is a noun if the previous word is the." Such rules of- ten give incorrect classifications. The main idea of boosting is to combine many such rules in a prin- cipled manner to produce a single highly accurate classification rule. There are similarities between boosting and transformation-based learning (Brill, 1993): both build classifiers by combining simple rules, and both are noted for their resistance to overfitting. But boosting, unlike transformation-based learning, rests on firm theoretical foundations; and it outper- forms transformation-based learning in our experi- ments. There are also superficial similarities between boosting and maxent. In both, the parameters are weights in a log-linear function. But in maxent, the log-linear function defines a probability, and the ob- jective is to maximize likelihood, which may not minimize classification error. In boosting, the log- linear function defines a hyperplane dividing exam- ples into (binary) classes, and boosting minimizes classification error directly. Hence boosting is usu- ally more appropriate when the objective is classifi- cation rather than density estimation. A notable property of boosting is that it maintains an explicit measure of how difficult it finds partic- ular training examples to be. The most difficult ex- amples are very often mislabelled examples. Hence, boosting can contribute to improving data quality by identifying annotation errors. 2 The boosting algorithm AdaBoost In this section, we describe the boosting algo- rithm AdaBoost that we used in our experiments. AdaBoost was first introduced by Freund and Schapire (1997); the version described here is a (slightly simplified) version of the one given by Schapire and Singer (1998). A formal descrip- tion of AdaBoost is shown in Figure 1. AdaBoost takes as input a training set of m labeled exam- ples ((xl,yl),..., (Xrn, Ym)) where xi is an exam- ple (say, as described by a vector of attribute val- ues), and Yi E {-1, -l--l} is the label associated with xi. For now, …

Content truncated to 500 words