Bradley-Terry Model

Based on wikipedia. The Bradley-Terry model (1952) is a probability model that allows us to infer scores for individual objects based on a dataset of pairwise comparisons between them. Specifically, it estimates the probability that $i▹j$ (i.e. $i$ is preferred to $j$) as:

$$P(i▹j)=\frac{p_i}{p_i+p_j}$$

Where $p_i$ is a positive real-valued score assigned to object $i$ (not necessarily a probability). Typically, $p_i$ is parametrized as an exponential score $p_i=e^{{\beta }_i}$, and the goal is to learn the parameters ${\beta }_i$ from pairwise comparisons. This results in:

$$P(i▹j)=\frac{e^{{\beta }_i}}{e^{{\beta }_i}+e^{{\beta }_j}}$$

Parameter Estimation

Parameter estimation is typically done using maximum likelihood. Starting with a set of pairwise comparisons between individual objects, let $w_{ij}$ be the number of times object $i$ beats object $j$. Then the likelihood of a given set of parameters $\mathbf{p}:=[p_1,...,p_n]$ ($n$ denotes number of objects) is as follows:

$$\begin{array}{rl}L(\mathbf{p})& =ln\prod _{ij}P(i▹j{)}^{w_{ij}}\\ & =\sum _{i=1}^n\sum _{j=1}^{n}ln{\left(\frac{p_i}{p_i+p_j}\right)}^{w_{ij}}\\ & =\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}\left[ln{p}_i-ln(p_i+p_j)\right]\end{array}$$

This likelihood function can then be minimized by differentiating wrt $p_i$ and solved by setting to zero.

BT Model as a Sigmoid Function

We can also express the likelihood as a function of the difference in scores ${\beta }_i-{\beta }_j$. Recall that the sigmoid function is $\sigma (x)=1/(1+e^{-x})$. Then: $$\begin{array}{rl}L(\mathbf{p})& =\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}\cdot ln\left[\frac{e^{{\beta }_i}}{e^{{\beta }_i}+e^{{\beta }_j}}\right]\\ & =\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}\cdot ln\sigma ({\beta }_i-{\beta }_j)\end{array}$$

The derivation for the second line above is found at /Identities/sigmoid. This re-parametrization shows that the BT-model is really modelling the preference as a difference in scores and then running that through the sigmoid function to convert it into a probability. This means that we are basically running a pairwise logistic regression.