Margin-Based Ranking Meets Boosting in the Middle

by: Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E Schapire

Learning Theory (2005), pp. 63-78.

View FullText article

Springer (DOI)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

Vezhnick, pprett

Find related articles with these CiteULike tags

adaboost, learning2rank, margin, no-tag, rankboost

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.

@incollection{citeulike:1704317, 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.}, author = {Rudin, Cynthia and Cortes, Corinna and Mohri, Mehryar and Schapire, Robert E. }, citeulike-article-id = {1704317}, doi = {10.1007/11503415\_5}, journal = {Learning Theory}, pages = {63--78}, posted-at = {2007-09-28 09:27:08}, priority = {4}, title = {Margin-Based Ranking Meets Boosting in the Middle}, url = {http://dx.doi.org/10.1007/11503415\_5}, year = {2005} }

RIS record

TY - CHAP ID - citeulike:1704317 L3 - citeulike-article-id:1704317 TI - Margin-Based Ranking Meets Boosting in the Middle JF - Learning Theory SP - 63 EP - 78 N2 - 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. AU - Rudin, Cynthia AU - Cortes, Corinna AU - Mohri, Mehryar AU - Schapire, Robert PY - 2005/// UR - http://dx.doi.org/10.1007/11503415_5 ER -

RIS BibTeX