nips nips2012 nips2012-165 nips2012-165-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sahand Negahban, Sewoong Oh, Devavrat Shah
Abstract: The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR’s TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining ranking, finding ‘scores’ for each object (e.g. player’s rating) is of interest to understanding the intensity of the preferences. In this paper, we propose a novel iterative rank aggregation algorithm for discovering scores for objects from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1]. 1
[1] A. Ammar and D. Shah. Communication, control, and computing (allerton), 2011, 49th annual allerton conference on. pages 776–783, September 2011.
[2] E. J. Cand` s and B. Recht. Exact matrix completion via convex optimization. Foundations of e Computational Mathematics, 9(6):717–772, 2009.
[3] R.H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. Information Theory, IEEE Transactions on, 56(6):2980 –2998, june 2010.
[4] S. Negahban and M. J. Wainwright. Restricted strong convexity and (weighted) matrix completion: Optimal bounds with noise. Journal of Machine Learning Research, 2012. To appear; posted at http://arxiv.org/abs/1009.2118.
[5] M. Condorcet. Essai sur l’application de l’analyse a la probabilit´ des d´ cisions rendues a la e e ` ` pluralit´ des voix. l’Imprimerie Royale, 1785. e
[6] K. J. Arrow. Social Choice and Individual Values. Yale University Press, 1963.
[7] M. Braverman and E. Mossel. Noisy sorting without resampling. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’08, pages 268–276. Society for Industrial and Applied Mathematics, 2008.
[8] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1955.
[9] D. R. Luce. Individual Choice Behavior. Wiley, New York, 1959.
[10] D. McFadden. Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, pages 105–142, 1973.
[11] K. T. Talluri and G. Van Ryzin. The Theory and Practice of Revenue Management. springer, 2005.
[12] M. Adler, P. Gemmell, M. Harchol-Balter, R. M. Karp, and C. Kenyon. Selection in the presence of noise: the design of playoff systems. In Proceedings of the fifth annual ACMSIAM symposium on Discrete algorithms, SODA ’94, pages 564–572. Society for Industrial and Applied Mathematics, 1994.
[13] M. E. J. Newman. Networks: An Introduction. Oxford University Press, 2010.
[14] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Seventh International World-Wide Web Conference (WWW 1998), 1998.
[15] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The eigentrust algorithm for reputation management in p2p networks. In Proceedings of the 12th international conference on World Wide Web, WWW ’03, pages 640–651, New York, NY, USA, 2003. ACM.
[16] R. Salakhutdinov and N. Srebro. Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. Technical Report abs/1002.2780v1, Toyota Institute of Technology, 2010.
[17] J. C. Duchi, L. Mackey, and M. I. Jordan. On the consistency of ranking algorithms. In Proceedings of the ICML Conference, Haifa, Israel, June 2010.
[18] L. R. Ford Jr. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 64(8):28–33, 1957.
[19] T. L. Saaty. Decision-making with the ahp: Why is the principal eigenvector necessary. European Journal of Operational Research, 145:pp. 85–91, 2003. 9