Обучение ранжированию

Обуче́ние ранжи́рованию (англ. learning to rank или machine-learned ranking, MLR)^[1] — это класс задач машинного обучения с учителем, заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента (например, «релевантен» или «не релевантен»; возможно использование и более, чем двух градаций). Цель ранжирующей модели — наилучшим образом (в некотором смысле) приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.

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

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

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

Обучающая выборка состоит из выборки поисковых запросов, подмножества документов, им отвечающим, и оценок релевантности каждого документа запросу. Они могут быть подготовлены как вручную, специально натренированными людьми (оценщиками качества поиска или асессорами), так и автоматически, на основе анализа пользовательских кликов^[2] или таких средств поисковых систем, как система SearchWiki поисковой системы Google.

Ранжирующие признаки

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

• Запросо-независимые или статические признаки — зависящие только от документа, но не от запроса. Например, PageRank или длина документа. Такие признаки обычно вычисляются на этапе индекcирования документов и часто используются для построения показателя статического качества документа, использующегося для повышения эффективности поисковых систем.^[3][4]
• Признаки, зависящие только от запроса. Например, «запрос про порно или нет».
• Запросо-зависимые или динамические признаки — зависящие и от документа, и от запроса. Например, мера TF-IDF соответствия документа запросу.

Ниже приведены некоторые примеры ранжирующих признаков, использующиеся в широко известном в данной области исследований наборе данных LETOR:^[5]

• Значения мер TF, TF-IDF, BM25, и языковой модели соответствия запросу различных зон документа (заголовка, URL, основного текста, текста ссылок);
• Длины и IDF-суммы зон документа;
• Ранги документа, полученные различными вариантами таких алгоритмов ссылочного ранжирования, как PageRank и HITS.

Метрики качества ранжирования

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

Примеры метрик:

• DCG и NDCG;
• Точность@n, NDCG@n (@n означает, что значение метрики считается только по n лучшим документам выдачи);
• MAP;
• Mean reciprocal rank;
• pfound — разработка компании Яндекс.^[6]

Классификация алгоритмов

В своей статье «Learning to Rank for Information Retrieval»^[1] и выступлениях на тематических конференциях, Тай-Ян Лью из Microsoft Research Asia проанализировал существующие на тот момент методы для решения задачи обучения ранжированию и предложил их классификацию на три подхода, в зависимости от используемого входного представления данных и функции штрафа:

Поточечный подход

В поточечном подходе (англ. pointwise approach) предполагается, что каждой паре запрос-документ поставлена в соответствие численная оценка. Задача обучения ранжированию сводится к построению регрессии: для каждой отдельной пары запрос-документ необходимо предсказать её оценку.

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

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

В попарном подходе (англ. pairwise approach) обучение ранжированию сводится к построению бинарного классификатора, которому на вход поступают два документа, соответствующих одному и тому же запросу, и требуется определить, какой из них лучше.

Примеры алгоритмов:^[1] RankNet, FRank, RankBoost, RankSVM, IR-SVM.

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

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

Примеры алгоритмов:^[1] SoftRank, SVM^map, AdaRank, RankGP, ListNet, ListMLE.

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Практическое применение

В крупных поисковых системах

Поисковые движки многих современных поисковых систем по Интернету, среди которых Яндекс, Yahoo^[7] и Bing, используют ранжирующие модели, построенные методами машинного обучения. Поиск Bing'а использует алгоритм RankNet.^[8] Новейший алгоритм машинного обучения ранжированию, разработанный и применяющийся в поисковой системе Яндекс получил название MatrixNet;^[9] сама компания Яндекс недавно спонсировала конкурс «Интернет-математика 2009»^[10] по построению ранжирующего алгоритма на наборе своих собственных данных.

В интервью в начале 2008 года, Питер Норвиг, директор по исследованиям в компании Google, заявил, что их поисковая система ещё не готова окончательно доверить ранжирование алгоритмам машинного обучения, мотивируя это тем, что автоматически созданные модели могут повести себя непредсказуемо на новых классах запросов, не похожих на запросы из обучающей выборки, по сравнению с моделями, созданными людьми-экспертами.^[11]

Примечания

1. ↑ ^{1 2 3 4} Tie-Yan Liu (2009), «Learning to Rank for Information Retrieval», Foundations and Trends in Information Retrieval: Vol. 3: No 3, сс. 225-331, ISBN 978-1-60198-244-5, DOI 10.1561/1500000016 . Доступны слайды c выступления Т. Лью на конференции WWW 2009.
2. ↑ Optimizing Search Engines using Clickthrough Data
3. ↑ Static quality scores and ordering
4. ↑ Richardson, M.; Prakash, A. and Brill, E. (2006). "Beyond PageRank: Machine Learning for Static Ranking". Proceedings of the 15th International World Wide Web Conference: 707-715. 
5. ↑ LETOR 3.0. A Benchmark Collection for Learning to Rank for Information Retrieval
6. ↑ Гулин А., Карпович П., Расковалов Д., Сегалович И. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения.
7. ↑ Yahoo Launches World’s Largest Hadoop Production Application (англ.)
8. ↑ Bing Search Blog: User Needs, Features and the Science behind Bing (англ.)
9. ↑ Roem.ru: Яндекс запустил новую формулу Снежинск, теперь тысяча переменных вместо 250.
10. ↑ Интернет-математика 2009
11. ↑ Are Machine-Learned Models Prone to Catastrophic Errors? (англ.)