Margin-based ranking meets boosting in the middle

Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationLearning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
PublisherSpringer Verlag
Pages63-78
Number of pages16
ISBN (Print)3540265562, 9783540265566
DOIs
StatePublished - 2005
Event18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy
Duration: Jun 27 2005Jun 30 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3559 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory
CountryItaly
CityBertinoro
Period6/27/056/30/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Margin-based ranking meets boosting in the middle'. Together they form a unique fingerprint.

Cite this