RecSys Часть III · Ранжирование · глава 10 из 19
Обучение ранжированию
Кандидаты отобраны — их нужно упорядочить. Вопрос «какой лосс взять» выглядит как выбор из каталога, но на деле это выбор того, что именно вы объявляете правдой: сама релевантность, наблюдаемый порядок или структура показанного списка. Разбираем три семейства, выводим BPR из правдоподобия и смотрим, что каждый выбор отнимает.
- Три семейства отличаются множеством, на котором считается лосс. Один айтем, пара, весь слейт. Всё остальное — следствия.
- Калибровка и порядок — разные вещи, и вторая не даёт первой. Монотонное преобразование скора не меняет ни AUC, ни NDCG, но теряет 67% выручки в арифметике вида \(P \cdot \text{цена}\).
- LambdaRank — это BPR с весами. Перестановка на позициях (1,2) весит в 31 раз больше, чем на (9,10); BPR обе пары считает одинаковыми.
- Главное ограничение общее для всех трёх. Они оптимизируют прокси при фиксированной политике показа и ничего не знают об айтемах, которых политика не показывала.
1. Три семейства
Классификация лоссов для ранжирования простая, и держать её надо именно в такой формулировке: лоссы отличаются тем, на каком множестве айтемов считается одно слагаемое.
Дальше вся глава — про то, что каждое расширение контекста даёт и что взамен отнимает.
2. Pointwise: релевантность напрямую
Самый прямолинейный подход: игнорируем, что айтемы показывались вместе, и предсказываем поточечный таргет.
Здесь \(y_{ui} \in \{0,1\}\) — метка пары, \(f(u,i)\) — логит модели, \(\sigma\) — сигмоида. Множитель \(y_{ui}\) убивает второе слагаемое, а \((1-y_{ui})\) — первое, поэтому для каждой пары остаётся ровно одно.
| \(f(u,i)\) | \(\sigma(f)\) | штраф при \(y=1\) | штраф при \(y=0\) |
|---|---|---|---|
| −3 | 0.047 | 3.049 | 0.049 |
| 0 | 0.500 | 0.693 | 0.693 |
| +3 | 0.953 | 0.049 | 3.049 |
Уверенная ошибка стоит в шестьдесят раз дороже уверенного попадания. Это и есть весь механизм.
В обычной классификации метка дана: письмо либо спам, либо нет. Здесь \(y_{ui}\) — результат вашего решения, и это самая трудная часть постановки, полностью спрятанная за безобидной формулой.
Пусть \(y = 1\) означает «добавил в корзину», а \(y = 0\) — «показали, но не добавил». Обратите внимание: ноль здесь значит «показали и отверг», а не «взаимодействия не было». Разница принципиальна.
- Айтемы, которые пользователю никогда не показывали, вообще не имеют метки. Они не нули — их просто нет в сумме.
- Если добавить их как нули, получится другая задача, и немедленно встанет вопрос, откуда брать негативы и как править их смещение. Это ровно сюжет сэмплирования негативов и LogQ-коррекции.
То есть за формулой прячутся два решения, которых в ней самой не видно: что считать единицей (клик? корзина? покупка? досмотр?) и какие пары вообще входят в сумму. Первое определяет, что модель оптимизирует; второе — что означает ноль. Оба решения дороже выбора архитектуры.
Бинарность при этом не обязательна: \(y_{ui}\) может быть дробным. С градуированными таргетами кросс-энтропия работает, если привести значения в \([0,1]\), — получается кросс-энтропия с мягкими метками, и это же механизм дистилляции.
Чего pointwise не умеет
- Не видит структуру списка и порядок в частности. Модель одинаково штрафуется за ошибку на позиции 1 и на позиции 50, хотя стоят они совершенно по-разному.
- Не согласован напрямую ни с AUC, ни с NDCG. Оптимизируя логлосс, вы оптимизируете качество вероятностей, а не порядок.
И тем не менее pointwise-головы живут в проде даже там, где итоговое ранжирование делает совсем другой лосс. Причина одна и она весомая.
Возьмём пять товаров с истинной вероятностью покупки и ценой. Вторая модель — то же самое, но логит умножен на два: монотонное преобразование, порядок по скору не меняется вообще.
| Айтем | \(p\) истинное | скор второй модели | цена |
|---|---|---|---|
| A | 0.30 | 0.1552 | 100 |
| B | 0.20 | 0.0588 | 200 |
| C | 0.10 | 0.0122 | 900 |
| D | 0.05 | 0.0028 | 400 |
| E | 0.02 | 0.0004 | 300 |
Порядок по скору у обеих моделей — ABCDE. Значит AUC и NDCG у них в точности совпадают: любая ранжирующая метрика зависит только от порядка.
А теперь ранжируем по ожидаемой выручке \(p \cdot \text{цена}\):
- по калиброванным вероятностям: C (90) > B (40) > A (30) > D (20) > E (6);
- по скорам второй модели: A (16) > B (12) > C (11) > D (1) > E (0).
Наверх встаёт A с ожидаемой выручкой 30 вместо C с ожидаемой выручкой 90 — потеря 67% на верхней позиции. Средний логлосс при этом честно ухудшается на 27%, с 0.3466 до 0.4394: логлосс разницу видит, ранжирующие метрики — нет.
Числа воспроизводятся скриптом _tools/ltr_demo.py в этом репозитории.
Отсюда правило, которое стоит помнить дословно: калиброванный скор нужен всякий раз, когда скор участвует в арифметике — \(P(\text{buy})\cdot\text{price}\), \(pCTR \cdot bid\) в рекламном аукционе, пороги для бизнес-правил. Ранжирующий лосс такой скор не даёт и по устройству дать не может.
Проверять калибровку удобно виджетом калибровки в тренажёре: он рисует, как предсказанная вероятность соотносится с наблюдаемой частотой.
3. Pairwise: BPR
Следующий шаг — перестать говорить модели «это единица, а это ноль» и начать говорить «вот этот выше вот того».
Постулируем, что вероятность «позитив ранжируется выше негатива» моделируется сигмоидой от разности скоров:
$$ P\bigl(i^{+} \succ i^{-} \mid u\bigr) = \sigma\bigl(f(u,i^{+}) - f(u,i^{-})\bigr) $$Правдоподобие всех наблюдаемых предпочтений — произведение этих вероятностей. Берём логарифм, меняем знак:
$$ \mathcal{L}_{\text{BPR}} = -\sum_{i^{+} \in P}\ \sum_{i^{-} \in N} \log \sigma\bigl(f(u,i^{+}) - f(u,i^{-})\bigr) $$Здесь \(P\) и \(N\) — множества позитивов и негативов пользователя, обычно из одного слейта, а двойная сумма перебирает все пары «каждый позитив против каждого негатива».
Заметьте, чего в формуле нет: метки \(y\). Абсолютные значения скоров не участвуют вовсе — только разность \(\Delta = f(u,i^{+}) - f(u,i^{-})\).
Первое: инвариантность к сдвигу. Прибавьте ко всем скорам одного пользователя любую константу — лосс не изменится ни на йоту. Модель свободна в абсолютных значениях, и калибровки у неё нет не «случайно», а по построению.
Второе: согласованность с AUC. AUC — это доля правильно упорядоченных пар «позитив–негатив», то есть \(\mathbb{E}\,\mathbb{1}[\Delta > 0]\). Индикатор недифференцируем, а \(\log\sigma(\Delta)\) — его гладкая верхняя оценка. BPR буквально минимизирует сглаженный \(1 - \text{AUC}\).
Продифференцируем по скору позитива:
$$ \frac{\partial \mathcal{L}}{\partial f(u,i^{+})} = -\sigma(-\Delta) $$Вес пары в градиенте — это \(\sigma(-\Delta)\), то есть функция уже достигнутого отступа:
| \(\Delta\) | вес | что это за пара |
|---|---|---|
| −3 | 0.9526 | перепутана, и сильно |
| −1 | 0.7311 | перепутана |
| 0 | 0.5000 | на границе |
| +1 | 0.2689 | упорядочена |
| +3 | 0.0474 | уверенно упорядочена |
| +5 | 0.0067 | практически выключена |
Перепутанная пара весит в 20 раз больше уже разведённой. Никакого явного майнинга хард-негативов писать не нужно — он встроен в форму лосса. Это то же самое свойство, что у софтмакса в главе 7, и по той же причине: производная логистической функции мала на насыщении.
Числа воспроизводятся скриптом _tools/ltr_demo.py.
Не даёт калибровки — см. инвариантность к сдвигу. Подставлять выход BPR в \(P(\text{buy})\cdot\text{price}\) бессмысленно: это не вероятность, а число с произвольным нулём.
Не различает позиции. Пара «первое место против второго» и пара «пятисотое против пятьсот первого» входят в сумму с одинаковым весом, хотя первая решает всё, а вторая не решает ничего. Именно эту дыру закрывает следующий раздел.
Большинство попарных лоссов — надстройки над BPR: перевзвешивания и более хитрый сэмплинг пар. Концептуально BPR совпадает с RankNet из мира поисковых систем.
4. LambdaRank: мостик от пар к метрике
Идея: раз метрику напрямую оптимизировать нельзя, подберём лосс так, чтобы градиенты были пропорциональны изменению метрики от перестановки этой пары.
Обозначения: \(f_i\) и \(f_j\) — скоры двух айтемов одного запроса; \(s_{ij} \in \{+1,-1\}\) — знак правильного порядка, нужный, чтобы одна формула работала для пары в любом порядке; \(\Delta\mathrm{Metric}_{ij}\) — насколько изменится метрика, если поменять эти два айтема местами (обычно \(|\Delta\mathrm{NDCG}|\)).
Второй множитель — ровно логистическая функция потерь на отступе, то есть тот же BPR. Всё отличие спрятано в первом множителе.
Список из десяти документов, ровно один релевантный, \(\mathrm{IDCG} = 1\). Считаем, что происходит с NDCG, когда релевантный документ съезжает на позицию ниже:
| Перестановка | NDCG до | NDCG после | \(\Delta\mathrm{NDCG}\) |
|---|---|---|---|
| 1 ↔ 2 | 1.0000 | 0.6309 | 0.3691 |
| 2 ↔ 3 | 0.6309 | 0.5000 | 0.1309 |
| 5 ↔ 6 | 0.3869 | 0.3562 | 0.0306 |
| 9 ↔ 10 | 0.3010 | 0.2891 | 0.0120 |
Пара (1,2) весит в 31 раз больше пары (9,10) — а для BPR обе пары одинаковы, он видит только знак разности. Вот вся суть LambdaRank в одном числе.
Числа воспроизводятся скриптом _tools/ltr_demo.py.
Хороший вопрос на собеседовании, и правильный ответ неочевиден. Формально лосс попарный — сумма идёт по парам. Но вес \(\Delta\mathrm{NDCG}_{ij}\) считается по всему слейту: чтобы узнать, насколько изменится метрика от перестановки пары, нужно знать позиции всех остальных документов и IDCG запроса.
Значит попарный по форме лосс несёт в себе информацию о структуре всего списка. Граница между семействами проходит не там, где кажется: важно не то, сколько айтемов в одном слагаемом, а сколько айтемов нужно знать, чтобы это слагаемое посчитать.
5. YetiRank: а что если разметка врёт
Метод из Яндекса, выигравший трек трансферного обучения на Yahoo! Learning to Rank Challenge и доступный сегодня в CatBoost. Разбирать его удобно именно здесь, потому что сам лосс у него — тот же попарный:
$$ \mathcal{L} \;=\; -\sum_{(i,j)} w_{ij} \log \frac{e^{x_i}}{e^{x_i} + e^{x_j}} $$Это буквально BPR, где \(x_i\) — скор модели. Всё своеобразие спрятано в весах, и они раскладываются в произведение двух независимых множителей:
$$ w_{ij} \;=\; N_{ij} \cdot c(l_i, l_j) $$Первый отвечает на вопрос «важна ли вообще эта пара», второй — «а точно ли \(i\) лучше \(j\)». Оба интересны, и по-разному.
Множитель \(N_{ij}\): какие пары имеют шанс встретиться наверху
Интуиция: важны не все пары, а только те, что могут оказаться рядом и высоко. Пара «первое место против пятисотого» ничего не решает — она и так упорядочена верно и никогда не перепутается.
Как это выясняют: скоры многократно зашумляют и переранжируют.
$$ \hat{x}_i \;=\; x_i + \log \frac{r_i}{1 - r_i}, \qquad r_i \sim U[0, 1] $$Добавка \(\log \frac{r}{1-r}\) — случайная величина с логистическим распределением, то есть скор «дрожит». После каждого возмущения список пересортировывается, и дальше главное: вес прибавляется только парам, оказавшимся соседними в новом порядке, а прибавка равна \(1/R\), где \(R\) — позиция этого соседства.
Отсюда три следствия, и все три стоит уметь назвать.
- Пары, ни разу не оказавшиеся соседями, получают ровно ноль. Не малый вес, а ноль: они выпадают из обучения полностью.
- Позиционный дисконт встроен через \(1/R\). Соседство на первом и втором месте даёт вклад 1, на сотом и сто первом — 0.01.
- Веса зависят от текущей модели и пересчитываются на каждой итерации бустинга. Пары, которые модель уже уверенно развела, перестают быть соседями при возмущении и постепенно выпадают.
В слейте из \(n\) документов пар \(\binom{n}{2}\), и растёт это квадратично: 45 при \(n=10\), 4950 при \(n=100\), 499 500 при \(n=1000\).
А у YetiRank за одно возмущение соседних пар ровно \(n-1\), то есть 99. При десяти возмущениях по умолчанию ненулевой вес получат не более 990 пар — 20% от 4950, и эта оценка не зависит от расположения скоров: рост линейный по \(n\), а не квадратичный.
На симуляции видно и второе, более тонкое свойство:
| Разброс скоров | Пар с весом | Средняя дистанция по рангу |
|---|---|---|
| 3 (скоры почти неразличимы) | 899 (18.2%) | 30.3 |
| 30 (скоры разведены) | 714 (14.4%) | 7.1 |
Чем увереннее модель развела документы, тем ближе по рангу оставшиеся пары — обучение само стягивается к тем местам списка, где ещё есть настоящая неопределённость.
Числа воспроизводятся скриптом _tools/ltr_demo.py.
Разница тоньше, чем кажется на первый взгляд, и она про отношение к собственной неуверенности.
- LambdaRank взвешивает пару тем, насколько изменится метрика, если её переставить. Причём \(\Delta\mathrm{NDCG}\) считается при текущем детерминированном порядке — то есть метод исходит из того, что модель уже права.
- YetiRank взвешивает пару тем, насколько вероятно, что она вообще окажется рядом и высоко. Возмущение скоров — это явное признание, что близкие скоры почти неразличимы и при малейшем шуме порядок между ними перевернётся.
Множитель \(c(l_i, l_j)\): модель ошибок разметки
Обычный попарный подход берёт \(c(l_i, l_j) = l_i - l_j\) и оставляет пары с положительной разностью: разметка объявляется истиной. YetiRank делает своё главное допущение и от этого отказывается.
Здесь \(p(u \mid l)\) — матрица ошибок разметки: вероятность того, что истинная метка \(u\) была записана асессором как \(l\). Вся сумма — вероятность того, что документ \(i\) на самом деле лучше документа \(j\), с учётом того, что обе метки могли быть проставлены неточно.
Возьмём пару с метками 3 и 2 при пятибалльной шкале. Классический подход скажет: разность 1, пара валидная, учись. YetiRank скажет: соседние градации асессоры путают сплошь и рядом, так что вероятность настоящего превосходства невелика, и вес пары надо срезать. А пара с метками 4 и 0 останется с весом около единицы: перепутать крайние градации трудно.
Эффект: обучение перестаёт тратиться на пары, различающиеся только шумом разметки. В оригинальной работе показано, что именно моделирование этой неопределённости дало основной прирост над LambdaRank.
В CatBoost у YetiRank есть параметр decay со значением по умолчанию 0.85 — вероятность того, что пользователь посмотрит следующую позицию. Это геометрическая модель просмотра из метрики pFound, которой в Яндексе меряли поиск. Тот же приём, что дисконт \(1/\log_2(i+1)\) в NDCG, но модель пользователя другая:
| Позиция | \(1/\log_2(1+i)\) — NDCG | \(0.85^{\,i-1}\) — pFound |
|---|---|---|
| 1 | 1.0000 | 1.0000 |
| 2 | 0.6309 | 0.8500 |
| 3 | 0.5000 | 0.7225 |
| 5 | 0.3869 | 0.5220 |
| 10 | 0.2891 | 0.2316 |
| 20 | 0.2277 | 0.0456 |
На двадцатой позиции модели расходятся в 5 раз: NDCG сохраняет там 0.228 от веса первой позиции, геометрическая — 0.046. Доля веса в топ-3 из двадцати: 30.3% против 40.1%.
Числа воспроизводятся скриптом _tools/ltr_demo.py.
Это разные утверждения о пользователе, а не два способа записать одно и то же. Логарифмический дисконт говорит «внимание убывает медленно, хвост всё ещё чего-то стоит»; геометрический — «на каждом шаге четверть аудитории уходит». Выбирая метрику, вы выбираете модель пользователя.
- Нет градуированной релевантности. Весь смысл \(c(l_i,l_j)\) в том, что меток несколько и соседние путаются. На бинарных «кликнул / не кликнул» множитель вырождается, и остаётся взвешенный BPR.
- Метки из логов, а не от асессоров. Клик — не мнение эксперта, он не «перепутан», он смещён иначе: позицией, показом, кликбейтом. Матрица ошибок разметки такой шум не описывает; здесь работают поправки на смещения, а не модель ошибок асессора. Это самая частая ошибка применения.
- Нужна калибровка. Как всякий попарный лосс, YetiRank зависит только от разностей скоров.
6. Listwise: softmax-over-slate
Последнее семейство учится сразу правильно располагать весь слейт. Самый простой и потому самый популярный вариант — софтмакс по слейту.
Здесь \(S\) — слейт, то есть множество айтемов, показанных вместе за один раз; сумма в знаменателе идёт по нему. \(y_i\) — метка айтема внутри слейта: в простейшем случае единица у выбранного и ноль у остальных, и тогда лосс сводится к \(-\log P(\text{выбранный} \mid S)\).
Это не вероятность клика. Софтмакс нормирован внутри слейта, и сумма по слейту всегда равна единице — что бы в слейте ни лежало.
Слейт из четырёх айтемов со скорами 2.0, 1.5, 1.0, 0.5:
| Слейт | A | B | C | D | E |
|---|---|---|---|---|---|
| из четырёх | 0.4551 | 0.2760 | 0.1674 | 0.1015 | — |
| добавили E со скором 3.0 | 0.2034 | 0.1234 | 0.0748 | 0.0454 | 0.5530 |
Скор айтема A не изменился ни на йоту — изменилось только окружение. А его «вероятность» упала на 55%, с 0.4551 до 0.2034.
Числа воспроизводятся скриптом _tools/ltr_demo.py.
Отсюда следствие, которое звучит парадоксально, но верно: listwise-выход не калиброван даже сильнее, чем pairwise. У BPR скор хотя бы не зависит от того, что лежит рядом; здесь зависит напрямую.
Формула буквально та же, что у sampled softmax из главы 7. Отличие одно, и оно принципиальное: откуда взялось множество в знаменателе.
- В кандидатогенерации знаменатель — сэмплированные негативы, и раз мы их сэмплировали, мы знаем их распределение и можем поправить смещение (LogQ).
- В ранжировании знаменатель — показанный слейт, то есть результат работы логирующей политики. Его распределение нам не подконтрольно, и поправлять его надо совсем другими средствами.
Это то же различие, что между негативами из показов и негативами из каталога, только теперь оно проявляется в знаменателе софтмакса.
7. Что из этого берут в прод
На собеседовании после разбора трёх семейств естественно спрашивают: «а что выбрать?» Правильный ответ — что в проде обычно живут несколько лоссов одновременно, и вот почему.
| Семейство | Моделирует | Даёт | Не даёт |
|---|---|---|---|
| Pointwise | саму релевантность | калиброванные вероятности | порядок, структуру слейта |
| Pairwise | наблюдаемый порядок | согласованность с AUC, майнинг хард-негативов даром | калибровку, различение позиций |
| Listwise | структуру слейта | близость к NDCG | калибровку; дороже и капризнее в обучении |
Типичная конструкция: многоголовая модель, где pointwise-головы дают калиброванные вероятности отдельных событий (клик, покупка, досмотр), а итоговый порядок собирается из них взвешенной комбинацией или отдельным ранжирующим лоссом сверху. Калибровка нужна не ради красоты — на ней держатся аукцион, бизнес-правила и любая арифметика с деньгами.
И самое важное, что стоит сказать в конце ответа. Все три семейства оптимизируют прокси при фиксированной политике показа.
Никакой лосс не расскажет модели про айтемы, которые политика никогда не показывала: их нет ни в поточечной сумме, ни в парах, ни в знаменателе софтмакса. Разорвать этот круг выбором лосса нельзя — надо влиять на саму политику, и это уже сюжет exploration и бандитов.
Вопросы с собеседований
Чем pointwise, pairwise и listwise отличаются по смыслу?
Множеством, на котором считается одно слагаемое лосса, и отсюда всё остальное.
Pointwise моделирует саму релевантность (BCE на 0/1) — даёт калиброванные вероятности, но не знает ни про порядок, ни про структуру слейта: ошибка на позиции 1 и на позиции 50 штрафуется одинаково.
Pairwise моделирует наблюдаемый порядок — согласован с AUC, потому что AUC и есть доля правильно упорядоченных пар, но калибровку теряет по построению.
Listwise моделирует структуру слейта — ближе всего к NDCG, дороже в обучении и калиброван ещё хуже.
Выведите BPR.
Постулируем \(P(i^+ \succ i^- \mid u) = \sigma(f(u,i^+) - f(u,i^-))\). Правдоподобие всех наблюдаемых предпочтений — произведение таких вероятностей; логарифмируем, меняем знак:
\(\mathcal{L}_{\mathrm{BPR}} = -\sum_{i^+ \in P}\sum_{i^- \in N} \log \sigma\bigl(f(u,i^+)-f(u,i^-)\bigr)\)
Два свойства, которые надо назвать сразу. Лосс зависит только от разности скоров — значит инвариантен к сдвигу и калибровки не даёт. И градиент по скору позитива равен \(-\sigma(-\Delta)\): перепутанная на 3 пара весит 0.95, уже разведённая на 3 — 0.047, то есть в 20 раз меньше. Майнинг трудных пар встроен в форму лосса.
Почему AUC и NDCG не видят калибровки, и когда это больно?
Обе метрики зависят только от порядка, а любое монотонное преобразование скора порядок сохраняет. Значит калиброванная модель и её же скор, пропущенный через монотонную функцию, неотличимы по AUC и NDCG.
Больно это становится ровно тогда, когда скор участвует в арифметике. Пример: пять товаров, ранжирование по скору у обеих моделей одинаковое, а ранжирование по ожидаемой выручке \(p \cdot \text{цена}\) — разное; наверх встаёт товар с ожидаемой выручкой 30 вместо 90, потеря 67% на верхней позиции. Логлосс при этом ухудшается на 27% — он разницу видит.
Отсюда практика: \(pCTR \cdot bid\) в аукционе, \(P(\text{buy})\cdot\text{price}\), пороги для бизнес-правил — везде нужен pointwise-выход, даже если итоговый порядок делает другой лосс.
Что такое LambdaRank и почему его считают listwise-лоссом?
Это pairwise-лосс, в котором каждая пара взвешена изменением метрики от её перестановки: \(\mathcal{L} = \sum_{(i,j)} \Delta\mathrm{NDCG}_{ij}\log(1+\exp(-s_{ij}(f_i-f_j)))\). Второй множитель — тот же BPR, всё своеобразие в первом.
Зачем: NDCG кусочно-постоянна и недифференцируема, напрямую её не оптимизировать, но градиенты можно взвесить вкладом пары в метрику. Разброс огромный — перестановка на позициях (1,2) даёт ΔNDCG 0.3691, на (9,10) — 0.0120, то есть в 31 раз меньше.
А listwise он потому, что ΔNDCG считается по всему слейту: нужны позиции всех остальных документов и IDCG запроса. Формально попарный лосс несёт информацию о структуре всего списка.
Как устроен YetiRank и чем он отличается от LambdaRank?
Сам лосс — попарный, тот же BPR. Всё в весах \(w_{ij} = N_{ij}\cdot c(l_i,l_j)\).
\(N_{ij}\): скоры многократно зашумляют логистическим шумом и пересортировывают; вес получают только пары, оказавшиеся соседними, с прибавкой \(1/R\) по позиции соседства. Отсюда — позиционный дисконт встроен, матрица весов разрежена (не более 990 пар из 4950 при 100 документах и 10 возмущениях, то есть линейно по n вместо квадратично), а веса пересчитываются на каждой итерации бустинга.
\(c(l_i,l_j)\): вероятность, что \(i\) действительно лучше \(j\), с учётом матрицы ошибок разметки. Пара «3 против 2» получает срезанный вес, пара «4 против 0» — почти единичный.
Отличие от LambdaRank: тот взвешивает пару тем, насколько изменится метрика при перестановке, исходя из того, что текущий порядок верен. YetiRank взвешивает тем, насколько вероятно, что пара вообще окажется рядом и высоко, — то есть явно моделирует собственную неуверенность.
Когда YetiRank применять не стоит?
Три случая. Первый — бинарные метки: множитель \(c(l_i,l_j)\) вырождается, остаётся просто взвешенный BPR. Второй — метки из логов, а не от асессоров: клик не «перепутан», он смещён позицией и показом, и матрица ошибок разметки такой шум не описывает; нужны поправки на смещения. Третий — когда нужна калибровка: как всякий попарный лосс, он зависит только от разностей скоров.
Второй случай — самая частая ошибка применения: метод берут в рекомендации по аналогии с поиском, где разметка действительно асессорская.
Чем listwise-софтмакс отличается от sampled softmax в кандидатогенерации?
Формула одна и та же. Отличие в том, откуда взялось множество в знаменателе, и оно принципиальное.
В кандидатогенерации знаменатель — сэмплированные негативы: мы сами задали распределение, значит знаем его и можем поправить смещение LogQ-коррекцией. В ранжировании знаменатель — показанный слейт, то есть результат логирующей политики; её распределение нам не подконтрольно.
Плюс listwise-выход не калиброван особенно сильно: добавьте в слейт из четырёх айтемов один сильный, и «вероятность» первого упадёт с 0.4551 до 0.2034 — на 55%, хотя сам айтем не изменился.
Какое ограничение есть у всех трёх семейств сразу?
Все они оптимизируют прокси при фиксированной политике показа. Айтемов, которые политика никогда не показывала, нет ни в поточечной сумме, ни в парах, ни в знаменателе софтмакса — никакой лосс о них модели не расскажет.
Это и есть петля обратной связи: модель учится на том, что показала предыдущая модель. Выбором лосса круг не разорвать — надо влиять на саму политику показа, то есть заниматься exploration.
Шпаргалка одним экраном
Классификация
Отличаются множеством, на котором считается слагаемое: айтем, пара, слейт.
Pointwise
BCE. Калибровка есть, порядка нет. Ноль означает «показали и отверг», а не «не было».
BPR
\(-\sum\log\sigma(\Delta)\). Из ММП, согласован с AUC, инвариантен к сдвигу → калибровки нет.
Градиент BPR
Вес пары \(\sigma(-\Delta)\): 0.95 при −3 против 0.047 при +3. Хард-негативы даром.
LambdaRank
BPR с весами ΔNDCG. Пара (1,2) весит в 31 раз больше (9,10). Формально pairwise, по сути listwise.
YetiRank
\(w_{ij}=N_{ij}c(l_i,l_j)\): возмущения дают разрежённость и дисконт, матрица ошибок — недоверие к разметке.
Listwise
Софтмакс по слейту. Нормирован внутри — добавили сильный айтем, «вероятность» A упала на 55%.
Общее ограничение
Все три — прокси при фиксированной политике. Про непоказанное не знает ни один.
Первоисточники
- S. Rendle, C. Freudenthaler, Z. Gantner, L. Schmidt-Thieme. BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI 2009.
- C. Burges. From RankNet to LambdaRank to LambdaMART: An Overview, MSR-TR-2010-82 — вся линия попарных лоссов от одного из авторов.
- A. Gulin, I. Kuralenok, D. Pavlov. Winning the Transfer Learning Track of Yahoo!'s Learning to Rank Challenge with YetiRank, JMLR W&CP 14, 2011.
- Z. Cao, T. Qin, T.-Y. Liu et al. Learning to Rank: From Pairwise Approach to Listwise Approach, ICML 2007 — ListNet, откуда пошло listwise-семейство.
- S. Bruch, X. Wang, M. Bendersky, M. Najork. An Analysis of the Softmax Cross Entropy Loss for Learning-to-Rank with Binary Relevance, ICTIR 2019 — почему софтмакс-лосс связан с NDCG.
- Документация CatBoost по ранжирующим функциям потерь — параметры
mode,decay,permutations,top. - Числа главы:
_tools/ltr_demo.pyв этом репозитории.