Shuo Chen
Thorsten Joachims
ABSTRACT
We present a general probabilistic framework for predicting the outcome of pairwise matchups (e.g. two-player sport matches) and pairwise preferences (e.g. product preferences), both of which have widespread applications ranging from matchmaking in computer games to recommendation in e-commerce. Unlike existing models for these tasks, our model not only learns representations of the items in a more expressive latent vector space, but also models how context modifies matchup and preference outcomes. For example, the context "weather" may alter the winning probability in a tennis match, or the fact that the user is on a mobile device may alter his preferences among restaurants. More generally, the model is capable of handling any symmetric game/comparison problem that can be described by vectorized player/item and game/context features. We provide a comprehensive evaluation of its predictive performance with real datasets from both domains to show its ability to predict preference and game outcomes more accurately than existing models. Furthermore, we demonstrate on synthetic datasets the expressiveness of the model when compared against theoretical limits.
Supplemental Material
- Wikipedia page on elo rating system. https://en.wikipedia.org/wiki/Elo_rating_system.Google Scholar
- R. P. Adams, G. E. Dahl, and I. Murray. Incorporating side information in probabilistic matrix factorization with gaussian processes. arXiv preprint arXiv:1003.4944, 2010.Google Scholar
- G. Adomavicius, R. Sankaranarayanan, S. Sen, and A. Tuzhilin. Incorporating contextual information in recommender systems using a multidimensional approach. ACM Transactions on Information Systems (TOIS), 23(1):103--145, 2005. Google ScholarDigital Library
- D. Agarwal and B.-C. Chen. Regression-based latent factor models. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 19--28. ACM, 2009. Google ScholarDigital Library
- L. Baltrunas and F. Ricci. Context-based splitting of item ratings in collaborative filtering. In Proceedings of the third ACM conference on Recommender systems, pages 245--248. ACM, 2009. Google ScholarDigital Library
- C. M. Bishop. Pattern recognition and machine learning. springer, 2006. Google ScholarDigital Library
- R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, pages 324--345, 1952.Google ScholarCross Ref
- M. Cattelan et al. Models for paired comparison data: A review with emphasis on dependent data. Statistical Science, 27(3):412--433, 2012.Google ScholarCross Ref
- D. Causeur and F. Husson. A 2-dimensional extension of the bradley--terry model for paired comparisons. Journal of statistical planning and inference, 135(2):245--259, 2005.Google Scholar
- S. Chen and T. Joachims. Modeling intransitivity in matchup and comparison data. In Proceedings of The 9th ACM International Conference on Web Search and Data Mining (WSDM). ACM, 2016. Google ScholarDigital Library
- W. Chu and Z. Ghahramani. Preference learning with gaussian processes. In Proceedings of the 22nd international conference on Machine learning, pages 137--144. ACM, 2005. Google ScholarDigital Library
- W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. In Advances in Neural Information Processing Systems 10: Proceedings of the 1997 Conference, volume 10, page 451. MIT Press, 1998. Google ScholarDigital Library
- P. Dangauthier, R. Herbrich, T. Minka, T. Graepel, et al. Trueskill through time: Revisiting the history of chess. In NIPS, 2007. Google ScholarDigital Library
- O. Delalleau, E. Contal, E. Thibodeau-Laufer, R. C. Ferrari, Y. Bengio, and F. Zhang. Beyond skill rating: Advanced matchmaking in ghost recon online. Computational Intelligence and AI in Games, IEEE Transactions on, 4(3):167--177, 2012.Google Scholar
- J. Fürnkranz and E. Hüllermeier. Preference learning. Springer, 2010. Google ScholarDigital Library
- W. V. Gehrlein. The probability of intransitivity of pairwise comparisons in individual preference. Mathematical social sciences, 17(1):67--75, 1989.Google Scholar
- M. E. Glickman. A comprehensive guide to chess ratings. American Chess Journal, 3:59--102, 1995.Google Scholar
- R. Herbrich, T. Minka, and T. Graepel. Trueskill™: A bayesian skill rating system. In Advances in Neural Information Processing Systems, pages 569--576, 2006. Google ScholarDigital Library
- T.-K. Huang, C.-J. Lin, and R. C. Weng. Ranking individuals by group comparisons. In Proceedings of the 23rd international conference on Machine learning, pages 425--432. ACM, 2006. Google ScholarDigital Library
- J. Huber, J. W. Payne, and C. Puto. Adding asymmetrically dominated alternatives: Violations of regularity and the similarity hypothesis. Journal of consumer research, pages 90--98, 1982.Google Scholar
- D. R. Hunter. Mm algorithms for generalized bradley-terry models. Annals of Statistics, pages 384--406, 2004.Google Scholar
- T. Joachims et al. Evaluating retrieval performance using clickthrough data., 2003.Google Scholar
- T. Joachims, L. Granka, B. Pan, H. Hembrooke, and G. Gay. Accurately interpreting clickthrough data as implicit feedback. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 154--161. ACM, 2005. Google ScholarDigital Library
- D. Jurafsky and J. H. Martin. Speech & language processing. Pearson Education India, 2000.Google Scholar
- A. Karatzoglou, X. Amatriain, L. Baltrunas, and N. Oliver. Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative filtering. In Proceedings of the fourth ACM conference on Recommender systems, pages 79--86. ACM, 2010. Google ScholarDigital Library
- P. Linares. Are inconsistent decisions better? an experiment with pairwise comparisons. European Journal of Operational Research, 193(2):492--498, 2009.Google ScholarCross Ref
- R. D. Luce. Individual Choice Behavior a Theoretical Analysis. john Wiley and Sons, 1959.Google Scholar
- K. O. May. Intransitivity, utility, and the aggregation of preference patterns. Econometrica: Journal of the Econometric Society, pages 1--13, 1954.Google Scholar
- I. McHale and A. Morton. A bradley-terry type model for forecasting tennis match results. International Journal of Forecasting, 27(2):619--630, 2011.Google ScholarCross Ref
- J. E. Menke and T. R. Martinez. A bradley--terry artificial neural network model for individual ratings in group competitions. Neural computing and Applications, 17(2):175--186, 2008. Google ScholarDigital Library
- T. V. Nguyen, A. Karatzoglou, and L. Baltrunas. Gaussian process factorization machines for context-aware recommendations. In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, pages 63--72. ACM, 2014. Google ScholarDigital Library
- S. Nikolenko and A. Sirotkin. A new bayesian rating system for team competitions. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 601--608, 2011.Google Scholar
- C. Ono, Y. Takishima, Y. Motomura, and H. Asoh. Context-aware preference model based on a study of difference between real and supposed situation data. UMAP, 9:102--113, 2009. Google ScholarDigital Library
- F. Radlinski and T. Joachims. Query chains: learning to rank from implicit feedback. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 239--248. ACM, 2005. Google ScholarDigital Library
- X. Ramirez-Garcia and M. García-Valdez. Post-filtering for a restaurant context-aware recommender system. In O. Castillo, P. Melin, W. Pedrycz, and J. Kacprzyk, editors, Recent Advances on Hybrid Approaches for Designing Intelligent Systems, volume 547 of Studies in Computational Intelligence, pages 695--707. Springer International Publishing, 2014.Google ScholarCross Ref
- S. Rendle, Z. Gantner, C. Freudenthaler, and L. Schmidt-Thieme. Fast context-aware recommendations with factorization machines. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pages 635--644. ACM, 2011. Google ScholarDigital Library
- P. Resnick and H. R. Varian. Recommender systems. Communications of the ACM, 40(3):56--58, 1997. Google ScholarDigital Library
- D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back-propagating errors. Cognitive modeling, 5:3, 1988.Google Scholar
- Y. Shi, A. Karatzoglou, L. Baltrunas, M. Larson, A. Hanjalic, and N. Oliver. Tfmap: Optimizing map for top-n context-aware recommendation. In Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval, pages 155--164. ACM, 2012. Google ScholarDigital Library
- I. Simonson and A. Tversky. Choice in context: Tradeoff contrast and extremeness aversion. JMR, Journal of Marketing Research, 29(3):281, 1992.Google ScholarCross Ref
- D. H. Stern, R. Herbrich, and T. Graepel. Matchbox: large scale online bayesian recommendations. In Proceedings of the 18th international conference on World wide web, pages 111--120. ACM, 2009. Google ScholarDigital Library
- L. L. Thurstone. A law of comparative judgment. Psychological review, 34(4):273, 1927.Google ScholarCross Ref
- S. Usami. Individual differences multidimensional bradley-terry model using reversible jump markov chain monte carlo algorithm. Behaviormetrika, 37(2):135--155, 2010.Google ScholarCross Ref
- G. N. Yannakakis, M. Maragoudakis, and J. Hallam. Preference learning for cognitive modeling: a case study on entertainment preferences. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 39(6):1165--1175, 2009. Google ScholarDigital Library
- L. Zhang, J. Wu, Z.-C. Wang, and C.-J. Wang. A factor-based model for context-sensitive skill rating systems. In Tools with Artificial Intelligence (ICTAI), 2010 22nd IEEE International Conference on, volume 2, pages 249--255. IEEE, 2010. Google ScholarDigital Library
- Y. Zheng, B. Mobasher, and R. Burke. Carskit: A java-based context-aware recommendation engine. In Proceedings of the 15th IEEE International Conference on Data Mining Workshops. IEEE, 2015. Google ScholarDigital Library
Index Terms
- Predicting Matchups and Preferences in Context
Recommendations
Modeling Intransitivity in Matchup and Comparison Data
WSDM '16: Proceedings of the Ninth ACM International Conference on Web Search and Data MiningWe present a method for learning potentially intransitive preference relations from pairwise comparison and matchup data. Unlike standard preference-learning models that represent the properties of each item/player as a single number, our method infers ...
Towards understanding balancing in exertion games
ACE '14: Proceedings of the 11th Conference on Advances in Computer Entertainment TechnologyPlaying exertion games with others can be engaging. However, players with different physical skill levels competing against each other can experience reduced engagement because they are either not challenged enough, or challenged too much. Balancing ...
Region-wise Ranking of Sports Players based on Link Fusion
WWW '18: Companion Proceedings of the The Web Conference 2018Players are ranked in various sports to show their importance over other players. Existing methods only consider intra-type links (e.g., player to player and team to team), but ignore inter-type links (e.g., one type of player to another type of player, ...
Comments