Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues

Nihar Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, Martin Wainwright
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:11-20, 2016.

Abstract

There are various parametric models for analyzing pairwise comparison data, including the Bradley-Terry-Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this work, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-shahb16, title = {Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues}, author = {Shah, Nihar and Balakrishnan, Sivaraman and Guntuboyina, Aditya and Wainwright, Martin}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {11--20}, 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/shahb16.pdf}, url = {https://proceedings.mlr.press/v48/shahb16.html}, abstract = {There are various parametric models for analyzing pairwise comparison data, including the Bradley-Terry-Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this work, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations.} }
Endnote
%0 Conference Paper %T Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues %A Nihar Shah %A Sivaraman Balakrishnan %A Aditya Guntuboyina %A Martin Wainwright %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-shahb16 %I PMLR %P 11--20 %U https://proceedings.mlr.press/v48/shahb16.html %V 48 %X There are various parametric models for analyzing pairwise comparison data, including the Bradley-Terry-Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this work, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations.
RIS
TY - CPAPER TI - Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues AU - Nihar Shah AU - Sivaraman Balakrishnan AU - Aditya Guntuboyina AU - Martin Wainwright 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-shahb16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 11 EP - 20 L1 - http://proceedings.mlr.press/v48/shahb16.pdf UR - https://proceedings.mlr.press/v48/shahb16.html AB - There are various parametric models for analyzing pairwise comparison data, including the Bradley-Terry-Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this work, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations. ER -
APA
Shah, N., Balakrishnan, S., Guntuboyina, A. & Wainwright, M.. (2016). Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:11-20 Available from https://proceedings.mlr.press/v48/shahb16.html.

Related Material