Информационный поиск
Learning to Rank
2010 год, Yahoo! Learning to Rank Challenge: 473 участника борются за $30,000 приза. Задача - ранжировать документы по 700 features. Победитель - LambdaMART с NDCG@5 = 0.798. Второе место - отрыв 0.003. Алгоритм из Microsoft Research немедленно внедряется в Bing и Yahoo! Search. Это момент, когда Machine Learning окончательно вытеснил hand-tuned формулы из ядра production поиска.
- **Yandex**: MatrixNet (аналог LambdaMART) с тысячами features - основа ранжирования с 2009 года
- **LinkedIn**: Gradient Boosted Trees для job recommendation ранжирования - 30% рост CTR vs предыдущей модели
- **Airbnb**: LambdaMART для ранжирования листингов по запросу - оптимизация booking conversion rate
Крис Бёрджес (2005)
В 2005 году Крис Бёрджес из Microsoft Research опубликовал 'Learning to Rank using Gradient Descent' - статью о RankNet, первом успешном нейросетевом подходе к Learning to Rank. Нейросеть обучалась предсказывать попарные предпочтения через sigmoid cross-entropy. В 2006 Бёрджес добавил ключевую идею LambdaRank: вместо реального gradient использовать 'lambda' - scaled gradient, где масштаб = |ΔNDCG|. Наконец, в 2010 LambdaMART объединил lambda gradients с GBDT. Вся линия работ прошла путь от академического любопытства до стандарта индустрии за 5 лет. LambdaMART и его производные (XGBoost LambdaRank, LightGBM LambdaRank) стали стандартным baseline для всех production search и recommendation систем
Pointwise: ранжирование как регрессия
Pointwise подход рассматривает ранжирование как задачу регрессии или классификации для каждого документа независимо. Для запроса q и документа d предсказывается скалярная relevance score. Документы сортируются по убыванию предсказанного score. Проблема: модель не видит других документов при обучении - нет информации о их относительном порядке.
Метрики оценки ranking: **NDCG@k** (Normalized Discounted Cumulative Gain) - взвешивает relevance по позиции, **MAP** (Mean Average Precision) - для бинарных меток, **MRR** (Mean Reciprocal Rank) - позиция первого релевантного. Pointwise оптимизирует MSE, не NDCG - отсюда несоответствие между loss и реальной метрикой.
Почему pointwise подход к Learning to Rank показывает худшие NDCG результаты по сравнению с pairwise/listwise?
Pairwise: ранжирование как сравнение пар
Pairwise подход обучает модель предсказывать относительный порядок пар документов: P(doc_i > doc_j | query). Для каждого запроса генерируются пары (doc_i, doc_j), где i более релевантен. Классический алгоритм - **RankNet** (Burges, 2005): нейросеть с cross-entropy loss на парах.
Число пар растёт квадратично: для 100 документов в списке - до 4950 пар. Для промышленных поисковых движков с тысячами документов на запрос это неприемлемо. Решение: sampling пар или переход к listwise методам.
В чём основная проблема масштабирования pairwise Learning to Rank на большие document lists?
Listwise: прямая оптимизация NDCG
Listwise подходы оптимизируют весь список сразу. **ListNet** (Cao et al., 2007) минимизирует KL-дивергенцию между предсказанным и идеальным распределением вероятностей top-1 документа. **ListMLE** оптимизирует log-likelihood правильного ранжирования. Оба метода напрямую работают с метриками списка, не парами.
Listwise подходы теоретически превосходят pointwise и pairwise, но на практике разница небольшая. LambdaMART - hybrid: использует pairwise lambda gradients для прямой оптимизации NDCG, что даёт лучшее из обоих миров.
Какое ключевое преимущество listwise методов перед pointwise и pairwise?
LambdaMART: GBDT для ранжирования
LambdaMART (Burges, 2010) - наиболее эффективный LtR алгоритм для традиционных feature-based систем. Объединяет MART (Multiple Additive Regression Trees, т.е. GBDT) с **lambda градиентами**. Lambda градиент для пары (i, j) учитывает ΔNDCG от перестановки документов: |ΔNDCG| * (pairwise RankNet gradient). Итог: оптимизируется NDCG через эффективный GBDT framework.
LambdaMART выиграл Yahoo! Learning to Rank Challenge 2010. Используется в Bing, Yahoo!, Yandex как baseline и часто как production модель. **lambdarank_truncation_level** критически важен: учёт только топ-K позиций при вычислении ΔNDCG ускоряет обучение и фокусирует модель на релевантных позициях.
Нейросетевые LtR модели всегда превосходят LambdaMART на production поисковых системах
LambdaMART часто конкурентоспособен или превосходит нейросетевые модели при правильно инженеренных features, особенно при ограниченных тренировочных данных
Нейросети требуют большие объёмы данных для обобщения; LambdaMART эффективнее с tabular features и меньшими датасетами
Как LambdaMART объединяет pairwise и listwise подходы?
Ключевые идеи
- **Pointwise**: регрессия relevance score независимо для каждого документа - прост, но не оптимизирует порядок
- **Pairwise** (RankNet): предсказание порядка пар документов - ближе к задаче, но O(n²) пар на запрос
- **Listwise** (ListNet, ApproxNDCG): оптимизирует метрики всего списка напрямую
- **LambdaMART**: GBDT с lambda градиентами = pairwise механизм + listwise метрика, industry standard
Вопросы для размышления
- Почему lambda gradient умножается на |ΔNDCG|, а не просто использует RankNet gradient - что это даёт модели?
- Как position bias в click data влияет на качество LtR модели и как IPS correction решает эту проблему?
- В каких условиях нейросетевой LtR (DSSM, Neural Ranking) превзойдёт LambdaMART в production search?