Модель Брэдли–Терри

Статистическая модель для парных сравнений

Модель Брэдли–Терри — это вероятностная модель для результата парных сравнений между элементами, командами или объектами. При наличии пары элементов i и j, взятых из некоторой популяции , она оценивает вероятность того, что парное сравнение i > j окажется верным, как

где p _i — положительная реальная оценка, присвоенная индивидууму i . Сравнение i > j можно читать как « i предпочтительнее j », « i ранжируется выше j » или « i превосходит j », в зависимости от приложения.

Например, p _i может представлять мастерство команды в спортивном турнире и вероятность того, что i выиграет игру против j . ^{[1] [2]} Или p _i может представлять качество или желательность коммерческого продукта и вероятность того, что потребитель предпочтет продукт i продукту j . ${\displaystyle \Pr(i>j)}$ ${\displaystyle \Pr(i>j)}$

Модель Брэдли–Терри может использоваться в прямом направлении для прогнозирования результатов, как описано, но чаще используется в обратном направлении для выведения оценок p _i с учетом наблюдаемого набора результатов. ^[2] В этом типе применения p _i представляет собой некоторую меру силы или качества , и модель позволяет нам оценивать силы из серии парных сравнений. Например, в опросе предпочтений в отношении вина респондентам может быть сложно дать полный рейтинг большого набора вин, но им относительно легко сравнить пары образцов вин и сказать, какое из них, по их мнению, лучше. Основываясь на наборе таких парных сравнений, модель Брэдли–Терри затем может использоваться для получения полного рейтинга вин. ${\displaystyle i}$

После того, как значения оценок p _i были рассчитаны, модель может затем также использоваться в прямом направлении, например, для прогнозирования вероятного результата сравнений, которые еще не произошли. В примере с опросом о вине, например, можно было бы рассчитать вероятность того, что кто-то предпочтет вино вместо вина , даже если никто в опросе напрямую не сравнивал эту конкретную пару. ${\displaystyle i}$ ${\displaystyle j}$

История и применение

Модель названа в честь Ральфа А. Брэдли и Милтона Э. Терри, ^[3] которые представили ее в 1952 году, ^[4] хотя она уже была изучена Эрнстом Цермело в 1920-х годах. ^{[1] [5] [6]} Приложения модели включают ранжирование участников спортивных, шахматных и других соревнований, ^[7] ранжирование продуктов в парных сравнительных опросах потребительского выбора , анализ иерархий доминирования в сообществах животных и людей, ^[8] ранжирование журналов , ранжирование моделей ИИ, ^[9] и оценку релевантности документов в поисковых системах с машинным обучением . ^[10]

Определение

Модель Брэдли–Терри может быть параметризована различными способами. Уравнение ( 1 ), возможно, является наиболее распространенным, но есть и ряд других. Брэдли и Терри сами определили экспоненциальные функции оценки , так что ^[2] ${\displaystyle p_{i}=e^{\beta _{i}}}$

${\displaystyle \Pr(i>j)={\frac {e^{\beta _{i}}}{e^{\beta _{i}}+e^{\beta _{j}}}}.}$

В качестве альтернативы можно использовать логит , такой что ^[1]

${\displaystyle \operatorname {logit} \Pr(i>j)=\log {\frac {\Pr(i>j)}{1-\Pr(i>j)}}=\log {\frac {\Pr(i>j)}{\Pr(j>i)}}=\beta _{i}-\beta _{j},}$

т.е. для ${\textstyle \operatorname {logit} p=\log {\frac {p}{1-p}}}$ ${\textstyle 0<p<1.}$

Эта формулировка подчеркивает сходство между моделью Брэдли–Терри и логистической регрессией . Обе используют по сути одну и ту же модель, но по-разному. В логистической регрессии обычно известны параметры и делается попытка вывести функциональную форму ; при ранжировании по модели Брэдли–Терри известна функциональная форма и делается попытка вывести параметры. ${\displaystyle \beta _{i}}$ ${\displaystyle \Pr(i>j)}$

При масштабном коэффициенте 400 это эквивалентно системе рейтинга Эло для игроков с рейтингами Эло R _i и R _j .

${\displaystyle \Pr(i>j)={\frac {e^{R_{i}/400}}{e^{R_{i}/400}+e^{R_{j}/400}}}={\frac {1}{1+e^{(R_{j}-R_{i})/400}}}.}$

Оценка параметров

Наиболее распространенное применение модели Брэдли–Терри — выведение значений параметров на основе наблюдаемого набора результатов , таких как победы и поражения в соревновании. Самый простой способ оценки параметров — оценка максимального правдоподобия , т. е. максимизация вероятности наблюдаемых результатов с учетом модели и значений параметров. ${\displaystyle p_{i}}$ ${\displaystyle i>j}$

