Ranking with a P-norm push

Conference Paper

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 to be arbitrarily large or small. We choose ℓ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. We prove that the minimizer of the objective is unique in a specific sense. © Springer-Verlag Berlin Heidelberg 2006.

Full Text

Duke Authors

Cited Authors

  • Rudin, C

Published Date

  • January 1, 2006

Published In

Volume / Issue

  • 4005 LNAI /

Start / End Page

  • 589 - 604

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540352945

International Standard Book Number 13 (ISBN-13)

  • 9783540352945

Digital Object Identifier (DOI)

  • 10.1007/11776420_43

Citation Source

  • Scopus