Обуче́ние ранжи́рованию (англ. 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 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.
- ↑ Optimizing Search Engines using Clickthrough Data. Дата обращения: 18 ноября 2009. Архивировано 29 декабря 2009 года.
- ↑ Static quality scores and ordering. Дата обращения: 18 ноября 2009. Архивировано 7 июля 2009 года.
- ↑ 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=предлагается) (справка) - ↑ LETOR 3.0. A Benchmark Collection for Learning to Rank for Information Retrieval. Дата обращения: 18 ноября 2009. Архивировано 16 февраля 2012 года.
- ↑ Гулин А., Карпович П., Расковалов Д., Сегалович И. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения. Архивная копия от 22 ноября 2009 на Wayback Machine
- ↑ Yahoo Launches World’s Largest Hadoop Production Application Архивная копия от 21 декабря 2009 на Wayback Machine (англ.)
- ↑ Bing Search Blog: User Needs, Features and the Science behind Bing Архивная копия от 25 ноября 2009 на Wayback Machine (англ.)
- ↑ Roem.ru: Яндекс запустил новую формулу Снежинск, теперь тысяча переменных вместо 250. Дата обращения: 20 ноября 2009. Архивировано 13 ноября 2009 года.
- ↑ Интернет-математика 2009. Дата обращения: 20 ноября 2009. Архивировано из оригинала 15 ноября 2009 года.
- ↑ Are Machine-Learned Models Prone to Catastrophic Errors? Архивная копия от 5 января 2010 на Wayback Machine (англ.)
- ↑ Perceptrons: An Associative Learning Network Архивная копия от 9 августа 2011 на Wayback Machine (англ.)
- ↑ Детекция поискового спама. Часть 15: Применение искусственных нейронных сетей Архивная копия от 10 марта 2013 на Wayback Machine (рус.)