Globerson et al. ICML 2007. Exponentiated Gradient Algorithms for Log Linear Structured Prediction

From Cohen Courses
Revision as of 16:44, 24 September 2011 by Ysim (talk | contribs)
Jump to navigationJump to search

Exponentiated gradient algorithms for log-linear structured prediction, by A. Globerson, T. Y Koo, X. Carreras, M. Collins. In Proceedings of the 24th international conference on Machine learning, 2007.

This Paper is available online [1].

Under construction

Summary

This paper describes an exponentiated gradient (EG) algorithm for training conditional log-linear models. In this paper, they propose a fast and efficient algorithm for optimizing log-linear models such as CRFs.

The common practice of optimizing the conditional log likelihood of a CRF is often via conjugate-gradient or L-BFGS algorithms (Sha_2003_shallow_parsing_with_conditional_random_fields), which typically would require at least one pass through the entire dataset before updating the weight vector. The author's approach here is an online algorithm based on exponentiated gradient updates (Kivinen & Warmuth JCSS 1997).

Brief description of the method

Consider a supervised learning setting with objects and corresponding labels , which maybe trees, sequences or other high dimensional structure. Also, assume we are given a function that maps pairs to feature vectors . Given a parameter vector , a conditional log-linear model defines a distribution over labels as:

where is a partition function.

The problem of learning from the training data is thus finding which maximizes the regularized log-likelihood:

where is the regularization parameter. The above equation has a convex dual which is derived in Lebanon and Lafferty NIPS 2001. With dual variables , and , we define:

where

The dual problem is thus

EG Algorithm

Given a set of distributions , the update equations are

where

and

Batch learning

At each iteration, is updated simultaneously with all (or subset of) the available training instances.

Online learning

At each iteration, we choose a single training instance, and update

Convergence rate of batch algorithm

To get within of the optimum parameters, we need iterations.

Experimental Result

The authors compared the performance of the EG algorithm to conjugated-gradient and L-BFGS methods.

Multiclass classification

The authors used a subset of the MNIST handwritten digits classification.

Multiclass.png

It can be seen that the EG algorithm converges considerably faster than the other methods.

Structured learning (dependency parsing)

The author used the Slovene data in UsesDataset:CoNLL-X Shared Task on Multilingual dependency parsing.

Depparse.png

It can be seen that the EG algorithm converges faster in terms of objective function and accuracy measures.