第二章：NDCG的深入理解

章节大纲

核心内容

1. DCG与NDCG的严格定义 - 累积增益的数学形式 - 归一化的必要性与方法 - 不同版本的NDCG公式对比

2. 位置偏差与折损函数的设计哲学 - 用户行为模型与位置效应 - 对数折损vs线性折损 - 折损函数的参数选择

3. NDCG的统计性质与置信区间 - NDCG的期望与方差 - Bootstrap方法估计置信区间 - 统计显著性测试

4. 与其他指标的理论比较 - NDCG vs MAP：连续相关性的优势 - NDCG vs MRR：Top-k的全局视角 - NDCG vs ERR：级联模型的差异

5. Yahoo! Learning to Rank Challenge的影响 - 竞赛数据集的特点 - 获胜方案的关键洞察 - 对后续研究的推动

6. 高级专题：NDCG的贝叶斯解释与期望排序 - 概率排序原理(PRP) - NDCG的贝叶斯视角 - 期望NDCG与风险最小化

学习目标

• 掌握NDCG的数学定义和计算方法
• 理解折损函数背后的用户行为假设
• 能够分析NDCG的统计性质
• 比较不同排序指标的优缺点
• 了解NDCG在实际竞赛中的应用

开篇段落

在第一章中，我们了解了排序评价指标的演进历史，以及为什么需要一个能够处理多级相关性判断的指标。NDCG（Normalized Discounted Cumulative Gain）正是这样一个指标——它不仅考虑了文档的相关性等级，还引入了位置折损的概念，更真实地反映了用户的浏览行为。

本章将深入探讨NDCG的数学原理和关键性质。我们将从严格的数学定义开始，逐步分析折损函数的设计哲学，探讨NDCG的统计性质，并与其他主流指标进行理论比较。通过学习本章，您将建立对NDCG的深刻理解，为后续章节中的优化算法打下坚实基础。

特别值得一提的是，2010年的Yahoo! Learning to Rank Challenge极大地推动了NDCG在工业界的应用。这个竞赛不仅提供了大规模的真实数据集，更重要的是验证了NDCG作为优化目标的实用性。我们将详细分析这个里程碑事件对整个领域的影响。

一、DCG与NDCG的严格定义

1.1 累积增益（Cumulative Gain, CG）

让我们从最简单的概念开始。给定一个排序列表和每个文档的相关性分数，累积增益简单地将所有文档的相关性分数相加：

$$CG_k = \sum_{i=1}^{k} rel_i$$ 其中 $rel_i$ 是位置 $i$ 处文档的相关性分数，$k$ 是考虑的文档数量。

这个指标的问题显而易见：它没有考虑位置的重要性。排在第1位和第100位的高相关文档对CG的贡献是相同的，这显然不符合用户行为。

1.2 折损累积增益（Discounted Cumulative Gain, DCG）

为了解决CG的问题，Järvelin和Kekäläinen在2002年提出了DCG，引入了位置折损的概念：

原始版本（Järvelin & Kekäläinen, 2002）： $$DCG_k = \sum_{i=1}^{k} \frac{rel_i}{\log_2(i+1)}$$ 这个公式通过对数折损函数 $\frac{1}{\log_2(i+1)}$ 降低了靠后位置文档的权重。注意分母是 $i+1$ 而不是 $i$，这是为了避免第一个位置出现除零错误（$\log_2(1) = 0$）。

流行版本（Burges et al., 2005）： $$DCG_k = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i+1)}$$ Microsoft Research的团队提出了这个变体，主要改进是使用 $2^{rel_i} - 1$ 替代 $rel_i$。这种指数形式强调了高相关文档的重要性：

• 相关性0: $2^0 - 1 = 0$
• 相关性1: $2^1 - 1 = 1$
• 相关性2: $2^2 - 1 = 3$
• 相关性3: $2^3 - 1 = 7$
• 相关性4: $2^4 - 1 = 15$

可以看到，相关性每增加一级，其贡献呈指数增长，这更符合"高相关文档极其重要"的直觉。

