Обучение ранжированию

Заметка о поиске аномалий закончилась оценкой (score) для каждой точки и аналитиком, который читает список сверху. Там имел значение только порядок оценок: детектор полезен, если настоящие аномалии идут первыми, а до тысячной строки никто не доходит. Это уже была задача ранжирования, решённая без разметки. В этой заметке мы решаем её с учителем. Поисковая система, каталог товаров, лента новостей и поисковая модель (retriever) вопросно-ответной системы — все они возвращают упорядоченный список, и люди судят о списке по его началу. Выход — порядок, а не метка. Заметка определяет, как измерить качество порядка, объясняет, почему такие меры нельзя оптимизировать напрямую, и строит три семейства функций потерь, которые их заменяют, заканчивая LambdaMART — ранжировщиком на градиентном бустинге, с которого до сих пор начинается большинство промышленных систем.

Обозначения. Запросу $q$ соответствуют $n$ документов-кандидатов. Документ $i$ описывается вектором признаков $x_i \in \mathbb R^d$ пары (запрос, документ) и имеет метку многоуровневой релевантности (graded relevance) $y_i \in \{0, 1, 2, 3, 4\}$, от нерелевантного до идеального; бинарная метка $y_i \in \{0, 1\}$ — частный случай. Модель $f$ ставит каждому документу оценку $s_i = f(x_i)$, и ранжирование сортирует документы по убыванию оценки. $y_{(j)}$ — метка документа на позиции $j$ этого ранжирования, а $k$ — порог (cutoff): метрика «на $k$» смотрит только на первые $k$ позиций. $\sigma(t) = 1/(1 + e^{-t})$ — логистическая функция.

Запросы, документы и релевантность#

Обучающие данные для ранжирования сгруппированы. У каждого запроса свой список кандидатов — обычно несколько сотен документов, которые дешёвый первый этап отобрал из миллионов, — и у каждого кандидата есть метка, поставленная асессором, который прочитал запрос и документ. Порядки сравниваются только внутри запроса: должен ли документ о ягуаре-животном идти раньше документа об автомобиле Jaguar, зависит от того, что спросили. Отсюда следует, что оценки модели имеют смысл лишь с точностью до сдвига, своего для каждого запроса. Прибавление константы ко всем оценкам запроса ничего не меняет.

Признаки описывают пару и бывают трёх видов:

• Признаки запроса зависят только от запроса: его длина, частота в логах, называет ли он товар. Они не могут изменить порядок внутри одного запроса, но могут изменить то, как следует читать другие признаки.
• Признаки документа зависят только от документа: его длина, свежесть, важность по ссылкам, например PageRank — стационарное распределение случайного пользователя, переходящего по ссылкам (random surfer).
• Признаки пары запрос–документ измеряют соответствие: оценка BM25 текста по словам запроса, косинус между их эмбеддингами, доля слов запроса в заголовке.

Из группировки следуют два практических правила. Валидационная выборка отделяется по запросам, а не по строкам: если документы одного запроса попадут и в обучение, и в валидацию, модель выучит особенности запроса и покажет качество, которого не достигнет на новых запросах, — это утечка из заметки о данных и утечках и групповые разбиения из заметки о валидации. Кроме того, ранжировщик обычно работает как второй этап каскада: быстрая поисковая модель сужает миллионы документов до сотен, а обученный ранжировщик их упорядочивает. Заметка о семантическом поиске строит именно такую пару для текста: биэнкодер (bi-encoder), который находит кандидатов, и кросс-энкодер (cross-encoder), который их переранжирует.

Измерение качества порядка#

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

Сквозной пример заметки — один запрос с шестью документами. В порядке, в котором их ранжирует модель, их метки равны

$$(y_{(1)}, \dots, y_{(6)}) = (0, 3, 1, 0, 2, 0).$$

Бинарная релевантность: точность, MAP и MRR#

Для бинарных метрик будем называть документ релевантным, если $y > 0$: здесь это позиции 2, 3 и 5.

Точность на $k$ (precision at k) — доля релевантных документов среди первых $k$:

$$\mathrm{P@}k = \frac1k \sum_{j=1}^k [\,y_{(j)} > 0\,].$$

В примере $\mathrm{P@1} = 0$, $\mathrm{P@3} = 2/3 = 0.667$ и $\mathrm{P@5} = 3/5 = 0.6$. Её легко читать, и она не учитывает порядок внутри первых $k$: релевантный документ на первом и на $k$-м месте учитывается одинаково.

Средняя точность (average precision) поощряет релевантные документы за то, что они идут рано. Она усредняет точность на позиции каждого релевантного документа по всем $R$ релевантным документам запроса:

$$\mathrm{AP} = \frac1R \sum_{j:\, y_{(j)} > 0} \mathrm{P@}j .$$

При релевантных документах на позициях 2, 3 и 5 $\mathrm{AP} = \frac13\big(\frac12 + \frac23 + \frac35\big) = 0.589$. Релевантный документ, который так и не был найден, даёт точность 0, но всё равно учитывается в $R$, поэтому AP штрафует за пропуски (Manning, Raghavan and Schütze, 2008, §8.4). Библиотеки расходятся в усечённых вариантах, AP@$k$: одни делят на $R$, другие на $\min(R, k)$; стоит проверять, какой вариант использован в опубликованном числе. Среднее AP по запросам — MAP (mean average precision).

