Учимся ранжировать - Википедия - Learning to rank

Часть серии по
Машинное обучение
и
сбор данных

Учимся ранжировать[1] или же машинное обучение (MLR) является применением машинное обучение обычно под наблюдением, полууправляемый или же обучение с подкреплением, в строительстве модели ранжирования за поиск информации системы.[2] Данные обучения состоит из списков элементов с некоторыми частичный заказ указывается между элементами в каждом списке. Этот порядок обычно создается путем выставления числовой или порядковой оценки или бинарной оценки (например, «релевантный» или «неактуальный») для каждого пункта. Целью модели ранжирования является ранжирование, т. Е. Создание перестановка элементов в новых невидимых списках аналогично ранжированию в обучающих данных.

Приложения

В поиске информации

Возможная архитектура поисковой системы с машинным обучением.

Рейтинг - центральная часть многих поиск информации проблемы, такие как поиск документов, совместная фильтрация, анализ настроений, и он-лайн реклама.

Возможная архитектура поисковой машины с машинным обучением показана на прилагаемом рисунке.

Данные обучения состоят из запросов и документов, соответствующих им, вместе со степенью релевантности каждого совпадения. Он может быть приготовлен вручную человеком. оценщики (или же рейтеры, так как Google называет их), которые проверяют результаты по некоторым запросам и определяют актуальность каждого результата. Невозможно проверить релевантность всех документов, поэтому обычно используется метод, называемый объединением - проверяются только несколько верхних документов, извлеченных некоторыми существующими моделями ранжирования. В качестве альтернативы обучающие данные могут быть получены автоматически путем анализа журналы переходов (т.е. результаты поиска, по которым пользователи нажимали),[3] цепочки запросов,[4] или такие функции поисковых систем, как Google SearchWiki.

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

Обычно пользователи ожидают, что поисковый запрос будет выполнен за короткое время (например, несколько сотен миллисекунд для веб-поиска), что делает невозможным оценку сложной модели ранжирования для каждого документа в корпусе, поэтому двухэтапная схема является использовал.[5] Во-первых, небольшое количество потенциально релевантных документов идентифицируется с использованием более простых моделей поиска, которые позволяют быстро оценивать запросы, например векторная космическая модель, логическая модель, взвешенное И,[6] или же BM25. Эта фаза называется верх- поиск документов и в литературе было предложено множество эвристических методов для ускорения этого процесса, например, использование статической оценки качества документа и многоуровневых индексов.[7] На втором этапе для повторного ранжирования этих документов используется более точная, но дорогостоящая в вычислительном отношении модель машинного обучения.

В других сферах

Алгоритмы обучения ранжированию применялись не только в поиске информации:

  • В машинный перевод для ранжирования набора предполагаемых переводов;[8]
  • В вычислительная биология для ранжирования кандидатов в трехмерные структуры в задаче предсказания структуры белка.[8]
  • В рекомендательные системы для определения ранжированного списка связанных новостных статей, который можно рекомендовать пользователю после того, как он или она прочитает текущую новостную статью.[9]
  • В программная инженерия, методы обучения ранжированию были использованы для локализации неисправностей.[10]

Векторы признаков

Для удобства алгоритмов MLR пары запрос-документ обычно представлены числовыми векторами, которые называются векторы признаков. Такой подход иногда называют набор функций и аналогичен мешок слов модель и векторная космическая модель используется в поиске информации для представления документов.

Компоненты таких векторов называются Особенности, факторы или же ранжирующие сигналы. Их можно разделить на три группы (особенности из поиск документов показаны в качестве примеров):

  • Независимый от запросов или же статический особенности - те возможности, которые зависят только от документа, а не от запроса. Например, PageRank или длину документа. Такие функции можно предварительно вычислить в автономном режиме во время индексирования. Их можно использовать для вычисления документа статический показатель качества (или же статический ранг), который часто используется для ускорения оценки поискового запроса.[7][11]
  • Зависит от запроса или же динамичный features - те функции, которые зависят как от содержимого документа, так и от запроса, например TF-IDF оценка или другие функции ранжирования без машинного обучения.
  • Возможности уровня запроса или же особенности запроса, которые зависят только от запроса. Например, количество слов в запросе. Дальнейшая информация: функция уровня запроса

