UMR CNRS 7253

Antoine Bordes
Antoine Bordes
Antoine Bordes
Antoine Bordes
Antoine Bordes

Site Tools


en:larank

Introduction

Optimization algorithms for large margin multiclass recognizers are often too costly to handle ambitious problems with structured outputs and exponential numbers of classes. Optimization algorithms that rely on the full gradient are not effective because, unlike the solution, the gradient is not sparse and is very large.

The LaRank algorithm sidesteps this difficulty by relying on a randomized exploration inspired by the perceptron algorithm. We show that this approach is competitive with gradient based optimizers on simple multiclass problems. Furthermore, a single LaRank pass over the training examples delivers test error rates that are nearly as good as those of the final solution.

For details, see the paper Solving MultiClass Support Vector Machines with LaRank by Antoine Bordes, Léon Bottou, Patrick Gallinari and Jason Weston. in Proceedings of ICML 2007.

General Implementation

We provide an implementation of LaRank under the GNU Public License.

Description : The source code can be downloaded here: larank.tar.gz. It contains a C++ library implementing the kernel cache and the basic operations. Two additional programs, la_rank_learn and la_rank_classify can be used to run experiments. la_rank_learn learns models for multiclass classification with LaRank. la_rank_classify uses a model learned with LaRank to make predictions.

The functions can be built by using make in the LaRank directory. Calling these programs without argument displays a summary of command line arguments and options. They take as arguments files of the format SVMlight/LibSVM.

Examples : The table below displays the results obtained with this implementation in a single training pass on the datasets and using the parameters of the LaRank paper. This implementation is faster than the one used in the LaRank paper.

Train. Time Comp. Kernels Dual Test. Error
LETTER 265 sec. 49M 518 2.6%
USPS 40 sec. 7.8M 505 4.25%
MNIST 4800 sec. 441M 3640 1.40%
INEX 255 sec. 17.5M 225800 26.91%

Fast Implementation using Linear Kernel

We present here a simpler implementation of LaRank designed for the use of a linear kernel function only.1)

It is also released under the GNU Public License and can be downloaded here: linearlarank1.2.tar.gz. This implementation is designed for large scale datasets with a large amount of training examples and/or features. It does not use any cache for kernel value. This version provides the same type of C++ library with the possibility to build two programs la_rank_learn and la_rank_classify.

This is is much faster than the regular version. See the results obtained using this implementation on the INEX dataset.

Train. Time Comp. Kernels Dual Test. Error
INEX 10 sec. n/a 226800 26.74%

It is 25x faster on this dataset!

1)
Thanks Francis for the bug fix.

User Tools