Обратный ранг (reciprocal rank) смотрит только на первый релевантный документ: $\mathrm{RR} = 1/j^*$, где $j^*$ — его позиция, и 0, если такого нет. Здесь $\mathrm{RR} = 1/2$. Его среднее по запросам, MRR (средний обратный ранг), подходит для задач с одним правильным ответом, например для вопроса с одним фрагментом, который на него отвечает; так заметка о семантическом поиске измеряет качество поисковой модели.

Разобранный пример для двух запросов. Второй запрос с бинарными метками $(1, 0, 0, 1)$ в порядке ранжирования имеет $\mathrm{AP} = \frac12\big(1 + \frac24\big) = 0.75$ и $\mathrm{RR} = 1$. После усреднения с первым запросом $\mathrm{MAP} = (0.589 + 0.75)/2 = 0.669$ и $\mathrm{MRR} = (0.5 + 1)/2 = 0.75$.

Многоуровневая релевантность: DCG и NDCG#

Бинарные метрики отбрасывают разницу между идеальным ответом и сносным. Дисконтированный совокупный выигрыш (discounted cumulative gain, DCG) её сохраняет. Каждый документ вносит выигрыш (gain), который растёт с его меткой, делённый на дисконт (discount), который растёт с его позицией:

$$\mathrm{DCG@}k = \sum_{j=1}^{k} \frac{2^{y_{(j)}} - 1}{\log_2(1 + j)} .$$

Идея совокупного выигрыша с логарифмическим дисконтом принадлежит Järvelin and Kekäläinen (2002), §2.2; они использовали в качестве выигрыша саму метку и не дисконтировали позиции до выбранной. Экспоненциальный выигрыш $2^y - 1$, при котором один идеальный документ ценнее нескольких удовлетворительных, с логарифмическим дисконтом начиная с первой позиции — это форма, которую использовали Burges et al. (2005), §5, и которую реализует большинство библиотек (Manning, Raghavan and Schütze, 2008, §8.4). Основание логарифма сокращается в NDCG ниже; основание 2 — соглашение. У DCG нет фиксированной шкалы: запрос с большим числом релевантных документов достигает больших значений, чем запрос с единственным хорошим ответом. NDCG делит на DCG идеального порядка — документов, отсортированных по метке, — так что 1 означает идеальное ранжирование:

$$\mathrm{NDCG@}k = \frac{\mathrm{DCG@}k}{\mathrm{IDCG@}k} .$$

Разобранный пример. Шесть документов дают такие вклады:

позиция $j$	1	2	3	4	5	6
метка $y_{(j)}$	0	3	1	0	2	0
выигрыш $2^{y} - 1$	0	7	1	0	3	0
дисконт $1/\log_2(1+j)$	1	0.631	0.5	0.431	0.387	0.356
вклад	0	4.417	0.5	0	1.161	0

поэтому $\mathrm{DCG@6} = 6.077$. Идеальный порядок $(3, 2, 1, 0, 0, 0)$ даёт $\mathrm{IDCG@6} = 7 + 3 \cdot 0.631 + 1 \cdot 0.5 = 9.393$, и $\mathrm{NDCG@6} = 6.077/9.393 = 0.647$. При $k = 3$ документ с меткой 2 выпадает из числителя, но не из идеального порядка, и $\mathrm{NDCG@3} = 4.917/9.393 = 0.523$. Больше всего теряется на позиции 1: документ с меткой 3 стоит на одно место ниже, чем нужно, и его подъём умножил бы его вклад на $1/0.631 = 1.58$.

Соглашения, которые меняют среднее. AP не определена для запроса с $R = 0$, а NDCG — для запроса с $\mathrm{IDCG@}k = 0$, то есть для запроса без единого релевантного документа. Раздел «Код» исключает такие запросы из среднего (68 из 1000 тестовых запросов); другие реализации ставят им 0 или 1. Каждый выбор описывает свою совокупность запросов, поэтому соглашение нужно указывать рядом с числом. Важны ещё два выбора: идеальный DCG обрезается на том же $k$, что и DCG, а документы с равными оценками упорядочиваются по какому-то правилу, здесь — по порядку сортировки.

Почему метрики нельзя оптимизировать напрямую#

Каждая метрика выше зависит от оценок только через порядок, который они задают. Малое изменение одной оценки либо оставляет порядок, а с ним и метрику, неизменным, либо меняет местами двух соседей, и метрика меняется скачком. Как функция оценок, а значит, и параметров модели, NDCG кусочно-постоянна: её градиент почти всюду равен нулю и не определён в точках скачков (Burges, 2010, §3). Градиентный спуск не получает от неё сигнала.

Рисунок

NDCG — ступенчатая функция оценок, функция потерь RankNet — гладкая

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

Поточечный подход: регрессия на метки#

