Efficient Bayesian Inference for Generalized Bradley-Terry Models

Francois Caron (1, 2) , Arnaud Doucet (3)

1 ALEA - Advanced Learning Evolutionary Algorithms
2 IMB - Institut de Mathématiques de Bordeaux
3 Dept of Statistics & Dept of Computer Science

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 behaviour, 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 (2004) has proposed efficient iterative MM (minorization-maximization) algorithms to perform maximum likelihood estimation for these generalized Bradley-Terry models whereas Bayesian inference is typically performed using MCMC (Markov chain Monte Carlo) algorithms based on tailored Metropolis-Hastings (M-H) proposals. We show here that these MM\ algorithms can be reinterpreted as special instances of Expectation-Maximization (EM) algorithms associated to 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.

Le modèle de Bradley-Terry est une approche populaire pour décrire les résultats possibles lorsque des éléments d'un ensemble sont mis en comparaison par paire. Il a trouvé de nombreuses applications incluant le comportement animal, le classement de joueurs d'échecs et la classification multi-classes. Plusieurs extensions du modèle classique ont été proposées dans la littérature afin de prendre en compte des matchs nuls, des comparaisons multiples et des comparaisons entre groupes. D'un point de vue computationel, Hunter (2004) a proposé des algorithmes MM (minorization-maximization) itératifs efficaces pour l'estimation du maximum de vraisemblance dans les modèles de Bradley-Terry généralisés, tandis que l'inférence bayésienne est réalisée à l'aide d'algorithmes MCMC (Markov chain Monte Carlo) basées sur des lois de proposition Metropolis-Hastings (M-H) adaptées. Nous montrons que ces algorithmes MM peuvent être réinterprétés comme des instances d'algorithmes EM (Expectation-Maximization) associés à des ensembles de variables latentes. Ces variables latentes nous permettent de dériver des algorithmes de Gibbs simples pour l'inférence bayésiennes. Nous démontrons expérimentalement l'efficacité de ces algorithmes sur plusieurs applications.

Mots clés: Bradley--Terry model; data augmentation; EM algorithm; Gibbs sampler; maximum likelihood estimation; MCMC algorithms; MM algorithm; Plackett--Luce model

Domaines: Méthodologie [stat.ME]; Machine Learning [stat.ML]; Calcul [stat.CO]

Francois Caron, Arnaud Doucet. Efficient Bayesian Inference for Generalized Bradley-Terry Models. Journal of Computational and Graphical Statistics, 2012, 21 (1), pp.174-196. ⟨inria-00533638⟩