Почему рейтинговая система Elo использует неправильное правило обновления?

Система рейтинга Эло использует алгоритм минимизации градиентного спуска функции кросс-энтропийной потери между ожидаемой и наблюдаемой вероятностью исхода в парных сравнениях. Мы можем написать общие функции потерь как

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

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

где сумма производится по всем исходам и всем противникам . - наблюдаемая частота события а - ожидаемая частота. $i$ $n$ $p_i$ $_i$ $q_i$

В случае только двух возможных результатов (победа или поражение) и одного противника у нас есть

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

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

Если - рейтинг игрока а - рейтинг игрока мы можем построить ожидаемую вероятность как тогда правило обновления градиентного спуска скажет использовать $\pi_i$ $i$ $\pi_j$ $j$

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

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

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)$

где и - ожидаемая и наблюдаемая вероятность выигрыша игрока против игрока . Это обновление правил. $q_i$ $p_i$ $i$ $j$ two outcomes

При наличии ничьих мы можем обобщить вышеприведенную модель, включая и третий результат с вероятностью

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}}}$

И мы можем построить функцию потери как

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))$

где - соответственно наблюдаемая вероятность , и и ожидаемая вероятность , и . В последнем случае правило обновления будет $p(w),p(l),p(d)$ winloosedraw $q(w),q(l),q(d)$ winloosedraw

π_{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

Вопрос в том, почему рейтинговая система Elo использует two outcomesправила обновления даже при наличии розыгрышей?

regression optimization rating Emanuele
источник

Ответы:

Вероятность рисования, в отличие от решающего результата, в системе Эло не указана . Вместо этого рассматривается ничья - как в ожидаемой производительности, так и в исходе матча - половина выигрыша и половина проигрыша.

Пример со страницы Эло в Википедии : «Ожидаемый счет игрока - это вероятность выигрыша плюс половина вероятности выигрыша. Таким образом, ожидаемый счет 0,75 может представлять 75% -ный шанс на выигрыш, 25% -ый шанс проигрыша и 0% -ый шанс». рисования. С другой стороны, он может представлять 50% вероятности выигрыша, 0% вероятности проигрыша и 50% вероятности выигрыша ».

Вероятность рисования, как я уже сказал, не указана , и это приводит к простому two outcomeправилу обновления, , в котором , поэтому после одного матча (победа) или (ничья, как половина выигрыша) или (проигрыш). $R_A^\prime = R_A + K(S_A - E_A)$ $S_A=1 \cdot (n_w + 0.5 \cdot n_d ) + 0 \cdot (0.5 \cdot n_d + n_l)$ $S_A=1$ $S_A=0.5$ $S_A=0$

Как и Elo, система Glicko не моделирует ничьи, но обновляет ее как среднее значение выигрыша и проигрыша (на игрока). Вместо этого в системе ранжирования TrueSkill «ничьи» моделируются исходя из предположения, что разница в производительности в конкретной игре мала. Следовательно, вероятность ничьей зависит только от разницы игровой силы двух игроков. Однако эмпирические результаты в игре шахматного шоу показывает, что ничья между профессиональными игроками более вероятна, чем у начинающих. Следовательно, вероятность рисования также зависит от уровня квалификации ».

Этот подход требует различного специфического моделирования для каждой игры (и TrueSkill применяется к нескольким играм Microsoft Xbox), поэтому он подходит для Elo и Glicko (предназначенных только для шахмат), и не для ранда , нашей многоцелевой системы ранжирования.

Томазо Нери
источник

«Ожидаемый счет игрока - это вероятность выигрыша плюс половина вероятности выигрыша». это именно то, что я нашел в формуле выше. В любом случае в формуле обновления Elo половина вероятности ничьей не указана, как вы указываете. Остается вопрос, почему в системе ранжирования Elo нас не волнуют ничьи?

Эммануил

Вы всегда можете выразить ожидаемый счет как шанс на выигрыш и шанс на проигрыш (и нулевой шанс на ничью - см. Первый пример из Википедии). В этом случае «ожидаемый счет игрока - это его вероятность выигрыша» (и что-то еще, потому что половина вероятности выигрыша равна нулю). После одного матча результатом является победа или проигрыш или половина выигрыша. Даже если у вас есть игра, в которой разрешены ничьи, вы можете обновить счет Эло, используя только комбинацию выигрыша и проигрыша, как будто ничья не имеет шансов.

Томазо Нери