Простейший, поточечный (pointwise) подход забывает, что задача — ранжирование. Каждая пара (запрос, документ) рассматривается как пример с целевой переменной $y_i$, на этих примерах обучается регрессия с квадратичной ошибкой или порядковый (ordinal) классификатор, и документы сортируются по предсказанию. Подходит любая модель курса, включая градиентный бустинг, и этот метод — сильное базовое решение.

Его функция потерь, однако, измеряет не то. Возьмём два документа одного запроса с метками 1 и 2. Предсказания $(1.9, 1.1)$ близки к меткам, среднеквадратичная ошибка $0.81$, но ставят документы в неправильном порядке. Предсказания $(-1, 0)$ далеки от меток, среднеквадратичная ошибка $4$, но порядок правильный. Регрессия предпочитает первые. В общем случае поточечная функция потерь тратит усилия на то, что не влияет на порядок: на точное значение каждого нерелевантного документа внизу длинного списка и на общий уровень меток запроса, который мог бы предсказать признак запроса, но который сдвигает все оценки запроса вместе. В разделе «Код» бустинговый регрессор отдаёт половину прироста от разбиений (split gain) такому признаку запроса.

Попарный подход: RankNet#

Ранжирование — это утверждение о парах: документ $i$ должен идти раньше документа $j$, когда $y_i > y_j$. RankNet (Burges et al., 2005) моделирует вероятность этого предпочтения через разность двух оценок,

$$P(i \rhd j) = \sigma(s_i - s_j) = \frac{1}{1 + e^{-(s_i - s_j)}},$$

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

$$C_{ij} = -\log \sigma(s_i - s_j) = \log\big(1 + e^{-(s_i - s_j)}\big).$$

Это логистическая функция потерь классификатора, на вход которому подаётся пара, а выход говорит, какой документ выигрывает, — кросс-энтропия из заметки о методе максимального правдоподобия, применённая к предпочтениям. С линейной оценкой $s = w^\top x$ это буквально логистическая регрессия на векторах разностей $x_i - x_j$, без свободного члена, поскольку сдвиг всех оценок сокращается. Burges et al. использовали в качестве $f$ нейронную сеть, а вместо жёстких 0 или 1 — целевые вероятности $\bar P_{ij}$, что допускает равные метки ($\bar P_{ij} = 1/2$) и предпочтения, измеренные несколькими экспертами (§3, формулы 1–3). Замена логистической функции потерь кусочно-линейной (hinge loss) даёт RankSVM (Joachims, 2002).

Разобранный пример. Неправильно упорядоченная пара с $s_i = 0.5$, $s_j = 1.0$ стоит $\log(1 + e^{0.5}) = 0.974$. Та же пара, упорядоченная правильно с отступом (margin) 2, $s_i = 2$, $s_j = 0$, стоит $\log(1 + e^{-2}) = 0.127$; при равных оценках стоимость равна $\log 2 = 0.693$. Функция потерь продолжает раздвигать правильно упорядоченные пары, слабо, пока отступ не станет большим.

Функция потерь — гладкая верхняя оценка числа неправильно упорядоченных пар с точностью до множителя: $[\,s_i \le s_j\,] \le C_{ij}/\log 2$. Поэтому её минимизация повышает счётчики правильно упорядоченных пар в духе AUC, а не NDCG.

Градиент и силы, которые он задаёт. Производная $C_{ij}$ по оценкам равна

$$\frac{\partial C_{ij}}{\partial s_i} = -\sigma(s_j - s_i) = -\frac{\partial C_{ij}}{\partial s_j} .$$

Обозначим через $\lambda_{ij} = \sigma(s_j - s_i) > 0$ величину этого толчка: она близка к 1 для сильно перепутанной пары и близка к 0 для пары, упорядоченной с большим отступом. Шаг градиентного спуска поднимает $s_i$ на $\eta\lambda_{ij}$ и опускает $s_j$ на ту же величину. Суммирование по всем парам, содержащим документ, даёт одно число на документ — его суммарную силу

$$\lambda_i = \sum_{j:\, y_i > y_j} \lambda_{ij} \;-\; \sum_{j:\, y_j > y_i} \lambda_{ji},$$

положительную, если документ должен подняться. В разобранном примере у перепутанной пары с оценками 0.5 и 1.0 $\lambda_{ij} = \sigma(0.5) = 0.622$, а у правильно упорядоченной пары с оценками 2 и 0 $\lambda_{ij} = \sigma(-2) = 0.119$. Для первой пары $\partial C_{ij}/\partial s_i = -0.622$, поэтому шаг спуска $s_i \leftarrow s_i - \eta\, \partial C_{ij}/\partial s_i$ поднимает $s_i$ на $0.622\,\eta$, как и должна положительная сила. Поскольку для полной функции потерь $C = \sum C_{ij}$ выполнено $\partial C / \partial s_i = -\lambda_i$, силы — это градиент по оценкам, взятый со знаком минус. Burges (2010, §2.1) заметил, что обновлению параметров нужны только эти суммы по документам: для нейронной сети антиградиент равен $-\partial C / \partial w = \sum_i \lambda_i\, \partial s_i / \partial w$, а обновление — $w \leftarrow w + \eta \sum_i \lambda_i\, \partial s_i / \partial w$ — один обратный проход на документ вместо одного на пару, что сократило время обучения на запрос с почти квадратичного по числу документов до почти линейного. Burges записывает градиент с противоположным знаком; принятое здесь соглашение — положительное значение означает «вверх» — делает рисунки нагляднее.

