Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction

Transactions of the Association for Computational Linguistics, 1 (2013) 207–218. Action Editor: Ben Taskar. Submitted 10/2012; Revised 3/2013; Published 5/2013. c⃝2013 Association for Computational Linguistics. Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction Ming-Wei Chang Wen-tau Yih Microsoft Research Redmond, WA 98052, USA {minchang,scottyih}@microsoft.com Abstract Due to the nature of complex NLP problems, structured prediction algorithms have been important modeling tools for a wide range of tasks. While there exists evidence showing that linear Structural Support Vector Machine (SSVM) algorithm performs better than struc- tured Perceptron, the SSVM algorithm is still less frequently chosen in the NLP community because of its relatively slow training speed. In this paper, we propose a fast and easy-to- implement dual coordinate descent algorithm for SSVMs. Unlike algorithms such as Per- ceptron and stochastic gradient descent, our method keeps track of dual variables and up- dates the weight vector more aggressively. As a result, this training process is as efficient as existing online learning methods, and yet de- rives consistently better models, as evaluated on four benchmark NLP datasets for part-of- speech tagging, named-entity recognition and dependency parsing. 1 Introduction Complex natural language processing tasks are in- herently structured. From sequence labeling prob- lems like part-of-speech tagging and named entity recognition to tree construction tasks like syntactic parsing, strong dependencies exist among the la- bels of individual components. By modeling such relations in the output space, structured output pre- diction algorithms have been shown to outperform significantly simple binary or multi-class classi- fiers (Lafferty et al., 2001; Collins, 2002; McDonald et al., 2005). Among the existing structured output prediction algorithms, the linear Structural Support Vector Machine (SSVM) algorithm (Tsochantaridis et al., 2004; Joachims et al., 2009) has shown outstanding performance in several NLP tasks, such as bilingual word alignment (Moore et al., 2007), constituency and dependency parsing (Taskar et al., 2004b; Koo et al., 2007), sentence compression (Cohn and La- pata, 2009) and document summarization (Li et al., 2009). Nevertheless, as a learning method for NLP, the SSVM algorithm has been less than popular al- gorithms such as the structured Perceptron (Collins, 2002). This may be due to the fact that cur- rent SSVM implementations often suffer from sev- eral practical issues. First, state-of-the-art imple- mentations of SSVM such as cutting plane meth- ods (Joachims et al., 2009) are typically compli- cated.1 Second, while methods like stochastic gradi- ent descent are simple to implement, tuning learning rates can be difficult. Finally, while SSVM mod- els can achieve superior accuracy, this often requires long training time. In this paper, we propose a novel optimiza- tion method for efficiently training linear SSVMs. Our method not only is easy to implement, but also has excellent training speed, competitive with both structured Perceptron (Collins, 2002) and MIRA (Crammer et al., 2005). When evaluated on several NLP tasks, including POS tagging, NER and dependency parsing, this optimization method also outperforms other approaches in terms of prediction accuracy. Our final algorithm is a dual coordinate 1Our algorithm is easy …

Content truncated to 500 words