##
Efficient Learning of Label Ranking by Soft Projections onto Polyhedra

*Shai Shalev-Shwartz, Yoram Singer*; 7(Jul):1567--1599, 2006.

### Abstract

We discuss the problem of learning to rank labels from a real valued
feedback associated with each label. We cast the feedback as a
preferences graph where the nodes of the graph are the labels and
edges express preferences over labels. We tackle the learning problem
by defining a loss function for comparing a predicted graph with a
feedback graph. This loss is materialized by decomposing the feedback
graph into bipartite sub-graphs. We then adopt the maximum-margin
framework which leads to a quadratic optimization problem with linear
constraints. While the size of the problem grows quadratically with
the number of the nodes in the feedback graph, we derive a problem of
a significantly smaller size and prove that it attains the same
minimum. We then describe an efficient algorithm, called SOPOPO, for
solving the reduced problem by employing a soft projection onto the
polyhedron defined by a reduced set of constraints. We also describe
and analyze a wrapper procedure for batch learning when multiple
graphs are provided for training. We conclude with a set of
experiments which show significant improvements in run time over a
state of the art interior-point algorithm.

[abs][pdf] [code]