Data-driven Rank Breaking for Efficient Rank Aggregation

Ashish Khetan, Sewoong Oh
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:89-98, 2016.

Abstract

Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. To reduce the computational complexity of learning the global ranking, a common practice is to use rank-breaking. Individuals’ preferences are broken into pairwise comparisons and then applied to efficient algorithms tailored for independent pairwise comparisons. However, due to the ignored dependencies, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce unbiased and accurate estimates is to treat the paired comparisons outcomes unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity in some canonical scenarios. Further, we identify how the accuracy depends on the spectral gap of a corresponding comparison graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-khetan16, title = {Data-driven Rank Breaking for Efficient Rank Aggregation}, author = {Khetan, Ashish and Oh, Sewoong}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {89--98}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/khetan16.pdf}, url = {https://proceedings.mlr.press/v48/khetan16.html}, abstract = {Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. To reduce the computational complexity of learning the global ranking, a common practice is to use rank-breaking. Individuals’ preferences are broken into pairwise comparisons and then applied to efficient algorithms tailored for independent pairwise comparisons. However, due to the ignored dependencies, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce unbiased and accurate estimates is to treat the paired comparisons outcomes unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity in some canonical scenarios. Further, we identify how the accuracy depends on the spectral gap of a corresponding comparison graph.} }
Endnote
%0 Conference Paper %T Data-driven Rank Breaking for Efficient Rank Aggregation %A Ashish Khetan %A Sewoong Oh %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-khetan16 %I PMLR %P 89--98 %U https://proceedings.mlr.press/v48/khetan16.html %V 48 %X Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. To reduce the computational complexity of learning the global ranking, a common practice is to use rank-breaking. Individuals’ preferences are broken into pairwise comparisons and then applied to efficient algorithms tailored for independent pairwise comparisons. However, due to the ignored dependencies, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce unbiased and accurate estimates is to treat the paired comparisons outcomes unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity in some canonical scenarios. Further, we identify how the accuracy depends on the spectral gap of a corresponding comparison graph.
RIS
TY - CPAPER TI - Data-driven Rank Breaking for Efficient Rank Aggregation AU - Ashish Khetan AU - Sewoong Oh BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-khetan16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 89 EP - 98 L1 - http://proceedings.mlr.press/v48/khetan16.pdf UR - https://proceedings.mlr.press/v48/khetan16.html AB - Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. To reduce the computational complexity of learning the global ranking, a common practice is to use rank-breaking. Individuals’ preferences are broken into pairwise comparisons and then applied to efficient algorithms tailored for independent pairwise comparisons. However, due to the ignored dependencies, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce unbiased and accurate estimates is to treat the paired comparisons outcomes unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity in some canonical scenarios. Further, we identify how the accuracy depends on the spectral gap of a corresponding comparison graph. ER -
APA
Khetan, A. & Oh, S.. (2016). Data-driven Rank Breaking for Efficient Rank Aggregation. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:89-98 Available from https://proceedings.mlr.press/v48/khetan16.html.

Related Material