Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction

Ming-Wei Chang, Wen-tau Yih


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 structured 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 Perceptron and stochastic gradient descent, our method keeps track of dual variables and updates the weight vector more aggressively. As a result, this training process is as efficient as existing online learning methods, and yet derives consistently better models, as evaluated on four benchmark NLP datasets for part-of-speech tagging, named-entity recognition and dependency parsing.
Anthology ID:
Q13-1017
Volume:
Transactions of the Association for Computational Linguistics, Volume 1
Month:
Year:
2013
Address:
Cambridge, MA
Editors:
Dekang Lin, Michael Collins
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
207–218
Language:
URL:
https://aclanthology.org/Q13-1017
DOI:
10.1162/tacl_a_00221
Bibkey:
Cite (ACL):
Ming-Wei Chang and Wen-tau Yih. 2013. Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction. Transactions of the Association for Computational Linguistics, 1:207–218.
Cite (Informal):
Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction (Chang & Yih, TACL 2013)
Copy Citation:
PDF:
https://aclanthology.org/Q13-1017.pdf
Data
Penn Treebank