Lucas Maystre
ABSTRACT
Inspired by applications in sports where the skill of players or teams competing against each other varies over time, we propose a probabilistic model of pairwise-comparison outcomes that can capture a wide range of time dynamics. We achieve this by replacing the static parameters of a class of popular pairwise-comparison models by continuous-time Gaussian processes; the covariance function of these processes enables expressive dynamics. We develop an efficient inference algorithm that computes an approximate Bayesian posterior distribution. Despite the flexbility of our model, our inference algorithm requires only a few linear-time iterations over the data and can take advantage of modern multiprocessor computer architectures. We apply our model to several historical databases of sports outcomes and find that our approach outperforms competing approaches in terms of predictive performance, scales to millions of observations, and generates compelling visualizations that help in understanding and interpreting the data.
- A. Agresti. 2012. Categorical Data Analysis(third ed.). Wiley.Google Scholar
- A. Birlutiu and T. Heskes. 2007. Expectation Propagation for Rating Players in Sports Competitions. In Proceedings of PKDD 2007. Warsaw, Poland.Google Scholar
- D. M. Blei, A. Kucukelbir, and J. D. McAuliffe. 2017. Variational Inference: A Review for Statisticians. J. Amer. Statist. Assoc. 112, 518 (2017), 859--877.Google ScholarCross Ref
- R. A. Bradley and M. E. Terry. 1952. Rank Analysis of Incomplete Block Designs:I. The Method of Paired Comparisons.Biometrika39, 3/4 (1952), 324--345.Google Scholar
- S. Chen and T. Joachims. 2016. Modeling Intransitivity in Matchup and Comparison Data. San Francisco, CA, USA.Google Scholar
- R. Coulom. 2008. Whole-History Rating: A Bayesian Rating System for Players of Time-Varying Strength. In Proceedings of CG 2008. Beijing, China. Google ScholarDigital Library
- P. Dangauthier, R. Herbrich, T. Minka, and T. Graepel. 2007. True Skill Through Time: Revisiting the History of Chess. In Advances in Neural Information Processing Systems 20. Vancouver, BC, Canada. Google ScholarDigital Library
- D. Duvenaud. 2014.Automatic Model Construction with Gaussian Processes. Ph.D. Dissertation. University of Cambridge.Google Scholar
- A. Elo. 1978. The Rating Of Chess Players, Past & Present. Arco Publishing.Google Scholar
- L. Fahrmeir and G. Tutz. 1994. Dynamic Stochastic Models for Time-Dependent Ordered Paired Comparison Systems.J. Amer. Statist. Assoc. 89, 428 (1994),1438--1449.Google ScholarCross Ref
- W. A. Glenn and H. A. David. 1960. Ties in Paired-Comparison Experiments Using a Modified Thurstone? Mosteller Model. Biometrics 16, 1 (1960), 86--109.Google ScholarCross Ref
- M. E. Glickman. 1993.Paired Comparison Models with Time-Varying Parameters. Ph.D. Dissertation. Harvard University.Google Scholar
- M. E. Glickman. 1999. Parameter estimation in large dynamic paired comparison experiments. Journal of the Royal Statistical Society, Series C (Applied Statistics)48, 3 (1999), 377--394.Google ScholarCross Ref
- S. Guo, S. Sanner, T. Graepel, and W. Buntine. 2012. Score-Based Bayesian Skill Learning. In Proceedings of ECML PKDD 2012. Bristol, United Kingdom.Google Scholar
- J. Hartikainen and S. Särkkä. 2010. Kalman filtering and smoothing solutions to temporal Gaussian process regression models. In Proceedings of MLSP 2010. Kittilä, Finland.Google Scholar
- R. Herbrich, T. Minka, and T. Graepel. 2006. TrueSkill?: A Bayesian Skill Rating System. In Advances in Neural Information Processing Systems 19. Vancouver, BC, Canada. Google ScholarDigital Library
- D. Karlis and I. Ntzoufras. 2009. Bayesian modelling of football outcomes: using the Skellam's distribution for the goal difference. IMA Journal of Management Mathematics 20, 2 (2009), 133--145.Google ScholarCross Ref
- M. E. Khan and W. Lin. 2017. Conjugate-Computation Variational Inference:Converting Variational Inference in Non-Conjugate Models to Inferences in Conjugate Models. In Proceedings of AISTATS 2017. Fort Lauderdale, FL, USA.Google Scholar
- M. J. Maher. 1982. Modelling association football scores. Statistica Neerlandica 36, 3 (1982), 109--118.Google ScholarCross Ref
- L. Maystre, V. Kristof, A. J. González Ferrer, and M. Grossglauser. 2016. The Player Kernel: Learning Team Strengths Based on Implicit Player Contributions. (Sept. 2016). Preprint, arXiv:1609.01176 {cs.LG}.Google Scholar
- D. McFadden. 1973. Conditional logit analysis of qualitative choice behavior. In Frontiers in Econometrics, P. Zarembka (Ed.). Academic Press, 105--142.Google Scholar
- T. P. Minka. 2001. A family of algorithms for approximate Bayesian inference. Ph.D. Dissertation. Massachusetts Institute of Technology. Google ScholarDigital Library
- H. Nickisch and C. E. Rasmussen. 2008. Approximations for Binary Gaussian Process Classification. Journal of Machine Learning Research 9, Oct (2008), 2035--2078.Google Scholar
- H. Nickisch, A. Solin, and A. Grigorievksiy. 2018. State Space Gaussian Processes with Non-Gaussian Likelihood. In Proceedings of ICML 2018. Long Beach, CA,USA.Google Scholar
- A. O'Hagan. 1978. Curve Fitting and Optimal Design for Prediction. Journal of the Royal Statistical Society, Series B40, 1 (1978), 1--42.Google Scholar
- C. E. Rasmussen and C. K. I. Williams. 2006. Gaussian Processes for Machine Learning. MIT Press. Google ScholarDigital Library
- S. Reece and S. Roberts. 2010. An introduction to Gaussian processes for the Kalman filter expert. In Proceedings of ICIF 2010. Edinburgh, UK.Google Scholar
- Y. Saatçi. 2012. Scalable Inference for Structured Gaussian Process Models. Ph.D. Dissertation. University of Cambridge.Google Scholar
- M. J. Salganik and K. E. C. Levy. 2015. Wiki Surveys: Open and Quantifiable Social Data Collection. PLoS ONE10, 5 (2015), 1--17.Google Scholar
- M. Seeger, S. Gerwinn, and M. Bethge. 2007. Bayesian Inference for Sparse Generalized Linear Models. In Proceedings of ECML 2007. Warsaw, Poland. Google ScholarDigital Library
- A. Solin. 2016.Stochastic Differential Equation Methods for Spatio-Temporal Gaussian Process Regression. Ph.D. Dissertation. Aalto University.Google Scholar
- A. Solin and S. Särkkä. 2014. Explicit Link Between Periodic Covariance Functions and State Space Models. In Proceedings of AISTATS 2014. Reykjavik, Iceland.Google Scholar
- H. Stern. 1992. Are all linear paired comparison models empirically equivalent? Mathematical Social Sciences23, 1 (1992), 103--117.Google Scholar
- S. Särkkä. 2013.Bayesian Filtering and Smoothing. Cambridge University Press. Google ScholarDigital Library
- L. L. Thurstone. 1927. A Law of Comparative Judgment. Psychological Review 34,4 (1927), 273--286.Google ScholarCross Ref
- M. J. Wainwright and M. I. Jordan. 2012. Graphical Models, Exponential Families,and Variational Inference. Foundations and Trends in Machine Learning 1, 1--2(2012), 1--305. Google ScholarDigital Library
- E. Zermelo. 1928. Die Berechnung der Turnier-Ergebnisse als ein Maximum problem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift 29, 1 (1928),436--460.Google ScholarCross Ref
Index Terms
- Pairwise Comparisons with Flexible Time-Dynamics
Recommendations
Predicting Matchups and Preferences in Context
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data MiningWe 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 ...
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 ...
A personal history of Bayesian statistics
The history of Bayesian statistics is traced, from a personal perspective, through various strands and via its re‐genesis during the 1960s to the current day. Emphasis is placed on broad‐sense Bayesian methodology that can be used to meaningfully analyze ...
Comments