jmlr jmlr2011 jmlr2011-2 jmlr2011-2-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ruby C. Weng, Chih-Jen Lin
Abstract: This paper describes a Bayesian approximation method to obtain online ranking algorithms for games with multiple teams and multiple players. Recently for Internet games large online ranking systems are much needed. We consider game models in which a k-team game is treated as several two-team games. By approximating the expectation of teams’ (or players’) performances, we derive simple analytic update rules. These update rules, without numerical integrations, are very easy to interpret and implement. Experiments on game data show that the accuracy of our approach is competitive with state of the art systems such as TrueSkill, but the running time as well as the code is much shorter. Keywords: Bayesian inference, rating system, Bradley-Terry model, Thurstone-Mosteller model, Plackett-Luce model
John Aitchison and Colin B. Begg. Statistical diagnosis when basic cases are not classified with certainty. Biometrika, 63:1–12, 1976. Ralph A. Bradley and Milton E. Terry. The rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324–345, 1952. Arpad E. Elo. The Rating of Chessplayers, Past and Present. Arco Publishing, New York, 2nd edition, 1986. Mark E. Glickman. Paired Comparison Models with Time-varying Parameters. PhD thesis, Department of Statistics, Harvard University, 1993. Mark E. Glickman. Parameter estimation in large dynamic paired comparison experiments. Applied Statistics, 48:377–394, 1999. John Guiver and Edward Snelson. Bayesian inference for Plackett-Luce ranking model. In Proceedings of the Twenty Sixth International Conference on Machine Learning (ICML), 2009. 299 W ENG AND L IN Ralf Herbrich, Tom Minka, and Thore Graepel. TrueSkillTM : A Bayesian skill rating system. In Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA, 2007. Jim C. Huang and Brendan J. Frey. Cumulative distribution networks and the derivative-sumproduct algorithm. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI), 2008. Tzu-Kuo Huang, Ruby C. Weng, and Chih-Jen Lin. Generalized Bradley-Terry models and multiclass probability estimates. Journal of Machine Learning Research, 7:85–115, 2006. URL http: //www.csie.ntu.edu.tw/˜cjlin/papers/generalBT.pdf. Willard D. James and Charles M. Stein. Estimation with quadratic loss. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 361– 379, 1961. Robert E. Kass and Adrian E. Raftery. Bayes factors. Journal of the American Statistical Association, 90(430):773–795, 1995. Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sumproduct algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001. John I. Marden. Analyzing and Modeling Rank Data. Chapman & Hall, London, 1995. Joshua E. Menke and Tony R. Martinez. A Bradley-Terry artificial neural network model for individual ratings in group competitions. Neural Computing and Applications, 17:175–186, 2008. Thomas Minka. A Family of Algorithms for Approximate Bayesian Inference. PhD thesis, MIT, 2001. Charles M. Stein. Estimation of the mean of a multivariate normal distribution. The Annals of Statistics, 9:1135–1151, 1981. Louis L. Thurstone. A law of comparative judgement. Psychological Reviews, 34:273–286, 1927. Luke Tierney and Joseph B. Kadane. Accurate approximations for posterior moments and marginal densities. Journal of the American Statistical Association, 81:82–86, 1986. Ruby C. Weng. A Bayesian Edgeworth expansion by Stein’s identity. Bayesian Analysis, 5(4): 741–764, 2010. Ruby C. Weng and Michael Woodroofe. Integrable expansions for posterior distributions for multiparameter exponential families with applications to sequential confidence levels. Statistica Sinica, 10:693–713, 2000. Michael Woodroofe. Very weak expansions for sequentially designed experiments: linear models. The Annals of Statistics, 17:1087–1102, 1989. Michael Woodroofe and D. Stephen Coad. Corrected confidence sets for sequentially designed experiments. Statistica Sinica, 7:53–74, 1997. Ernst Zermelo. Die berechnung der Turnier-Ergebnisse als ein maximumproblem der wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 29:436–460, 1929. 300