Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction

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.

DCD-SSVM.pdf
PDF file

In  Transactions of the Association for Computational Linguistics

Details

TypeArticle
Pages207−218
Volume1
> Publications > Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction