TrueSkill A Bayesian Skill Rating System

https://proceedings.neurips.cc/paper/2006/file/f44ee263952e65b3610b8ba51229d1f9-Paper.pdf

Problem

Są rozgrywane mecze, skill drużyny w danym meczu to suma skilli graczy w drużynie w drużynie, skill gracza w danym meczu to sample z rozkładu normalnego wokół skilla gracza i ustalonej wariancji. Zadanie: muszą zaraportować skilla każdego gracza po skończonym meczu.

Rozwiązanie

Na początku zakładamy, że istnieje taki proces generujący wyniki meczu:

1. gracz $i$ ma skilla $s_i$ oraz $s_i\sim \mathcal{N}({\mu }_i,{\sigma }_i^2)$
2. gracz $i$ ma performance $p_i$ w danym meczu oraz $p_i\sim \mathcal{N}(s_i,{\beta }^2)$ gdzie $\beta$ jest stałe
3. performance $t_j$ teamu $j$ to suma performance graczy w danym teamie

Z meczu mamy outcome $r=(r_1,\dots ,r_k)$ gdzie $r_1$ to miejsce, które zajął team nr 1.

Zastanawiamy się jakie jest prawdopodobieństwo $\mathbb{P}(s,p,t|r,A)$, czyli zastanawiamy się jakie jest rozkład prawdopodobieństwa $s$, $p$, $t$ gdy dany jest wynik meczu $r$ oraz podział na drużyny $A$. Inaczej mówiąc, zastanawiamy się jakie wartości $s$, $p$, $t$ mogły wygenerować taki wynik meczu.

Końcowo chcemy wyliczyć posterior $\mathbb{P}(s_i|r,A)$, co osiągamy poprzez marginalizację, tzn. $\mathbb{P}(s_i|r,A)={\int }_{-\infty }^{+\infty }\dots {\int }_{-\infty }^{+\infty }\mathbb{P}(s,p,t|r,A)dpdt$ W jaki sposób policzyć tą marginalizację efektywnie? A no trzeba zapisać obliczenia jako Factor graph i użyć algorytmu Sum-product message passing, który powie nam jak policzyć to efektywnie.

Uwaga: tu jest założenie, że po nieskończonej liczbie meczy ${\sigma }_i$ zbiega do 0, tzn. algorytm zbiega odkrywając prawdziwe $s_i$.

Publikacja oparta na A family of algorithms for approximate Bayesian inference oraz Factor graphs and the sum-product algorithm. Oparta o algorytm expectation propagation zaproponowany w publikacji A family of algorithms for approximate Bayesian inference.

TODO: Online learning algorithm: Gaussian density filtering (?) - posterior distribution jest przybliżany rozkładem normalnym i jest używany jako prior do następnego meczu.

W Update equations (1) $\mu$ to $m$, a ${\sigma }^2$ to $v^2$ !!