CMU-ML-10-109
Machine Learning Department
School of Computer Science, Carnegie Mellon University



CMU-ML-10-109

Learning Structured Classifiers with Dual Coordinate Ascent

Andre E.T. Martins*, Kevin Gimpel, Noah S. Smith
Eric P. Xing, Mario A.T. Figueiredo*, Pedro M.Q. Aguiar**

June 2010

CMU-ML-10-109.pdf


Keywords: Structured prediction, online learning, dual coordinate ascent

We present a unified framework for online learning of structured classifiers that handles a wide family of convex loss functions, properly including CRFs, structured SVMs, and the structured perceptron. We introduce a new aggressive online algorithm that optimizes any loss in this family. For the structured hinge loss, this algorithm reduces to 1-best MIRA; in general, it can be regarded as a dual coordinate ascent algorithm. The approximate inference scenario is also addressed. Our experiments on two NLP problems show that the algorithm converges to accurate models at least as fast as stochastic gradient descent, without the need to specify any learning rate parameter.

23 pages

*Instituto de Telecommunicações, Instituto Superior Técnico, Lisboa, Portugal
**Instituto de Sistemas e Robótica, Instituto Superior Técnico, Lisboa, Portugal


SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu