Обуче́ние ранжи́рованию (англ. 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, с. 225-331, ISBN 978-1-60198-244-5, DOI 10.1561/1500000016. Доступны слайды Архивировано 31 марта 2010 года. c выступления Т. Лью на конференции WWW 2009.
- ↑ Optimizing Search Engines using Clickthrough Data
- ↑ Static quality scores and ordering
- ↑ 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.
- ↑ LETOR 3.0. A Benchmark Collection for Learning to Rank for Information Retrieval
- ↑ Гулин А., Карпович П., Расковалов Д., Сегалович И. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения.
- ↑ Yahoo Launches World’s Largest Hadoop Production Application Архивная копия от 21 декабря 2009 на Wayback Machine (англ.)
- ↑ Bing Search Blog: User Needs, Features and the Science behind Bing (англ.)
- ↑ Roem.ru: Яндекс запустил новую формулу Снежинск, теперь тысяча переменных вместо 250.
- ↑ Интернет-математика 2009
- ↑ Are Machine-Learned Models Prone to Catastrophic Errors? (англ.)
- ↑ Perceptrons: An Associative Learning Network (англ.)
- ↑ Детекция поискового спама. Часть 15: Применение искусственных нейронных сетей (рус.)
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .