SAG4CRF: Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
By Mark
Schmidt and Mohamed Osama Ahmed
(2015)
Last updated 12 Apr 2015.
Summary
The SAG4CRF code contains C implementations (via Matlab mex files) of the non-uniform stochastic average gradient (SAG-NUS*) method, as well as several related methods, for the problem of training chain-structured conditional random field models with L2-regularization.
The SAG-NUS method is decribed in the following paper:
Clicking on the image belows shows a poster giving an overview of this work:
The image below gives the slides for a talk on this work:
The specific methods available in the package are:
- L-BFGS: Deterministic quasi-Newton implemented via minFunc.
- Hybrid: Hybrid of deterministic quasi-Newton and stochastic gradient.
- Pegasos: Stochastic gradient method with decreasing step sizes.
- SG: Stochastic gradient method with constant step size.
- ASG: Averaged stochastic gradient method with constant step size.
- AdaGrad: Stochastic gradient method with per-variable decreasing step sizes.
- OEG: Online dual exponentiated gradient method.
- SAG: Stochastic average gradient method with constant step size.
- SAG-LS: Stochastic average gradient method with line search.
- SAG-NUS: Stochastic average gradient method with line-search and adaptive non-uniform sampling.
- SAG-NUSn: Same as above, but with less backtracking.
- SAG-NUS*: Same as above, but with strategy for skipping line-search.
These methods use a variant of the data format from the crfChain software, and take advantage of sparse operations to allow categorical features with a large number of states.
Download and Examples
To use the code, download and
unzip SAG4CRF.zip.
Once this is done, type the following in Matlab:
>> cd SAG4CRF % Change to the unzipped directory
>> addpath(genpath(pwd)) % Add all sub-directories to the path
>> mexAll % Compile mex files (not necessary on all systems)
>> example_SAG4CRF % Run/compare all the methods
>> example_SAG4CRF_warmStart % Shows how to use warm-starting and stopping criterion
Mark Schmidt > Software > SAG