Bayes-Optimal Scorers for Bipartite Ranking

Aditya Krishna Menon, Robert C. Williamson
Proceedings of The 27th Conference on Learning Theory, PMLR 35:68-106, 2014.

Abstract

We address the following seemingly simple question: what is the Bayes-optimal scorer for a bipartite ranking risk? The answer to this question helps establish the consistency of the minimisation of surrogate bipartite risks, and elucidates the relationship between bipartite ranking and other established learning problems. We show that the answer is non-trivial in general, but may be easily determined for certain special cases using the theory of proper losses. Our analysis immediately establishes equivalences between several seemingly disparate risks for bipartite ranking, such as minimising a suitable class-probability estimation risk, and minimising the p-norm push risk proposed by Rudin (2009).

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-menon14, title = {Bayes-Optimal Scorers for Bipartite Ranking}, author = {Menon, Aditya Krishna and Williamson, Robert C.}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {68--106}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/menon14.pdf}, url = {https://proceedings.mlr.press/v35/menon14.html}, abstract = {We address the following seemingly simple question: what is the Bayes-optimal scorer for a bipartite ranking risk? The answer to this question helps establish the consistency of the minimisation of surrogate bipartite risks, and elucidates the relationship between bipartite ranking and other established learning problems. We show that the answer is non-trivial in general, but may be easily determined for certain special cases using the theory of proper losses. Our analysis immediately establishes equivalences between several seemingly disparate risks for bipartite ranking, such as minimising a suitable class-probability estimation risk, and minimising the p-norm push risk proposed by Rudin (2009).} }
Endnote
%0 Conference Paper %T Bayes-Optimal Scorers for Bipartite Ranking %A Aditya Krishna Menon %A Robert C. Williamson %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-menon14 %I PMLR %P 68--106 %U https://proceedings.mlr.press/v35/menon14.html %V 35 %X We address the following seemingly simple question: what is the Bayes-optimal scorer for a bipartite ranking risk? The answer to this question helps establish the consistency of the minimisation of surrogate bipartite risks, and elucidates the relationship between bipartite ranking and other established learning problems. We show that the answer is non-trivial in general, but may be easily determined for certain special cases using the theory of proper losses. Our analysis immediately establishes equivalences between several seemingly disparate risks for bipartite ranking, such as minimising a suitable class-probability estimation risk, and minimising the p-norm push risk proposed by Rudin (2009).
RIS
TY - CPAPER TI - Bayes-Optimal Scorers for Bipartite Ranking AU - Aditya Krishna Menon AU - Robert C. Williamson BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-menon14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 68 EP - 106 L1 - http://proceedings.mlr.press/v35/menon14.pdf UR - https://proceedings.mlr.press/v35/menon14.html AB - We address the following seemingly simple question: what is the Bayes-optimal scorer for a bipartite ranking risk? The answer to this question helps establish the consistency of the minimisation of surrogate bipartite risks, and elucidates the relationship between bipartite ranking and other established learning problems. We show that the answer is non-trivial in general, but may be easily determined for certain special cases using the theory of proper losses. Our analysis immediately establishes equivalences between several seemingly disparate risks for bipartite ranking, such as minimising a suitable class-probability estimation risk, and minimising the p-norm push risk proposed by Rudin (2009). ER -
APA
Menon, A.K. & Williamson, R.C.. (2014). Bayes-Optimal Scorers for Bipartite Ranking. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:68-106 Available from https://proceedings.mlr.press/v35/menon14.html.

Related Material