Improved working set selection for LaRank

TY - CHAP

T1 - Improved working set selection for LaRank

AU - Tuma, Matthias

AU - Igel, Christian

N1 - Conference code: 14

PY - 2011

Y1 - 2011

N2 - LaRank is a multi-class support vector machine training algorithm for approximate online and batch learning based on sequential minimal optimization. For batch learning, LaRank performs one or more learning epochs over the training set. One epoch sequentially tests all currently excluded training examples for inclusion in the dual optimization problem, with intermittent reprocess optimization steps on examples currently included. Working set selection for one reprocess step chooses the most violating pair among variables corresponding to a random example. We propose a new working set selection scheme which exploits the gradient update necessarily following an optimization step. This makes it computationally more efficient. Among a set of candidate examples we pick the one yielding maximum gain between either of the classes being updated and a randomly chosen third class. Experiments demonstrate faster convergence on three of four benchmark datasets and no significant difference on the fourth.

AB - LaRank is a multi-class support vector machine training algorithm for approximate online and batch learning based on sequential minimal optimization. For batch learning, LaRank performs one or more learning epochs over the training set. One epoch sequentially tests all currently excluded training examples for inclusion in the dual optimization problem, with intermittent reprocess optimization steps on examples currently included. Working set selection for one reprocess step chooses the most violating pair among variables corresponding to a random example. We propose a new working set selection scheme which exploits the gradient update necessarily following an optimization step. This makes it computationally more efficient. Among a set of candidate examples we pick the one yielding maximum gain between either of the classes being updated and a randomly chosen third class. Experiments demonstrate faster convergence on three of four benchmark datasets and no significant difference on the fourth.

U2 - 10.1007/978-3-642-23672-3_40

DO - 10.1007/978-3-642-23672-3_40

M3 - Book chapter

T3 - Lecture notes in computer science

SP - 327

EP - 334

BT - Computer Analysis of Images and Patterns

A2 - Real, Pedro

A2 - Diaz-Pernil, Daniel

A2 - Molina-Abril, Helena

A2 - Berciano, Ainhoa

A2 - Kropatsch, Walter

PB - Springer

T2 - 14th International Conference on Computer Analysis of Images and Patterns

Y2 - 29 August 2011 through 31 August 2011

ER -