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

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

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

1

где 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 я}$

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

Стандартным обобщением модели BT является модель Плакетта– Льюса , ^{[11] [12]} , которая моделирует ранжирование элементов. В тех же обозначениях, что и модель BT: Это можно представить как вытягивание из урны с заменой . Урна содержит шары, окрашенные пропорционально , ​​и один извлекается из урны с заменой. Если у шара новый цвет, то этот шар помещается в качестве следующего по рангу шара. В противном случае, если шар имеет уже вытянутый цвет, то он отбрасывается.${\displaystyle N}$$${\displaystyle \Pr(y_{1}>\dots >y_{N})={\frac {p_{y_{1}}}{p_{y_{1}}+\dots +p_{y_{N} }}}{\frac {p_{y_{2}}}{p_{y_{2}}+\dots +p_{y_{N}}}}\dots {\frac {p_{y_{N}}}{p_{y_{N}}}}}$$${\displaystyle p_{1},p_{2},\точки ,p_{N}}$

Учитывая пропорции , модель PL может быть выбрана методом «экспоненциальной гонки». Один выбирает «время радиоактивного распада» из « экспоненциальных часов», то есть . Затем ранжирует элементы в соответствии с порядком, в котором они распались. В этой интерпретации сразу становится ясно, что модель PL удовлетворяет аксиоме выбора Люса (из того же Люса). Следовательно, для любых двух , сводится к модели BT, и в общем случае для любого подмножества выборов сводится к меньшей модели PL с теми же параметрами.${\displaystyle p_{1},p_{2},\точки ,p_{N}}$${\displaystyle N}$${\displaystyle t_{1}\sim \mathrm {Exp} (p_{1}),\dots ,t_{N}\sim \mathrm {Exp} (p_{N})}$${\displaystyle y,z}$${\displaystyle \Pr(y>z)={\frac {p_{y}}{p_{y}+p_{z}}}}$${\displaystyle y_{1},\dots,y_{M}}$$${\displaystyle \Pr(y_{1}>\dots >y_{N})={\frac {p_{y_{1}}}{p_{y_{1}}+\dots +p_{y_{M}}}}{\frac {p_{y_{2}}}{p_{y_{2}}+\dots +p_{y_{M}}}}\dots {\frac {p_{y_{M}}}{p_{y_{M}}}}}$$

Наиболее распространенное применение модели Брэдли–Терри — выведение значений параметров на основе наблюдаемого набора результатов , таких как победы и поражения в соревновании. Самый простой способ оценки параметров — оценка максимального правдоподобия , т. е. максимизация вероятности наблюдаемых результатов с учетом модели и значений параметров.${\displaystyle p_{i}}$${\displaystyle я>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}={\frac {\sum _{j}w_{ij}}{\sum _{j}(w_{ij}+w_{ji})/(p_{i}+p_{j})}}.}$

2

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

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

3

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

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

4

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

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

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

${\displaystyle 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 ). ^[15]

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

Модель Crowd-BT, разработанная в 2013 году Ченом и др. ^[16], пытается расширить стандартную модель Брэдли–Терри для краудсорсинговых настроек, одновременно сокращая количество необходимых сравнений, принимая во внимание надежность каждого судьи. В частности, она выявляет и исключает судей, предположительно являющихся спамерами (выбирающими варианты случайным образом) или злонамеренными (выбирающими всегда неправильный выбор). В краудсорсинговой задаче ранжирования документов по сложности чтения с 624 судьями, каждый из которых вносил до 40 парных сравнений, было показано, что Crowd-BT превосходит как стандартную модель Брэдли–Терри, так и систему ранжирования TrueSkill . Она была рекомендована для использования, когда качественные результаты ценятся выше эффективности, а количество сравнений велико. ^[17]

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