Нам пообещали починить Rl соревы на каггле!
Кагл стафф пообещал починить будущие RL соревнования: будут прогонять модель Бредли-Терри после периода 'охлаждения' лб. Это ответ на огромную дисперсию и шатание рейтинга в покемонах. Сейчас используют вариацию на тему Glicko score и уже многие заметили ее нестабильность.
Хочу вставить свои 5 копеек и
повыпендриваться своими двумя мастерами в статах объяснить, почему это плохой фикс для Pokemon и даже Orbit Wars
Для начала вспомним, что за Бредли Терри. Подробные выкладки можно почитать
тут, а я попробую объяснить на пальцах. Изначально модель придумал Эрнст Цермело для оценки силы игроков в шахматных турнирах. Сам Эрнст известен тем, что отказался приветствовать фюрера перед каждой парой в университете Фрайбурга и ушел с места почетного профессора. А еще придумал
аксиому выбора. Потом модель вновь переоткрыли, как это водится, через 20 лет.
Базовая идея модели: хотим по стохастическим парным сравнениям определить ранкинг каких-то предметов. Например выяснить, не только то, кто самый крутой шахматист, а кто второй по силе, третий и тд. У нас есть статистика матчей и нам не слишком важно, чтобы каждый сыграл с каждым. Но нам очень важно, чтобы граф связей (игр/сравнений) был связный. Т.е. шагая от шахматиста к шахматисту по связям (матчам с известным исходом) мы всегда могли достичь любого шахматиста лиги.
Хотим из нашего графа побед/поражений (частично заполненного, но связного) вывести такие theta_i, theta_j, что
P(i победит j) = sigma(theta_i - theta_j).
С точки зрения моделей мы банально учим логрег на одной фиче: разнице one hot энкодингов игроков. Пусть у нас три игрока и мы их кодируем:
A. (1, 0, 0)
B. (0, 1, 0)
C. (0, 0, 1)
Тогда один матч, где A играл с C и выиграл у нас будет представлен так:
Фичи: (1, 0, -1) = (1, 0, 0) - (0, 0, 1) = A - C
Таргет: (1) (A победил)
Учим мы соответственно
theta_i. Они собой и представляют 'силу' каждого участника.
Статистические предположения для такой модели следующие:
1. Попарные сравнения независимые (игра каждый раз начинается с начала игры и игры независимые)
2. Латентные качества не меняются (боты не становятся сильнее/слабее между играми)
3. Вероятность победы в паре определяется разностью сил
4. Нет никаких matchup эффектов
Сама модель потом развилась в ELO и Glicko скоры как онлайн-вариант подсчета. И именно последняя используется сейчас на каггле. Если почитаете первую ссылку, то там еще и связь с PageRank можно найти. И даже
скоры силы в баскетболе тоже развитие этих идей.
Так вот, почему идея использовать Бредли-Терри для каггла довольно странная: последние RL соревнования нарушают один из асампшенов модели.
Для покемонов нарушаются два последних: у колод есть матчап эффекты и игроки заранее не равны. Т.е. сила определяется и колодой, и пилотирующим алгоритмом. А колоды работают по принципу камень-ножницы-бумага, которые по дизайну не могут быть отражены в модели.
Более того, модель еще и не поддерживает случай игры вчетвером, поэтому починить дисперсию игр в Orbit тоже не выйдет. Придется использовать какое-нибудь расширение в стиле Плакетта-Люса.
Единственный плюс: где первый фикс метрики, там и выбор разных алгоритмов формирования лб для разных соревнований. Логично силу агентов сравнивать разными способами для разных игр. А то представьте, что мы бы все челленджи по классификации меряли только с помощью Roc-Auc.
