Ranking-метрики NDCG, MAP, MRR на собеседовании Data Scientist

Зачем разбирать на собесе

Ranking — рекомендации, поиск, лента, фрод-скоринг. Метрики ranking — другие, чем у классификации. На собесе DS: «формула NDCG», «MRR vs MAP», «Hit@10 для recsys». Senior — graded relevance, normalization, position bias.

Главная боль без понимания — DS отчитывается AUC=0.95, но в проде юзер не находит товар на первой странице. AUC не учитывает порядок в топ-K.

Hit@K и Recall@K

Hit@K. 1 если хоть один релевантный объект попал в топ-K, иначе 0. На датасете — доля запросов с попаданием.

Recall@K. Какая доля релевантных объектов попала в топ-K.

Релевантные: {item_5, item_7, item_12}
Топ-5 рекомендаций: [item_3, item_5, item_8, item_9, item_2]

Hit@5 = 1 (item_5 в топ-5)
Recall@5 = 1/3 (попал 1 из 3 релевантных)

Применение:

• Recsys для длинных лент — Hit@10 (видит ли юзер хоть что-то полезное).
• Поиск с одним правильным ответом — Hit@1, MRR.
• Когда релевантных много — Recall@K показывает охват.

MRR — Mean Reciprocal Rank

Средняя обратная позиция первого релевантного объекта в выдаче.

RR(query) = 1 / rank(first relevant)
MRR = mean(RR) по всем queries

Query 1: топ = [A, B*, C, D]    → first relevant = B на позиции 2 → RR = 1/2
Query 2: топ = [E, F, G*, H]    → first relevant = G на позиции 3 → RR = 1/3
Query 3: топ = [I, J, K, L]     → нет релевантных                  → RR = 0

MRR = (1/2 + 1/3 + 0) / 3 ≈ 0.278

Применение:

• Поиск с одним правильным ответом (factual QA, autocomplete).
• KB-пополнение, link prediction.
• «Один правильный товар» в e-commerce.

Слабое место: не учитывает остальных релевантных за пределами первого.

MAP — Mean Average Precision

Average Precision (AP) для одного query:

AP = Σ_k=1..K (precision@k · rel(k)) / |total relevant|

rel(k) = 1 если k-й результат релевантен, иначе 0.

Геометрически — площадь под precision-recall кривой для query.

MAP = mean AP по всем queries.

Query: топ = [item1*, item2, item3*, item4, item5*]   (* = релевантно, всего 3 релевантных)

precision@1 = 1/1 = 1.0  (item1 релевантен)
precision@3 = 2/3 ≈ 0.67 (2 релевантных из 3)
precision@5 = 3/5 = 0.6  (3 релевантных из 5)

AP = (1·1 + 0.67·1 + 0.6·1) / 3 ≈ 0.756

Применение:

• Многоэлементный поиск (Google search).
• Recsys с множественной релевантностью.
• Object detection (mAP — mean Average Precision over classes).

Свойства:

• Учитывает все релевантные объекты.
• Награждает раннюю позицию релевантных (precision@k уменьшается с k).
• Работает с binary relevance (релевантно / нет).

NDCG — Normalized DCG

DCG (Discounted Cumulative Gain). Поддерживает graded relevance (релевантность не binary, а 0-5 или float).

DCG@K = Σ_k=1..K (2^rel_k - 1) / log₂(k+1)

rel_k — релевантность объекта на позиции k (например, 0=не релевантно, 1=частично, 2=полностью).

Топ-3:    [рейтинг 3, рейтинг 1, рейтинг 2]

DCG = (2^3 - 1)/log₂(2) + (2^1 - 1)/log₂(3) + (2^2 - 1)/log₂(4)
    = 7/1 + 1/1.585 + 3/2
    ≈ 7 + 0.631 + 1.5
    ≈ 9.13

IDCG (Ideal DCG). DCG при идеальной сортировке (релевантные сначала).

Ideal: [3, 2, 1]
IDCG = 7/1 + 3/1.585 + 1/2 ≈ 7 + 1.893 + 0.5 ≈ 9.39