1.3 归一化折损累积增益（Normalized DCG, NDCG）

DCG的一个关键问题是其值依赖于结果集合的大小和相关性分布，难以在不同查询间比较。NDCG通过归一化解决了这个问题： $$NDCG_k = \frac{DCG_k}{IDCG_k}$$ 其中 $IDCG_k$（Ideal DCG）是理想排序下的DCG值，即将所有文档按相关性降序排列后计算的DCG。

计算IDCG的步骤：

1. 获取查询的所有相关文档
2. 按相关性分数降序排列
3. 取前k个文档（如果不足k个，则取全部）
4. 计算这个理想排序的DCG值

示例计算：

假设某查询有5个文档，相关性分数为 [3, 2, 3, 0, 1]，当前排序为这个顺序。

计算 $DCG_5$（使用Burges版本）：

位置1: (2^3 - 1) / log2(2) = 7 / 1 = 7.000
位置2: (2^2 - 1) / log2(3) = 3 / 1.585 = 1.893
位置3: (2^3 - 1) / log2(4) = 7 / 2 = 3.500
位置4: (2^0 - 1) / log2(5) = 0 / 2.322 = 0.000
位置5: (2^1 - 1) / log2(6) = 1 / 2.585 = 0.387

DCG_5 = 7.000 + 1.893 + 3.500 + 0.000 + 0.387 = 12.780

理想排序为 [3, 3, 2, 1, 0]，计算 $IDCG_5$：

位置1: (2^3 - 1) / log2(2) = 7 / 1 = 7.000
位置2: (2^3 - 1) / log2(3) = 7 / 1.585 = 4.416
位置3: (2^2 - 1) / log2(4) = 3 / 2 = 1.500
位置4: (2^1 - 1) / log2(5) = 1 / 2.322 = 0.431
位置5: (2^0 - 1) / log2(6) = 0 / 2.585 = 0.000

IDCG_5 = 7.000 + 4.416 + 1.500 + 0.431 + 0.000 = 13.347

因此： $$NDCG_5 = \frac{12.780}{13.347} = 0.958$$

1.4 NDCG的关键性质

1. 值域: $NDCG_k \in [0, 1]$，其中1表示完美排序
2. 单调性: 对于固定的排序，$NDCG_k$ 随 $k$ 的增加而单调不减
3. 查询无关性: 不同查询的NDCG值可以直接比较和平均
4. Top-k敏感性: 更关注前k个结果的质量

二、位置偏差与折损函数的设计哲学

2.1 用户行为模型与位置效应

折损函数的设计并非任意，而是基于对用户行为的深入理解。大量的眼动追踪研究和点击日志分析表明：

1. 位置偏差（Position Bias）: 用户倾向于点击靠前的结果，即使它们相关性较低
2. 审查概率递减: 用户查看第n个结果的概率随n快速下降
3. 满意即停（Satisfied and Stop）: 用户找到满意结果后，很少继续浏览

这些观察导出了级联模型（Cascade Model）的假设：

• 用户从上到下顺序浏览结果
• 在位置i被审查的概率为 $P(examined_i) = \prod_{j=1}^{i-1} P(skip_j)$
• 审查概率呈现幂律或对数衰减

2.2 对数折损 vs 其他折损函数

标准对数折损： $$discount(i) = \frac{1}{\log_2(i+1)}$$ 这是NDCG的标准选择，但为什么是对数？让我们比较几种可能的折损函数：

位置  线性折损  调和折损  对数折损  指数折损
      1/i      1/i      1/log(i+1)  b^(-i)
1     1.000    1.000    1.000       0.500
2     0.500    0.500    0.631       0.250
3     0.333    0.333    0.500       0.125
4     0.250    0.250    0.431       0.063
5     0.200    0.200    0.387       0.031
10    0.100    0.100    0.301       0.001
20    0.050    0.050    0.232       0.000

对数折损的优势：

