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

Обуче́ние ранжи́рованию (англ. 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.

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

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

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

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

В своей статье «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. 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. Доступны слайды Архивировано 31 марта 2010 года. 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 Архивная копия от 21 декабря 2009 на Wayback Machine (англ.)
  8. Bing Search Blog: User Needs, Features and the Science behind Bing (англ.)
  9. Roem.ru: Яндекс запустил новую формулу Снежинск, теперь тысяча переменных вместо 250.
  10. Интернет-математика 2009 (недоступная ссылка). Дата обращения: 20 ноября 2009. Архивировано 15 ноября 2009 года.
  11. Are Machine-Learned Models Prone to Catastrophic Errors? (англ.)
  12. Perceptrons: An Associative Learning Network (англ.)
  13. Детекция поискового спама. Часть 15: Применение искусственных нейронных сетей Архивная копия от 10 марта 2013 на Wayback Machine (рус.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.