Efficient Ranking from Pairwise Comparisons

Fabian Wauthier, Michael Jordan, Nebojsa Jojic
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):109-117, 2013.

Abstract

The ranking of n objects based on pairwise comparisons is a core machine learning problem, arising in recommender systems, ad placement, player ranking, biological applications and others. In many practical situations the true pairwise comparisons cannot be actively measured, but a subset of all n(n-1)/2 comparisons is passively and noisily observed. Optimization algorithms (e.g., the SVM) could be used to predict a ranking with fixed expected Kendall tau distance, while achieving an Ω(n) lower bound on the corresponding sample complexity. However, due to their centralized structure they are difficult to extend to online or distributed settings. In this paper we show that much simpler algorithms can match the same Ω(n) lower bound in expectation. Furthermore, if an average of O(n\log(n)) binary comparisons are measured, then one algorithm recovers the true ranking in a uniform sense, while the other predicts the ranking more accurately near the top than the bottom. We discuss extensions to online and distributed ranking, with benefits over traditional alternatives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-wauthier13, title = {Efficient Ranking from Pairwise Comparisons}, author = {Wauthier, Fabian and Jordan, Michael and Jojic, Nebojsa}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {109--117}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/wauthier13.pdf}, url = {https://proceedings.mlr.press/v28/wauthier13.html}, abstract = {The ranking of n objects based on pairwise comparisons is a core machine learning problem, arising in recommender systems, ad placement, player ranking, biological applications and others. In many practical situations the true pairwise comparisons cannot be actively measured, but a subset of all n(n-1)/2 comparisons is passively and noisily observed. Optimization algorithms (e.g., the SVM) could be used to predict a ranking with fixed expected Kendall tau distance, while achieving an Ω(n) lower bound on the corresponding sample complexity. However, due to their centralized structure they are difficult to extend to online or distributed settings. In this paper we show that much simpler algorithms can match the same Ω(n) lower bound in expectation. Furthermore, if an average of O(n\log(n)) binary comparisons are measured, then one algorithm recovers the true ranking in a uniform sense, while the other predicts the ranking more accurately near the top than the bottom. We discuss extensions to online and distributed ranking, with benefits over traditional alternatives. } }
Endnote
%0 Conference Paper %T Efficient Ranking from Pairwise Comparisons %A Fabian Wauthier %A Michael Jordan %A Nebojsa Jojic %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-wauthier13 %I PMLR %P 109--117 %U https://proceedings.mlr.press/v28/wauthier13.html %V 28 %N 3 %X The ranking of n objects based on pairwise comparisons is a core machine learning problem, arising in recommender systems, ad placement, player ranking, biological applications and others. In many practical situations the true pairwise comparisons cannot be actively measured, but a subset of all n(n-1)/2 comparisons is passively and noisily observed. Optimization algorithms (e.g., the SVM) could be used to predict a ranking with fixed expected Kendall tau distance, while achieving an Ω(n) lower bound on the corresponding sample complexity. However, due to their centralized structure they are difficult to extend to online or distributed settings. In this paper we show that much simpler algorithms can match the same Ω(n) lower bound in expectation. Furthermore, if an average of O(n\log(n)) binary comparisons are measured, then one algorithm recovers the true ranking in a uniform sense, while the other predicts the ranking more accurately near the top than the bottom. We discuss extensions to online and distributed ranking, with benefits over traditional alternatives.
RIS
TY - CPAPER TI - Efficient Ranking from Pairwise Comparisons AU - Fabian Wauthier AU - Michael Jordan AU - Nebojsa Jojic BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-wauthier13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 109 EP - 117 L1 - http://proceedings.mlr.press/v28/wauthier13.pdf UR - https://proceedings.mlr.press/v28/wauthier13.html AB - The ranking of n objects based on pairwise comparisons is a core machine learning problem, arising in recommender systems, ad placement, player ranking, biological applications and others. In many practical situations the true pairwise comparisons cannot be actively measured, but a subset of all n(n-1)/2 comparisons is passively and noisily observed. Optimization algorithms (e.g., the SVM) could be used to predict a ranking with fixed expected Kendall tau distance, while achieving an Ω(n) lower bound on the corresponding sample complexity. However, due to their centralized structure they are difficult to extend to online or distributed settings. In this paper we show that much simpler algorithms can match the same Ω(n) lower bound in expectation. Furthermore, if an average of O(n\log(n)) binary comparisons are measured, then one algorithm recovers the true ranking in a uniform sense, while the other predicts the ranking more accurately near the top than the bottom. We discuss extensions to online and distributed ranking, with benefits over traditional alternatives. ER -
APA
Wauthier, F., Jordan, M. & Jojic, N.. (2013). Efficient Ranking from Pairwise Comparisons. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):109-117 Available from https://proceedings.mlr.press/v28/wauthier13.html.

Related Material