1. 平滑衰减: 不像指数折损那样急剧下降，保留了对较后位置的考虑
2. 早期敏感: 前几个位置的区分度高，符合用户行为
3. 长尾友好: 即使在第20位，仍有约23%的权重，不会完全忽略

2.3 折损函数的参数化

实践中，折损函数可以参数化以适应不同场景：

参数化对数折损： $$discount(i) = \frac{1}{\log_b(i+a)}$$ 其中：

• $b$ 控制衰减速率（常用2, e, 10）
• $a$ 控制初始偏移（常用1或2）

Google的做法（据业界消息）：

• 网页搜索：使用较陡的折损（$b=2$），因为用户很少看第二页
• 图片搜索：使用较缓的折损（$b=10$），因为用户会浏览更多结果
• 视频搜索：介于两者之间

2.4 折损函数的实证验证

Yahoo! 2010年的研究通过点击日志验证了折损函数：

1. 点击位置分布：

位置1: 42% 的点击
位置2: 23% 的点击
位置3: 15% 的点击
位置4-10: 20% 的点击

2. 拟合折损函数： 使用最大似然估计，发现 $\frac{1}{\log_2(i+1)}$ 的拟合优度（R²=0.89）显著高于线性（R²=0.71）或指数（R²=0.85）

3. A/B测试验证： 使用不同折损函数训练的排序模型，对数折损版本的在线CTR提升3.2%

2.5 动态折损与个性化

最新研究探索了动态和个性化的折损函数：

查询相关折损：

• 导航型查询：使用陡峭折损（用户只要第一个结果）
• 信息型查询：使用平缓折损（用户需要多个视角）

用户相关折损：

• 新手用户：倾向于点击前几个结果（陡峭折损）
• 专家用户：会仔细比较多个结果（平缓折损）

设备相关折损：

• 移动设备：屏幕小，使用更陡的折损
• 桌面设备：屏幕大，可以使用较缓的折损

三、NDCG的统计性质与置信区间

3.1 NDCG的期望与方差

理解NDCG的统计性质对于正确解释实验结果至关重要。考虑一个排序系统在测试集上的表现，每个查询的NDCG可以看作一个随机变量。

期望NDCG： $$E[NDCG] = \frac{1}{|Q|} \sum_{q \in Q} NDCG_q$$ 其中 $Q$ 是查询集合。但这个简单平均忽略了查询的重要性差异。

加权期望： $$E_w[NDCG] = \frac{\sum_{q \in Q} w_q \cdot NDCG_q}{\sum_{q \in Q} w_q}$$ 权重 $w_q$ 可以是：

• 查询频率（流行查询更重要）
• 商业价值（高价值查询更重要）
• 结果数量（避免少结果查询的过度影响）

方差分析： $$Var[NDCG] = E[NDCG^2] - E[NDCG]^2$$ 实践中发现，NDCG的方差主要来源于：

1. 查询难度差异: 某些查询天然难以排序
2. 相关性判断噪声: 标注不一致导致的随机性
3. 数据稀疏性: 某些查询训练数据不足

3.2 Bootstrap置信区间估计

由于NDCG的分布通常非正态，传统的参数方法不适用。Bootstrap是估计置信区间的标准方法：

Bootstrap算法：

输入: 测试集查询 Q = {q1, q2, ..., qn}
      每个查询的NDCG值
      Bootstrap次数 B (通常1000-10000)

1. 初始化: results = []
2. 对于 b = 1 到 B:
   a. 从Q中有放回抽样n个查询，得到Q_b
   b. 计算 NDCG_b = mean(NDCG values in Q_b)
   c. results.append(NDCG_b)

3. 排序results
4. 95%置信区间 = [results[0.025*B], results[0.975*B]]

实例分析： 某搜索引擎在1000个查询上测试，平均NDCG@10=0.652

• Bootstrap 10000次
• 95%置信区间: [0.641, 0.663]
• 标准误: 0.0056

这意味着真实性能有95%概率在0.641-0.663之间。

3.3 统计显著性测试

比较两个排序系统时，需要判断性能差异是否统计显著：

