NDCG 归一化折损累计增益
五层读懂一个词。这次拆的是：NDCG (Normalized Discounted Cumulative Gain)--考虑排序位置和分级相关性的综合指标，搜索引擎排序评估的事实标准。
L1 · 一句话点破
NDCG@K = 实际排序的 DCG / 理想排序的 DCG。DCG 把每个位置的相关性按 $1/\log_2(\text{rank}+1)$ 折损累加，NDCG 归一化到 [0, 1]。考虑排序位置（top 重）和分级相关性（高度相关 vs 一般相关），是排序质量评估的金标准。
L2 · 通俗类比
继续用考试比喻，但这次答案有"质量分"：
- 高度相关答案 = 3 分
- 一般相关答案 = 1 分
- 不相关 = 0 分
学生答 5 题（top-5），老师评分：
学生 A 的答案（高度相关排前）：
- 第 1 名：3 分（高度相关）
- 第 2 名：3 分（高度相关）
- 第 3 名：1 分（一般）
- 第 4 名：0 分
- 第 5 名：0 分
学生 B 的答案（高度相关排后）：
- 第 1 名：1 分（一般）
- 第 2 名：0 分
- 第 3 名：3 分（高度相关）
- 第 4 名：3 分（高度相关）
- 第 5 名：0 分
谁更好？ 直觉是 A（高度相关排前）。但简单累加分数都是 7 分，区分不出。
DCG 的做法：位置折损。第 1 名权重 1，第 2 名权重 $1/\log_2 3 \approx 0.63$，第 3 名 $1/\log_2 4 = 0.5$，...
- 学生 A DCG = 3×1 + 3×0.63 + 1×0.5 + 0 + 0 = 5.39
- 学生 B DCG = 1×1 + 0 + 3×0.5 + 3×0.43 + 0 = 3.79
A 的 DCG 高，符合直觉。
NDCG 的做法：除以理想 DCG（高度相关全排前），归一化到 [0, 1]。
- 理想 DCG = 3×1 + 3×0.63 + 1×0.5 + 0 + 0 = 5.39（高度相关排前 2，一般排第 3）
- 学生 A NDCG = 5.39 / 5.39 = 1.0（完美）
- 学生 B NDCG = 3.79 / 5.39 = 0.70
NDCG 综合考虑了位置（top 重）和相关性分级（高度 vs 一般），是排序评估最全面的指标。
L3 · 正经定义
NDCG (Normalized Discounted Cumulative Gain)：
步骤 1：CG (Cumulative Gain)
$$ \text{CG@K} = \sum_{i=1}^{K} \text{rel}_i $$
$\text{rel}_i$ 是位置 $i$ 文档的相关性等级（如 0/1/2/3）。
步骤 2：DCG (Discounted Cumulative Gain)
$$ \text{DCG@K} = \sum_{i=1}^{K} \frac{\text{rel}_i}{\log_2(i+1)} $$
位置折损：第 1 名权重 1，第 $i$ 名权重 $1/\log_2(i+1)$。
变体 DCG（工业常用，强调高相关性）：
$$ \text{DCG@K} = \sum_{i=1}^{K} \frac{2^{\text{rel}_i} - 1}{\log_2(i+1)} $$
$2^{\text{rel}_i} - 1$ 让高相关性（rel=3）贡献远大于低相关性（rel=1）。
步骤 3：IDCG (Ideal DCG)
理想排序（相关性从高到低排列）的 DCG：
$$ \text{IDCG@K} = \sum_{i=1}^{K} \frac{2^{\text{rel}_i^{\text{sorted}}} - 1}{\log_2(i+1)} $$
$\text{rel}^{\text{sorted}}$ 是相关性按降序排列。
步骤 4：NDCG
$$ \text{NDCG@K} = \frac{\text{DCG@K}}{\text{IDCG@K}} $$
归一化到 [0, 1]，1.0 表示完美排序。
多查询平均：
$$ \text{NDCG@K} = \frac{1}{|Q|} \sum_{q \in Q} \text{NDCG@K}(q) $$
伪代码：
import math
def dcg_at_k(relevances, k):
"""relevances: list of relevance scores, 已按检索排序"""
dcg = 0.0
for i, rel in enumerate(relevances[:k], start=1):
dcg += (2 ** rel - 1) / math.log2(i + 1)
return dcg
def ndcg_at_k(retrieved_relevances, k):
"""
retrieved_relevances: list of relevance scores, 按检索排序
"""
dcg = dcg_at_k(retrieved_relevances, k)
idcg = dcg_at_k(sorted(retrieved_relevances, reverse=True), k)
return dcg / idcg if idcg > 0 else 0.0
# 示例
# 检索返回 5 个文档，相关性 [3, 3, 1, 0, 0]（高度相关排前）
relevances = [3, 3, 1, 0, 0]
print(ndcg_at_k(relevances, k=5)) # 1.0（完美排序）
# 相关性 [1, 0, 3, 3, 0]（高度相关排后）
relevances = [1, 0, 3, 3, 0]
print(ndcg_at_k(relevances, k=5)) # ~0.70（高度相关排后，NDCG 低）L4 · 原理深挖
4.1 为什么需要 NDCG
Hit Rate / Recall / Precision 的局限：
- 只考虑"是否相关"（二元）
- 不考虑相关性分级（高度相关 vs 一般相关）
- 不考虑排序位置（top-1 和 top-10 同等对待）
MRR 的局限：
- 只看第一个相关文档
- 不考虑后续排序
- 二元相关性
NDCG 的优势：
- 分级相关性：rel=0/1/2/3，区分高度相关和一般相关
- 位置折损：top 位置权重高，长尾权重低
- 全排序：考虑 top-K 内所有相关文档的位置
- 归一化：跨查询可比
4.2 位置折损函数：为什么用 $1/\log_2(\text{rank}+1)$
折损函数的选择：
| 位置 | $1/\log_2(\text{rank}+1)$ | $1/\text{rank}$ | $1/\text{rank}^2$ |
|---|---|---|---|
| 1 | 1.0 | 1.0 | 1.0 |
| 2 | 0.63 | 0.5 | 0.25 |
| 5 | 0.39 | 0.2 | 0.04 |
| 10 | 0.30 | 0.1 | 0.01 |
$1/\log_2(\text{rank}+1)$ 的特性：
- 衰减适中：top 重但长尾不忽略
- 对数衰减：符合用户注意力衰减（研究表明用户注意力对数衰减）
- 第 1 名和第 2 名差异适中（1.0 vs 0.63）
对比 $1/\text{rank}$（MRR 用）：
- 衰减更快：第 10 名 0.1（vs DCG 的 0.30）
- top 主导更强
对比 $1/\text{rank}^2$：
- 衰减极快：第 10 名 0.01
- 几乎只看 top-3
实践：DCG 的对数折损是经验最优，兼顾 top 重和长尾贡献。
4.3 相关性分级：为什么用 $2^{\text{rel}} - 1$
原始 DCG：直接用 $\text{rel}$（如 0/1/2/3）
变体 DCG：用 $2^{\text{rel}} - 1$
| rel | 原始 | $2^{\text{rel}} - 1$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 3 | 7 |
$2^{\text{rel}} - 1$ 的优势：
- 高相关性贡献指数增长（rel=3 贡献 7，远超 rel=1 的 1）
- 鼓励把高度相关排 top（top 位置高权重 × 高相关性高分）
实践：工业搜索引擎（Google、Bing）用变体 DCG（$2^{\text{rel}} - 1$），学术评估两者都有。
4.4 NDCG 的归一化
为什么要归一化：
- 不同查询的相关文档数量不同
- DCG 绝对值跨查询不可比
- 归一化到 [0, 1] 后跨查询可比
IDCG 的计算：
- 把相关性按降序排列
- 计算 DCG
边界情况：
- 无相关文档：IDCG = 0，NDCG = 0/0，通常记为 0
- 单相关文档：IDCG = DCG（如果排第 1），NDCG = 1.0
4.5 NDCG@K 的 K 选择
K 的选择与场景：
| 场景 | K | 原因 |
|---|---|---|
| 网页搜索 | 10 | 用户看 top-10 |
| 移动搜索 | 5 | 屏幕小 |
| 电商搜索 | 20 | 用户浏览多 |
| RAG | 5~10 | LLM context 限制 |
| 推荐系统 | 10~50 | 用户浏览深度 |
NDCG@10 是搜索引擎最常用，对应用户看首页的体验。
4.6 NDCG 与其他指标的对比
| 指标 | 分级相关 | 位置折损 | 全排序 | 归一化 | 适用 |
|---|---|---|---|---|---|
| Hit Rate@K | 否（二元） | 否 | 否 | 否 | RAG |
| Recall@K | 否 | 否 | 否 | 否 | 召回 |
| Precision@K | 否 | 否 | 否 | 否 | 精确 |
| MRR@K | 否 | 是（1/rank） | 否（只第一） | 否 | 问答 |
| MAP | 否 | 是（隐式） | 是 | 否 | 多相关 |
| NDCG@K | 是 | 是 | 是 | 是 | 综合排序 |
NDCG 是最全面的指标：分级 + 位置 + 全排序 + 归一化。
4.7 NDCG 的局限
局限 1：依赖相关性分级标注。
需要人工标注分级相关性（0/1/2/3），成本高。二元标注时 NDCG 退化为类似 DCG。
局限 2：对标注噪声敏感。
分级标注主观，不同标注者可能给不同等级。需多标注者投票。
局限 3：IDCG 计算需所有相关文档。
如果只标了 top-K 内的相关性，IDCG 可能低估（漏标的相关文档未计入理想排序）。
局限 4：不区分"几乎相关"和"完全不相关"。
rel=0 的文档无论排第几都不贡献，但用户看到"几乎相关"和"完全不相关"的 rel=0 体验不同。
局限 5：跨查询平均的 bias。
简单平均 NDCG 可能偏向相关文档少的查询（容易得高 NDCG）。可加权平均。
4.8 NDCG 在工业中的应用
搜索引擎：
- Google、Bing、百度都用 NDCG@10 评估排序质量
- 人工标注分级相关性
- A/B 测试看 NDCG 变化
推荐系统：
- 用 NDCG@10 / NDCG@50 评估推荐排序
- 相关性 = 用户行为（点击、购买、停留）
电商搜索：
- NDCG@20 评估商品排序
- 相关性 = 购买转化率
RAG：
- 辅助指标（非主指标）
- 评估 chunk 排序质量
- 主指标仍是 Hit Rate@K
4.9 NDCG 的计算优化
增量计算：
DCG 可增量更新（新文档加入时只算新位置）。适合在线评估。
近似计算：
大规模评估时，可只算 top-K 的 DCG（忽略长尾），加速。
缓存 IDCG：
IDCG 只依赖相关性分布，可预计算缓存。
L5 · 沿革与坑
5.1 历史脉络
- 2000s：Järvelin & Kekäläinen 2002 提出 NDCG
- 2000s：TREC 评测采用 NDCG
- 2010s：Yahoo Learning to Rank Challenge、Yandex 用 NDCG 评估
- 2010s：搜索引擎工业标准（Google、Bing）
- 2020+：推荐系统、RAG 也用 NDCG 评估排序
5.2 使用常见坑
坑 1：用二元相关性。
rel 只用 0/1，NDCG 退化为类似 DCG，丢失分级信息。要标注 0/1/2/3 分级。
坑 2：标注不全。
只标 top-K 内相关性，IDCG 低估（漏标的相关文档未计入理想排序）。要标全所有可能相关文档。
坑 3：标注噪声。
分级标注主观，需多标注者投票。单标注者 NDCG 方差大。
坑 4：K 选错。
NDCG@1000 让长尾贡献稀释 top，NDCG@1 太严格。搜索引擎用 NDCG@10。
坑 5：跨查询简单平均。
相关文档少的查询容易高 NDCG，简单平均偏向这类查询。可按相关文档数加权。
坑 6：评估集太小。
100 query 的 NDCG 方差大。建议至少 500 query。
坑 7：用 NDCG 评估 RAG。
RAG 关心 top-k 是否含答案（Hit Rate@K），不关心排序质量（LLM 能从 top-k 中找）。NDCG 是辅助指标。
坑 8：忘了归一化。
报告 DCG 而非 NDCG，跨查询不可比。要用 NDCG。
坑 9：IDCG=0 时除零。
无相关文档时 IDCG=0，NDCG=0/0。要特殊处理（通常记 0）。
坑 10：相关性定义不一致。
不同标注者对"高度相关"定义不同。要制定标注规范，多标注者投票。
5.3 NDCG 的变体
Alpha-NDCG：
评估排序的多样性（novelty）。每个文档有主题，重复主题折扣。
Intent-Aware NDCG：
多意图查询，每意图分别算 NDCG 后平均。
NDCG with Click Feedback：
用点击数据估计相关性，降低人工标注成本。但有位置偏置。
5.4 NDCG 提升策略
提升 NDCG@10 的方法：
- 更好排序模型：Cross-encoder / LTR 精排
- 分级相关性训练：用分级标注训练，而非二元
- 难负样本训练：区分"几乎相关"和"一般相关"
- 个性化：用户偏好让高度相关排前
- 多样性重排：避免 top-10 都是相似结果
典型提升幅度：
- 单 BM25：NDCG@10 ≈ 0.40
- 单 Dense：NDCG@10 ≈ 0.50
- 混合检索：NDCG@10 ≈ 0.55
- 混合 + 精排：NDCG@10 ≈ 0.65
- 混合 + LTR：NDCG@10 ≈ 0.70
5.5 NDCG vs MAP vs MRR
| 指标 | 分级 | 位置 | 全排序 | 适用 |
|---|---|---|---|---|
| NDCG@K | 是 | 是 | 是 | 综合排序 |
| MAP | 否 | 是（隐式） | 是 | 多相关二元 |
| MRR@K | 否 | 是 | 否 | 问答单答案 |
选择建议：
- 分级相关性 + 综合排序：NDCG@K
- 二元相关性 + 多相关：MAP
- 单答案 + 位置：MRR@K
- RAG：Hit Rate@K
速记卡
| 维度 | NDCG |
|---|---|
| 公式 | DCG / IDCG |
| DCG | $\sum (2^{\text{rel}_i} - 1) / \log_2(i+1)$ |
| IDCG | 理想排序的 DCG |
| 范围 | [0, 1] |
| 分级相关性 | 是（0/1/2/3） |
| 位置折损 | $1/\log_2(\text{rank}+1)$ |
| 全排序 | 是 |
| 归一化 | 是 |
| 适用 | 综合排序评估 |
与其他指标对比：
| 指标 | 分级 | 位置 | 全排序 | 归一化 |
|---|---|---|---|---|
| Hit Rate@K | 否 | 否 | 否 | 否 |
| MRR@K | 否 | 是 | 否 | 否 |
| MAP | 否 | 是 | 是 | 否 |
| NDCG@K | 是 | 是 | 是 | 是 |
位置折损数值：
| 位置 | $1/\log_2(\text{rank}+1)$ |
|---|---|
| 1 | 1.0 |
| 2 | 0.63 |
| 5 | 0.39 |
| 10 | 0.30 |
一句话记忆：NDCG = DCG / IDCG，DCG 用 $1/\log_2(\text{rank}+1)$ 折损累加分级相关性，归一化到 [0, 1]。考虑位置（top 重）和分级（高度 vs 一般），是排序评估的金标准。搜索引擎用 NDCG@10，RAG 用 Hit Rate@K。
上一篇：MRR 平均倒数排名 -- 关心第一个相关文档位置。下一篇：知识库 Knowledge Base -- RAG 的知识存储与管理。