Efficient computation of rankings from pairwise comparisons

Autor:	Newman, M. E. J.
Rok vydání:	2022
Předmět:	Statistics - Machine Learning Computer Science - Machine Learning
Zdroj:	Journal of Machine Learning Research 24, 238 (2023)
Druh dokumentu:	Working Paper
Popis:	We study the ranking of individuals, teams, or objects, based on pairwise comparisons between them, using the Bradley-Terry model. Estimates of rankings within this model are commonly made using a simple iterative algorithm first introduced by Zermelo almost a century ago. Here we describe an alternative and similarly simple iteration that provably returns identical results but does so much faster -- over a hundred times faster in some cases. We demonstrate this algorithm with applications to a range of example data sets and derive a number of results regarding its convergence. Comment: 25 pages, 1 figure, 1 table; additional material on MAP estimation and rates of convergence
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2207.00076 Zobrazit plný text záznamu View this record from Arxiv