Учимся ранжировать - Learning to rank

Обучение ранжированию или ранжирование с помощью машинного обучения ( MLR ) - это применение машинного обучения , обычно контролируемого , частично контролируемого или подкрепляющего обучения , при построении моделей ранжирования для систем поиска информации. Данные обучения состоят из списков элементов с некоторым частичным порядком, указанным между элементами в каждом списке. Этот порядок обычно создается путем выставления числовой или порядковой оценки или бинарного суждения (например, «релевантный» или «нерелевантный») для каждого пункта. Модель ранжирования предназначена для ранжирования, т. Е. Создания перестановки элементов в новых, невидимых списках аналогично ранжированию в обучающих данных.

Приложения

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

Возможная архитектура поисковой системы с машинным обучением.

Ранжирование является центральной частью многих задач поиска информации , таких как поиск документов , совместная фильтрация , анализ настроений и онлайн-реклама .

Возможная архитектура поисковой машины с машинным обучением показана на прилагаемом рисунке.

Данные обучения состоят из запросов и документов, соответствующих им, вместе со степенью релевантности каждого совпадения. Он может быть приготовлен вручную человеческими испытателями (или оценщиками , поскольку Google называет их), которые проверяют результаты для некоторых запросов и определить релевантность каждого результата. Невозможно проверить релевантность всех документов, поэтому обычно используется метод, называемый объединением - проверяются только несколько верхних документов, извлеченных некоторыми существующими моделями ранжирования. В качестве альтернативы данные обучения могут быть получены автоматически путем анализа журналов переходов по ссылкам (т. Е. Результатов поиска, которые получили клики от пользователей), цепочек запросов или таких функций поисковых систем, как SearchWiki Google .

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

Обычно пользователи ожидают, что поисковый запрос будет выполнен за короткое время (например, несколько сотен миллисекунд для веб-поиска), что делает невозможным оценку сложной модели ранжирования для каждого документа в корпусе, поэтому двухэтапная схема является использовал. Во-первых, небольшое количество потенциально релевантных документов идентифицируется с использованием более простых моделей поиска, которые позволяют быстро оценивать запросы, таких как модель векторного пространства , логическая модель , взвешенное И или BM25 . Этот этап называется поиском верхнего документа, и в литературе предлагалось множество эвристических методов для его ускорения, например использование статической оценки качества документа и многоуровневых индексов. На втором этапе для повторного ранжирования этих документов используется более точная, но дорогостоящая в вычислительном отношении модель машинного обучения.

В других сферах

Алгоритмы обучения ранжированию применялись не только в поиске информации, но и в других областях:

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

Векторы признаков

Для удобства алгоритмов MLR пары запрос-документ обычно представлены числовыми векторами, которые называются векторами признаков . Такой подход иногда называют набором функций и аналогичен модели набора слов и модели векторного пространства, используемой при поиске информации для представления документов.

Компоненты таких векторов называются признаками , факторами или ранжирующими сигналами . Их можно разделить на три группы (в качестве примеров показаны функции поиска документов ):

  • Независимые от запроса или статические функции - те функции, которые зависят только от документа, но не от запроса. Например, PageRank или длина документа. Такие функции могут быть предварительно вычислены в автономном режиме во время индексирования. Их можно использовать для вычисления статической оценки качества документа (или статического ранга ), которая часто используется для ускорения оценки поискового запроса.
  • Зависящие от запроса или динамические функции - те функции, которые зависят как от содержимого документа, так и от запроса, такие как оценка TF-IDF или другие функции ранжирования, не связанные с машинным обучением.
  • Функции уровня запроса или функции запроса , которые зависят только от запроса. Например, количество слов в запросе.

Некоторые примеры функций, которые использовались в известном наборе данных LETOR :

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

Меры оценки

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

Примеры показателей качества ранжирования:

DCG и его нормализованный вариант NDCG обычно предпочтительнее в академических исследованиях, когда используются несколько уровней релевантности. Другие показатели, такие как MAP, MRR и точность, определены только для двоичных суждений.

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

  • Ожидаемый взаимный ранг (ERR);
  • Яндекс pfound.

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

Подходы

