Improved Natural Language Learning via Variance-Regularization Support Vector Machines

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 172–181, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Improved Natural Language Learning via Variance-Regularization Support Vector Machines Shane Bergsma University of Alberta sbergsma@ualberta.ca Dekang Lin Google, Inc. lindek@google.com Dale Schuurmans University of Alberta dale@cs.ualberta.ca Abstract We present a simple technique for learn- ing better SVMs using fewer training ex- amples. Rather than using the standard SVM regularization, we regularize toward low weight-variance. Our new SVM ob- jective remains a convex quadratic func- tion of the weights, and is therefore com- putationally no harder to optimize than a standard SVM. Variance regularization is shown to enable dramatic improvements in the learning rates of SVMs on three lex- ical disambiguation tasks. 1 Introduction Discriminative training is commonly used in NLP and speech to scale the contribution of different models or systems in a combined predictor. For example, discriminative training can be used to scale the contribution of the language model and translation model in machine translation (Och and Ney, 2002). Without training data, it is often rea- sonable to weight the different models equally. We propose a simple technique that exploits this intu- ition for better learning with fewer training exam- ples. We regularize the feature weights in a Sup- port Vector Machine (Cortes and Vapnik, 1995) to- ward a low-variance solution. Since the new SVM quadratic program is convex, it is no harder to op- timize than the standard SVM objective. When training data is generated through hu- man effort, faster learning saves time and money. When examples are labeled automatically, through user feedback (Joachims, 2002) or from tex- tual pseudo-examples (Smith and Eisner, 2005; Okanohara and Tsujii, 2007), faster learning can reduce the lag before a new system is useful. We demonstrate faster learning on lexical dis- ambiguation tasks. For these tasks, a system pre- dicts a label for a word in text, based on the word’s context. Possible labels include part-of- speech tags, named-entity types, and word senses. A number of disambiguation systems make pre- dictions with the help of N-gram counts from a web-scale auxiliary corpus, typically via a search- engine (Lapata and Keller, 2005) or N-gram cor- pus (Bergsma et al., 2009). When discriminative training is used to weigh the counts for classifi- cation, many of the learned feature weights have similar values. Good weights have low variance. For example, consider the task of preposition selection. A system selects the most likely prepo- sition given the context, and flags a possible error if it disagrees with the user’s choice: • I worked in Russia from 1997 to 2001. • I worked in Russia *during 1997 to 2001. Bergsma et al. (2009) use a variety of web counts to predict the correct preposition. They have fea- tures for COUNT(in Russia from), COUNT(Russia from 1997), COUNT(from 1997 to), etc. If these are high, from is predicted. Similarly, they have fea- tures for COUNT(in Russia during), COUNT(Russia during 1997), COUNT(during 1997 to). These fea- tures predict …

Content truncated to 500 words