Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction

Ming-Wei Chang and 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.

Details

Publication typeArticle
Published inTransactions of the Association for Computational Linguistics
Pages207−218
Volume1
PublisherACL – Association for Computational Linguistics
> Publications > Dual Coordinate Descent Algorithms for Efficient Large Margin Structured Prediction