Списочный подход: распределение на порядках#

Попарная функция потерь видит два документа за раз. Списочная (listwise) функция потерь сравнивает весь предсказанный список со всем идеальным. Поскольку порядки дискретны, приём, как и для классов, состоит в том, чтобы превратить оценки в распределение вероятностей. Модель Плакетта–Льюса (Plackett–Luce) строит порядок по одной позиции: первый документ выбирается с вероятностью, пропорциональной $e^{s_i}$, второй — так же среди оставшихся, и так далее, поэтому вероятность порядка $\pi$ равна

$$P_s(\pi) = \prod_{j=1}^{n} \frac{e^{s_{\pi(j)}}}{\sum_{l=j}^{n} e^{s_{\pi(l)}}} .$$

Порядок, сортирующий по оценке, — самый вероятный, а перемещение документа с большей оценкой ниже документа с меньшей делает порядок менее вероятным (Cao et al., 2007, §4.1). Суммировать по всем $n!$ порядкам непрактично, поэтому ListNet оставляет только первый множитель — вероятность оказаться первым (top-one probability) для каждого документа,

$$P_s(i) = \frac{e^{s_i}}{\sum_{l=1}^n e^{s_l}},$$

то есть softmax по списку (§4.2, теорема 6). Метки задают целевое распределение так же, $P_y(i) = e^{y_i}/\sum_l e^{y_l}$, а функция потерь — кросс-энтропия $-\sum_i P_y(i) \log P_s(i)$ (§5).

Разобранный пример. У трёх документов с оценками $(2, 1, 0)$ вероятности оказаться первым равны $e^2/(e^2 + e + 1) = 0.665$, затем $0.245$ и $0.090$; вероятность полного порядка $(1, 2, 3)$ равна $0.665 \cdot e/(e + 1) = 0.486$. Если их метки равны $(2, 0, 1)$, целевое распределение равно $(0.665, 0.090, 0.245)$, а кросс-энтропия — $0.987$: функция потерь хочет поменять местами второй и третий документы.

Softmax по кандидатам с кросс-энтропией появляется снова всякий раз, когда из списка нужно выбрать один элемент: заметка о многоклассовой классификации применяет его к классам, а контрастная функция потерь, на которой обучаются биэнкодеры семантического поиска, — к фрагментам, с одним релевантным фрагментом на запрос и остальными фрагментами батча в роли списка. Списочная функция потерь видит весь список, но всё ещё обращается со всеми позициями одинаково: ничто в ней не говорит, что первое место важнее пятого.

LambdaRank: градиенты, взвешенные по NDCG#

RankNet минимизирует число неправильно упорядоченных пар, и на сквозном примере это приводит к неверным приоритетам. Сильнее всего он толкает документ с меткой 2 на пятом месте, который проигрывает три пары менее релевантным документам над ним. Для NDCG важнее документ с меткой 3 на втором месте: один его обмен с нерелевантным документом наверху поднял бы NDCG больше, чем что-либо, что может произойти на позиции 5.

Наблюдение, лежащее в основе LambdaRank (Burges, Ragno and Le, 2006), состоит в том, что обучению нужны только градиенты по оценкам, $\lambda$, а не функция потерь, градиентами которой они являются. Поэтому запишем градиенты напрямую: сохраним силу RankNet для каждой пары и умножим её на то, насколько пара важна для метрики,

$$\lambda_{ij} = \sigma(s_j - s_i)\, \lvert \Delta\mathrm{NDCG}_{ij} \rvert ,$$

где $\Delta\mathrm{NDCG}_{ij}$ — изменение NDCG, если документы $i$ и $j$ поменяются позициями в текущем ранжировании, а все остальные останутся на местах (Burges, 2010, §4.1, формула 6). Силы документов $\lambda_i$ суммируются, как и раньше. Из десяти функций сил, которые попробовали Burges, Ragno и Le, лучше всего на их валидационных данных сработала именно эта — градиент RankNet, масштабированный изменением NDCG при обмене (§6.2).

Изменение при обмене выражается в замкнутом виде. Обмен документов $i$ и $j$ на позициях $p_i$ и $p_j$ меняет только их два слагаемых в DCG. С выигрышами $g = 2^y - 1$ и дисконтами $D(p) = 1/\log_2(1 + p)$ два слагаемых $g_i D(p_i) + g_j D(p_j)$ превращаются в $g_i D(p_j) + g_j D(p_i)$, поэтому

$$\lvert \Delta \mathrm{NDCG}_{ij} \rvert = \frac{\lvert g_i - g_j \rvert \, \lvert D(p_i) - D(p_j) \rvert}{\mathrm{IDCG}} .$$