Некоторые примеры функций, которые использовались в известных ЛЕТОР набор данных:

Выбор и разработка хороших функций - важная область машинного обучения, которая называется разработка функций.

Меры оценки

Основная статья: Evaluation_measures_ (information_retrieval) § Offline_metrics

Существует несколько показателей (метрик), которые обычно используются для оценки того, насколько хорошо алгоритм работает с данными обучения, и для сравнения производительности различных алгоритмов MLR. Часто проблема обучения ранжированию переформулируется как задача оптимизации по одной из этих метрик.

Примеры показателей качества ранжирования:

DCG и его нормализованный вариант NDCG обычно предпочтительнее в академических исследованиях, когда используются несколько уровней релевантности.[12] Другие показатели, такие как MAP, MRR и точность, определены только для двоичных суждений.

Недавно было предложено несколько новых показателей оценки, которые претендуют на то, чтобы моделировать удовлетворенность пользователя результатами поиска лучше, чем показатель DCG:

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

Подходы

Ти-Ян Лю из Microsoft Research Asia проанализировал существующие алгоритмы для обучения ранжированию проблем в своей статье «Обучение ранжированию для поиска информации».[1] Он разделил их на три группы по их входному представлению и функция потерь: поточечный, попарный и списочный подход. На практике списочные подходы часто превосходят попарные и точечные подходы. Это утверждение было дополнительно подтверждено крупномасштабным экспериментом по производительности различных методов обучения ранжированию на большом наборе эталонных наборов данных.[15]

Точечный подход

В этом случае предполагается, что каждая пара запрос-документ в обучающих данных имеет числовую или порядковую оценку. Тогда проблема обучения ранжированию может быть аппроксимирована проблемой регрессии - по единственной паре запрос-документ предсказать ее оценку.

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

Парный подход

В этом случае проблема обучения ранжированию аппроксимируется задачей классификации - обучением двоичный классификатор это может сказать, какой документ лучше в данной паре документов. Цель состоит в том, чтобы минимизировать среднее количество инверсии в рейтинге.

Списочный подход

Эти алгоритмы пытаются напрямую оптимизировать значение одного из вышеуказанных критериев оценки, усредненное по всем запросам в обучающих данных. Это сложно, потому что большинство показателей оценки не являются непрерывными функциями по отношению к параметрам модели ранжирования, и поэтому необходимо использовать непрерывные приближения или границы для показателей оценки.

Список методов

Ниже приведен частичный список опубликованных алгоритмов обучения для ранжирования с указанием года первой публикации каждого метода:

ГодИмяТипПримечания
1989ОПРФ [16]2 точечноПолиномиальная регрессия (вместо машинного обучения эта работа относится к распознаванию образов, но идея та же)
1992SLR [17]2 точечноПоэтапная логистическая регрессия
1994NMOpt [18]2 списокНеметрическая оптимизация
1999МАРТ (Деревья множественной аддитивной регрессии)2 попарно
2000Рейтинг SVM (RankSVM)2 попарноБолее свежая экспозиция находится в[3] который описывает приложение для ранжирования с помощью журналов переходов.
2002Розыгрыш[19]1 точечноПорядковая регрессия.
2003RankBoost2 попарно
2005RankNet2 попарно
2006ИК-СВМ2 попарноРанжирование SVM с нормализацией на уровне запроса в функции потерь.
2006LambdaRankпопарно / по спискуRankNet, в которой функция попарных потерь умножается на изменение метрики IR, вызванное свопом.
2007AdaRank3 список
2007Откровенный2 попарноНа основе RankNet использует другую функцию потерь - потерю верности.
2007GBRank2 попарно
2007ListNet3 список
2007McRank1 точечно
2007QBRank2 попарно
2007RankCosine3 список
2007RankGP[20]3 список
2007RankRLS2 попарно

Рейтинг на основе регулярных наименьших квадратов. Работа расширена в[21] научиться ранжировать по графам общих предпочтений.