Ти-Ян Лю из Microsoft Research Asia проанализировал существующие алгоритмы обучения ранжированию проблем в своей книге « Обучение ранжированию для поиска информации» . Он разделил их на три группы по их входным пространствам, выходным пространствам, пространствам гипотез (основная функция модели) и функциям потерь : поточечный, попарный и списочный подход. На практике списочные подходы часто превосходят попарные и точечные подходы. Это утверждение было дополнительно подтверждено крупномасштабным экспериментом по производительности различных методов обучения ранжированию на большом наборе эталонных наборов данных.

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

Точечный подход

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

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

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

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

Во многих случаях двоичный классификатор реализован с функцией оценки . Например, RankNet адаптирует вероятностную модель и определяет, как предполагаемая вероятность того, что документ имеет более высокое качество, чем :

где - кумулятивная функция распределения , например, стандартный логистический CDF , т.е.

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

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

Список методов

Ниже приведен частичный список опубликованных алгоритмов обучения для ранжирования с указанием года первой публикации каждого метода:

Год Имя Тип Примечания
1989 г. ОПРФ 2 точечно Полиномиальная регрессия (вместо машинного обучения эта работа относится к распознаванию образов, но идея та же)
1992 г. SLR 2 точечно Поэтапная логистическая регрессия
1994 г. NMOpt 2 по списку Неметрическая оптимизация
1999 г. MART (деревья множественной аддитивной регрессии) 2 попарно
2000 г. Ранжирование SVM (RankSVM) 2 попарно В более свежем изложении описывается приложение для ранжирования с использованием журналов переходов по ссылкам.
2002 г. Розыгрыш 1 точечно Порядковая регрессия.
2003 г. RankBoost 2 pairwise
2005 г. RankNet 2 попарно
2006 г. ИК-СВМ 2 попарно Ранжирование SVM с нормализацией уровня запроса в функции потерь.
2006 г. LambdaRank попарно / по списку RankNet, в которой функция попарных потерь умножается на изменение показателя IR, вызванное свопом.
2007 г. AdaRank 3 по списку
2007 г. Откровенный 2 попарно На основе RankNet используется другая функция потерь - потеря точности.
2007 г. GBRank 2 попарно
2007 г. ListNet 3 по списку
2007 г. McRank 1 точечно
2007 г. QBRank 2 попарно
2007 г. Ранг 3 по списку
2007 г. RankGP 3 по списку
2007 г. RankRLS 2 попарно

Рейтинг на основе регулярных наименьших квадратов. Работа распространяется на обучение ранжированию по графам общих предпочтений.