Разобранный пример. В сквозном списке обмен документа с меткой 3 на позиции 2 с нерелевантным на позиции 1 меняет NDCG на $7 \times (1 - 0.631)/9.393 = 0.275$. Его обмен с документом с меткой 2 на позиции 5 меняет NDCG на $(7 - 3)(0.631 - 0.387)/9.393 = 0.104$, а обмен документов с метками 1 и 2 на позициях 3 и 5 — всего на $(3 - 1)(0.5 - 0.387)/9.393 = 0.024$. При оценках $2.5, 2.0, \dots, 0.0$ суммарные силы такие:

Рисунок

Силы λ на документах запроса: RankNet и LambdaRank

Знаки сил совпадают везде, кроме документа с меткой 1 на третьем месте, который LambdaRank едва заметно толкает вниз, а приоритеты меняются. Самый сильный толчок вверх у RankNet, $+2.429$, получает документ на пятом месте; у LambdaRank, $+0.286$ против $+0.184$, — документ на втором месте. Оба сильнее всего толкают вниз нерелевантный документ наверху.

Есть ли функция потерь? При фиксированном порядке документов $\lambda$ — это градиенты, взятые с обратным знаком, функции $\sum \lvert\Delta \mathrm{NDCG}_{ij}\rvert \log(1 + e^{-(s_i - s_j)})$, то есть функции потерь RankNet с весами; но веса меняются всякий раз, когда меняется порядок, поэтому лямбды не являются градиентами одной фиксированной гладкой функции оценок (Burges, 2010, §4.3 и §7). Можно записать кусочные целевые функции, веса которых зависят от текущего ранжирования, но лямбды не являются обычной производной ни этих функций, ни самого NDCG, кусочно-постоянного. Эмпирически обучение с ними, по-видимому, достигает локального максимума NDCG: Burges (2010, §4.2) описывает, как веса обученной модели возмущали в сотнях случайных направлений и NDCG уменьшался во всех. Замена $\Delta\mathrm{NDCG}$ изменением другой метрики, MAP или MRR, обучает модель уже под эту метрику (§4.1).

LambdaMART: лямбды как цели бустинга#

Градиентному бустингу нужен только градиент функции потерь по текущим оценкам: каждое новое дерево обучается на антиградиент в каждой обучающей точке, а значения в его листьях задаются линейным поиском или шагом Ньютона. Лямбды — ровно такие градиенты, поэтому они подставляются напрямую. LambdaMART (Wu et al., 2010; Burges, 2010, §7) — это MART, градиентный бустинг Фридмана над регрессионными деревьями, в котором целевые значения заменены на $\lambda_i$:

1. Для каждого запроса отсортировать документы по текущим оценкам $F(x_i)$ и вычислить для каждого документа $\lambda_i$ и его кривизну $w_i = \sum_j \lvert\Delta\mathrm{NDCG}_{ij}\rvert\, \rho_{ij}(1 - \rho_{ij})$, где $\rho_{ij} = \sigma(s_j - s_i)$, а сумма берётся по всем парам, содержащим $i$.
2. Обучить регрессионное дерево на $\lambda_i$ всех документов всех запросов методом наименьших квадратов.
3. Задать значение листа $l$ шагом Ньютона, $\gamma_l = \sum_{i \in l} \lambda_i / \sum_{i \in l} w_i$, и добавить дерево с шагом обучения: $F \leftarrow F + \eta\, \gamma_{l(x)}$.

Силы одного запроса в сумме дают ноль, поскольку каждая пара добавляет $+\lambda_{ij}$ одному документу и $-\lambda_{ij}$ другому. Разбиение по признаку, постоянному внутри каждого запроса, например по признаку запроса, отправляет в каждую сторону запросы целиком; поэтому силы с каждой стороны по-прежнему суммируются в ноль, и разбиение по целым запросам не уменьшает квадратичную ошибку. Признак запроса ещё может помочь глубже в дереве, когда в узле остаётся лишь часть документов каждого запроса, но общий уровень запроса, который поточечному бустингу приходится моделировать, не даёт LambdaMART ничего, что можно было бы подогнать. Ансамбль ранжировщиков LambdaMART выиграл трек 1 конкурса Yahoo! Learning to Rank Challenge 2010 года (§1), и именно этот метод реализуют целевые функции ранжирования распространённых библиотек бустинга, например lambdarank в LightGBM и rank:ndcg в XGBoost.

На синтетических данных из раздела «Код», 1000 тестовых запросов по 30 документов, линейная модель получает одинаковый NDCG@5 с поточечной и с попарной функцией потерь (0.647 и 0.646), поточечно обученные бустинговые деревья достигают 0.766, а LambdaMART с тем же числом и глубиной деревьев — 0.814. Поточечный бустинг тратит 51% прироста от разбиений на признак запроса, LambdaMART — ничего. Разрыв зависит от случайной генерации данных: на пяти генерациях он составлял от 0.007 до 0.048, всегда в пользу LambdaMART. На данных без эффекта уровня запроса два бустинга сближаются гораздо сильнее, и это общая картина: преимущество LambdaMART реально, но часто невелико, а хорошо настроенный поточечный бустинг — трудное базовое решение.

