nips nips2013 nips2013-128 nips2013-128-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hossein Azari Soufiani, William Chen, David C. Parkes, Lirong Xia
Abstract: In this paper we propose a class of efficient Generalized Method-of-Moments (GMM) algorithms for computing parameters of the Plackett-Luce model, where the data consists of full rankings over alternatives. Our technique is based on breaking the full rankings into pairwise comparisons, and then computing parameters that satisfy a set of generalized moment conditions. We identify conditions for the output of GMM to be unique, and identify a general class of consistent and inconsistent breakings. We then show by theory and experiments that our algorithms run significantly faster than the classical Minorize-Maximization (MM) algorithm, while achieving competitive statistical efficiency. 1
[1] Hossein Azari Soufiani, David C. Parkes, and Lirong Xia. Random utility theory for social choice. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), pages 126– 134, Lake Tahoe, NV, USA, 2012.
[2] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.
[3] Marquis de Condorcet. Essai sur l’application de l’analyse a la probabilit´ des d´ cisions rendues a la e e ` ` pluralit´ des voix. Paris: L’Imprimerie Royale, 1785. e
[4] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th World Wide Web Conference, pages 613–622, 2001.
[5] Patricia Everaere, S´ bastien Konieczny, and Pierre Marquis. The strategy-proofness landscape of merge ing. Journal of Artificial Intelligence Research, 28:49–105, 2007.
[6] Lester R. Ford, Jr. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 64(8):28–33, 1957.
[7] Lars Peter Hansen. Large Sample Properties of Generalized Method of Moments Estimators. Econometrica, 50(4):1029–1054, 1982.
[8] David R. Hunter. MM algorithms for generalized Bradley-Terry models. In The Annals of Statistics, volume 32, pages 384–406, 2004.
[9] Toshihiro Kamishima. Nantonac collaborative filtering: Recommendation based on order responses. In Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining (KDD), pages 583–588, Washington, DC, USA, 2003.
[10] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
[11] Tie-Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011.
[12] Tyler Lu and Craig Boutilier. Learning Mallows models with pairwise preferences. In Proceedings of the Twenty-Eighth International Conference on Machine Learning (ICML 2011), pages 145–152, Bellevue, WA, USA, 2011.
[13] Robert Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959.
[14] Colin L. Mallows. Non-null ranking model. Biometrika, 44(1/2):114–130, 1957.
[15] Andrew Mao, Ariel D. Procaccia, and Yiling Chen. Better human computation through principled voting. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Bellevue, WA, USA, 2013.
[16] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise comparisons. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), pages 2483– 2491, Lake Tahoe, NV, USA, 2012.
[17] Robin L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society. Series C (Applied Statistics), 24(2):193–202, 1975.
[18] Louis Leon Thurstone. A law of comparative judgement. Psychological Review, 34(4):273–286, 1927. 9