[БЕЗ_ЗВУКА] В этом видео мы обсудим подходы к решению задачи ранжирования, а именно какие методы могут использоваться для ее решения. Всего выделяют три подхода: pointwise — поточечный, pairwise — попарный и listwise — списочный. Мы приведем по одному примеру метода из каждого подхода, чтобы вы понимали, чем они отличаются и какие у них особенности. Первый, самый простой подход — это поточечный. В нем мы забываем о том, что целевая переменная задается на парах объектов, и пытаемся непосредственно для каждого объекта предсказывать оценку его релевантности. Например, если мы говорим о задаче ранжирования поисковой выдачи, то асессор поставил каждому объекту, каждой паре «запрос — документ» некоторую оценку y. Ее мы и будем предсказывать. При этом мы никак не учитываем, что на самом деле нам важна не конкретная оценка, а порядок, который ей задается. Тем не менее, данный подход простой в том смысле, что его можно решать известными нам методами. Например, с помощью линейной регрессии и среднеквадратичной ошибки. Мы умеем решать эту задачу и получим некоторую модель, которая предсказывает релевантность. Дальше по выходам этой модели можно пытаться ранжировать объекты. Неизвестно, хорошо это или плохо, но при этом с каким-то качеством задачу мы решим. Следующий подход — попарный, или pairwise. В нем мы все же вспоминаем, как устроена целевая переменная, и записываем функционал, который зависит от пар объектов. Мы суммируем по всем парам объектов таких, что x(i) < x(j), и штрафуем те пары, на которых, как оказалось, что оценка релевантности для i-го объекта больше, чем оценка релевантности для j-го объекта. Если это выполнено, то мы неправильно отранжируем данную пару, поэтому штраф вполне логичен. К сожалению, функционал оказывается дискретным, здесь стоит индикатор, и поэтому непосредственно его минимизировать не получится. Но при этом можно действовать так же, как мы действовали с классификаторами: можно оценить сверху данный функционал, можно считать, что разница между выходами модели на j-м и i-м объекте — это отступ, и задать некоторую гладкую функцию от отступа L(M), и суммировать значения данной функции по всем парам, для которых мы знаем порядок. Например, если мы выберем такую же функцию L, как и в логистической регрессии log (1 + e(−M) ), то мы получим метод, который называется RankNet. После этого можно решать задачу с помощью, например, стохастического градиентного спуска. Так и устроены попарные подходы: мы записываем функционал, но при этом сводим его к решению простыми методами, сводим к гладкому функционалу. Если записать один шаг стохастического градиента для метода RankNet, мы получим вот такую формулу, в которой мы еще и считаем, что модель у нас линейная. Мы ранжируем с помощью линейной модели. Формула получается не очень сложная и зависит от одной пары x(i) и x(j), для которой мы знаем порядок. Возникает вопрос: а можно ли как-то модифицировать данный метод, а именно данную формулу шага, чтобы оптимизировался не наш исходный функционал, который гладко оценивает долю дефектных пар, а, например, он оптимизировал NDCG? Ответ положительный. Оказывается, что если мы домножим градиент исходного функционала на то, на сколько изменится NDCG, если мы поменяем местами i-й и j-й объект — здесь это обозначается как ΔNDCGij, то при выполнении градиентного спуска с помощью данных шагов мы уже будем оптимизировать NDCG. Это эмпирический факт, он не доказан. Но при этом оказывается, что действительно на практике NDCG улучшается при решении задачи данным методом. Есть и более сложные подходы к решению задачи оптимизации NDCG, но при этом в них уже предпринимается попытка как-то работать с дискретным функционалом, а это гораздо сложнее. Это же самый простой подход, в котором удается это делать. Метод называется LambdaRank. Итак, мы обсудили три подхода: поточечный, попарный и списочный к решению задачи ранжирования. При этом на практике чаще всего используется попарный подход, поскольку, с одной стороны, он учитывает структуру задачи. В нем используется тот факт, что у нас ответы заданы на парах объектах. И при этом он не очень сложный, он сводит решение задачи к простому стохастическому градиентному спуску или другому оптимизационному методу, в отличие от списочного подхода, где уже приходится работать с дискретными функционалами.