Weng and Lin 2011 - Update Rules Derivation and Error Correction

Summary

The core derivation: posterior mean/variance via Corollary 2, approximated at $z=0$ to give $\mu \leftarrow \mu +\Omega$ and ${\sigma }^2\leftarrow {\sigma }^2\max (1-\Delta ,\kappa )$; an exact two-team Thurstone-Mosteller check shows the approximation omits prior variance, fixed by ${\beta }_i^2={\beta }^2+{\sigma }_i^2$; multi-team outcomes factor into pairs; team skill is the sum of member skills and updates are shared in proportion to ${\sigma }_{ij}^2$.

Overview

Let $Z_i=({\theta }_i-{\mu }_i)/{\sigma }_i$ and $f(z)=P(D\mid z)$ the outcome probability. The posterior of $Z$ has the form $C{\varphi }_k(z)f(z)$, so Corollary 2 applies.

Main Content

Exact posterior moments (Eqs. 25-26)

${\mu }_i^{\text{new}}={\mu }_i+{\sigma }_{i}E\left[{\partial }_{z_i}f/f\right]={\mu }_i+E\left[\partial \log f/\partial {\theta }_i\right]$ (the average score of the outcome with respect to ${\theta }_i$); $({\sigma }_i^{\text{new}}{)}^2={\sigma }_i^2(1+E[{\nabla }^{2}f/f{]}_{ii}-E[{\partial }_{z_i}f/f{]}^2)$.

Proposed approximation (Eqs. 27-30)

Replace expectations by their value at $z=0$ (i.e. $\theta =\mu$):

$${\mu }_i\leftarrow {\mu }_i+{\Omega }_i,{\Omega }_i={\sigma }_i\frac{{\partial }_{z_i}f(z)}{f(z)}{|}_{z=0};{\sigma }_i^2\leftarrow {\sigma }_i^2\max (1-{\Delta }_i,\kappa ),{\Delta }_i=-\frac{\partial }{\partial z_i}\left(\frac{{\partial }_{z_i}f}{f}\right){|}_{z=0}.$$

$\kappa >0$ is a small floor because $1-{\Delta }_i$ can be negative. ${\Omega }_i$ is the average relative rate of change of the outcome probability with respect to ${\theta }_i$; ${\Delta }_i$ the rate of change of that score.

3.2 Error analysis (two-team TM)

For two teams with $X_i\sim N({\theta }_i,{\beta }_i^2)$ the joint posterior is $\propto \varphi (\frac{{\theta }_1-{\mu }_1}{{\sigma }_1})\varphi (\frac{{\theta }_2-{\mu }_2}{{\sigma }_2})\Phi \left(\frac{{\theta }_1-{\theta }_2}{\sqrt{{\beta }_1^2+{\beta }_2^2}}\right)$ and the exact posterior mean is (Eq. 33)

$$E[{\theta }_1]={\mu }_1+\frac{{\sigma }_1^2}{\sqrt{{\sum }_i({\beta }_i^2+{\sigma }_i^2)}}\frac{\varphi \left(\frac{{\mu }_1-{\mu }_2}{\sqrt{{\sum }_i({\beta }_i^2+{\sigma }_i^2)}}\right)}{\Phi \left(\frac{{\mu }_1-{\mu }_2}{\sqrt{{\sum }_i({\beta }_i^2+{\sigma }_i^2)}}\right)}.$$

The approximation (Eq. 36) has the same form with $\sum {\beta }_i^2$ only. Correction: use ${\beta }_i^2\leftarrow {\beta }^2+{\sigma }_i^2$ (with a constant ${\beta }^2$). Appendix C shows the same argument applies to Bradley-Terry, giving $c_{iq}^2={\sigma }_i^2+{\sigma }_q^2+2{\beta }^2$.

3.3 Factorisation of multi-team outcomes

For $k$ teams the exact TM probability needs a $(k-1)$-dimensional integral. Factor $f={\prod }_q{f}_q$ so that $\partial f/f={\sum }_q\partial f_q/f_q$:

• Partial-pair (Eq. 39): $f={\prod }_{a=1}^{k-1}P(\text{team ranked }a\text{ beats team ranked }a+1)$ (adjacent ranks only).
• Full-pair (Eq. 40): $f={\prod }_{i<q}P(\text{outcome of }i\text{ vs }q)$, all $k(k-1)/2$ pairs. PL factors naturally by stage.

3.4 Individual skills inside teams

Team strength is additive

${\theta }_i={\sum }_{j=1}^{n_i}{\theta }_{ij}$, so ${\mu }_i={\sum }_j{\mu }_{ij}$ and ${\sigma }_i^2={\sum }_j{\sigma }_{ij}^2$. Updates (Eqs. 43-44): ${\mu }_{ij}\leftarrow {\mu }_{ij}+\frac{{\sigma }_{ij}^2}{{\sigma }_i^2}{\Omega }_i$, ${\sigma }_{ij}^2\leftarrow {\sigma }_{ij}^2\max (1-\frac{{\sigma }_{ij}^2}{{\sigma }_i^2}{\Delta }_i,\kappa )$.

So the team’s skill change is distributed in proportion to member variances: uncertain players move more. (Derived from $f(z)=\bar{f}(\bar{z})$ with $Z_i={\sum }_j{\sigma }_{ij}{Z}_{ij}/{\sigma }_i$.)

Examples

Variance floor in action

Setup. $\mu =25$, ${\sigma }^2=(25/3{)}^2\approx 69.4$ for both players, ${\beta }^2=(25/6{)}^2\approx 17.4$, one win. Solution. $c^2=2{\sigma }^2+2{\beta }^2\approx 173.6$; see numbers in Weng and Lin 2011 - Bradley-Terry Update Algorithms: ${\sigma }^2$ falls from 69.4 to about 65.1 (a 6% reduction after one game). Interpretation. Early games move means a lot but variances slowly - which is why ${\gamma }_q$ (an additional damping factor in the BT algorithm) can matter.

Connections

• Compare with the Kalman gain: gain $\approx {\sigma }_i^2/c_{iq}$ times a score residual $(s-\hat{p})$ (The Kalman Filter).

See Also

Weng and Lin 2011 - Bradley-Terry Update Algorithms · Weng and Lin 2011 - Thurstone-Mosteller and Plackett-Luce Update Rules