2007SVMкарта3 список
2008LambdaSMART / LambdaMARTпопарно / по спискуВ недавнем конкурсе Yahoo Learning to Rank, победившем в конкурсе, использовалось множество моделей LambdaMART. По материалам MART (1999)[22] «LambdaSMART» для Lambda-submodel-MART или LambdaMART для случая без подмодели (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-109.pdf ).
2008ListMLE3 списокНа основе ListNet.
2008PermuRank3 список
2008SoftRank3 список
2008Уточнение рейтинга[23]2 попарноПолуконтролируемый подход к обучению ранжированию с использованием Boosting.
2008SSRankBoost[24]2 попарноРасширение RankBoost для обучения с частично размеченными данными (полу-контролируемое обучение для ранжирования)
2008SortNet[25]2 попарноSortNet, алгоритм адаптивного ранжирования, который упорядочивает объекты, используя нейронную сеть в качестве компаратора.
2009MPBoost2 попарноСохраняющий величину вариант RankBoost. Идея состоит в том, что чем более неравны метки пары документов, тем сложнее алгоритм должен пытаться их ранжировать.
2009BoltzRank3 списокВ отличие от более ранних методов, BoltzRank создает модель ранжирования, которая во время запроса просматривает не только отдельный документ, но и пары документов.
2009BayesRank3 списокМетод объединяет модель Плакетта-Люса и нейронную сеть для минимизации ожидаемого байесовского риска, связанного с NDCG, с точки зрения принятия решений.
2010NDCG Boost[26]3 списокПовышающий подход к оптимизации NDCG.
2010GBlend2 попарноРасширяет GBRank до задачи обучения для объединения совместного решения нескольких задач обучения для ранжирования с некоторыми общими функциями.
2010IntervalRank2 попарно и по списку
2010CRR2 поточечно и попарноКомбинированная регрессия и ранжирование. Использует стохастический градиентный спуск для оптимизации линейной комбинации точечно-квадратичной потери и попарной потери шарнира из Ranking SVM.
2015FaceNetпопарноРанжирует изображения лиц по триплетной метрике с помощью глубокой сверточной сети.
2016XGBoostпопарноПоддерживает различные цели ранжирования и показатели оценки.
2017ES-рейтингсписокЭволюционная стратегия Методика обучения ранжированию с 7 метриками оценки пригодности
2018PolyRank[27]попарноОдновременно изучает ранжирование и базовую генеративную модель из парных сравнений.
2018FATE-Net / FETA-Net [28]списокСквозные обучаемые архитектуры, которые явно учитывают все элементы для моделирования контекстных эффектов.
2019FastAP [29]списокОптимизирует среднюю точность для изучения глубоких вложений
2019Шелковицасписок и гибридИзучает политики ранжирования, максимизируя несколько показателей по всему набору данных
2019DirectRankerпопарноОбобщение архитектуры RankNet

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

История

Норберт Фур представил общую идею MLR в 1992 году, описывая обучающие подходы к поиску информации как обобщение оценки параметров;[30] конкретный вариант этого подхода (с использованием полиномиальная регрессия ) была опубликована им тремя годами ранее.[16] Билл Купер предложил логистическая регрессия с той же целью в 1992 г. [17] и использовал его со своим Беркли исследовательской группы для обучения успешной функции ранжирования TREC. Manning et al.[31] предполагают, что эти ранние работы достигли ограниченных результатов в свое время из-за ограниченности доступных обучающих данных и плохих методов машинного обучения.

Несколько конференций, таких как НИПС, СИГИР и ICML с середины 2000-х (десятилетие) проводил семинары, посвященные проблеме обучения ранжированию.

Практическое использование поисковыми системами

Коммерческий поисковые системы начал использовать системы ранжирования с машинным обучением с 2000-х (десятилетие). Одной из первых поисковых систем, начавших использовать его, была AltaVista (позже его технология была приобретена Увертюра, а потом Yahoo ), который запустил повышение градиента -подготовка рейтинговых функций в апреле 2003 года.[32][33]

