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

Для пары элементов i и j взятых из некоторой совокупности, она оценивает вероятность того, что попарное сравнение i > j окажется верным, как

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

где p_i — положительная реальная оценка.

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

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

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

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

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

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

Тогда вероятность можно представить через сигмоиду

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

Эта формулировка подчеркивает сходство между моделью Брэдли–Терри и логистической регрессией . Оба используют по сути одну и ту же модель, но по-разному. В логистической регрессии обычно известны параметры ${\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 . Тогда вероятность этого набора результатов в модели Брэдли–Терри равна ${\displaystyle \prod _{ij}[\Pr(i>j)]^{w_{ij}}}$ а логарифм правдоподобия вектора параметров p = [p₁, ..., p_n] равен ^[1]

${\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] [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})}},}$

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

${\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]. ^[13]

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

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

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

Затем мы нормализуем все параметры, разделив их на их среднее геометрическое ${\displaystyle (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 . Например,

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

Если в игре присутствует вероятность ничьи то модель можно расширить введя дополнительный параметр^[14] ${\displaystyle \theta >0}$. Тогда вероятности исходов:

${\displaystyle \Pr(i>j)={\frac {p_{i}}{p_{i}+\theta p_{j}}}}$ - вероятность что i побеждает j

${\displaystyle \Pr(j>i)={\frac {p_{j}}{\theta p_{i}+p_{j}}}}$ - вероятность что j побеждает i

${\displaystyle \Pr(j=i)={\frac {(\theta ^{2}-1)p_{i}p_{j}}{(p_{i}+\theta p_{j})(\theta p_{i}+p_{j})}}}$ - вероятность ничьей

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

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями. (7 января 2025)