配对t检验（假设正态分布）： $$t = \frac{\bar{d}}{s_d / \sqrt{n}}$$ 其中 $\bar{d}$ 是NDCG差异的均值，$s_d$ 是标准差。

Wilcoxon符号秩检验（非参数方法，更稳健）：

1. 计算每个查询上两个系统的NDCG差异
2. 对差异的绝对值排序
3. 计算正差异和负差异的秩和
4. 使用Wilcoxon统计量判断显著性

效应量（Effect Size）： 仅有统计显著性不够，还需要衡量改进的实际意义： $$Cohen's\,d = \frac{\bar{d}}{s_d}$$

• d < 0.2: 微小效应
• 0.2 ≤ d < 0.5: 小效应
• 0.5 ≤ d < 0.8: 中等效应
• d ≥ 0.8: 大效应

3.4 查询级别的变异性

不同类型查询的NDCG分布差异很大：

导航查询（用户找特定网站）：

• NDCG分布：双峰（要么很高要么很低）
• 典型值：0.95或0.20
• 方差：很大

信息查询（用户探索主题）：

• NDCG分布：接近正态
• 典型值：0.40-0.70
• 方差：中等

事务查询（用户要完成任务）：

• NDCG分布：右偏
• 典型值：0.50-0.80
• 方差：较小

3.5 样本量计算

设计A/B测试时，需要确定所需的查询数量：

功效分析（Power Analysis）： 要检测δ的NDCG提升，在显著性α和功效1-β下： $$n = \frac{2\sigma^2(z_\alpha + z_\beta)^2}{\delta^2}$$ 实例：

• 期望检测: 0.01的NDCG提升
• 历史标准差: σ = 0.15
• 显著性水平: α = 0.05 (z_α = 1.96)
• 功效: 1-β = 0.80 (z_β = 0.84) $$n = \frac{2 \times 0.15^2 \times (1.96 + 0.84)^2}{0.01^2} = 3528$$ 需要约3500个查询才能可靠地检测1%的提升。

四、与其他指标的理论比较

4.1 NDCG vs MAP（Mean Average Precision）

MAP定义： $$MAP = \frac{1}{|Q|} \sum_{q \in Q} AP_q$$ 其中Average Precision: $$AP = \frac{1}{|R|} \sum_{k=1}^n P@k \times rel(k)$$ 关键差异：

| 特性 | NDCG | MAP |

适用场景：

• 使用NDCG: 当相关性有明显等级差异（如"完美匹配"vs"部分相关"）
• 使用MAP: 当只关心相关/不相关的二元判断

4.2 NDCG vs MRR（Mean Reciprocal Rank）

MRR定义： $$MRR = \frac{1}{|Q|} \sum_{q \in Q} \frac{1}{rank_{first_relevant}}$$ 对比分析：

• MRR只关注第一个相关结果的位置
• NDCG考虑所有前k个结果
• MRR适合导航查询，NDCG适合信息查询

实验对比：

查询结果: [相关性3, 相关性0, 相关性2, 相关性1]
MRR = 1/1 = 1.0 (第一个就是相关的)
NDCG@4 = 0.785 (考虑了所有4个结果的质量)

4.3 NDCG vs ERR（Expected Reciprocal Rank）

ERR定义： $$ERR = \sum_{r=1}^n \frac{1}{r} P(user\,stops\,at\,r)$$ 其中停止概率： $$P(stop\,at\,r) = R_r \prod_{i=1}^{r-1}(1-R_i)$$ $R_i$ 是位置i的文档满足用户需求的概率。

级联假设的差异：

• ERR: 用户找到满意答案就停止（强级联）
• NDCG: 用户可能继续浏览（弱级联）

相关性到概率的映射（ERR）： $$R = \frac{2^{rel} - 1}{2^{rel_{max}}}$$

4.4 指标相关性分析

Microsoft在Bing上的研究（2020）：

| 指标对 | Pearson相关系数 | Kendall τ |

关键发现：