Bing считается, что поиск осуществляется RankNet алгоритм,[34][когда? ] который был изобретен в Microsoft Research в 2005 году.

В ноябре 2009 года российская поисковая система Яндекс объявил[35] что он значительно повысил качество поиска благодаря внедрению новой проприетарной MatrixNet алгоритм, вариант повышение градиента метод, который использует не обращающие внимания деревья решений.[36] Недавно они также спонсировали соревнование по ранжированию машинного обучения «Интернет-математика 2009».[37] на основе производственных данных собственной поисковой системы. Yahoo объявил аналогичный конкурс в 2010 году.[38]

По состоянию на 2008 г. Google с Питер Норвиг отрицали, что их поисковая система полагается исключительно на ранжирование с помощью машинного обучения.[39] Cuil Генеральный директор Том Костелло предполагает, что они предпочитают модели, созданные вручную, потому что они могут превзойти модели с машинным обучением, если сравнивать их с такими показателями, как CTR или время на целевой странице, потому что модели с машинным обучением "узнают, что говорят люди им нравится, а не то, что на самом деле нравится людям ".[40]

В январе 2017 года технология была включена в Открытый исходный код поисковый движок Apache Solr ™,[41] таким образом, делая ранг поиска с машинным обучением широко доступным и для корпоративного поиска.

Уязвимости

Подобно приложениям распознавания в компьютерное зрение, недавние алгоритмы ранжирования на основе нейронных сетей также оказались подвержены скрытому состязательные атаки, как по кандидатам, так и по запросам.[42] При небольших возмущениях, незаметных для людей, порядок ранжирования может быть произвольно изменен. Кроме того, было обнаружено, что возможны переносимые состязательные примеры, не зависящие от модели, что позволяет проводить состязательные атаки методом черного ящика на системы глубокого ранжирования, не требуя доступа к их базовым реализациям.[42][43]

И наоборот, надежность таких систем ранжирования может быть улучшена с помощью противостоящей защиты, такой как защита Мадри.[44]

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

