UMR CNRS 7253

Antoine Bordes
Antoine Bordes
Antoine Bordes
Antoine Bordes
Antoine Bordes

Site Tools


en:larank

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en:larank [2013/04/16 11:54] (current)
bordesan created
Line 1: Line 1:
 +
 +=== 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 [[http://​www.fsf.org/​licensing/​licenses/​gpl.html|GNU Public License]].
 +
 +** Description **: The source code can be downloaded here: {{en:​larank.tar.gz|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.((Thanks [[http://​nieme.lip6.fr/​Main/​HomePage|Francis]] for the bug fix.)) ​
 +
 +It is also released under the [[http://​www.fsf.org/​licensing/​licenses/​gpl.html|GNU Public License]] and can be downloaded here: {{en:​linearlarank1.2.tar.gz|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!
  

User Tools