Метрики оценки качества поиска в MLR:
что мы знаем и о чем догадываемся

Начнем с основного пойнта в вопросе — ранжирования. Ранжирование — это способ сортировки элементов (сайтов, видео, изображений, новостных постов и т.д.) на основе их релевантности.

Под релевантностью мы понимаем степень отношения объекта определенному запросу. Допустим, у нас есть запрос и ряд «объектов» в той или иной мере отвечающих ему. Чем выше степень соответствия объекта запросу — тем выше уровень релевантности. Задача ранжирования — отдать наиболее релевантный объект в ответ на запрос. Чем выше релевантность, тем выше вероятность того, что пользователь совершит целевое действие (зайдет на страницу, купит товар, посмотрит видео и тд.).

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

Обучение ранжированию или Learning to rank (MLR) — это направление машинного обучения, которое занимается изучением и разработкой алгоритмов ранжирования, способных к самообучению. Его основная задача — определить наиболее эффективные алгоритмы и подходы, основываясь на их качественной и количественной оценке. Почему возникла проблема обучения ранжированию?

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

Ранжирование выполняется на базе модели сортировки f (q, d), где q — запрос пользователя, d — файл. Классическая модель f (q, d) работает без самообучения и не учитывает взаимосвязи между словами (пример — модели Okapi BM25, Vector space model, BIR).

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

Но здесь важно отменить несколько пунктов:

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

Обучение ранжированию — это полноценная учебная задача, которая включает обучение и тестирование. Данные для обучения включают в себя:

Каждый запрос связан с рядом файлов. Невозможно проверить релевантность всех файлов, поэтому обычно используется метод объединения — проверяются только несколько «верхних» документов, извлеченных существующими моделями ранжирования. Также данные для обучения могут быть получены автоматически из Google SearchWiki или же путем анализа журнала переходов, цепочек запросов. Но, к сожалению, объем этих данных — даже не сотая доля процента от требуемого объема для обучения ИИ.

Степень соответствия определяется файла запросу несколькими способами. Наиболее распространенный подход предполагает, что степень релевантности документа основывается на ряде показателей. Чем выше соответствие одного показателя — тем выше оценка по нему. Оценки релевантности получены из набора маркировки поисковой системы, которая принимает 5 значений от 0 (нерелевантно) до 5 (совершенно актуально). Оценки по всем показателям суммируются.

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

Однако здесь есть важный нюанс: обработка запросов пользователей должна выполняться на высокой скорости. И задействовать сложные схемы оценки в таком варианте (для каждого запроса) невозможно. Поэтому проверка выполняется на двух этапах:

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

Признаки делятся на три группы:

Такой подход позволяет предоставить пользователю наиболее точные результаты на странице выдачи. Признаки ранжирования собраны в LETOR — сборнике эталонов для исследований по обучению ранжированию в информационном поиске.

Для оценки каждого файла, который возвращается в ответ на запрос, используется как двоичная (релевантный/ нерелевантный), так и многоуровневая (например, релевантность от 0 до 5) шкалы. На практике запросы могут быть некорректными и иметь разные оттенки релевантности. Например, в запросе «Dog» есть двусмысленность: машина не знает, ищет ли пользователь планету Dog (собаку), альбом группы Blink-182 или репера Snoop Dogg.

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

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

Если мы хотим понять метрику NDCG, мы должны сначала понять CG (совокупный выигрыш) и DCG (дисконтированный совокупный выигрыш), а также понять два допущения, которые мы делаем, когда используем DCG и связанные с ним показатели:

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

Совокупный прирост на определенной позиции в рейтинге p, где rel_i — это оценка релевантность результата на позиции i. Каждая оценка релевантности связана с документом.

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

Например:

Очевидно, что Набор показателей B возвращает гораздо более полезный результат, чем Набор показателей A, но мера CG говорит, что они возвращают одинаково хорошие результаты.

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

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

Мы выполняем это путем сортировки всех соответствующих документов в корпусе по их относительной релевантности, получая максимально возможную DCG через позицию p(также известную как с).

Где, идеальный дисконтированный совокупный выигрыш:

Подробнее о подсчете метрики можно прочитать в Википедии.

Это доля извлеченных из индекса ПС документов, имеющих отношение к запросу; @n означает, что значение метрики считается только по n лучшим документам выдачи.

где D_rel — это множество релевантных документов в базе, а D_retl — множество документов, найденных системой.

Средняя точность для набора запросов — это значение средней точности для каждого запроса.

где Q — количество запросов.

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

где rank_i — положение первого релевантного документа для запроса i.

Разработка Яндекс, которая используется для оценки качества ранжирования. Расчет PFound производится по такой формуле:

Где pLook[i] — вероятность просмотреть i-й документ из списка, а pRel[i] — вероятность того, что i-й документ окажется релевантным.

Тема метрик оценки качества поиска актуальна и важна на сегодня. Но, к сожалению, мы можем говорить о ней только с точки зрения теоретизирования, но не реально работающего Google или Яндекса. Метрики оценки качества поиска, в нашем случае, — это по большей части фантазирование. И вот почему: мы не можем иметь на руках всех данных которые есть в Google или Яндекс, так как даже в самом в отделах этих компаний у людей далеко не все данные.

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

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

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

Всем удачи и высоких позиций!