Solving MultiClass Supp ort Vector Machines with LaRank

Solving MultiClass Supp ort Vector Machines with LaRank
Antoine Bordes - LIP, Universite de Paris 6,104 Avenue du Pdt Kennedy, 75016 Paris, France Léon Bottou - NEC Laboratories America, Inc.,, USA Patrick Gallinari - LIP, Universite de Paris 6,104 Avenue du Pdt Kennedy, 75016 Paris, France Jason Weston - NEC Laboratories America, Inc.,, USA
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.

Antoine Bordes - LIP, Universite de Paris 6,104 Avenue du Pdt Kennedy, 75016 Paris, France
Léon Bottou - NEC Laboratories America, Inc.,, USA
Patrick Gallinari - LIP, Universite de Paris 6,104 Avenue du Pdt Kennedy, 75016 Paris, France
Jason Weston - NEC Laboratories America, Inc.,, USA

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.