Рекомендации

  1. ^ а б Ти-Янь Лю (2009 г.), «Обучение ранжированию для поиска информации», Основы и тенденции поиска информации, 3 (3): 225–331, Дои:10.1561/1500000016, ISBN  978-1-60198-244-5. Слайды из выступления Ти-Янь Лю на WWW 2009 конференция доступно онлайн
  2. ^ Мехриар Мохри, Афшин Ростамизаде, Амит Талвалкар (2012) Основы машинного обучения, TheMIT Press ISBN  9780262018258.
  3. ^ а б Иоахимс, Т. (2002), «Оптимизация поисковых систем с использованием данных о переходах» (PDF), Материалы конференции ACM по открытию знаний и интеллектуальному анализу данных
  4. ^ Иоахим Т .; Радлински Ф. (2005), «Цепочки запросов: обучение ранжированию на основе неявной обратной связи» (PDF), Материалы конференции ACM по открытию знаний и интеллектуальному анализу данных, arXiv:cs / 0605035, Bibcode:2006cs ........ 5035R
  5. ^ Б. Камбазоглу; Х. Сарагоса; О. Шапель; Дж. Чен; К. Ляо; Z. Zheng; J. Degenhardt., «Оптимизация раннего выхода для аддитивных систем ранжирования с машинным обучением» (PDF), WSDM '10: Материалы третьей Международной конференции ACM по веб-поиску и интеллектуальному анализу данных, 2010 г.
  6. ^ Broder A .; Carmel D .; Herscovici M .; Соффер А .; Зиен Дж. (2003), «Эффективная оценка запроса с использованием двухуровневого процесса поиска» (PDF), Материалы Двенадцатой Международной конференции по управлению информацией и знаниями: 426–434, ISBN  978-1-58113-723-1, заархивировано из оригинал (PDF) на 2009-05-21, получено 2009-12-15
  7. ^ а б Manning C .; Рагхаван П .; Шютце Х. (2008), Введение в поиск информации, Издательство Кембриджского университета. Раздел 7.1
  8. ^ а б Кевин К. Дух (2009), Обучение ранжированию с частично размеченными данными (PDF)
  9. ^ Юаньхуа Львов, Таэсуп Мун, Пранам Колари, Чжаохуэй Чжэн, Сюаньхуэй Ван и И Чанг, Обучение моделированию взаимосвязи для рекомендаций новостей В архиве 2011-08-27 на Wayback Machine, в Международной конференции по всемирной паутине (WWW), 2011 г.
  10. ^ Сюань, Цзифэн; Монперрус, Мартин (2014). «Обучение объединению нескольких показателей ранжирования для локализации неисправности». 2014 IEEE Международная конференция по сопровождению и развитию программного обеспечения. С. 191–200. CiteSeerX  10.1.1.496.6829. Дои:10.1109 / ICSME.2014.41. ISBN  978-1-4799-6146-7. S2CID  11223473.
  11. ^ Richardson, M .; Пракаш, А .; Брилл, Э. (2006). «За пределами PageRank: машинное обучение для статического ранжирования» (PDF). Материалы 15-й Международной конференции в Интернете. С. 707–715.
  12. ^ http://www.stanford.edu/class/cs276/handouts/lecture15-learning-ranking.ppt
  13. ^ Оливье Шапель; Дональд Метцлер; Я Чжан; Пьер Гринспан (2009), «Ожидаемый взаимный рейтинг по оценке релевантности» (PDF), CIKM, заархивировано из оригинал (PDF) на 2012-02-24
  14. ^ Гулин А .; Карпович П .; Расковалов Д .; Сегалович И. (2009), «Яндекс на РОМИП'2009: оптимизация алгоритмов ранжирования методами машинного обучения» (PDF), Материалы РОМИП'2009.: 163–168 (на русском)
  15. ^ Налог, Ник; Боктинг, Сандер; Хиемстра, Джорд (2015), «Сравнение 87 методов обучения ранжированию» (PDF), Обработка информации и управление, 51 (6): 757–772, Дои:10.1016 / j.ipm.2015.07.002, заархивировано из оригинал (PDF) на 2017-08-09, получено 2017-10-15
  16. ^ а б Фур, Норберт (1989), "Оптимальные функции полиномиального поиска, основанные на принципе вероятностного ранжирования", ACM-транзакции в информационных системах, 7 (3): 183–204, Дои:10.1145/65943.65944, S2CID  16632383
  17. ^ а б Купер, Уильям С .; Гей, Фредерик Ч .; Дэбни, Дэниел П. (1992), "Вероятностный поиск на основе поэтапной логистической регрессии", SIGIR '92 Труды 15-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска: 198–210, Дои:10.1145/133160.133199, ISBN  978-0897915236, S2CID  125993
  18. ^ Бартелл, Брайан Т .; Коттрелл Гаррисон В .; Белью, Ричард К. (1994), «Автоматическая комбинация нескольких ранжированных поисковых систем», SIGIR '94 Материалы 17-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска: 173–181, ISBN  978-0387198897
  19. ^ «Шутки». CiteSeerX  10.1.1.20.378. Цитировать журнал требует | журнал = (помощь)
  20. ^ «RankGP». CiteSeerX  10.1.1.90.220. Цитировать журнал требует | журнал = (помощь)
  21. ^ Пахиккала, Тапио; Цивцивадзе, Евгений; Аирола, Антти; Ярвинен, Йоуни; Боберг, Йорма (2009), "Эффективный алгоритм обучения ранжированию по графам предпочтений", Машинное обучение, 75 (1): 129–165, Дои:10.1007 / s10994-008-5097-z.
  22. ^ К. Берджес. (2010). От RankNet к LambdaRank к LambdaMART: обзор.
  23. ^ Ронг Джин, Хамед Вализадеган, Ханг Ли, Уточнение рейтинга и его применение для поиска информации, в Международной конференции по всемирной паутине (WWW), 2008 г.
  24. ^ Массих-Реза Амини, Вин Чыонг, Сирил Гутте, Алгоритм усиления для изучения функций двудольного ранжирования с частично размеченными данными В архиве 2010-08-02 в Wayback Machine, Международная конференция ACM SIGIR, 2008 г. код В архиве 2010-07-23 на Wayback Machine доступен для исследовательских целей.
  25. ^ Леонардо Ригутини, Тициано Папини, Марко Маджини, Франко Скарселли, «SortNet: обучение ранжированию с помощью алгоритма сортировки на основе нейронных сетей», Семинар SIGIR 2008: Обучение ранжированию для поиска информации, 2008 г.
  26. ^ Хамед Вализадеган, Ронг Джин, Руофей Чжан, Цзяньчан Мао, Обучение ранжированию с помощью оптимизации показателей NDCG, в Proceeding of Neural Information Processing Systems (NIPS), 2010.
  27. ^ Давыдов, Ори; Айлон, Нир; Оливейра, Иво Ф. Д. (2018). «Новый и гибкий подход к анализу парных сравнительных данных». Журнал исследований в области машинного обучения. 19 (60): 1–29. ISSN  1533-7928.
  28. ^ Пфанншмидт, Карлсон; Гупта, Прита; Хюллермайер, Эйке (2018). «Глубокие архитектуры для изучения контекстно-зависимых функций ранжирования». arXiv:1803.05796 [stat.ML ].
  29. ^ Фатих Чакир, Кун Хе, Сиде Ся, Брайан Кулис, Стэн Скларофф, Глубокое метрическое обучение для ранжирования, В Proc. Конференция IEEE по компьютерному зрению и распознаванию образов (CVPR), 2019.
  30. ^ Фур, Норберт (1992), "Вероятностные модели в поиске информации", Компьютерный журнал, 35 (3): 243–255, Дои:10.1093 / comjnl / 35.3.243
  31. ^ Manning C .; Рагхаван П .; Шютце Х. (2008), Введение в поиск информации, Издательство Кембриджского университета. Разделы 7.4 и 15.5
  32. ^ Ян О. Педерсен. История MLR В архиве 2011-07-13 на Wayback Machine
  33. ^ Патент США 7,197,497
  34. ^ Блог поиска Bing: потребности пользователей, особенности и наука, лежащая в основе Bing
  35. ^ Запись в корпоративном блоге Яндекса о новой модели рейтинга «Снежинск» (на русском)
  36. ^ Алгоритм не разглашается, но некоторые детали были обнародованы в [1] и [2].
  37. ^ «Страница конкурса Яндекс Интернет-математика 2009». Архивировано из оригинал на 2015-03-17. Получено 2009-11-11.
  38. ^ "Yahoo Learning to Rank Challenge". Архивировано из оригинал на 2010-03-01. Получено 2010-02-26.
  39. ^ Раджараман, Ананд (2008-05-24). «Склонны ли модели с машинным обучением к катастрофическим ошибкам?». В архиве из оригинала 18.09.2010. Получено 2009-11-11.
  40. ^ Костелло, Том (26.06.2009). «Блог Cuil: Как поживает Bing?». Архивировано из оригинал 27 июня 2009 г.
  41. ^ "Как Bloomberg интегрировал Learning-to-Rank в Apache Solr | Tech в Bloomberg". Технология в Bloomberg. 2017-01-23. Получено 2017-02-28.
  42. ^ а б Чжоу, Мо; Ню, Чжэньсин; Ван, Ле; Чжан, Цилинь; Хуа, банда (2020). «Состязательный рейтинг атаки и защиты». arXiv:2002.11293v2 [cs.CV ].
  43. ^ Ли, Цзе; Джи, Ронгронг; Лю, Хун; Хун, Сяопэн; Гао, Юэ; Тиан, Ци. "Универсальная атака возмущением на поиск изображений". Международная конференция по компьютерному зрению (ICCV 2019). С. 4899–4908.
  44. ^ Мадри, Александр; Макелов, Александр; Шмидт, Людвиг; Ципрас, Димитрис; Влада, Адриан (19.06.2017). «На пути к моделям глубокого обучения, устойчивым к враждебным атакам». arXiv:1706.06083v4 [stat.ML ].


внешняя ссылка

Соревнования и общедоступные наборы данных
Открытый исходный код