UMass Machine Learning and Friends Lunch | Main / Exponentiated Gradient Algorithms For CR Fs And Max-Margin Markov Networks

Terry Koo

Log-linear and maximum-margin models are two commonly-used methods insupervised machine learning, and are frequently used in structured prediction problems. This talk will describe exponentiated gradient(EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function. We study both batch and online variants of the algorithm,and provide rates of convergence for both cases. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models.