NDCG, MAP и почему ranking-метрики не оптимизируют напрямую
Чем NDCG отличается от MAP и почему такие метрики сложно напрямую оптимизировать градиентным спуском?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
NDCG учитывает позицию и graded relevance через discounted gain, MAP усредняет precision на позициях релевантных документов. Прямая оптимизация трудна, потому что сортировка дискретна; обычно используют surrogate loss.
Полный разбор
MAP удобен, когда релевантность бинарная: для каждого релевантного документа считается precision на его позиции, затем значения усредняются. NDCG богаче: он учитывает graded relevance, например оценку 0/1/2/3, и дисконтирует вклад по позиции. Поэтому ошибка в верхней части выдачи стоит дороже, чем такая же ошибка внизу.
Проблема прямой оптимизации в том, что метрика зависит от порядка после сортировки. Сама операция сортировки дискретна: маленькое изменение score может не менять порядок вообще, а потом резко поменять соседние элементы. Обычный backprop через такую метрику не работает.
На практике используют surrogate losses: pointwise classification/regression, pairwise loss на парах pos-neg, listwise подходы и LambdaRank/LambdaMART, где градиенты приближенно взвешиваются ожидаемым изменением NDCG.
Теория
Ranking-модель обычно обучается на дифференцируемой proxy-цели, а NDCG/MAP используются как offline evaluation.
Типичные ошибки
- Считать NDCG просто precision с другим названием.
- Игнорировать graded relevance.
- Пытаться напрямую backprop-ить через обычную сортировку.