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

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

\Pr(i>j)={\frac {p_{i}}{p_{i}+p_{j}}}

( 1 )

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

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

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

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

История и приложения

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

Определение

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

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

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

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

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

С масштабным коэффициентом 400 это эквивалентно рейтинговой системе Эло для игроков с рейтингами Эло $R i$ и $R j$ .

\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}}}.

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

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

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

{\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 ]} показал, что это выражение имеет только один максимум, который можно найти, дифференцируя по $p_{i}$ и установка результата равным нулю, что приводит к

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

( 2 )

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

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

( 3 )

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

p_{i}\leftarrow {\frac {p'_{i}}{\left(\prod _{j=1}^{n}p'_{j}\right)^{1/n}}}.

( 4 )

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

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

которое можно решить повторением

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

( 5 )

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

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

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

Результаты
	А	Б	С	Д
А	–	2	0	1
Б	3	–	5	0
С	0	3	–	1
Д	4	0	3	–

Например, команда А дважды обыграла команду Б и трижды проиграла команде Б; вообще не играл за команду С; выиграл один раз и четырежды проиграл команде D.

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

$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 ) снова, чтобы обновить $p_{2}$ , убедившись, что используется новое значение $p_{1}$ что мы только что рассчитали:

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

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

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

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

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

Для дальнейшего улучшения оценок мы повторяем процесс, используя новые $значения p$ . Например,

$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. Таким образом, модель Брэдли-Терри позволяет нам сделать вывод о взаимоотношениях между всеми четырьмя командами. хотя не все команды играли друг с другом.

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Хантер, Дэвид Р. (2004). «Алгоритмы ММ для обобщенных моделей Брэдли – Терри» . Анналы статистики . 32 (1): 384–406. CiteSeerX 10.1.1.110.7878 . дои : 10.1214/aos/1079120141 . JSTOR 3448514 .
^ Перейти обратно: ^а ^б ^с Агрести, Алан (2014). Категориальный анализ данных . Джон Уайли и сыновья. стр. 436–439.
^ ЭЕМ ван Беркум. «Модель Брэдли-Терри» . Энциклопедия математики . Проверено 18 ноября 2014 .
^ Брэдли, Ральф Аллан; Терри, Милтон Э. (1952). «Ранговый анализ неполных блочных конструкций: I. Метод парных сравнений». Биометрика . 39 (3/4): 324–345. дои : 10.2307/2334029 . JSTOR 2334029 .
^ Перейти обратно: ^а ^б ^с Цермело, Эрнст (1929). «Подсчет результатов турнира как задача максимума теории вероятностей». Математический журнал . 29 (1): 436–460. дои : 10.1007/BF01180541 . S2CID 122877703 .
^ Хайнц-Дитер Эббингауз (2007), Эрнст Цермело: подход к его жизни и работе , Springer, стр. 268–269, ISBN 9783540495536
^ Шев, А.; Фуджи, К.; Се, Ф.; МакКоуэн, Б. (2014). «Системное тестирование модели Брэдли-Терри на предмет нелинейной иерархии ранжирования» . ПЛОС Один . 9 (12): e115367. дои : 10.1371/journal.pone.0115367 . ПМК 4274013 . ПМИД 25531899 .
^ Бойд, Роберт; Силк, Джоан Б. (1983). «Метод присвоения кардинальных рангов доминирования». Поведение животных . 31 (1): 45–58. дои : 10.1016/S0003-3472(83)80172-9 . S2CID 53178779 .
^ «Арена чат-ботов: новые модели и обновление системы Elo | LMSYS Org» . lmsys.org . Проверено 30 января 2024 г.
^ Шуммер, Мартин; Йылмаз, Эмине (2011). Полуконтролируемое обучение ранжированию с регуляризацией предпочтений (PDF) . ЦИКМ.
^ Форд-младший, LR (1957). «Решение проблемы ранжирования на основе бинарных сравнений». Американский математический ежемесячник . 64 (8): 28–33. дои : 10.1080/00029890.1957.11989117 .
^ Дикстра-младший, Отто (1956). «Заметка о ранговом анализе неполных блочных конструкций». Биометрия . 12 : 301–306. дои : 10.2307/2334029 . JSTOR 2334029 .
^ Перейти обратно: ^а ^б Ньюман, МЕДЖ (2023). «Эффективное вычисление рейтингов на основе парных сравнений» . Журнал исследований машинного обучения . 24 (238): 1–25.

[hunter-1] Перейти обратно: ^а ^б ^с ^д ^и Хантер, Дэвид Р. (2004). «Алгоритмы ММ для обобщенных моделей Брэдли – Терри» . Анналы статистики . 32 (1): 384–406. CiteSeerX 10.1.1.110.7878 . дои : 10.1214/aos/1079120141 . JSTOR 3448514 .

[agresti-2] Перейти обратно: ^а ^б ^с Агрести, Алан (2014). Категориальный анализ данных . Джон Уайли и сыновья. стр. 436–439.

[3] ЭЕМ ван Беркум. «Модель Брэдли-Терри» . Энциклопедия математики . Проверено 18 ноября 2014 .

[4] Брэдли, Ральф Аллан; Терри, Милтон Э. (1952). «Ранговый анализ неполных блочных конструкций: I. Метод парных сравнений». Биометрика . 39 (3/4): 324–345. дои : 10.2307/2334029 . JSTOR 2334029 .

[zermelo-5] Перейти обратно: ^а ^б ^с Цермело, Эрнст (1929). «Подсчет результатов турнира как задача максимума теории вероятностей». Математический журнал . 29 (1): 436–460. дои : 10.1007/BF01180541 . S2CID 122877703 .

[6] Хайнц-Дитер Эббингауз (2007), Эрнст Цермело: подход к его жизни и работе , Springer, стр. 268–269, ISBN 9783540495536

[7] Шев, А.; Фуджи, К.; Се, Ф.; МакКоуэн, Б. (2014). «Системное тестирование модели Брэдли-Терри на предмет нелинейной иерархии ранжирования» . ПЛОС Один . 9 (12): e115367. дои : 10.1371/journal.pone.0115367 . ПМК 4274013 . ПМИД 25531899 .

[8] Бойд, Роберт; Силк, Джоан Б. (1983). «Метод присвоения кардинальных рангов доминирования». Поведение животных . 31 (1): 45–58. дои : 10.1016/S0003-3472(83)80172-9 . S2CID 53178779 .

[9] «Арена чат-ботов: новые модели и обновление системы Elo | LMSYS Org» . lmsys.org . Проверено 30 января 2024 г.

[10] Шуммер, Мартин; Йылмаз, Эмине (2011). Полуконтролируемое обучение ранжированию с регуляризацией предпочтений (PDF) . ЦИКМ.

[11] Форд-младший, LR (1957). «Решение проблемы ранжирования на основе бинарных сравнений». Американский математический ежемесячник . 64 (8): 28–33. дои : 10.1080/00029890.1957.11989117 .

[12] Дикстра-младший, Отто (1956). «Заметка о ранговом анализе неполных блочных конструкций». Биометрия . 12 : 301–306. дои : 10.2307/2334029 . JSTOR 2334029 .

[newman-13] Перейти обратно: ^а ^б Ньюман, МЕДЖ (2023). «Эффективное вычисление рейтингов на основе парных сравнений» . Журнал исследований машинного обучения . 24 (238): 1–25.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]