Efficient Bayesian Inference for Generalized Bradley–Terry Models

Abstract

Abstract The Bradley–Terry model is a popular approach to describe probabilities of the possible outcomes when elements of a set are repeatedly compared with one another in pairs. It has found many applications including animal behavior, chess ranking, and multiclass classification. Numerous extensions of the basic model have also been proposed in the literature including models with ties, multiple comparisons, group comparisons, and random graphs. From a computational point of view, Hunter has proposed efficient iterative minorization-maximization (MM) algorithms to perform maximum likelihood estimation for these generalized Bradley–Terry models whereas Bayesian inference is typically performed using Markov chain Monte Carlo algorithms based on tailored Metropolis–Hastings proposals. We show here that these MM algorithms can be reinterpreted as special instances of expectation-maximization algorithms associated with suitable sets of latent variables and propose some original extensions. These latent variables allow us to derive simple Gibbs samplers for Bayesian inference. We demonstrate experimentally the efficiency of these algorithms on a variety of applications. Key Words: Data augmentationEM algorithmGibbs samplerMaximum likelihood estimationMCMC algorithmsMM algorithmPlackett–Luce modelRank data Acknowledgment The authors are grateful to Persi Diaconis for helpful discussions and pointers to references on the Plackett– Luce and random graph models and to Luke Bornn for helpful comments. Notes The authors actually use a normal approximation of the gamma distribution, and work with normalized data. To obtain similar algorithms, we consider unnormalized data. The data is provided in the supplementary material. It can also be downloaded from http://sites.stat.psu.edu/~dhunter/code/btmatlab/. Chess data can be downloaded from http://kaggle.com/chess.