NDCG = DCG / IDCG. Нормализованный, ∈ [0, 1].

NDCG = 9.13 / 9.39 ≈ 0.972

Свойства:

• Учитывает позицию (log discount).
• Поддерживает graded relevance.
• Нормализован — сравним между запросами.

В индустрии — главная метрика для ranking. Учиться через learning-to-rank (LambdaMART, listwise losses).

Когда что выбирать

Hit@K:

• Простой baseline.
• Лента / feed для пользователя.

MRR:

• Один правильный ответ (search, autocomplete).
• Question Answering.

MAP:

• Множественная binary релевантность.
• Object detection (mAP).
• Information retrieval (классические задачи).

NDCG:

• Graded relevance (рейтинг 1-5).
• E-commerce search.
• Большинство современных recsys.

Precision@K, Recall@K:

• Когда K — операционный capacity (например, можно показать 10 товаров).
• В сочетании с другими.

Бизнес-метрики поверх

Технические ranking-метрики не всё. Бизнес обычно смотрит:

• CTR (click-through rate) — кликают ли на результаты.
• Conversion — покупают ли после клика.
• Revenue per query / per session.
• Diversity / Serendipity — разнообразие выдачи (anti-filter-bubble).
• Coverage — какая доля каталога вообще когда-либо показывается.
• Engagement metrics — время на сайте, retention.

Технические метрики (NDCG) валидируются через A/B тесты на бизнес-метриках.

Частые ошибки

Считать Hit@K на одном пользователе. Hit@K — статистика по multiple queries. На одном — это просто 0/1.

Сравнивать NDCG между разными запросами без normalization. NDCG нормализован, MAP и MRR — нет. Сравнения требуют осторожности.

Использовать AUC для ranking task. AUC оценивает score-based бинарную классификацию, не учитывает порядок в топ-K. На сильно skewed выдачах (top-K важно) — слабая метрика.

Считать precision@K без cap. Если релевантных меньше K — precision@K не может быть 1.

Игнорировать tie-breaking. Если два объекта имеют одинаковый score — порядок не определён, метрики могут плавать. Стабильная сортировка + tie-breaker (часто timestamp).

Учитывать только positive interactions. Implicit feedback: clicks ≠ relevance, position bias реален. Для честной оценки — counterfactual evaluation, IPS, etc.

Усреднение метрик с разной важностью queries. Все queries одинаково усредняются. Если 10% запросов дают 90% дохода — взвешивай.

Тестировать только offline. Оффлайн NDCG может улучшиться, а CTR в прод — упасть. A/B обязательно.

Связанные темы

• Loss функции на собесе DS
• ROC-AUC vs PR-AUC на собесе DS
• Class imbalance на собесе DS
• Embeddings на собесе DS
• Подготовка к собесу Data Scientist

FAQ

NDCG для рекомендаций без явного рейтинга?

Используй прокси: bought=2, clicked=1, viewed-skipped=0. Или binary (clicked / not clicked) — тогда NDCG ≈ DCG-style вариант MAP.

Что такое position bias?

Юзеры кликают первый результат чаще не потому, что он лучше, а потому, что он первый. Лечение — IPS-веса (inverse propensity scoring) или counterfactual learning.

Как обработать tie?

При равных score — стабильная сортировка по дополнительному критерию (timestamp, popularity). Иначе метрика прыгает между запусками.

Pairwise vs listwise loss?

Pairwise — RankNet (ошибка на парах a, b). Listwise — LambdaMART, ListNet (ошибка на всём списке). Listwise обычно лучше на NDCG, pairwise — proxima legkij baseline.

Что такое hit@∞?

Hit@∞ = Recall = 1 (все релевантные попадают). По сути граничный случай — обычно K фиксирован (10, 50, 100).

Это официальная информация?

Нет. Статья основана на классических работах Information Retrieval (Manning «IR», Liu «Learning to Rank») и стандартных подходах в ML.

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.