Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks

摘要

Log-linear and maximum-margin models are two commonly-used methods insupervised machine learning, and are frequently used in structuredprediction problems. Efficient learning of parameters in these modelsis therefore an important problem, and becomes a key factor whenlearning from very large data sets. This paper describesexponentiated gradient (EG) algorithms for training such models, whereEG updates are applied to the convex dual of either the log-linear ormax-margin objective function; the dual in both the log-linear andmax-margin cases corresponds to minimizing a convex function withsimplex constraints. We study both batch and online variants of thealgorithm, and provide rates of convergence for both cases. In themax-margin case, O(1/ε) EG updates are required toreach a given accuracy ε in the dual; in contrast, forlog-linear models only O(log(1/ε)) updates arerequired. For both the max-margin and log-linear cases, our boundssuggest that the online EG algorithm requires a factor of n lesscomputation to reach a desired accuracy than the batch EG algorithm,where n is the number of training examples. Our experiments confirmthat the online algorithms are much faster than the batch algorithmsin practice. We describe how the EG updates factor in a convenientway for structured prediction problems, allowing the algorithms to beefficiently applied to problems such as sequence learning or naturallanguage parsing. We perform extensive evaluation of the algorithms,comparing them to L-BFGS and stochastic gradient descent forlog-linear models, and to SVM-Struct for max-marginmodels. The algorithms are applied to a multi-classproblem as well as to a more complex large-scale parsing task. In allthese settings, the EG algorithms presented here outperform the othermethods. color="gray">