Модель Брэдли – Терри - это вероятностная модель, которая может предсказать результат парного сравнения. Для пары индивидов i и j, взятых из некоторой популяции , он оценивает вероятность того, что попарное сравнение i > j окажется верным, как
где p i - положительный реальный балл, присвоенный индивиду i . Сравнение i > j может быть прочитано как « i предпочтительнее j », « i ранжируется выше, чем j » или « i превосходит j », в зависимости от приложения.
Например, p i может представлять мастерство команды в спортивном турнире, рассчитанное по количеству раз, когда i выигрывал матч.затем представляет собой вероятность того, что я выиграю матч против j . [1] [2] Другой пример, используемый для объяснения цели модели, - это оценка продуктов в определенной категории по качеству. Хотя человеку сложно составить прямой рейтинг (многих) марок вин, возможно, будет целесообразно сравнить образцы пар вин и сказать для каждой пары, какой из них лучше. Затем модель Брэдли – Терри может быть использована для получения полного ранжирования. [2]
История и приложения
Модель названа в честь Р. А. Брэдли и М. Е. Терри [3], которые представили ее в 1952 году [4], хотя она уже была изучена Цермело в 1920-х годах. [1] [5] [6]
Реальные приложения модели включают оценку влияния статистических журналов или ранжирование документов по релевантности в поисковых системах с машинным обучением . [7] В последнем приложенииможет отражать, что документ i более релевантен запросу пользователя, чем документ j , поэтому он должен отображаться раньше в списке результатов. Затем индивидуальные p i выражают релевантность документа и могут быть оценены по частоте, с которой пользователи нажимают на определенные «совпадения», когда им представлен список результатов. [8]
Определение
Модель Брэдли – Терри можно параметризовать различными способами. Один из способов сделать это - выбрать один параметр для каждого наблюдения, что приведет к модели из n параметров p 1 , ..., p n . [9] Другой вариант, фактически версия, рассмотренная Брэдли и Терри, [2] использует экспоненциальные функции оценки. чтобы
или, используя логит (и запрещая связи), [1]
сведение модели к логистической регрессии на парах лиц.
Оценка параметров
Следующий алгоритм вычисляет параметры p i базовой версии модели на основе выборки наблюдений. Формально он вычисляет оценку максимального правдоподобия , т. Е. Максимизирует вероятность наблюдаемых данных. Алгоритм восходит к работе Цермело. [1]
Требуемые наблюдения являются результатами предыдущих сравнений, например, пары ( i , j ), где i превосходит j . Обобщая эти результаты , как вес Ij , сколько раз я обыграла J , мы получим логарифмическую функцию правдоподобия вектора параметров р = р 1 , ..., р п в [1]
Обозначим количество «выигранных» сравнений через i как W i . Начиная с произвольного вектора p , алгоритм итеративно выполняет обновление
для всех я . После вычисления всех новых параметров их следует перенормировать,
Эта процедура оценки улучшает логарифмическую вероятность на каждой итерации и в конечном итоге сходится к уникальному максимуму.
Смотрите также
Рекомендации
- ^ а б в г д Хантер, Дэвид Р. (2004). «Алгоритмы ММ для обобщенных моделей Брэдли – Терри» . Летопись статистики . 32 (1): 384–406. CiteSeerX 10.1.1.110.7878 . DOI : 10.1214 / AOS / 1079120141 . JSTOR 3448514 .
- ^ а б в Агрести, Алан (2014). Категориальный анализ данных . Джон Вили и сыновья. С. 436–439.
- ^ EEM van Berkum. «Модель Брэдли-Терри» . Энциклопедия математики . Проверено 18 ноября 2014 года .
- ^ Брэдли, Ральф Аллан; Терри, Милтон Э. (1952). «Ранговый анализ неполных блочных конструкций: I. Метод парных сравнений». Биометрика . 39 (3/4): 324–345. DOI : 10.2307 / 2334029 . JSTOR 2334029 .
- ^ Цермело, Эрнст (1929). "Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung". Mathematische Zeitschrift . 29 (1): 436–460. DOI : 10.1007 / BF01180541 .
- ^ Хайнц-Дитер Эббингаус (2007), Эрнст Цермело: подход к своей жизни и работе , стр. 268–269, ISBN 9783540495536
- ^ Шуммер, Мартин; Йилмаз, Эмине (2011). Полу-контролируемое обучение для ранжирования с регуляризацией предпочтений (PDF) . CIKM.
- ^ Радлински, Филип; Иоахим, Торстен (2007). Active Exploration for Learning Rankings from Clickthrough Data (PDF) . KDD '07 Материалы 13-й международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных. С. 570–579. DOI : 10.1145 / 1281192.1281254 .
- ^ Fangzhao Wu; Цзюнь Сюй; Ханг Ли; Синь Цзян (2014). Оптимизация ранжирования с ограничениями . CIKM '14 Труды 23-й Международной конференции ACM по управлению информацией и знаниями. С. 1049–1058. DOI : 10.1145 / 2661829.2661895 .