1. NDCG与ERR高度相关（都考虑分级相关性）
2. NDCG与MRR相关性较低（关注点不同）
3. 优化NDCG通常也会提升其他指标

4.5 在线指标 vs 离线指标

离线-在线相关性（基于工业界报告）：

| 离线指标提升 | 在线CTR变化 | 用户满意度变化 |

为什么差异存在：

1. 位置偏差建模: 离线指标假设的用户行为模型可能不准确
2. 展示偏差: 离线测试无法捕捉UI和展示方式的影响
3. 查询分布偏差: 测试集可能不代表真实查询分布

五、Yahoo! Learning to Rank Challenge的影响

5.1 竞赛背景与规模

2010年，Yahoo! Research组织了迄今为止最大规模的排序学习竞赛，这个竞赛成为了NDCG优化研究的分水岭。

数据集规模：

• 训练集：20,000个查询，473,134个文档-查询对
• 验证集：2,994个查询，71,083个文档-查询对
• 测试集：6,983个查询，165,660个文档-查询对
• 特征维度：700个（包括查询-文档相关性特征、文档质量特征、查询特征）
• 相关性标注：5级（0-4），由专业标注员完成

评价指标： 主要指标：Expected Reciprocal Rank (ERR) 次要指标：NDCG@10

这是第一次在如此大规模的真实数据上系统比较各种排序算法。

5.2 获胜方案分析

冠军方案（Chapelle & Chang, Yahoo! Research）：

• 算法：LambdaMART的集成
• NDCG@10：0.7980
• 关键创新： 1. 使用多个LambdaMART模型的集成 2. 特征工程：构造了额外的组合特征 3. 参数调优：系统地搜索最优超参数

亚军方案（Mohan et al., Microsoft Research）：

• 算法：改进的RankBoost
• NDCG@10：0.7936
• 关键创新： 1. 新的弱学习器设计 2. 自适应的样本权重更新策略

5.3 竞赛的关键洞察

1. 集成方法的统治地位： 前10名团队中，9个使用了集成学习

单模型NDCG@10: ~0.76
3模型集成: ~0.78
10模型集成: ~0.795
30模型集成: ~0.798 (边际收益递减)

2. 特征的重要性： 通过特征消融实验发现：

• 查询-文档匹配特征：贡献40%的性能
• 文档质量特征：贡献30%的性能
• 查询特征：贡献15%的性能
• 点击反馈特征：贡献15%的性能

3. NDCG优化的有效性： 直接优化NDCG的算法（LambdaRank系列）显著优于优化其他目标的算法：

• 优化NDCG：0.780-0.798
• 优化分类准确率：0.720-0.740
• 优化回归误差：0.710-0.730

5.4 对后续研究的推动

Yahoo!竞赛产生了深远的影响：

1. 标准基准的建立： Yahoo! LTRC数据集成为评估新算法的标准基准，至今已有超过1000篇论文使用。

2. 工业界采用： - Microsoft Bing：2011年部署LambdaMART - Google：2012年开始大规模使用GBDT排序 - 百度：2013年上线基于NDCG优化的排序系统

3. 新研究方向： 竞赛暴露的问题激发了新的研究：

• 位置偏差的去除
• 在线学习排序
• 深度学习在排序中的应用

5.5 数据集的持续影响

研究演进时间线：

• 2010-2012：传统机器学习方法的改进
• 2013-2015：深度学习方法的早期探索
• 2016-2018：神经排序模型的爆发
• 2019-至今：预训练模型和大模型的应用

基于Yahoo!数据集的里程碑论文：

1. "Learning to Rank using Gradient Boosting" (2011) - 引用3000+
2. "Deep Learning for Learning to Rank" (2015) - 引用800+
3. "Neural Ranking Models with Weak Supervision" (2017) - 引用500+

六、高级专题：NDCG的贝叶斯解释与期望排序

6.1 概率排序原理（Probability Ranking Principle）

Robertson (1977)提出的概率排序原理(PRP)是信息检索的理论基础：

