PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Bayesian Inference for Generalized Bradley-Terry Models

Francois Caron, Arnaud Doucet

arXiv:1011.1761v1stat.MEstat.COstat.ML

TL;DR

Generalized Bradley-Terry models need effective Bayesian inference beyond existing MM estimation and tailored Metropolis-Hastings methods. The paper reinterprets MM algorithms as EM procedures using latent variables, then derives Gibbs samplers and finds that they mix well experimentally and outperform a recently proposed Metropolis-Hastings algorithm.

  • Problem

    Bayesian inference for generalized Bradley-Terry models typically relies on intractable-posterior approximations and tailored Metropolis-Hastings proposals.

  • Method

    The paper introduces latent variables to reinterpret generalized Bradley-Terry MM algorithms as EM algorithms and derives Gibbs samplers from the same augmentations.

  • Results

    The resulting Gibbs samplers mix well experimentally and outperform a recently proposed Metropolis-Hastings algorithm.

  • Takeaways & Limitations

    Latent-variable formulations provide a simple route to Bayesian inference for an important class of generalized Bradley-Terry models without designing Metropolis-Hastings proposal distributions.

  • Takeaways & Limitations

    The basic augmentation can suffer slow EM convergence and slow Markov-chain mixing when some π_k values are small.

Abstract

from arXiv · show

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.

Efficient Bayesian Inference for Generalized Bradley-Terry Models

The paper studies Bayesian inference for generalized Bradley-Terry models by connecting efficient MM algorithms to EM algorithms and deriving Gibbs samplers from latent variables.

  • The Bradley-Terry model describes pairwise comparison outcomes and has applications in animal behavior, chess ranking, and multiclass classification.
  • The paper reinterprets generalized Bradley-Terry MM algorithms as EM algorithms associated with suitable latent variables.
  • The introduced latent variables yield simple Gibbs samplers for Bayesian inference.
  • The paper demonstrates the efficiency of these algorithms experimentally across multiple applications.

1 Introduction

The introduction situates Bradley-Terry models within pairwise comparison methods, reviews MM and Bayesian approaches, and presents latent-variable EM and Gibbs-sampling contributions.

  • Bradley-Terry models assign skill parameters to elements and model the probability that one element beats another.
  • The model has applications in player ranking, multiclass classification, and extensions covering home advantage, draws, multiple comparisons, and team comparisons.
  • MM algorithms provide iterative procedures for maximum-likelihood estimation in generalized Bradley-Terry models.
  • Existing Bayesian approaches use approximations because the posterior is typically intractable, including expectation propagation and tailored Metropolis-Hastings proposals.
  • The paper reinterprets several MM algorithms as EM algorithms through suitable latent variables and proposes original EM algorithms for further generalizations.
  • The resulting Gibbs samplers avoid designing proposal distributions for Metropolis-Hastings updates and are reported to perform well experimentally.

2 Bradley-Terry model

For the basic Bradley-Terry model, the paper introduces latent variables that produce a tractable complete-data likelihood, reinterpret the MM update as EM, and enable posterior sampling.

  • Pairwise comparison data are summarized by win counts and total comparisons, which determine the Bradley-Terry likelihood.
  • The Thurstonian representation uses exponential arrival times, with the individual having the lowest arrival time declared the winner.
  • Using aggregated latent variables rather than every pair of arrival times preserves a simple complete-data log-likelihood and reduces missing information.
  • The same latent variables define a data-augmentation sampler for the posterior distribution of the skill parameters and latent variables.

3 Generalized Bradley-Terry models

The paper extends the latent-variable EM and Gibbs framework to home advantage, ties, team comparisons, and related generalized Bradley-Terry models.

  • Home advantage: In the home-advantage model, θ measures the strength of the advantage when θ > 1 or disadvantage when θ < 1.
  • Home advantage: The home-advantage model uses latent variables to derive an EM algorithm and a Gibbs sampler for λ, θ, and the latent variables.
  • Home advantage: With flat priors, the home-advantage EM algorithm is similar to Hunter's MM algorithm.
  • Model with ties: The ties model introduces tie counts and latent variables, yielding a complete-data likelihood and EM formulation under specified priors for λ and θ.
  • Model with ties: The ties model also supports Gibbs sampling and exact sampling from a mixture of Gamma distributions after a change of variable.
  • Group comparisons: For team comparisons, latent variables Z and C support data augmentation and an EM algorithm based on exponential-density representations.

4 Multiple comparisons

