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

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

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

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

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

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

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

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

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

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

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

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

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

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

• DCG и NDCG;
• Точность@n, NDCG@n (@n означает, что значение метрики считается только по n лучшим документам выдачи);
• MAP;
• среднеобратный ранг;
• 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, заявил, что их поисковая система ещё не готова окончательно доверить ранжирование алгоритмам машинного обучения, мотивируя это тем, что, во-первых, автоматически созданные модели могут повести себя непредсказуемо на новых классах запросов, не похожих на запросы из обучающей выборки, по сравнению с моделями, созданными людьми-экспертами. Во-вторых, создатели текущего ранжирующего алгоритма Google уверены в том, что и их модель способна решать задачи более эффективно, нежели чем машинное обучение.^[11] Первая причина представляет для нас куда более значительный интерес, поскольку она не только восходит к такой известной проблеме индуктивной логики, сформулированной немецким математиком К. Г. Гемпелем и вступающей в противоречие с интуицией (утверждение «все вороны черные» логически эквивалентно тому, что «все нечерные предметы — не вороны»), но и заставляет нас вернуться к ряду нерешенных вопросов Ф. Розенблатта, создавшего первую в мире нейронную сеть, способную к перцепции и формированию отклика на воспринятый им стимул — однослойный персептрон.^[12] Опираясь на критику элементарного перцептрона Розенблатта, мы можем понять всю уязвимость данной рейтингующей модели, о который нам сообщают специалисты Google: способны ли искусственные системы обобщать свой индивидуальный опыт на широкий класс ситуаций, для которых отклик не был сообщен им заранее? Нет, индивидуальный опыт искусственных систем на практике всегда ограничен и никогда не является полным. Так или иначе, инструментарий машинного обучения позволяет решать проблему спамдексинга с достаточно высокой степенью эффективности^[13].