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

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

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

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

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

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

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

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

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

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

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

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

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

• и ;
• Точность @ n , NDCG@ n (@ n означает, что значение метрики считается только по n лучшим документам выдачи);
• ;
• среднеобратный ранг ;
• — разработка компании Яндекс .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В интервью в начале 2008 года Питер Норвиг , директор по исследованиям в компании Google , заявил, что их поисковая система ещё не готова окончательно доверить ранжирование алгоритмам машинного обучения, мотивируя это тем, что, во-первых, автоматически созданные модели могут повести себя непредсказуемо на новых классах запросов, не похожих на запросы из обучающей выборки, по сравнению с моделями, созданными людьми-экспертами. Во-вторых, создатели текущего ранжирующего алгоритма Google уверены в том, что и их модель способна решать задачи более эффективно, нежели чем машинное обучение. Первая причина представляет для нас куда более значительный интерес, поскольку она не только восходит к такой известной проблеме индуктивной логики, сформулированной немецким математиком К. Г. Гемпелем и вступающей в противоречие с интуицией ( утверждение «все вороны черные» логически эквивалентно тому, что «все нечерные предметы — не вороны» ), но и заставляет нас вернуться к ряду нерешенных вопросов Ф. Розенблатта , создавшего первую в мире нейронную сеть , способную к перцепции и формированию отклика на воспринятый им стимул — однослойный персептрон. Опираясь на критику элементарного перцептрона Розенблатта, мы можем понять всю уязвимость данной рейтингующей модели, о который нам сообщают специалисты Google: способны ли искусственные системы обобщать свой индивидуальный опыт на широкий класс ситуаций, для которых отклик не был сообщен им заранее? Нет, индивидуальный опыт искусственных систем на практике всегда ограничен и никогда не является полным. Так или иначе, инструментарий машинного обучения позволяет решать проблему спамдексинга с достаточно высокой степенью эффективности .

Примечания