Клики и смещение из-за позиции#

Разметка асессоров дорога, а поисковая система видит миллионы кликов в день. Клики — тоже метки, но смещённые. Пользователь может кликнуть только на то, что он просмотрел, а верх списка люди просматривают гораздо чаще, чем низ. В исследовании с отслеживанием взгляда (eye-tracking) Joachims et al. (2005) для одних пользователей меняли местами два первых результата поисковой системы, а для других переворачивали весь список: первая позиция всё равно собирала больше кликов, чем оправдывала её релевантность, — это смещение доверия (trust bias) к порядку поисковой системы (§5.2.1). Модель, обученная на сырых кликах, учится ставить первым то, что показывали первым.

Стандартная позиционная модель (position-based model) разделяет два шага. Она предполагает, что клик требует просмотра, что просмотр зависит только от позиции и что после просмотра клик зависит только от документа. При этих предположениях формула умножения вероятностей (chain rule) даёт

$$P(\text{клик} \mid \text{документ}, \text{позиция } p) = \underbrace{P(\text{просмотр} \mid p)}_{\text{вероятность просмотра } \theta_p} \cdot P(\text{клик} \mid \text{просмотр}, \text{документ}),$$

где второй множитель отвечает за релевантность, а вероятность просмотра (propensity) $\theta_p$ зависит только от позиции (Joachims, Swaminathan and Schnabel, 2017, §5.1). Деление каждого клика на вероятность просмотра той позиции, где он произошёл, — взвешивание по обратной вероятности просмотра (inverse propensity scoring, IPS) — даёт оценку того, какими были бы клики, если бы каждый документ был просмотрен (формула 5). Она несмещённая в рамках модели, если у каждой используемой позиции $\theta_p > 0$ и вероятности просмотра верны; она устраняет смещение из-за показа, заложенное в модель, но не описанное выше смещение доверия, при котором сам клик после просмотра зависит от позиции. Это выборка по значимости (importance sampling), в которой роль распределения-предложения (proposal) играет залогированное ранжирование. Сами вероятности просмотра оцениваются по небольшим рандомизированным экспериментам, например по обмену результата между двумя позициями для части пользователей (§5.3).

Разобранный пример (симуляция). Документ, на который кликнули бы 30% просмотревших его пользователей, показан 100 000 раз на позиции 1, где его просматривают всегда, и 100 000 раз на позиции 3, где его просматривают в 40% случаев. Смоделированные доли кликов (click-through rate, CTR) равны 0.299 и 0.119: по сырым кликам документ на позиции 3 в два с половиной раза хуже. После деления на вероятности просмотра 1.0 и 0.4 оценки равны 0.299 и 0.297 — это тот же документ.

Второе средство меняет то, что извлекается из кликов, а не то, как они взвешиваются. Клик на результат на позиции 3, когда позиции 1 и 2 были пропущены, говорит, что пользователь предпочёл его этим двум, — это попарное предпочтение, гораздо менее чувствительное к позиции, чем сам клик (Joachims et al., 2005, §5.3). Такие предпочтения напрямую подаются в попарную функцию потерь. Какими бы ни были метки, окончательный вердикт новому ранжировщику выносит онлайн-эксперимент: A/B-тест на поведении реальных пользователей.

Что изменилось#

	Классификация и регрессия	Обучение ранжированию
Выход	метка или число для каждого объекта	порядок кандидатов каждого запроса
Данные	независимые примеры	списки, сгруппированные по запросам; разбиение по запросам
Метрика	по объектам: доля правильных ответов, log loss, AUC	по спискам, с весом по позиции: P@$k$, MAP, MRR, NDCG
Сигнал для обучения	градиент функции потерь	у метрики его нет; поточечные, попарные или списочные суррогаты
Самый известный метод	логистическая регрессия, градиентный бустинг	LambdaMART: бустинг на попарных градиентах, взвешенных по NDCG
Метки	даны	асессоры или клики с поправкой на смещение из-за позиции

Ограничения#

• Метрика — это выбор при моделировании. Выигрыш $2^y - 1$, логарифмический дисконт и порог $k$ кодируют предположения о том, как люди читают список. Разные метрики предпочитают разные ранжировщики, а офлайн-метрика — лишь суррогат того, что делают пользователи.
• Лямбды — эвристика. Они не являются градиентом фиксированной функции потерь, и их успех на NDCG эмпиричен. Каждый шаг обучения требует времени, квадратичного по длине списка запроса, поскольку перебирается каждая пара.
• Документы оцениваются независимо. Сортировка по независимым оценкам не может выразить, что два почти дубликата не должны оба оказаться наверху или что список должен покрывать несколько значений неоднозначного запроса. Для разнообразия нужна модель всего списка.
• Меток мало, или они смещены. Асессоры расходятся во мнениях и стоят дорого; клики требуют модели поведения пользователей, и ошибка в вероятностях просмотра становится смещением ранжировщика.
• Петли обратной связи. Ранжировщик, обученный на кликах по собственным прошлым ранжированиям, учится на том, что сам решил показать; документы, которые он никогда не показывал, не получают ни кликов, ни шанса.