Предположим, что мы знаем результаты набора парных соревнований между определенной группой индивидуумов, и пусть w _ij будет числом раз, когда индивидуум i побеждает индивидуума j . Тогда вероятность этого набора результатов в модели Брэдли–Терри равна , а логарифмическое правдоподобие вектора параметров p = [ p ₁ , ..., p _n ] равно ^[1] ${\displaystyle \prod _{ij}[\Pr(i>j)]^{w_{ij}}}$

${\displaystyle {\begin{aligned}{\mathcal {l}}(\mathbf {p} )&=\ln \prod _{ij}{{\bigl [}\Pr(i>j){\bigr ]}}^{w_{ij}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\ln {\biggl [}\left({\frac {p_{i}}{p_{i}+p_{j}}}\right)^{w_{ij}}{\biggr ]}\\[6pt]&=\sum _{ij}w_{ij}\ln {\biggl (}{\frac {p_{i}}{p_{i}+p_{j}}}{\biggr )}=\sum _{ij}{\bigl [}w_{ij}\ln(p_{i})-w_{ij}\ln(p_{i}+p_{j}){\bigr ]}.\end{aligned}}}$

Цермело ^[5] показал, что это выражение имеет только один максимум, который можно найти, дифференцируя по и приравнивая результат к нулю, что приводит к ${\displaystyle p_{i}}$

Это уравнение не имеет известного решения в замкнутой форме, но Цермело предложил решить его простой итерацией. Начиная с любого удобного набора (положительных) начальных значений для , итеративно выполняется обновление ${\displaystyle p_{i}}$

для всех i по очереди. Результирующие параметры произвольны с точностью до общей мультипликативной константы, поэтому после вычисления всех новых значений их следует нормализовать, разделив на их геометрическое среднее, таким образом:

Эта процедура оценки улучшает логарифмическое правдоподобие на каждой итерации и гарантированно в конечном итоге достигает уникального максимума. ^{[5] [11]} Однако сходимость медленная. ^{[1] [12]} Совсем недавно было отмечено ^[13], что уравнение ( 2 ) также можно переписать как

${\displaystyle p_{i}={\frac {\sum _{j}w_{ij}p_{j}/(p_{i}+p_{j})}{\sum _{j}w_{ji}/(p_{i}+p_{j})}},}$

которую можно решить путем итерации

снова нормализуя после каждого раунда обновлений с использованием уравнения ( 4 ). Эта итерация дает идентичные результаты, что и в ( 3 ), но сходится гораздо быстрее и, следовательно, обычно предпочтительнее, чем ( 3 ). ^[13]

Рабочий пример процедуры решения

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

Например, команда A дважды обыграла команду B и трижды проиграла команде B; вообще не играла с командой C; выиграла один раз и проиграла четыре раза команде D.

Мы хотели бы оценить относительную силу команд, что мы делаем, вычисляя параметры , где более высокие параметры указывают на большую доблесть. Для этого мы инициализируем четыре записи в векторе параметров p произвольно, например, присваивая значение 1 каждой команде: [1, 1, 1, 1] . Затем мы применяем уравнение ( 5 ) для обновления , что дает ${\displaystyle p_{i}}$ ${\displaystyle p_{1}}$

$${\displaystyle p_{1}={\frac {\sum _{j(\neq 1)}w_{1j}p_{j}/(p_{1}+p_{j})}{\sum _{j(\neq 1)}w_{j1}/(p_{1}+p_{j})}}={\frac {2{\frac {1}{1+1}}+0{\frac {1}{1+1}}+1{\frac {1}{1+1}}}{3{\frac {1}{1+1}}+0{\frac {1}{1+1}}+4{\frac {1}{1+1}}}}=0.429.}$$

Теперь мы снова применяем ( 5 ) для обновления , убедившись, что используем новое значение, которое мы только что вычислили: ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$

$${\displaystyle p_{2}={\frac {\sum _{j(\neq 2)}w_{2j}p_{j}/(p_{2}+p_{j})}{\sum _{j(\neq 2)}w_{j2}/(p_{2}+p_{j})}}={\frac {3{\frac {0.429}{1+0.429}}+5{\frac {1}{1+1}}+0{\frac {1}{1+1}}}{2{\frac {1}{1+0.429}}+3{\frac {1}{1+1}}+0{\frac {1}{1+1}}}}=1.172}$$

Аналогично для и получаем ${\displaystyle p_{3}}$ ${\displaystyle p_{4}}$

$${\displaystyle p_{3}={\frac {\sum _{j(\neq 3)}w_{3j}p_{j}/(p_{3}+p_{j})}{\sum _{j(\neq 3)}w_{j3}/(p_{3}+p_{j})}}={\frac {0{\frac {0.429}{1+0.429}}+3{\frac {1.172}{1+1.172}}+1{\frac {1}{1+1}}}{0{\frac {1}{1+0.429}}+5{\frac {1}{1+1.172}}+3{\frac {1}{1+1}}}}=0.557}$$

$${\displaystyle p_{4}={\frac {\sum _{j(\neq 4)}w_{4j}p_{j}/(p_{4}+p_{j})}{\sum _{j(\neq 4)}w_{j4}/(p_{4}+p_{j})}}={\frac {4{\frac {0.429}{1+0.429}}+0{\frac {1.172}{1+1.172}}+3{\frac {0.557}{1+0.557}}}{1{\frac {1}{1+0.429}}+0{\frac {1}{1+1.172}}+1{\frac {1}{1+0.557}}}}=1.694}$$

Затем мы нормализуем все параметры, разделив их на их среднее геометрическое значение , чтобы получить оценочные параметры p = [0,516, 1,413, 0,672, 2,041] . ${\displaystyle (0.429\times 1.172\times 0.557\times 1.694)^{1/4}=0.830}$

Чтобы еще больше улучшить оценки, мы повторяем процесс, используя новые значения p . Например,

$${\displaystyle p_{1}={\frac {2\cdot {\frac {1.413}{0.516+1.413}}+0\cdot {\frac {0.672}{0.516+0.672}}+1\cdot {\frac {2.041}{0.516+2.041}}}{3\cdot {\frac {1}{0.516+1.413}}+0\cdot {\frac {1}{0.516+0.672}}+4\cdot {\frac {1}{0.516+2.041}}}}=0.725.}$$

Повторяя этот процесс для оставшихся параметров и нормализуя, мы получаем p = [0,677, 1,034, 0,624, 2,287] . Повторение еще 10 раз дает быструю сходимость к окончательному решению p = [0,640, 1,043, 0,660, 2,270] . Это означает, что команда D является сильнейшей, а команда B — второй по силе, в то время как команды A и C почти равны по силе, но уступают командам B и D. Таким образом, модель Брэдли–Терри позволяет нам сделать вывод о взаимосвязи между всеми четырьмя командами, даже если не все команды играли друг с другом.

Смотрите также

• Порядковая регрессия
• модель Раша
• Шкала (общественные науки)
• Система рейтинга Эло
• модель Терстона

Ссылки

1. Хантер, Дэвид Р. (2004). «Алгоритмы ММ для обобщенных моделей Брэдли–Терри». Анналы статистики . 32 (1): 384–406. CiteSeerX  10.1.1.110.7878 . doi :10.1214/aos/1079120141. JSTOR  3448514.
2. Agresti, Alan (2014). Категориальный анализ данных . John Wiley & Sons. С. 436–439.
3. EEM van Berkum. "Модель Брэдли-Терри". Энциклопедия математики . Получено 18 ноября 2014 г.
4. Брэдли, Ральф Аллан; Терри, Милтон Э. (1952). «Ранговый анализ неполных блочных схем: I. Метод парных сравнений». Biometrika . 39 (3/4): 324–345. doi :10.2307/2334029. JSTOR  2334029.
5. Цермело, Эрнст (1929). «Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung». Mathematische Zeitschrift . 29 (1): 436–460. дои : 10.1007/BF01180541. S2CID  122877703.
6. Хайнц-Дитер Эббингауз (2007), Эрнст Цермело: Подход к его жизни и творчеству , Springer, стр. 268–269, ISBN 9783540495536
7. Шев, А.; Фуджи, К.; Хси, Ф.; МакКован, Б. (2014). «Системное тестирование модели Брэдли-Терри против нелинейной иерархии ранжирования». PLOS One . 9 (12): e115367. doi : 10.1371/journal.pone.0115367 . PMC 4274013. PMID  25531899 . 
8. Бойд, Роберт; Силк, Джоан Б. (1983). «Метод назначения рангов кардинального доминирования». Animal Behaviour . 31 (1): 45–58. doi :10.1016/S0003-3472(83)80172-9. S2CID  53178779.
9. "Chatbot Arena: Новые модели и обновление системы Elo | LMSYS Org". lmsys.org . Получено 2024-01-30 .
10. Шуммер, Мартин; Йилмаз, Эмине (2011). Полуконтролируемое обучение ранжированию с регуляризацией предпочтений (PDF) . CIKM.
11. Форд, младший, Л. Р. (1957). «Решение проблемы ранжирования с помощью бинарных сравнений». American Mathematical Monthly . 64 (8): 28–33. doi :10.1080/00029890.1957.11989117.
12. Dykstra, Jr., Otto (1956). «Заметка о ранговом анализе неполных блочных конструкций». Биометрия . 12 : 301–306. doi :10.2307/2334029. JSTOR  2334029.
13. Newman, MEJ (2023). «Эффективное вычисление рейтингов из парных сравнений». Журнал исследований машинного обучения . 24 (238): 1–25.