Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, Martin Wainwright
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:856-865, 2015.

Abstract

Consider the problem of identifying the underlying qualities of a set of items based on measuring noisy comparisons between pairs of items. The Bradley-Terry-Luce (BTL) and Thurstone models are the most widely used parametric models for such pairwise comparison data. Working within a standard minimax framework, this paper provides sharp upper and lower bounds on the optimal error in estimating the underlying qualities under the BTL and the Thurstone models. These bounds are are topology-aware, meaning that they change qualitatively depending on the comparison graph induced by the subset of pairs being compared. Thus, in settings where the subset of pairs may be chosen, our results provide some principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors. We use this result to investigate the relative merits of cardinal and ordinal measurement schemes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-shah15, title = {{Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence}}, author = {Shah, Nihar and Balakrishnan, Sivaraman and Bradley, Joseph and Parekh, Abhay and Ramchandran, Kannan and Wainwright, Martin}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {856--865}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/shah15.pdf}, url = {https://proceedings.mlr.press/v38/shah15.html}, abstract = {Consider the problem of identifying the underlying qualities of a set of items based on measuring noisy comparisons between pairs of items. The Bradley-Terry-Luce (BTL) and Thurstone models are the most widely used parametric models for such pairwise comparison data. Working within a standard minimax framework, this paper provides sharp upper and lower bounds on the optimal error in estimating the underlying qualities under the BTL and the Thurstone models. These bounds are are topology-aware, meaning that they change qualitatively depending on the comparison graph induced by the subset of pairs being compared. Thus, in settings where the subset of pairs may be chosen, our results provide some principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors. We use this result to investigate the relative merits of cardinal and ordinal measurement schemes.} }
Endnote
%0 Conference Paper %T Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence %A Nihar Shah %A Sivaraman Balakrishnan %A Joseph Bradley %A Abhay Parekh %A Kannan Ramchandran %A Martin Wainwright %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-shah15 %I PMLR %P 856--865 %U https://proceedings.mlr.press/v38/shah15.html %V 38 %X Consider the problem of identifying the underlying qualities of a set of items based on measuring noisy comparisons between pairs of items. The Bradley-Terry-Luce (BTL) and Thurstone models are the most widely used parametric models for such pairwise comparison data. Working within a standard minimax framework, this paper provides sharp upper and lower bounds on the optimal error in estimating the underlying qualities under the BTL and the Thurstone models. These bounds are are topology-aware, meaning that they change qualitatively depending on the comparison graph induced by the subset of pairs being compared. Thus, in settings where the subset of pairs may be chosen, our results provide some principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors. We use this result to investigate the relative merits of cardinal and ordinal measurement schemes.
RIS
TY - CPAPER TI - Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence AU - Nihar Shah AU - Sivaraman Balakrishnan AU - Joseph Bradley AU - Abhay Parekh AU - Kannan Ramchandran AU - Martin Wainwright BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-shah15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 856 EP - 865 L1 - http://proceedings.mlr.press/v38/shah15.pdf UR - https://proceedings.mlr.press/v38/shah15.html AB - Consider the problem of identifying the underlying qualities of a set of items based on measuring noisy comparisons between pairs of items. The Bradley-Terry-Luce (BTL) and Thurstone models are the most widely used parametric models for such pairwise comparison data. Working within a standard minimax framework, this paper provides sharp upper and lower bounds on the optimal error in estimating the underlying qualities under the BTL and the Thurstone models. These bounds are are topology-aware, meaning that they change qualitatively depending on the comparison graph induced by the subset of pairs being compared. Thus, in settings where the subset of pairs may be chosen, our results provide some principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors. We use this result to investigate the relative merits of cardinal and ordinal measurement schemes. ER -
APA
Shah, N., Balakrishnan, S., Bradley, J., Parekh, A., Ramchandran, K. & Wainwright, M.. (2015). Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:856-865 Available from https://proceedings.mlr.press/v38/shah15.html.

Related Material