Multi-Class Confidence Weighted Algorithms

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 496–504, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Multi-Class Confidence Weighted Algorithms Koby Crammer∗ ∗Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 {crammer,kulesza}@cis.upenn.edu Mark Dredze† Alex Kulesza∗ †Human Language Technology Center of Excellence Johns Hopkins University Baltimore, MD 21211 mdredze@cs.jhu.edu Abstract The recently introduced online confidence-weighted (CW) learning algorithm for binary classification per- forms well on many binary NLP tasks. However, for multi-class problems CW learning updates and inference cannot be computed analytically or solved as convex optimization problems as they are in the binary case. We derive learning algorithms for the multi-class CW setting and provide extensive evaluation using nine NLP datasets, including three derived from the recently released New York Times corpus. Our best algorithm out- performs state-of-the-art online and batch methods on eight of the nine tasks. We also show that the confidence information maintained during learning yields useful probabilistic information at test time. 1 Introduction Online learning algorithms such as the Perceptron process one example at a time, yielding simple and fast updates. They generally make few statisti- cal assumptions about the data and are often used for natural language problems, where high dimen- sional feature representations, e.g., bags-of-words, demand efficiency. Most online algorithms, how- ever, do not take into account the unique properties of such data, where many features are extremely rare and a few are very frequent. Dredze, Crammer and Pereira (Dredze et al., 2008; Crammer et al., 2008) recently introduced confidence weighted (CW) online learning for bi- nary prediction problems. CW learning explicitly models classifier weight uncertainty using a multi- variate Gaussian distribution over weight vectors. The learner makes online updates based on its con- fidence in the current parameters, making larger changes in the weights of infrequently observed features. Empirical evaluation has demonstrated the advantages of this approach for a number of bi- nary natural language processing (NLP) problems. In this work, we develop and test multi-class confidence weighted online learning algorithms. For binary problems, the update rule is a sim- ple convex optimization problem and inference is analytically computable. true in the multi-class setting.However, neither is We discuss sev- eral efficient online learning updates. These up- date rules can involve one, some, or all of the competing (incorrect) labels. We then perform an extensive evaluation of our algorithms using nine multi-class NLP classification problems, includ- ing three derived from the recently released New York Times corpus (Sandhaus, 2008). To the best of our knowledge, this is the first learning evalua- tion on these data. Our best algorithm outperforms state-of-the-art online algorithms and batch algo- rithms on eight of the nine datasets. Surprisingly, we find that a simple algorithm in which updates consider only a single competing label often performs as well as or better than multi- constraint variants if it makes multiple passes over the data. This is especially promising for large datasets, where the efficiency of the update can be important. In …

Content truncated to 500 words