Margin-based Ranking and an Equivalence between AdaBoost and RankBoost
We study boosting algorithms for learning to rank. We give a general margin-based bound for ranking based on covering numbers for the hypothesis space. Our bound suggests that algorithms that maximize the ranking margin will generalize well. We then describe a new algorithm, smooth margin ranking...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
MIT Press
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/52342 |
| _version_ | 1826203724653002752 |
|---|---|
| author | Rudin, Cynthia Schapire, Robert E. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Rudin, Cynthia Schapire, Robert E. |
| author_sort | Rudin, Cynthia |
| collection | MIT |
| description | We study boosting algorithms for learning to rank. We give a general margin-based bound for
ranking based on covering numbers for the hypothesis space. Our bound suggests that algorithms
that maximize the ranking margin will 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.” Finally,
we prove that AdaBoost and RankBoost are equally good for the problems of bipartite ranking and
classification in terms of their asymptotic behavior on the training set. Under natural conditions,
AdaBoost achieves an area under the ROC curve that is equally as good as RankBoost’s; furthermore,
RankBoost, when given a specific intercept, achieves a misclassification error that is as good
as AdaBoost’s. This may help to explain the empirical observations made by Cortes andMohri, and
Caruana and Niculescu-Mizil, about the excellent performance of AdaBoost as a bipartite ranking
algorithm, as measured by the area under the ROC curve. |
| first_indexed | 2024-09-23T12:42:23Z |
| format | Article |
| id | mit-1721.1/52342 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:42:23Z |
| publishDate | 2010 |
| publisher | MIT Press |
| record_format | dspace |
| spelling | mit-1721.1/523422022-09-28T09:31:50Z Margin-based Ranking and an Equivalence between AdaBoost and RankBoost Rudin, Cynthia Schapire, Robert E. Sloan School of Management Rudin, Cynthia Rudin, Cynthia area under the ROC curve AdaBoost generalization bounds RankBoost ranking We study boosting algorithms for learning to rank. We give a general margin-based bound for ranking based on covering numbers for the hypothesis space. Our bound suggests that algorithms that maximize the ranking margin will 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.” Finally, we prove that AdaBoost and RankBoost are equally good for the problems of bipartite ranking and classification in terms of their asymptotic behavior on the training set. Under natural conditions, AdaBoost achieves an area under the ROC curve that is equally as good as RankBoost’s; furthermore, RankBoost, when given a specific intercept, achieves a misclassification error that is as good as AdaBoost’s. This may help to explain the empirical observations made by Cortes andMohri, and Caruana and Niculescu-Mizil, about the excellent performance of AdaBoost as a bipartite ranking algorithm, as measured by the area under the ROC curve. 2010-03-05T16:33:37Z 2010-03-05T16:33:37Z 2009-10 2009-07 Article http://purl.org/eprint/type/JournalArticle 1532-4435 http://hdl.handle.net/1721.1/52342 Rudin, Cynthia, and Robert E. Schapire. “Margin-based Ranking and an Equivalence between AdaBoost and RankBoost.” Journal of Machine Learning Research 10 (2009): 2193-2232. en_US http://www.jmlr.org/papers/volume10/rudin09a/rudin09a.pdf Journal of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf MIT Press JMLR at author request |
| spellingShingle | area under the ROC curve AdaBoost generalization bounds RankBoost ranking Rudin, Cynthia Schapire, Robert E. Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title | Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title_full | Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title_fullStr | Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title_full_unstemmed | Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title_short | Margin-based Ranking and an Equivalence between AdaBoost and RankBoost |
| title_sort | margin based ranking and an equivalence between adaboost and rankboost |
| topic | area under the ROC curve AdaBoost generalization bounds RankBoost ranking |
| url | http://hdl.handle.net/1721.1/52342 |
| work_keys_str_mv | AT rudincynthia marginbasedrankingandanequivalencebetweenadaboostandrankboost AT schapireroberte marginbasedrankingandanequivalencebetweenadaboostandrankboost |