2007 г. Карта SVM 3 по списку
2008 г. LambdaSMART / LambdaMART попарно / по списку В недавнем конкурсе Yahoo Learning to Rank, победившем в конкурсе, использовалось множество моделей LambdaMART. На основе MART (1999) «LambdaSMART» для Lambda-submodel-MART или LambdaMART для случая без подмодели (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/ 02 / tr-2008-109.pdf ).
2008 г. ListMLE 3 по списку На основе ListNet.
2008 г. PermuRank 3 по списку
2008 г. SoftRank 3 по списку
2008 г. Уточнение рейтинга 2 попарно Полуконтролируемый подход к обучению ранжированию с использованием Boosting.
2008 г. SSRankBoost 2 попарно Расширение RankBoost для обучения с частично размеченными данными (полу-контролируемое обучение для ранжирования)
2008 г. SortNet 2 попарно SortNet, алгоритм адаптивного ранжирования, который упорядочивает объекты, используя нейронную сеть в качестве компаратора.
2009 г. MPBoost 2 попарно Сохраняющий величину вариант RankBoost. Идея состоит в том, что чем более неравны метки пары документов, тем сложнее алгоритм должен пытаться их ранжировать.
2009 г. BoltzRank 3 по списку В отличие от более ранних методов, BoltzRank создает модель ранжирования, которая просматривает во время запроса не только отдельный документ, но и пары документов.
2009 г. BayesRank 3 по списку Метод сочетает в себе модель Плакетта-Люса и нейронную сеть, чтобы минимизировать ожидаемый байесовский риск, связанный с NDCG, с точки зрения принятия решений.
2010 г. NDCG Boost 3 по списку Повышающий подход к оптимизации NDCG.
2010 г. GBlend 2 попарно Расширяет GBRank до задачи обучения для объединения совместного решения нескольких задач обучения для ранжирования с некоторыми общими функциями.
2010 г. IntervalRank 2 попарно и по списку
2010 г. CRR 2 точечно и попарно Комбинированная регрессия и ранжирование. Использует стохастический градиентный спуск для оптимизации линейной комбинации точечно-квадратичных потерь и попарных потерь на шарнирах из SVM ранжирования.
2014 г. LCR 2 попарно Применено местное предположение о низком ранге для совместного ранжирования. Получил награду за лучшую студенческую работу на WWW'14.
2015 г. FaceNet попарно Ранжирует изображения лиц по триплетной метрике с помощью глубокой сверточной сети.
2016 г. XGBoost попарно Поддерживает различные цели ранжирования и показатели оценки.
2017 г. ES-рейтинг по списку Эволюционная стратегия Методика обучения ранжированию с 7 метриками оценки пригодности
2018 г. PolyRank попарно Одновременно изучает ранжирование и базовую генеративную модель из парных сравнений.
2018 г. FATE-Net / FETA-Net по списку Сквозные обучаемые архитектуры, которые явно учитывают все элементы для моделирования контекстных эффектов.
2019 г. FastAP по списку Оптимизирует среднюю точность для изучения глубоких встраиваний
2019 г. Шелковица список и гибрид Изучает политики ранжирования, максимизируя несколько показателей по всему набору данных
2019 г. DirectRanker попарно Обобщение архитектуры RankNet
2020 г. PRM попарно Трансформаторная сеть, кодирующая как зависимости между элементами, так и взаимодействия

между пользователем и предметами

Примечание: поскольку большинство алгоритмов контролируемого обучения могут применяться к точечным случаям, выше показаны только те методы, которые специально разработаны с учетом ранжирования.

История

Норберт Фур представил общую идею MLR в 1992 году, описывая подходы к обучению в поиске информации как обобщение оценки параметров; конкретный вариант этого подхода (с использованием полиномиальной регрессии ) был опубликован им тремя годами ранее. Билл Купер предложил логистическую регрессию для той же цели в 1992 году и использовал ее со своей исследовательской группой в Беркли для обучения успешной функции ранжирования для TREC . Manning et al. предполагают, что эти ранние работы достигли ограниченных результатов в свое время из-за небольшого количества доступных обучающих данных и плохих методов машинного обучения.

На нескольких конференциях, таких как NIPS , SIGIR и ICML, с середины 2000-х (десятилетие) проводились семинары, посвященные проблеме обучения ранжированию.

Практическое использование поисковыми системами

Коммерческие поисковые машины начали использовать системы ранжирования с машинным обучением с 2000-х (десятилетие). Одной из первых поисковых систем, начавших ее использовать, была AltaVista (позже ее технология была приобретена Overture , а затем Yahoo ), которая запустила функцию ранжирования с использованием градиентного повышения в апреле 2003 года.

Считается, что поиск Bing основан на алгоритме RankNet , изобретенном Microsoft Research в 2005 году.

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

В 2008 году Google «S Питер Норвиг отрицал , что их поисковая система исключительно полагается на машины узнал рейтинг. Генеральный директор Cuil , Том Костелло, предполагает, что они предпочитают модели, созданные вручную, потому что они могут превзойти модели с машинным обучением, если сравнивать их с такими показателями, как CTR или время на целевой странице, потому что модели с машинным обучением «узнают, что люди говорят, что им нравится, а не то, что на самом деле нравится людям ».

В январе 2017 года эта технология была включена в поисковую систему с открытым исходным кодом Apache Solr ™, что сделало ранг поиска с машинным обучением широко доступным также для корпоративного поиска.

Уязвимости

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

И наоборот, надежность таких систем ранжирования может быть повышена с помощью противостоящей защиты, такой как защита Мэдри.

Смотрите также

использованная литература


внешние ссылки

Соревнования и общедоступные наборы данных
Открытый исходный код