Margin-based ranking meets boosting in the middle

Conference Paper

We present several results related to ranking. We give a general margin-based bound for ranking based on the L∞ covering number of the hypothesis space. Our bound suggests that algorithms that maximize the ranking margin generalize well. We then describe a new algorithm, Smooth Margin Ranking, that precisely converges to a maximum ranking-margin solution. The algorithm is a modification of RankBoost, analogous to Approximate Coordinate Ascent Boosting. We also prove a remarkable property of AdaBoost: under very natural conditions, AdaBoost maximizes the exponentiated loss associated with the AUC and achieves the same AUC as RankBoost. This explains the empirical observations made by Cortes and Mohri, and Caruana and Niculescu-Mizil, about the excellent performance of AdaBoost as a ranking algorithm, as measured by the AUC. © Springer-Verlag Berlin Heidelberg 2005.

Full Text

Duke Authors

Cited Authors

  • Rudin, C; Cortes, C; Mohri, M; Schapire, RE

Published Date

  • January 1, 2005

Published In

Volume / Issue

  • 3559 LNAI /

Start / End Page

  • 63 - 78

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540265562

International Standard Book Number 13 (ISBN-13)

  • 9783540265566

Digital Object Identifier (DOI)

  • 10.1007/11503415_5

Citation Source

  • Scopus