nips nips2012 nips2012-286 nips2012-286-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hossein Azari, David Parks, Lirong Xia
Abstract: Random utility theory models an agent’s preferences on alternatives by drawing a real-valued score on each alternative (typically independently) from a parameterized distribution, and then ranking the alternatives according to scores. A special case that has received significant attention is the Plackett-Luce model, for which fast inference methods for maximum likelihood estimators are available. This paper develops conditions on general random utility models that enable fast inference within a Bayesian framework through MC-EM, providing concave loglikelihood functions and bounded sets of global maxima solutions. Results on both real-world and simulated data provide support for the scalability of the approach and capability for model selection among general random utility models including Plackett-Luce. 1
[1] Steven Berry, James Levinsohn, and Ariel Pakes. Automobile prices in market equilibrium. Econometrica, 63(4):841–890, 1995.
[2] Henry David Block and Jacob Marschak. Random orderings and stochastic theories of responses. In Contributions to Probability and Statistics, pages 97–132, 1960. 3 The use of predictive likelihood allows us to evaluate the performance of the estimated parameters on the rest of the data, and is similar in this sense to cross validation for supervised learning. 8
[3] James G. Booth and James P. Hobert. Maximizing Generalized Linear Mixed Model Likelihoods with an Automated Monte Carlo EM Algorithm. JRSS. Series B, 61(1):265–285, 1999.
[4] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng, editors. Handbook of Markov Chain Monte Carlo. Chapman and Hall/CRC, 2011.
[5] Francois Caron and Arnaud Doucet. Efficient Bayesian Inference for Generalized Bradley-Terry Models. Journal of Computational and Graphical Statistics, 21(1):174–196, 2012.
[6] 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
[7] Vincent Conitzer, Matthew Rognlie, and Lirong Xia. Preference functions that score rankings and maximum likelihood estimation. In Proc. IJCAI, pages 109–115, 2009.
[8] Vincent Conitzer and Tuomas Sandholm. Common voting rules as maximum likelihood estimators. In Proc. UAI, pages 145–152, 2005.
[9] Lester R. Ford, Jr. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 64(8):28–33, 1957.
[10] Isobel Claire Gormley and Thomas Brendan Murphy. A grade of membership model for rank data. Bayesian Analysis, 4(2):265–296, 2009.
[11] Przemyslaw Grzegorzewski. Kendall’s correlation coefficient for vague preferences. Soft Computing, 13(11):1055–1061, 2009.
[12] John Guiver and Edward Snelson. Bayesian inference for Plackett-Luce ranking models. In Proc. ICML, pages 377–384, 2009.
[13] Edith Hemaspaandra, Holger Spakowski, and J¨ rg Vogel. The complexity of Kemeny elections. Theoreto ical Computer Science, 349(3):382–391, December 2005.
[14] David R. Hunter. MM algorithms for generalized Bradley-Terry models. In The Annals of Statistics, volume 32, pages 384–406, 2004.
[15] Toshihiro Kamishima. Nantonac collaborative filtering: Recommendation based on order responses. In Proc. KDD, pages 583–588, 2003.
[16] Tie-Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011.
[17] Tyler Lu and Craig Boutilier. Learning mallows models with pairwise preferences. In Proc. ICML, pages 145–152, 2011.
[18] R. Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959.
[19] Daniel McFadden. Conditional logit analysis of qualitative choice behavior. In Frontiers of Econometrics, pages 105–142, New York, NY, 1974. Academic Press.
[20] Carl N. Morris. Natural Exponential Families with Quadratic Variance Functions. Annals of Statistics, 10(1):65–80, 1982.
[21] R. L. Plackett. The analysis of permutations. JRSS. Series C, 24(2):193–202, 1975.
[22] Andr´ Pr´ kopa. Logarithmic concave measures and related topics. In Stochastic Programming, pages s e 63–82. Academic Press, 1980.
[23] Ariel D. Procaccia, Sashank J. Reddi, and Nisarg Shah. A maximum likelihood approach for selecting sets of alternatives. In Proc. UAI, 2012.
[24] Frank Proschan and Yung L. Tong. Chapter 29. log-concavity property of probability measures. FSU techinical report Number M-805, pages 57–68, 1989.
[25] Magnus Roos, J¨ rg Rothe, and Bj¨ rn Scheuermann. How to calibrate the scores of biased reviewers by o o quadratic programming. In Proc. AAAI, pages 255–260, 2011.
[26] Louis Leon Thurstone. A law of comparative judgement. Psychological Review, 34(4):273–286, 1927.
[27] Nicolaus Tideman. Collective Decisions and Voting: The Potential for Public Choice. Ashgate Publishing, 2006.
[28] Greg C. G. Wei and Martin A. Tanner. A Monte Carlo Implementation of the EM Algorithm and the Poor Man’s Data Augmentation Algorithms. JASA, 85(411):699–704, 1990.
[29] Lirong Xia and Vincent Conitzer. A maximum likelihood approach towards aggregating partial orders. In Proc. IJCAI, pages 446–451, 2011.
[30] Lirong Xia, Vincent Conitzer, and J´ rˆ me Lang. Aggregating preferences in multi-issue domains by using eo maximum likelihood estimators. In Proc. AAMAS, pages 399–406, 2010.
[31] John I. Jr. Yellott. The relationship between Luce’s Choice Axiom, Thurstone’s Theory of Comparative Judgment, and the double exponential distribution. J. of Mathematical Psychology, 15(2):109–144, 1977.
[32] H. Peyton Young. Optimal voting rules. Journal of Economic Perspectives, 9(1):51–64, 1995. 9