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

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

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

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

править

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

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

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

править

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

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

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

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

править

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

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

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

править

В своей статье «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, SVMmap, AdaRank, RankGP, ListNet, ListMLE.

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

править

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

править

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

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

Примечания

править
  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, pp. 225—331, doi:10.1561/1500000016, ISBN 978-1-60198-244-5. Доступны слайды Архивировано 31 марта 2010 года. c выступления Т. Лью на конференции WWW 2009.
  2. Optimizing Search Engines using Clickthrough Data. Дата обращения: 18 ноября 2009. Архивировано 29 декабря 2009 года.
  3. Static quality scores and ordering. Дата обращения: 18 ноября 2009. Архивировано 7 июля 2009 года.
  4. Richardson, M. (2006). "Beyond PageRank: Machine Learning for Static Ranking" (PDF). Proceedings of the 15th International World Wide Web Conference. pp. 707—715. Архивировано (PDF) 15 августа 2009. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка)
  5. LETOR 3.0. A Benchmark Collection for Learning to Rank for Information Retrieval. Дата обращения: 18 ноября 2009. Архивировано 16 февраля 2012 года.
  6. Гулин А., Карпович П., Расковалов Д., Сегалович И. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения. Архивная копия от 22 ноября 2009 на Wayback Machine
  7. Yahoo Launches World’s Largest Hadoop Production Application Архивная копия от 21 декабря 2009 на Wayback Machine (англ.)
  8. Bing Search Blog: User Needs, Features and the Science behind Bing Архивная копия от 25 ноября 2009 на Wayback Machine (англ.)
  9. Roem.ru: Яндекс запустил новую формулу Снежинск, теперь тысяча переменных вместо 250. Дата обращения: 20 ноября 2009. Архивировано 13 ноября 2009 года.
  10. Интернет-математика 2009. Дата обращения: 20 ноября 2009. Архивировано из оригинала 15 ноября 2009 года.
  11. Are Machine-Learned Models Prone to Catastrophic Errors? Архивная копия от 5 января 2010 на Wayback Machine (англ.)
  12. Perceptrons: An Associative Learning Network Архивная копия от 9 августа 2011 на Wayback Machine (англ.)
  13. Детекция поискового спама. Часть 15: Применение искусственных нейронных сетей Архивная копия от 10 марта 2013 на Wayback Machine (рус.)