Title: Ranking with a P-norm Push

(NYU-CS-TR874)

Authors:  Cynthia Rudin

Abstract:

We are interested in supervised ranking with the following twist: our
goal is to design algorithms that perform especially well near the top
of the ranked list, and are only required to perform sufficiently well
on the rest of the list. Towards this goal, we provide a general form
of convex objective that gives high-scoring examples more importance.
This push'' near the top of the list can be chosen arbitrarily large
or small. We choose $\ell_p$-norms to provide a specific type of push;
as $p$ becomes large, the algorithm concentrates harder near the top
of the list.

We derive a generalization bound based on the $p$-norm objective. We
then derive a corresponding boosting-style algorithm, and illustrate
the usefulness of the algorithm through experiments on UCI data.