Как посчитать NDCG в SQL

Зачем NDCG

NDCG (Normalized Discounted Cumulative Gain) — стандарт для оценки качества ранжирования. Используют в поиске, рекомендациях, фидах. В отличие от precision@k или recall@k, NDCG учитывает позицию: релевантный документ на 1-м месте ценнее, чем на 10-м, плюс работает с градированной релевантностью (0/1/2/3), а не только бинарной.

DCG и IDCG

DCG (Discounted Cumulative Gain) — сумма релевантности с log-дисконтом по позиции:

DCG@k = Σ (2^rel_i − 1) / log2(i + 1), для i от 1 до k

IDCG (Ideal DCG) — DCG идеального ранжирования (все самые релевантные сверху).

NDCG = DCG / IDCG, нормировано в [0, 1].

NDCG@k в SQL

Данные: для каждого query_id есть список doc_id с predicted_rank (от модели) и relevance (ground truth).

WITH ranked AS (
    SELECT
        query_id,
        doc_id,
        relevance,
        ROW_NUMBER() OVER (PARTITION BY query_id ORDER BY predicted_rank) AS pos,
        ROW_NUMBER() OVER (PARTITION BY query_id ORDER BY relevance DESC) AS ideal_pos
    FROM ranking_results
    WHERE query_id = 'q_42'
),
dcg AS (
    SELECT
        query_id,
        SUM((POWER(2, relevance) - 1) / LOG(2, pos + 1)) AS dcg
    FROM ranked
    WHERE pos <= 10
    GROUP BY query_id
),
idcg AS (
    SELECT
        query_id,
        SUM((POWER(2, relevance) - 1) / LOG(2, ideal_pos + 1)) AS idcg
    FROM ranked
    WHERE ideal_pos <= 10
    GROUP BY query_id
)
SELECT
    d.query_id,
    d.dcg,
    i.idcg,
    d.dcg / NULLIF(i.idcg, 0) AS ndcg_at_10
FROM dcg d
JOIN idcg i USING (query_id);

Средний NDCG по запросам

Для оценки модели усредняют NDCG по всем запросам:

WITH ranked AS (
    SELECT
        query_id,
        relevance,
        ROW_NUMBER() OVER (PARTITION BY query_id ORDER BY predicted_rank) AS pos,
        ROW_NUMBER() OVER (PARTITION BY query_id ORDER BY relevance DESC) AS ideal_pos
    FROM ranking_results
),
per_query AS (
    SELECT
        query_id,
        SUM(CASE WHEN pos <= 10 THEN (POWER(2, relevance) - 1) / LOG(2, pos + 1) ELSE 0 END) AS dcg,
        SUM(CASE WHEN ideal_pos <= 10 THEN (POWER(2, relevance) - 1) / LOG(2, ideal_pos + 1) ELSE 0 END) AS idcg
    FROM ranked
    GROUP BY query_id
)
SELECT
    AVG(dcg / NULLIF(idcg, 0)) AS mean_ndcg_at_10,
    COUNT(*) AS queries_evaluated
FROM per_query
WHERE idcg > 0;

idcg > 0 отсекает запросы без релевантных документов вообще — иначе делили бы на 0.

Сравнение моделей

WITH ndcg_per_model AS (
    SELECT
        model,
        query_id,
        SUM(CASE WHEN pos <= 10 THEN (POWER(2, relevance) - 1) / LOG(2, pos + 1) ELSE 0 END)
        / NULLIF(SUM(CASE WHEN ideal_pos <= 10 THEN (POWER(2, relevance) - 1) / LOG(2, ideal_pos + 1) ELSE 0 END), 0)
        AS ndcg
    FROM (
        SELECT
            model, query_id, relevance,
            ROW_NUMBER() OVER (PARTITION BY model, query_id ORDER BY predicted_rank) AS pos,
            ROW_NUMBER() OVER (PARTITION BY model, query_id ORDER BY relevance DESC) AS ideal_pos
        FROM model_predictions
    ) r
    GROUP BY model, query_id
)
SELECT
    model,
    AVG(ndcg) AS mean_ndcg,
    STDDEV(ndcg) / SQRT(COUNT(*)) AS sem
FROM ndcg_per_model
WHERE ndcg IS NOT NULL
GROUP BY model
ORDER BY mean_ndcg DESC;

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

Ошибка 1. Деление на 0 при пустом IDCG. Если у запроса нет релевантных документов, IDCG = 0. Фильтровать idcg > 0 или вернуть NULL — иначе SQL выдаст division by zero.

Ошибка 2. Бинарная релевантность вместо градированной. POWER(2, relevance) - 1 для бинарной даёт 0 или 1 — теряете преимущество перед обычным precision@k. Если данные бинарные, NDCG = MRR-подобная метрика.

Ошибка 3. Не тот логарифм. Стандарт — log2. В Postgres это LOG(2, x). В MySQL — LOG2(x). Перепутаете на ln — формула остаётся в [0,1], но не сравнима с публикациями.

Ошибка 4. NDCG@k без явного k. Указывайте @5, @10, @20 в названии метрики. @5 и @100 дают разные числа на одних и тех же предсказаниях.

Ошибка 5. IDCG из тех же документов, что отранжировала модель. IDCG считают по идеальному порядку всех существующих релевантных, а не только тех, что вернула модель.

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

• Как посчитать precision-recall в SQL
• Как посчитать AUC-ROC в SQL
• Как посчитать F1-score в SQL
• Ranking-метрики NDCG на собесе DS

FAQ

Чем NDCG лучше precision@k?

Учитывает позицию: релевантный на 1-м месте даёт больший gain, чем на 10-м. Плюс градированная релевантность 0/1/2/3.

Какой k выбрать?

@5 — для веб-поиска, @10 — для рекомендаций ленты, @20-50 — для long-tail recsys.

NDCG vs MAP?

MAP — для бинарной релевантности. NDCG — для градированной. На бинарных данных они близки.

Что считать релевантным?

В offline-оценке — судьи или прошлые клики/покупки. В online — CTR/conversion на позицию.

Range NDCG?

[0, 1]. 1 = идеальное ранжирование. На практике у production-моделей 0.7–0.9 в зависимости от домена.