Модель Брэдли-Терри — это вероятностная модель для результатов попарных сравнений между элементами, командами или объектами.
Для пары элементов и взятых из некоторой совокупности, она оценивает вероятность того, что попарное сравнение окажется верным, как
где — положительная реальная оценка.
Сравнение объектов можно интерпретировать как « предпочтительнее », « ранжируется выше » или « превосходит », « выигрывает у », в зависимости от приложения.
Например, может представлять рейтинг команды в спортивном турнире, а вероятность того, что команда выиграет игру против . Или может представлять качество коммерческого продукта и тогда вероятность того, что потребитель предпочтет продукт продукту .
Модель Брэдли-Терри может использоваться в прямом направлении для прогнозирования результатов, как описано выше, но чаще используется в обратном направлении для выведения оценок с учетом результатов наблюдений. При таком применении представляет собой некоторую меру качества или рейтинг объекта , а модель позволяет нам оценить на основе серии попарных сравнений. Например, при опросе о винных предпочтениях респондентам может быть сложно дать полную оценку большому набору вин, но им относительно легко сравнить пары образцов вин и сказать, какое из них, по их мнению, лучше. На основе набора таких попарных сравнений можно затем использовать модель Брэдли-Терри для выведения полного рейтинга вин.
После расчета оценок модель можно использовать и в прямом направлении, например, для прогнозирования вероятного результата матчей, которые еще не были проведены. Например, в примере с опросом о вине можно рассчитать вероятность того, что кто-то предпочтет вино за вином , даже если никто из участников опроса напрямую не сравнивал эту конкретную пару.
История создания Модель названа в честь Ральфа А. Брэдли и Милтона Э. Терри, которые представили ее в 1952 году, хотя она уже была изучена Эрнстом Цермело в 1920-х годах. Приложения модели включают в себя ранжирование участников спортивных, шахматных и других соревнований, ранжирование продуктов в парных сравнительных исследованиях потребительского выбора, анализ иерархий доминирования в сообществах животных и людей, ранжирование журналов, ранжирование моделей ИИ, и оценку релевантности документов в поисковых системах с машинным обучением.
Определение Модель Брэдли-Терри можно параметризовать различными способами. Уравнение , пожалуй, самое распространенное, но есть и ряд других. Брэдли и Терри сами определили экспоненциальные функции оценки , так что.
Тогда вероятность можно представить через сигмоиду
Эта формулировка подчеркивает сходство между моделью Брэдли-Терри и логистической регрессией. Оба используют по сути одну и ту же модель, но по-разному. В логистической регрессии обычно известны параметры и попытки вывести функциональную форму ; при ранжировании по модели Брэдли-Терри известна функциональная форма и делается попытка вывести параметры.
При масштабном коэффициенте 400 это эквивалентно системе рейтинга Эло для игроков с рейтингами Эло и .
Оценка параметров Наиболее распространенное применение модели Брэдли-Терри — вывод значений параметров учитывая наблюдаемый набор результатов , например, победы и поражения в соревновании. Самый простой способ оценки параметров — это оценка максимального правдоподобия, то есть максимизация вероятности наблюдаемых результатов с учетом значений модели и параметров.
Предположим, что мы знаем результаты набора парных соревнований между определенной группой лиц, и пусть будет числом раз, когда лицо побеждает лицо . Тогда вероятность этого набора результатов в модели Брэдли-Терри равна а логарифм правдоподобия вектора параметров равен
Цермело показал, что это выражение имеет только один максимум, который можно найти, дифференцируя по и приравнивая к нулю, что приводит к
Это уравнение не имеет известного замкнутого решения, но Цермело предложил решить его методом простой итерации. Начиная с любого удобного набора (положительных) начальных значений для , итеративно выполнять обновление:
для всех в свою очередь. Результирующие параметры являются произвольными с точностью до общей мультипликативной константы, поэтому после вычисления всех новых значений их следует нормализовать путем деления на их среднее геометрическое следующим образом:
Эта процедура оценки улучшает логарифмическое правдоподобие на каждой итерации и гарантированно в конечном итоге достигает уникального максимума. Однако сходимость происходит медленно. Совсем недавно было отмечено, что уравнение можно также переписать как
которую можно решить путем итерации
снова нормализуем после каждого раунда обновлений с использованием уравнения . Эта итерация дает идентичные результаты, что и в , но сходится гораздо быстрее и поэтому обычно предпочтительнее, чем .
Рабочий пример процедуры решения Рассмотрим спортивное соревнование между четырьмя командами, которые в общей сложности играют между собой 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.
Мы хотели бы оценить относительную силу команд, что мы делаем путем расчета параметров , причем более высокие параметры указывают на большую доблесть. Для этого мы произвольно инициализируем четыре записи в векторе параметров , например, присваивая каждой команде значение 1: . Затем мы применяем уравнение для обновления , что дает
Теперь снова применяем для обновления , убедившись, что используете новое значение что мы только что подсчитали:
Аналогично для и мы получаем
Затем мы нормализуем все параметры, разделив их на их среднее геометрическое чтобы получить оценочные параметры .
Чтобы еще больше улучшить оценки, мы повторяем процесс, используя новые значения . Например,
Повторяя этот процесс для оставшихся параметров и нормализуя, получаем . Повторение еще 10 раз дает быструю сходимость к окончательному решению . Это означает, что команда D является сильнейшей, а команда B — второй по силе, в то время как команды A и C почти равны по силе, но уступают командам B и D. Таким образом, модель Брэдли-Терри позволяет нам сделать вывод о взаимоотношениях между всеми четырьмя командами, даже если не все команды играли друг с другом.
Расширение модели на случай игр с ничьей Если в игре присутствует вероятность ничьи то модель можно расширить введя дополнительный параметр . Тогда вероятности исходов:
— вероятность что побеждает
— вероятность что побеждает
— вероятность ничьей
См. также Рейтинг Эло
Примечания
Категория:Теория вероятностей и математическая статистика