Что нужно запомнить#

• Данные для ранжирования сгруппированы по запросам; важен только порядок внутри запроса, и валидация должна разбивать данные по запросам.
• P@$k$ считает релевантные документы среди первых $k$; AP усредняет точность на каждой релевантной позиции; RR равен $1/$позиция первого релевантного документа; DCG суммирует выигрыши $2^y - 1$, дисконтированные делением на $\log_2(1 + j)$, а NDCG делит на идеальный DCG.
• Метрики ранжирования кусочно-постоянны по оценкам: градиент почти всюду равен нулю. Обучать нужно суррогат, а валидировать — по метрике.
• Поточечный подход: регрессия на метки. Попарный (RankNet): логистическая функция потерь от $s_i - s_j$ для каждой пары с $y_i > y_j$. Списочный (ListNet): кросс-энтропия между softmax от меток и softmax от оценок.
• LambdaRank умножает градиент RankNet для каждой пары, $\sigma(s_j - s_i)$, на $\lvert\Delta\mathrm{NDCG}_{ij}\rvert$; LambdaMART обучает бустинговые деревья на этих лямбдах со значениями листьев по шагу Ньютона.
• Клик — это релевантность, умноженная на просмотр; взвешивание по обратной вероятности просмотра — это выборка по значимости с залогированным ранжированием в роли распределения-предложения.

Код#

Сквозной пример, силы с рисунка, сравнение четырёх ранжировщиков на синтетических запросах и клики при смещении из-за позиции:

import numpy as np
from sklearn.linear_model import Ridge, LogisticRegression
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.tree import DecisionTreeRegressor

def dcg(y, k):                                    # y: метки в порядке ранжирования (последняя ось); выигрыш 2^y - 1, дисконт log2(1 + позиция)
    y = np.asarray(y, float)[..., :k]
    return ((2 ** y - 1) / np.log2(np.arange(2, y.shape[-1] + 2))).sum(-1)
def ndcg(y, s, k):                                # y, s: (запросы, документы); запрос без релевантных документов даёт nan
    ranked = np.take_along_axis(y, np.argsort(-s, axis=-1), -1)
    with np.errstate(invalid='ignore'):
        return dcg(ranked, k) / dcg(-np.sort(-y, axis=-1), k)

# сквозной пример: метки в том порядке, в котором модель ранжирует шесть документов
lab = np.array([0, 3, 1, 0, 2, 0]); rel = lab > 0
ap = (np.cumsum(rel) / np.arange(1, 7))[rel].mean()
print(rel[:3].mean().round(3), rel[:5].mean(), ap.round(4), 1 / (np.argmax(rel) + 1))  # 0.667 0.6 0.5889 0.5
print(dcg(lab, 6).round(3), dcg(np.sort(lab)[::-1], 6).round(3), (dcg(lab, 6) / dcg(np.sort(lab)[::-1], 6)).round(3))  # 6.077 9.393 0.647

def lambdas(y, s):                                # силы LambdaRank, веса Ньютона и силы RankNet для батча запросов
    g = 2.0 ** y - 1
    pos = np.argsort(np.argsort(-s, axis=-1), axis=-1) + 1
    disc = 1 / np.log2(1 + pos)
    ideal = np.maximum(dcg(-np.sort(-y, axis=-1), y.shape[-1]), 1e-12)[..., None, None]
    better = y[..., :, None] > y[..., None, :]                       # пары (i, j), в которых i релевантнее j
    rho = 1 / (1 + np.exp(s[..., :, None] - s[..., None, :]))       # сила RankNet для пары: sigmoid(s_j - s_i)
    dn = np.abs((g[..., :, None] - g[..., None, :]) * (disc[..., :, None] - disc[..., None, :])) / ideal
    lam, hes, rn = np.where(better, rho * dn, 0), np.where(better, rho * (1 - rho) * dn, 0), np.where(better, rho, 0)
    return lam.sum(-1) - lam.sum(-2), hes.sum(-1) + hes.sum(-2), rn.sum(-1) - rn.sum(-2)

lam, _, ranknet = lambdas(lab[None].astype(float), np.array([[2.5, 2.0, 1.5, 1.0, 0.5, 0.0]]))
print(ranknet.round(3), lam.round(3))
# [[-2.234  1.571  0.182 -1.269  2.429 -0.679]] [[-0.383  0.286 -0.005 -0.052  0.184 -0.031]]

# синтетические запросы: по 30 документов, 6 признаков; признак 5 — признак запроса, общий для всех его документов
rng = np.random.default_rng(0)
Q, N, d = 1300, 30, 6
X = rng.normal(size=(Q, N, d))
X[..., 5] = rng.normal(size=(Q, 1))
z = X[..., 0] + 0.7 * X[..., 1] + X[..., 2] * X[..., 3] + 1.5 * X[..., 5] + rng.normal(0, 0.7, (Q, N))
Y = np.digitize(z, [1, 2, 3, 4]).astype(float)                       # многоуровневая релевантность 0..4
tr, te = slice(0, 300), slice(300, Q)                                  # разбиение по запросам: 300 для обучения, 1000 для теста
Xtr, Ytr, Xte = X[tr].reshape(-1, d), Y[tr].ravel(), X[te].reshape(-1, d)
score = lambda s: np.nanmean(ndcg(Y[te], s.reshape(1000, N), 5)).round(3)

