Bradley–Terry model

The Bradley–Terry model is a probability model that can predict the outcome of a paired comparison. Given a pair of individuals i and j drawn from some population, it estimates the probability that the pairwise comparison i > j turns out true, as

${\displaystyle P(i>j)={\frac {p_{i}}{p_{i}+p_{j}}}}$

where p_i is a positive real-valued score assigned to individual i. The comparison i > j can be read as "i is preferred to j", "i ranks higher than j", or "i beats j", depending on the application.

For example, p_i may represent the skill of a team in a sports tournament, estimated from the number of times i has won a match. ${\displaystyle P(i>j)}$ then represents the probability that i will win a match against j.[1][2] Another example used to explain the model's purpose is that of scoring products in a certain category by quality. While it's hard for a person to draft a direct ranking of (many) brands of wine, it may be feasible to compare a sample of pairs of wines and say, for each pair, which one is better. The Bradley–Terry model can then be used to derive a full ranking.[2]

History and applications

The model is named after R. A. Bradley and M. E. Terry,[3] who presented it in 1952,[4] although it had already been studied by Zermelo in the 1920s.[1][5][6]

Real-world applications of the model include estimation of the influence of statistical journals, or ranking documents by relevance in machine-learned search engines.[7] In the latter application, ${\displaystyle P(i>j)}$ may reflect that document i is more relevant to the user's query than document j, so it should be displayed earlier in the results list. The individual p_i then express the relevance of the document, and can be estimated from the frequency with which users click particular "hits" when presented with a result list.[8]

Definition

The Bradley–Terry model can be parametrized in various ways. One way to do so is to pick a single parameter per observation, leading to a model of n parameters p₁, ..., p_n.[9] Another variant, in fact the version considered by Bradley and Terry,[2] uses exponential score functions ${\displaystyle p_{i}=e^{\beta _{i}}}$ so that

${\displaystyle P(i>j)={\frac {e^{\beta _{i}}}{e^{\beta _{i}}+e^{\beta _{j}}}}}$

or, using the logit (and disallowing ties),[1]

${\displaystyle \operatorname {logit} (P(i>j))=\log \left({\frac {P(i>j)}{1-P(i>j)}}\right)=\log \left({\frac {P(i>j)}{P(j>i)}}\right)=\beta _{i}-\beta _{j}}$

reducing the model to logistic regression on pairs of individuals.

Estimating the parameters

The following algorithm computes the parameters p_i of the basic version of the model from a sample of observations. Formally, it computes a maximum likelihood estimate, i.e., it maximizes the likelihood of the observed data. The algorithm dates back to the work of Zermelo.[1]

The observations required are the outcomes of previous comparisons, for example, pairs (i, j) where i beats j. Summarizing these outcomes as w_ij, the number of times i has beaten j, we obtain the log-likelihood of the parameter vector p = p₁, ..., p_n as[1]

${\displaystyle L(\mathbf {p} )=\sum _{i}^{n}\sum _{j}^{n}w_{ij}\ln p_{i}-w_{ij}\ln(p_{i}+p_{j}).}$

Denote the number of comparisons "won" by i as W_i. Starting from an arbitrary vector p, the algorithm iteratively performs the update

${\displaystyle p'_{i}=W_{i}\left(\sum _{j\neq i}{\frac {w_{ij}+w_{ji}}{p_{i}+p_{j}}}\right)^{-1}}$

for all i. After computing all of the new parameters, they should be renormalized,

${\displaystyle p_{i}\leftarrow {\frac {p'_{i}}{\sum _{j=1}^{n}p'_{j}}}.}$

This estimation procedure improves the log-likelihood in every iteration, and eventually converges to a unique maximum.

See also

• Ordinal regression
• Rasch model
• Scale (social sciences)
• Elo rating system
• Thurstonian model

References

1. Hunter, David R. (2004). "MM algorithms for generalized Bradley–Terry models". The Annals of Statistics. 32 (1): 384–406. CiteSeerX 10.1.1.110.7878. doi:10.1214/aos/1079120141. JSTOR 3448514.
2. Agresti, Alan (2014). Categorical Data Analysis. John Wiley & Sons. pp. 436–439.
3. E.E.M. van Berkum. "Bradley-Terry model". Encyclopedia of Mathematics. Retrieved 18 November 2014.
4. Bradley, Ralph Allan; Terry, Milton E. (1952). "Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons". Biometrika. 39 (3/4): 324–345. doi:10.2307/2334029. JSTOR 2334029.
5. Zermelo, Ernst (1929). "Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung". Mathematische Zeitschrift. 29 (1): 436–460. doi:10.1007/BF01180541.
6. Heinz-Dieter Ebbinghaus (2007), Ernst Zermelo: An Approach to His Life and Work, pp. 268–269, ISBN 9783540495536
7. Szummer, Martin; Yilmaz, Emine (2011). Semi-supervised learning to rank with preference regularization (PDF). CIKM.
8. Radlinski, Filip; Joachims, Thorsten (2007). Active Exploration for Learning Rankings from Clickthrough Data (PDF). KDD '07 Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 570–579. doi:10.1145/1281192.1281254.
9. Fangzhao Wu; Jun Xu; Hang Li; Xin Jiang (2014). Ranking Optimization with Constraints. CIKM '14 Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. pp. 1049–1058. doi:10.1145/2661829.2661895.