Weng and Lin 2011 - Ranking Models and the W-Stein Approximation

Summary

Section 2 reviews how ranked data are modelled (Thurstone-Mosteller, Bradley-Terry, Plackett-Luce, Elo) and states Woodroofe’s extension of Stein’s lemma, which makes posterior mean and variance for Gaussian-prior skills computable from derivatives of the outcome likelihood.

Overview

A game with $k$ teams gives ranks $r(i)$ (smaller is better). Ties share a rank and the next team skips ahead: ranks $(2,2,4,1)$ for teams 1-4 mean teams 1 and 2 tie for second and team 3 is fourth. The inverse map $\bar{r}(a)$ lists teams in order, any one-to-one map with $r(\bar{r}(a))\le r(\bar{r}(a+1))$.

Main Content

Performance-ordering model

Each team has an unobserved performance $X_i$; the outcome is the event $X_{\bar{r}(1)}>X_{\bar{r}(2)}>\cdots >X_{\bar{r}(k)}$.

• Thurstone-Mosteller (TM): $X_i\sim N({\theta }_i,{\beta }_i^2)$, so $P(X_i>X_q)=\Phi (({\theta }_i-{\theta }_q)/\sqrt{{\beta }_i^2+{\beta }_q^2})$.
• Bradley-Terry (BT): $P(X_i>X_q)=v_i/(v_i+v_q)$, from Gumbel performances with location ${\theta }_i=\log v_i$ (logistic difference).

Plackett-Luce (PL)

$P(\bar{r}(1),\dots ,\bar{r}(k))={\prod }_{a=1}^k\frac{e^{{\theta }_{\bar{r}(a)}}}{{\sum }_{b\ge a}{e}^{{\theta }_{\bar{r}(b)}}}$: choose the favourite, then the next favourite from the remainder.

Elo update

${\theta }_i\leftarrow {\theta }_i+K(s-P(i\text{ wins}))$ with $s=1$ for a win and 0 otherwise; the logistic variant is BT. USCF uses $K=32$ for amateurs and $p_{iq}^{\ast }=10^{{\theta }_i/400}/(10^{{\theta }_i/400}+10^{{\theta }_q/400})$.

Figure 1. Win probability vs. ${\theta }_i-{\theta }_q\in [-6,6]$ for the Gaussian model with $({\beta }_i^2+{\beta }_q^2{)}^{1/2}=4/\sqrt{2\pi }\approx 1.6$ (chosen so slopes agree at 0) and the logistic model. They nearly coincide near equal skill, but the logistic gives a weaker team a higher chance, which is why chess federations prefer it.

Why not MCMC. MCMC does not reuse earlier analysis when new data arrive, so for sequential updating the authors use deterministic approximations: Laplace, variational Bayes, expectation propagation (TrueSkill’s choice).

Lemma 1 (W-Stein identity, Woodroofe 1989)

Let $d\Gamma (z)=f(z){\varphi }_k(z)dz$ with $f$ almost differentiable, ${\varphi }_k$ the standard $k$-variate normal density, and $h$ a real function. Then

$$\int hd\Gamma =\int fd{\Phi }_k\cdot \int hd{\Phi }_k+\int (Uh{)}^{\top }\nabla fd{\Phi }_k,$$

provided integrals are finite, where $Uh=[g_1,\dots ,g_k{]}^{\top }$, $g_j(z)=e^{z_j^2/2}{\int }_{z_j}^{\infty }[h_j(z_{1:j-1},w)-h_{j-1}(z_{1:j-1})]e^{-w^2/2}dw$.

Corollary 2 (posterior moments)

If $Z$ has density $C{\varphi }_k(z)f(z)$, then $E[Z_i]=E\left[\frac{{\partial }_{i}f(Z)}{f(Z)}\right]$ and $E[Z_i{Z}_q]={\delta }_{iq}+E{\left[\frac{{\nabla }^{2}f(Z)}{f(Z)}\right]}_{iq}$.

Proof sketch (Appendix A). Exchange the order of integration (Fubini); the same device proves Stein’s lemma. For $h(z)=z_i$, $Uh=e_i$; for $h(z)=z_i{z}_j$ with $i<j$, $Uh=z_i{e}_j$ (Appendix B works $k=3$, $h=z_1{z}_2$).

Examples

Why the identity gives an Elo step

Setup. Two teams; $f$ = probability that team 1 wins, a logistic function of ${\theta }_1-{\theta }_2$; priors $N({\mu }_i,{\sigma }_i^2)$. Solution. Corollary 2 gives $E[{\theta }_1]={\mu }_1+{\sigma }_{1}E[{\partial }_{z_1}f/f]$, the average relative gradient of the outcome probability. Evaluating at the prior mean gives ${\mu }_1+({\sigma }_1^2/c)(1-\hat{p})$ (see Weng and Lin 2011 - Bradley-Terry Update Algorithms). Interpretation. The shift is the surprise $(s-\hat{p})$ scaled by uncertainty: an Elo step with automatic, uncertainty-driven $K$.

Connections

Gaussian belief updating of skill is a Kalman-style observation update (The Kalman Filter).

See Also

Weng and Lin 2011 - Update Rules Derivation and Error Correction