egstra: EG for Structured Learning

The egstra package provides a framework for dual exponentiated-gradient optimization of part-factored structured models. The current implementation focuses on log-linear (Lafferty et al., ICML 2001) and max-margin (Taskar et al., NIPS 2003) models; both of these parameter estimation methods are popular in the literature and have strong theoretical and empirical motivation. Extensions of the dual EG updates to other optimization problems may be considered in the future. For more information on the dual EG optimization framework implemented by the egstra package, see Bartlett et al. (NIPS 2004), Globerson et al. (ICML 2007), and Collins et al. (in submission).

Download egstra

The egstra package is written in C/C++, and the full source code is distributed as a .tar.gz archive. The code is released under the GNU General Public License, which may be found here; a copy of the GPL should also be included in the above archive.

We have extensively used egstra on a GNU/Linux-x86 platform, and we have also used the package on OSX-G4 and OSX-x86 platforms. No support is guaranteed, but bug-reports and queries may be sent to maestro@csail.mit.edu.

egstra-0.2 11/9/2007 Some bug-fixes, support for regularization-path training in the dual EG optimizer, and facilities for decoding test data.
Updated on 11/27/2007 to fix an issue in which learning rates were incorrectly being scaled by 1/(N*C). Thanks to Jinhui Yuan for directing us to this issue. Note that the issue does not affect the correctness of the algorithm; the learning rates were simply behaving according to a different scale. In particular, if you were using the automatic learning-rate search facility, you should not see any noticable difference between the output of the updated code and the code with the scaling error.
egstra-0.1 10/3/2007 Initial implementation, based on a large-scale refactoring of a heavily modified version of the deeper package. Includes implementations of the dual-EG method, stochastic gradient descent, and the (averaged) perceptron.