
Research
Abstracts  2007 
Exponentiated Gradient Algorithms for LogLinear Structured PredictionAmir Globerson, Xavier Carreras, Terry Koo & Michael CollinsAbstractConditional loglinear models are a popular method for structured prediction. Efficient learning of the model parameters is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes an exponentiated gradient (EG) algorithm for training such models. EG is applied to the convex dual of the maximum likelihood objective; this results in both sequential and parallel update algorithms, where in the sequential algorithm parameters are updated in an online fashion. We provide a convergence proof for both algorithms, which also applies to maxmargin learning, simplifying previous results on EG learning of maxmargin models, and leading to a tighter bound on the convergence rate for these models. Experimental results on a large scale parsing task show that the proposed algorithm converges much faster than a conjugategradient approach both in terms of optimization objective and test error. OverviewStructured learning problems involve the prediction of objects such as sequences or parse trees. The set of possible objects may be exponentially large, but each object typically has rich internal structure. Several models that implement learning in this scenario have been proposed over the last few years [1,2]. The underlying idea in these methods is to classify each instance into a label using a prediction rule Here is a feature vector, and is a set of weights that are learned from labeled data. The methods differ in their approach to learning the weight vector. The Maximum Margin Markov Networks of Taskar et al. [1] rely on margin maximization, while the Conditional Random Fields (CRFs) of Lafferty et al. [2] construct a conditional loglinear model and maximize the likelihood of the observed data. Empirically both methods have shown promising results on complex structured labeling tasks. In both CRFs and maxmargin models, the learning task involves an optimization problem which is convex, and therefore does not suffer from problems with local minima. However, finding the optimal weight vector w may still be computationally intensive, especially for very large data sets with millions of data points. In the current paper, we propose a fast and efficient algorithm for optimizing loglinear models such as CRFs. To highlight the difficulty we address, consider the common practice of optimizing the conditional loglikelihood of a CRF using conjugate gradient algorithms, or other methods such as LBFGS [3]. Any update to the weight vector would require at least one pass over the data set, and typically more due to linesearch calls. Since conjugate gradient convergence typically requires several tens of iterations if not hundreds, the above optimization scheme can turn out to be quite slow. It would seem advantageous to have an algorithm that updates the weight vector after every sample point, instead of after the entire data set. One example of such algorithms is stochastic gradient descent and its variants [4]. A different approach, which we employ here, was first suggested by Jaakkola and Haussler [5]. It proceeds via the convex dual problem of the likelihood maximization problem. As in the dual Support Vector Machine (SVM) problem, the dual variables correspond to data points . Specifically, to every point there corresponds a distribution satisfying: It is thus tempting to optimize for each separately, much like the Sequential Minimization Optimization (SMO) algorithm [6] often used to optimize SVMs. Several authors (e.g. Keerthi et al. [7]) have studied such an approach, using different optimization schemes, and ways of maintaining the distribution constraints on . Here we present an algorithm based on Exponentiated Gradient (EG) updates [8]. These updates are specifically designed for optimizing over distributions, and were recently used in the maxmargin setting [9]. Our use of EG results in very simple updates that can be performed for every sample point, giving an onlinelike algorithm. We provide a convergence proof of the algorithm, using a symmetrization of the KL divergence. Our proof is relatively simple, and applies both to the maxmargin and loglinear settings. Furthermore, we show that convergence can be obtained for the maxmargin case with a higher learning rate than that used in the proof of Bartlett et al. [9], giving a tighter bound on the rate of convergence. Finally, we compare our EG algorithm to a conjugate gradient optimization on a standard multiclass learning problem, and a complex natural language parsing problem. In both settings we show that EG converges much faster than conjugate gradient, both in terms of objective function and classification error. Primal and Dual Problems for LogLinear ModelsConsider a supervised learning setting where we are given training data . A globallynormalized loglinear model defines the following conditional probability distribution over labels: where is the partition function and is an appropriate feature mapping. We wish to find the weights that maximize the regularized loglikelihood, which yields the following convex primal optimization problem: where is the regularization constant. The above has an equivalent convex dual, as derived by Lebanon & Lafferty [10]. For each example and label, introduce the dual variable , and define vectors as aggregates of these duals. Let be the set of distributions over the labels for a given example. The dual problem can be expressed as where the dual objective function is Exponentiated Gradient AlgorithmsThe method of Exponentiated Gradient (EG) updates was first introduced by Kivinen and Warmuth [8] and extended to structured learning by Bartlett et al. [9]. We briefly describe batch and onlinelike methods for performing EG updates on our dual optimization problem (cf. DLL above). Given an initial distribution and the gradient of the objective function at that point, the EG update is defined by where is a constant learning rate that controls how strongly the algorithm adjusts the parameters. Note that the normalization of ensures that the updated parameters form a distribution. For convenience, define The batch and onlinelike EG updates are then simple to describe. In the batch setting, we fix , compute all gradients and update all of the duals simultaneously via In the online setting, we consider each in sequence, compute the appropriate gradient and perform the update Convergence of the Batch and Online UpdatesWe briefly sketch our proof of convergence. The analysis relies on manipulations of three divergence measures between sets of distributions : Here, is the cumulative KL divergence between the two sets of distributions, is the Mahalanobis distance (parameterized by the matrix ), and is the Bregman divergence (parameterized by a strictly convex function ). For both loglinear and maxmargin definitions of the dual objective , it is possible to obtain a constant learning rate for which By the definition of and , it follows that This result allows us to deduce that both batch and onlinelike EG updates will eventually converge at the optimum of the dual problem DLL. Furthermore, by applying an additional lemma from Kivinen and Warmuth [8], we can prove that the batch algorithm will converge within of the optimum after updates. Unfortunately, this lemma does not apply to the onlinelike EG updating strategy, and we have not yet proven a rate of convergence for this strategy. However, our experiments indicate that onlinelike EG updates converge considerably faster than stateoftheart batch optimization approaches such as conjugate gradient descent and quasiNewton methods (e.g., LBFGS). AcknowledgementsThis work was funded by a grant from the National Science Foundation (DMS0434222) and a grant from NTT, Agmt. Dtd. 6/21/1998. In addition, A. Globerson is supported by a postdoctoral fellowship from the Rothschild Foundation  Yad Hanadiv. References:[1] B. Taskar, C. Guestrin, and D. Koller. Maxmargin markov networks. In NIPS, 2004. [2] J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML, 2001. [3] Sha, F., and Pereira, F. Shallow parsing with conditional random fields. In Proceedings of HLTNAACL, 2003. [4] Vishwanathan, S. N., Schraudolph, N. N., Schmidt, M.W., and Murphy, K. P. Accelerated training of conditional random fields with stochastic gradient methods. In Proceedings of ICML, 2006. [5] Jaakkola, T., and Haussler, D. Probabilistic kernel regression models. In Proceedings of AISTATS, 1999. [6] Platt, J. Fast training of support vector machines using sequential minimal optimization. In Advances in kernel methods  support vector learning. MIT Press, 1998. [7] Keerthi, S., Duan, K., Shevade, S., and Poo, A. N. A fast dual algorithm for kernel logistic regression. Machine Learning, 61, 151165, 2005. [8] Kivinen, J., and Warmuth, M. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132, 163, 1997. [9] Bartlett, P., Collins, M., Taskar, B., and McAllester, D. Exponentiated gradient algorithms for largemargin structured classification. In NIPS, 2004. [10] Lebanon, G, and Lafferty, J. Boosting and maximum likelihood for exponential models. In NIPS, 2004. 