The Plackett-Luce model extends Bradley-Terry comparisons to ranked lists of more than two individuals. A latent-variable augmentation yields EM and Gibbs algorithms, and the same construction extends to mixtures of Plackett-Luce models.

  • Model: The Plackett-Luce model handles comparisons in which more than two individuals are ranked.For comparison i, the ranking is represented as an ordered list of p_i individuals.
  • Latent-variable augmentation: Latent variables Z_ij are introduced for each ranking position before forming the complete log-likelihood.The augmentation is indexed by comparison i and ranking position j=1,...,p_i−1.
  • EM algorithm: The Q function from this augmentation is equivalent to Hunter’s majorizing function when a=1 and b=0.This identifies the EM construction with the corresponding MM update in that parameter setting.
  • EM algorithm: The EM update uses w_k, the number of rankings in which individual k is not last, together with the indicator δ_ijk.δ_ijk indicates whether individual k receives a rank no better than position j in comparison i.
  • Gibbs sampling: The same augmentation supports a data-augmentation Gibbs sampler for p(λ,z|D).The sampler is specified as an iterative procedure using the latent variables and skill parameters.
  • Extensions: The construction also applies to mixtures of Plackett-Luce models.The paper states that EM and Gibbs samplers can be defined for this further extension using exactly the same augmentation.

5 Discussion

The discussion develops latent-variable EM and Gibbs formulations across Bradley-Terry extensions, while highlighting identifiability and convergence issues. It also connects the framework to random graphs, feature-based choice models, and categorical data.

  • Identifiability: The likelihood is invariant to rescaling λ, so the scale parameter Λ is not likelihood-identifiable.The prior representation separates normalized skill parameters π from the global scale Λ.
  • Identifiability: Random rescaling after normalizing λ can improve MCMC mixing, but it is useless when inference concerns only normalized π.The additional step samples a prior scale and rescales the normalized parameter vector.
  • Alternative augmentation: The paper introduces an alternative basic Bradley-Terry EM algorithm that avoids a scale parameter by using latent variables M_ij and C_ij.These variables are defined for paired comparisons with positive counts n_ij.
  • Convergence: The basic EM augmentation can converge slowly when π_k is small because π_i+π_j is large.The same slow-mixing issue arises for the corresponding Gibbs Markov chain.
  • Random graphs: The framework extends to random-graph models whose degree sequence is a sufficient statistic for the graph distribution.The graph model assigns edge probabilities through positive parameters λ_k and uses observed adjacency indicators r_ij.
  • Choice models: Feature-based choice models assign weights to features possessed by one object but not another, and admit EM and Gibbs algorithms through the same construction.The distinguishing feature contribution is the sum of weights for features present in i and absent in j.
  • Categorical data: For categorical data, latent variables enable EM and Gibbs algorithms for estimating or sampling the feature-weight parameters under the specified prior.The paper presents this model as an alternative to the multinomial logit model.

6 Experimental results

Experiments compare Gibbs and Metropolis–Hastings sampling on synthetic, NASCAR, and chess data, examining mixing, prediction, posterior skill estimates, and prior effects. The results indicate that the proposed Bayesian procedures can handle sparse participation and improve predictive performance through regularization and full Bayesian analysis.

  • 6.1 Synthetic Data: 500 simulated datasets with K = 4 individuals compared Gibbs sampling against a modified Gormley–Murphy M-H algorithm across sample sizes.Each dataset used a = 5, with 10,000 Gibbs iterations; mean lag-1 autocorrelation and 90% confidence bounds were reported.
  • 6.2 Nascar 2002 dataset: The NASCAR experiment predicts each next race from previous races using MAP estimates and compares test log-likelihood across values of a.The dataset contains 87 drivers across 36 races, with mean log-likelihood and 90% confidence bounds reported.
  • 6.2 Nascar 2002 dataset: The NASCAR Bayesian analysis retains drivers with limited participation, including drivers entering only one race, rather than requiring their removal for maximum-likelihood estimation.Hunter (2004) found that the original dataset prevented an MLE because four drivers placed last in every race they entered.
  • 6.3 Chess data: The chess experiment predicts outcomes for the final 5 months using 95 months of history, and reports improved results from penalizing skill parameters and full Bayesian analysis.The Markov chain also displays good mixing properties after 10,000 iterations with 1,000 burn-in iterations.

7 Conclusion

The paper reframes many Bradley–Terry MM algorithms as EM algorithms, extends EM to additional model variants, and derives Gibbs samplers for Bayesian inference. Experiments show good mixing and outperformance of a recently proposed M-H algorithm.

  • 7 Conclusion: Most MM algorithms from Hunter (2004) can be reinterpreted as special cases of EM algorithms.The paper also proposes original EM algorithms for some recent Bradley–Terry generalizations.
  • 7 Conclusion: Latent variables introduced for the EM derivations lead directly to Gibbs samplers for Bayesian inference.The resulting MCMC algorithms are reported to mix well experimentally.
  • 7 Conclusion: The proposed Gibbs samplers experimentally outperform a recently proposed M-H algorithm.
Loading 1011.1761v1…