Dlaczego system oceny Elo używa niewłaściwej reguły aktualizacji?

System oceny Elo wykorzystuje algorytm minimalizacji spadku gradientu funkcji utraty entropii krzyżowej między spodziewanym i obserwowanym prawdopodobieństwem wyniku w porównaniach w parach. Możemy zapisać funkcje strat ogólnych jako

E = - \sum_{n, i} p_{i} L o g (q_{i})

$E=-\sum_{n,i} p_i Log (q_i)$

gdzie suma jest wykonywana dla wszystkich wyników i wszystkich przeciwników . to obserwowana częstotliwość zdarzenia $i$ $n$ $p_i$ $_i$ oraz $q_i$ oczekiwaną częstotliwość.

W przypadku tylko dwóch możliwych wyników (wygrana lub przegrana) i jednego przeciwnika mamy

E = - p L o g (q) - (1 - p) L o g (1 - q)

$E=-p Log (q)-(1-p)Log(1-q)$

Jeśli jest rankingiem gracza i $\pi_i$ $i$ jest rankingiem gracza , możemy zbudować oczekiwane prawdopodobieństwo jako $\pi_j$ $j$

q_{i} = \frac{e^{π_{i}}}{e^{π_{i}} + e^{π_{j}}}

$q_i=\frac{e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}}$

a następnie reguła aktualizacji opadania gradientu mówi użycie

q_{j} = \frac{e^{π_{j}}}{e^{π_{i}} + e^{π_{j}}}

$q_j=\frac{e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}}$

π_{i}^{'} = π_{i} - η (q_{i} - p_{i})

$\pi_i'=\pi_i-\eta (q_i-p_i)$

π_{j}^{'} = π_{j} - η (q_{j} - p_{j})

$\pi_j'=\pi_j-\eta (q_j-p_j)$

gdzie a są oczekiwane i obserwowane prawdopodobieństwo wygranej gracza wobec gracza . To sązasady aktualizacji. $q_i$ $p_i$ $i$ $j$ two outcomes

W przypadku losowań możemy uogólnić powyższy model z prawdopodobieństwem trzeciego wyniku

q (d) = \frac{ν e^{\frac{π_{i} + π_{j}}{2}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q(d)=\frac{\nu e^{\frac{\pi_i+\pi_j}{2}}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

q_{i} (w) = \frac{e^{π_{i}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q_i(w)=\frac{ e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

q_{j} (w) = \frac{e^{π_{j}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q_j(w)=\frac{ e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

I możemy zbudować funkcję Loss jako

E = - p (w) L o g (q (w)) - (1 - p (w) - p (d)) L o g (q (l)) - p (d) L o g (q (d))

$E=-p(w)Log(q(w))-(1-p(w)-p(d))Log(q(l))-p(d)Log(q(d))$

gdzie $p(w),p(l),p(d)$ winloosedraw $q(w),q(l),q(d)$ win , loosei draw. W tym drugim przypadku reguła aktualizacji byłaby

π_{i}^{'} = π_{i} - η (q_{i} (w) + \frac{q_{i} (d)}{2} - p_{i} (w) - \frac{p_{i} (d)}{2})

$\pi_i'=\pi_i-\eta (q_i(w)+\frac{q_i(d)}{2}-p_i(w)-\frac{p_i(d)}{2})$

π_{j}^{'} = π_{j} - η (q_{j} (w) + \frac{q_{j} (d)}{2} - p_{j} (w) - \frac{p_{j} (d)}{2})

$\pi_j'=\pi_j-\eta (q_j(w)+\frac{q_j(d)}{2}-p_j(w)-\frac{p_j(d)}{2})$

$q_j(w)$ $q_j(d)$ $i$ $j$ $p_i(w)$ $p_i(d)$ $i$ $j$ three outcome

Pytanie brzmi, dlaczego system oceny Elo korzysta z two outcomes reguły aktualizacji nawet w przypadku losowań?

regression optimization rating

— emanuele
źródło

Prawdopodobieństwo losowania, w przeciwieństwie do uzyskania decydującego wyniku, nie jest określone w systemie Elo. Zamiast tego rozważa się remis - zarówno pod względem oczekiwanego wyniku, jak i wyniku meczu - pół zwycięstwa i pół przegranej.

Przykład ze strony Elo w Wikipedii : „Oczekiwany wynik gracza to jego prawdopodobieństwo wygranej plus połowa jego prawdopodobieństwa losowania. Zatem oczekiwany wynik 0,75 może oznaczać 75% szans na wygraną, 25% szans na przegraną i 0% szans na z drugiej strony może oznaczać 50% szansy na wygraną, 0% szansy na przegraną i 50% szansy na remis. ”

Prawdopodobieństwo rysowania, jak już powiedziałem, nie jest określone i prowadzi do prostej two outcomereguły aktualizacji, $R_A^\prime = R_A + K(S_A - E_A)$ , w którym $S_A=1 \cdot (n_w + 0.5 \cdot n_d ) + 0 \cdot (0.5 \cdot n_d + n_l)$ , więc po jednym meczu $S_A=1$ (wygrana) lub $S_A=0.5$ (remis, jako połowa wygranej), lub $S_A=0$ (utrata).

Podobnie jak Elo, system Glicko nie modeluje losowań, ale dokonuje aktualizacji jako średniej wygranej i przegranej (na gracza). Zamiast tego w systemie rankingowym TrueSkill „losowania są modelowane przy założeniu, że różnica w wydajności w danej grze jest niewielka. Stąd szansa na losowanie zależy tylko od różnicy siły gry dwóch graczy. Jednak ustalenia empiryczne w grze pokazu szachowego, że losowanie jest bardziej prawdopodobne między zawodowymi graczami niż początkującymi. Dlatego szansa na losowanie wydaje się również zależeć od poziomu umiejętności. ”

To podejście wymaga innego specyficznego modelowania dla każdej gry (a TrueSkill jest stosowany do kilku gier Microsoft Xbox), więc jest odpowiedni dla Elo i Glicko (zaprojektowanych tylko dla szachów) i nie jest przeznaczony do rankingowej , naszego uniwersalnego systemu rankingowego.

— Tomaso Neri
źródło

„Oczekiwanym wynikiem gracza jest prawdopodobieństwo wygranej plus połowa prawdopodobieństwa losowania”. jest dokładnie tym, co znalazłem w powyższym wzorze. W każdym razie we wzorze aktualizacji Elo połowa prawdopodobieństwa losowania nie jest określona, jak wskazujesz. Pozostaje pytanie, dlaczego w systemie rankingowym Elo nie dbamy o losowania?

— emanuele

Można zawsze wyrazić oczekiwany wynik jako szansę na wygraną i możliwość utraty (i zerową szansę na rysunku - patrz pierwszy przykład z Wikipedii). W tym przypadku „oczekiwanym wynikiem gracza jest jego prawdopodobieństwo wygranej” (i cokolwiek więcej, ponieważ połowa prawdopodobieństwa losowania wynosi zero). Po pojedynczym meczu wynikiem jest wygrana, przegrana lub połowa wygranej. Nawet jeśli masz grę, w której dozwolone są losowania, możesz zaktualizować wynik Elo, używając kombinacji wygranej i przegranej, tak jakby remisy nie miały szans.

— Tomaso Neri