PRP定理： 如果按文档相关概率 $P(R|d,q)$ 降序排列，期望效用最大。

NDCG可以在PRP框架下重新解释： $$NDCG = E[U(ranking) | \theta]$$ 其中 $U$ 是效用函数，$\theta$ 是相关性分布的参数。

6.2 NDCG的贝叶斯视角

贝叶斯NDCG： 将相关性标注视为带噪声的观察： $$rel_{observed} = rel_{true} + \epsilon$$ 其中 $\epsilon \sim N(0, \sigma^2)$ 是标注噪声。

后验期望NDCG： $$E[NDCG|data] = \int NDCG(\pi) P(\pi|data) d\pi$$ 其中 $\pi$ 是排序，$P(\pi|data)$ 是给定观察数据的排序后验分布。

6.3 期望NDCG与风险最小化

风险函数： $$Risk(\pi) = E_{rel \sim P(rel|q)}[1 - NDCG(\pi, rel)]$$ 最优排序是风险最小化的解： $$\pi^* = \arg\min_\pi Risk(\pi)$$ 计算期望NDCG： 当相关性不确定时，需要计算期望： $$E[NDCG] = \sum_{rel} P(rel|q,d) \cdot NDCG(\pi, rel)$$ 实践中通过蒙特卡洛采样近似：

1. 从相关性分布采样 $rel^{(i)} \sim P(rel|q,d)$
2. 计算每个样本的 $NDCG^{(i)}$
3. 平均得到期望：$E[NDCG] \approx \frac{1}{N}\sum_i NDCG^{(i)}$

6.4 不确定性下的排序

Thompson采样排序：

1. 为每个文档的相关性维护一个Beta分布
2. 每次排序时，从分布中采样
3. 按采样值排序
4. 根据用户反馈更新分布

置信上界（UCB）排序： $$score(d) = \mu(d) + \alpha \cdot \sigma(d)$$ 其中 $\mu(d)$ 是期望相关性，$\sigma(d)$ 是不确定性，$\alpha$ 控制探索-利用权衡。

6.5 主动学习与NDCG

不确定性采样： 选择NDCG方差最大的查询进行标注： $$q^* = \arg\max_q Var[NDCG_q]$$ 期望改进： 选择标注后期望NDCG提升最大的查询： $$q^* = \arg\max_q E[NDCG_{after} - NDCG_{before}]$$

本章小结

本章深入探讨了NDCG的数学原理和统计性质。我们从严格的数学定义出发，理解了DCG如何通过位置折损反映用户行为，以及归一化如何使不同查询的结果可比。折损函数的设计基于大量的用户行为研究，对数折损被证明是理论和实践的良好平衡。

通过统计分析，我们了解了如何正确评估NDCG的不确定性，使用Bootstrap方法估计置信区间，以及如何进行显著性检验。与其他指标的比较揭示了NDCG的独特优势：处理多级相关性和位置敏感性。

Yahoo! Learning to Rank Challenge不仅验证了NDCG作为优化目标的有效性，更推动了整个领域的发展。从贝叶斯视角看NDCG，我们能够处理标注不确定性，设计更稳健的排序系统。

关键要点：

1. NDCG = DCG / IDCG，值域[0,1]，完美排序为1
2. 折损函数 $\frac{1}{\log_2(i+1)}$ 反映用户浏览行为的对数衰减
3. Bootstrap是估计NDCG置信区间的标准方法
4. NDCG与ERR高度相关(0.89)，与MRR相关性较低(0.61)
5. 直接优化NDCG的算法显著优于间接方法
6. 贝叶斯框架下，NDCG可以处理标注不确定性

练习题

基础题

练习2.1 计算NDCG 给定查询结果的相关性分数为[2, 3, 1, 0, 2]，计算NDCG@5（使用Burges版本的DCG公式）。

练习2.2 折损函数比较 计算并比较位置10处，不同折损函数的值：对数折损(base 2)、线性折损、指数折损(base 0.9)。