print('random', score(rng.normal(size=(1000, N))))                    # random 0.19
print('linear, pointwise', score(Ridge(1.0).fit(Xtr, Ytr).predict(Xte)))   # linear, pointwise 0.647
i = np.nonzero(Y[tr][:, :, None] > Y[tr][:, None, :])                 # линейный RankNet: логистическая регрессия на разностях
diff = X[tr][i[0], i[1]] - X[tr][i[0], i[2]]
pairwise = LogisticRegression(fit_intercept=False).fit(np.vstack([diff, -diff]), np.r_[np.ones(len(diff)), np.zeros(len(diff))])
print('linear, RankNet', score(Xte @ pairwise.coef_.ravel()))         # linear, RankNet 0.646
gbm = GradientBoostingRegressor(n_estimators=100, max_depth=3, random_state=0).fit(Xtr, Ytr)
print('trees, pointwise', score(gbm.predict(Xte)), gbm.feature_importances_.round(2))
# trees, pointwise 0.766 [0.25 0.13 0.06 0.06 0.   0.51]

F, Ft, imp = np.zeros((300, N)), np.zeros(len(Xte)), np.zeros(d)   # LambdaMART: деревья обучаются на лямбдах, листья делают шаг Ньютона
for m in range(100):
    lam, hes, _ = lambdas(Y[tr], F)
    tree = DecisionTreeRegressor(max_depth=3, random_state=0).fit(Xtr, lam.ravel())
    leaf = tree.apply(Xtr)
    imp += tree.tree_.compute_feature_importances(normalize=False)
    gamma = np.bincount(leaf, lam.ravel(), leaf.max() + 1) / np.maximum(np.bincount(leaf, hes.ravel(), leaf.max() + 1), 1e-12)
    F += 0.1 * gamma[leaf].reshape(300, N)
    Ft += 0.1 * gamma[tree.apply(Xte)]
print('trees, LambdaMART', score(Ft), (imp / imp.sum()).round(2))
# trees, LambdaMART 0.814 [0.49 0.41 0.05 0.04 0.   0.  ]

# клики при смещении из-за позиции: релевантность 0.3, вероятность просмотра 1.0 на позиции 1 и 0.4 на позиции 3
for p in (1.0, 0.4):
    clicks = rng.random(100_000) < p * 0.3
    print(p, clicks.mean().round(3), (clicks / p).mean().round(3))   # 1.0 0.299 0.299 | 0.4 0.119 0.297

Дальше#

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

Литература#

• C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, G. Hullender. Learning to Rank using Gradient Descent. ICML, 2005. RankNet: вероятностная попарная функция потерь (§3, формулы 1–3); NDCG с выигрышем $2^r - 1$ (§5, формула 16).
• C. J. C. Burges, R. Ragno, Q. V. Le. Learning to Rank with Nonsmooth Cost Functions. NeurIPS, 2006. LambdaRank; выбор функции сил (§6.2).
• C. J. C. Burges. From RankNet to LambdaRank to LambdaMART: An Overview. Microsoft Research Technical Report MSR-TR-2010-82, 2010. RankNet и его факторизация (§2, §2.1), метрики информационного поиска (§3), LambdaRank (§4.1–4.3, формула 6), LambdaMART и его шаг Ньютона (§7).
• Q. Wu, C. J. C. Burges, K. M. Svore, J. Gao. Adapting Boosting for Information Retrieval Measures. Information Retrieval, 13(3), 2010. LambdaMART.
• Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, H. Li. Learning to Rank: From Pairwise Approach to Listwise Approach. ICML, 2007; расширенная версия — MSR-TR-2007-40. ListNet: вероятность перестановки (§4.1), вероятность оказаться первым (§4.2), функция потерь (§5).
• T. Joachims. Optimizing Search Engines using Clickthrough Data. KDD, 2002. RankSVM.
• K. Järvelin, J. Kekäläinen. Cumulated Gain-Based Evaluation of IR Techniques. ACM Transactions on Information Systems, 20(4), 2002. Дисконтированный совокупный выигрыш (§2.2) и его нормированная версия (§2.3).
• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. §8.4 (оценка ранжированных результатов: точность на $k$, MAP, NDCG).
• T. Joachims, L. Granka, B. Pan, H. Hembrooke, G. Gay. Accurately Interpreting Clickthrough Data as Implicit Feedback. SIGIR, 2005. Смещение доверия (§5.2.1), клики как относительные предпочтения (§5.3).
• T. Joachims, A. Swaminathan, T. Schnabel. Unbiased Learning-to-Rank with Biased Feedback. WSDM, 2017. Модель вероятностей просмотра, зависящих от позиции, и оценка IPS (§5.1, формула 5), оценка вероятностей просмотра с помощью обменов (§5.3).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 24: обучение ранжированию, 2019.