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

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

Для пары элементов Шаблон:Mvar и Шаблон:Mvar взятых из некоторой совокупности, она оценивает вероятность того, что попарное сравнение Шаблон:Math окажется верным, как

$\mathrm{Pr}(i>j)=\frac{p_i}{p_i+p_j}$ [1]Шаблон:Anchor

где Шаблон:Mvar — положительная реальная оценка.

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

Например, Шаблон:Mvar может представлять рейтинг команды в спортивном турнире, а $\mathrm{Pr}(i>j)$ вероятность того, что команда Шаблон:Mvar выиграет игру против Шаблон:Mvar . Или Шаблон:Mvar может представлять качество коммерческого продукта и тогда$\mathrm{Pr}(i>j)$ вероятность того, что потребитель предпочтет продукт Шаблон:Mvar продукту Шаблон:Mvar .

Модель Брэдли–Терри может использоваться в прямом направлении для прогнозирования результатов, как описано выше, но чаще используется в обратном направлении для выведения оценок Шаблон:Mvar с учетом результатов наблюдений. При таком применении Шаблон:Mvar представляет собой некоторую меру качества или рейтинг объекта $i$, а модель позволяет нам оценить Шаблон:Mvar на основе серии попарных сравнений. Например, при опросе о винных предпочтениях респондентам может быть сложно дать полную оценку большому набору вин, но им относительно легко сравнить пары образцов вин и сказать, какое из них, по их мнению, лучше. На основе набора таких попарных сравнений можно затем использовать модель Брэдли–Терри для выведения полного рейтинга вин.

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

История создания

Модель названа в честь Ральфа А. Брэдли и Милтона Э. Терри, которые представили ее в 1952 году, хотя она уже была изучена Эрнстом Цермело в 1920-х годах. Приложения модели включают в себя ранжирование участников спортивных, шахматных и других соревнований, ранжирование продуктов в парных сравнительных исследованиях потребительского выбора, анализ иерархий доминирования в сообществах животных и людей, ранжирование журналов, ранжирование моделей ИИ, и оценку релевантности документов в поисковых системах с машинным обучением .

Определение

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

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

$\mathrm{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).$

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

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

$\mathrm{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$, например, победы и поражения в соревновании. Самый простой способ оценки параметров — это оценка максимального правдоподобия, т. е. максимизация вероятности наблюдаемых результатов с учетом значений модели и параметров.

Предположим, что мы знаем результаты набора парных соревнований между определенной группой лиц, и пусть Шаблон:Mvar будет числом раз, когда лицо Шаблон:Mvar побеждает лицо Шаблон:Mvar . Тогда вероятность этого набора результатов в модели Брэдли–Терри равна $\prod _{ij}[\mathrm{Pr}(i>j){]}^{w_{ij}}$ а логарифм правдоподобия вектора параметров Шаблон:Math равен

$\begin{array}{cc}𝓁(𝐩)& =\ln \prod _{ij}{[\mathrm{Pr}(i>j)]}^{w_{ij}}=\sum _{i=1}^n\sum _{j=1}^n\ln \left[{\left(\frac{p_i}{p_i+p_j}\right)}^{w_{ij}}\right]\\ & =\sum _{ij}{w}_{ij}\ln \left(\frac{p_i}{p_i+p_j}\right)=\sum _{ij}[w_{ij}\ln (p_i)-w_{ij}\ln (p_i+p_j)].\end{array}$

Цермело показал, что это выражение имеет только один максимум, который можно найти, дифференцируя по $p_i$ и приравнивая к нулю, что приводит к

$p_i=\frac{\sum _j{w}_{ij}}{\sum _j(w_{ij}+w_{ji})/(p_i+p_j)}$ [2]Шаблон:Anchor

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

${p_i}^{\prime }=\frac{\sum _j{w}_{ij}}{\sum _j(w_{ij}+w_{ji})/(p_i+p_j)}$ [3] Шаблон:Anchor

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

$p_i\leftarrow \frac{p{\text{'}}_i}{{\left(\prod _{j=1}^{n}p{\text{'}}_j\right)}^{1/n}}$ [4]Шаблон:Anchor

Эта процедура оценки улучшает логарифмическое правдоподобие на каждой итерации и гарантированно в конечном итоге достигает уникального максимума. Однако сходимость происходит медленно. Совсем недавно было отмечено , что уравнение [2] можно также переписать как

$p_i=\frac{\sum _j{w}_{ij}{p}_j/(p_i+p_j)}{\sum _j{w}_{ji}/(p_i+p_j)},$

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

${p_i}^{\prime }=\frac{\sum _j{w}_{ij}{p}_j/(p_i+p_j)}{\sum _j{w}_{ji}/(p_i+p_j)}$ [5]Шаблон:Anchor

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

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

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

Результаты

	A	B	C	D
A	–	2	0	1
B	3	–	5	0
C	0	3	–	1
D	4	0	3	–

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

Мы хотели бы оценить относительную силу команд, что мы делаем путем расчета параметров $p_i$, причем более высокие параметры указывают на большую доблесть. Для этого мы произвольно инициализируем четыре записи в векторе параметров Шаблон:Math, например, присваивая каждой команде значение 1: Шаблон:Math . Затем мы применяем уравнение [5] для обновления $p_1$, что дает

$$p_1=\frac{\sum _{j(\ne 1)}{w}_{1j}{p}_j/(p_1+p_j)}{\sum _{j(\ne 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(\ne 2)}{w}_{2j}{p}_j/(p_2+p_j)}{\sum _{j(\ne 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(\ne 3)}{w}_{3j}{p}_j/(p_3+p_j)}{\sum _{j(\ne 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(\ne 4)}{w}_{4j}{p}_j/(p_4+p_j)}{\sum _{j(\ne 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$ чтобы получить оценочные параметры Шаблон:Math .

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

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

Повторяя этот процесс для оставшихся параметров и нормализуя, получаем Шаблон:Math . Повторение еще 10 раз дает быструю сходимость к окончательному решению Шаблон:Math . Это означает, что команда D является сильнейшей, а команда B — второй по силе, в то время как команды A и C почти равны по силе, но уступают командам B и D. Таким образом, модель Брэдли–Терри позволяет нам сделать вывод о взаимоотношениях между всеми четырьмя командами, даже если не все команды играли друг с другом.

Расширение модели на случай игр с ничьей

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

$\mathrm{Pr}(i>j)=\frac{p_i}{p_i+\theta p_j}$ - вероятность что Шаблон:Mvar побеждает Шаблон:Mvar

$\mathrm{Pr}(j>i)=\frac{p_j}{\theta p_i+p_j}$ - вероятность что Шаблон:Mvar побеждает Шаблон:Mvar

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

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

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