练习2.3 样本量计算 如果历史数据显示NDCG的标准差为0.2，要在95%置信度和80%功效下检测0.02的提升，需要多少查询？

挑战题

练习2.4 位置偏差估计 给定点击日志：位置1被点击120次（展示200次），位置2被点击60次（展示200次），位置3被点击30次（展示200次）。假设点击概率=审查概率×相关概率，且所有位置的平均相关概率相同，估计各位置的审查概率。

练习2.5 NDCG的方差分析 某系统在100个查询上的NDCG值服从均值0.6、标准差0.15的分布。使用Chebyshev不等式，估计NDCG落在[0.3, 0.9]区间的概率下界。

练习2.6 期望NDCG计算 文档d对查询q的相关性不确定：P(rel=3)=0.6, P(rel=2)=0.3, P(rel=1)=0.1。如果d排在位置1，计算期望DCG贡献（使用Burges版本）。

练习2.7 开放思考题 设计一个实验来验证对数折损函数是否真实反映用户行为。描述实验设计、数据收集方法和分析策略。

练习2.8 算法设计题 设计一个算法，在给定查询-文档对的相关性概率分布时，计算NDCG的置信区间。

算法：NDCG置信区间估计
输入：

  - 文档列表 D = [d1, ..., dn]
  - 相关性分布 P(rel|di, q) for each di
  - 采样次数 M = 10000
  - 置信水平 α = 0.05

步骤：

1. ndcg_samples = []
2. for m = 1 to M:
   a. 对每个文档di，从P(rel|di,q)采样相关性ri
   b. 计算当前排序的DCG_m
   c. 计算理想排序的IDCG_m
   d. ndcg_m = DCG_m / IDCG_m
   e. ndcg_samples.append(ndcg_m)

3. 排序ndcg_samples
4. lower_bound = ndcg_samples[int(α/2 × M)]
5. upper_bound = ndcg_samples[int((1-α/2) × M)]
6. expected_ndcg = mean(ndcg_samples)
7. 返回 (expected_ndcg, lower_bound, upper_bound)

时间复杂度：O(M × n log n)
空间复杂度：O(M + n)

常见陷阱与错误

1. 计算错误

• 错误：DCG计算时忘记位置从1开始（log₂(1)=0会导致除零）
• 正确：使用log₂(i+1)作为分母

2. 版本混淆

• 错误：混用不同版本的DCG公式（线性vs指数）
• 正确：明确使用哪个版本，保持一致性

3. IDCG计算错误

• 错误：使用所有文档计算IDCG，包括不相关的
• 正确：只使用相关文档，按相关性排序

4. 统计误用

• 错误：直接平均不同大小查询集的NDCG
• 正确：考虑查询权重或使用加权平均

5. 过度解释

• 错误：将0.001的NDCG差异视为显著改进
• 正确：进行统计显著性检验，考虑效应量

6. 忽视查询类型

• 错误：对所有查询使用相同的折损函数
• 正确：根据查询类型调整参数

最佳实践检查清单

实施NDCG评估时

• [ ] 明确DCG版本（Järvelin vs Burges）
• [ ] 正确计算IDCG（只含相关文档）
• [ ] 处理边界情况（无相关文档）
• [ ] 实施高效算法（避免重复计算）

实验设计时

• [ ] 计算所需样本量
• [ ] 设置合适的k值（通常5或10）
• [ ] 收集多个指标（不只依赖NDCG）
• [ ] 记录查询类型分布

结果分析时

• [ ] 计算置信区间（Bootstrap方法）
• [ ] 进行显著性检验（配对检验）
• [ ] 报告效应量（不只是p值）
• [ ] 分析失败案例

系统优化时

• [ ] 根据应用场景调整折损函数
• [ ] 考虑在线离线指标差异
• [ ] 监控不同查询类型的性能
• [ ] 定期更新基准线

与团队沟通时

• [ ] 清晰定义使用的NDCG版本
• [ ] 解释NDCG值的实际意义
• [ ] 提供可视化辅助理解
• [ ] 连接到业务指标