**归一化折损累积增益(NDCG)**是一种衡量排序质量的指标,应用于信息检索、推荐系统和学习排序。它通过为相关项目赋予增益、对靠后位置的增益进行折损,再将所得分数除以理想排序的分数,来评价一个有序列表。与仅区分结果相关或不相关的指标不同,NDCG 可以使用分级相关性,例如“不相关”“部分相关”和“高度相关”。通常在固定的排名截断位置报告这一指标,记作 NDCG@。
定义
NDCG 结合了三个思想:
- **增益:**相关性越高的项目,贡献的价值越大。
- **折损:**项目在排序中越靠后,贡献就越小。
- **归一化:**将当前排序与同一评估情境下的最佳排序进行比较。
设 为排名第 的项目的相关性等级,排名从 1 开始。一种广泛使用的定义将截断位置 处的折损累积增益表示为
分子 是增益函数。分母根据结果所在的位置对其增益进行折损。排名第 1 的折损权重为 1,第 2 的权重约为 ,第 3 的权重为 。
理想折损累积增益 的计算方式是:将可用项目按相关性从高到低排列,再应用同一公式。于是有
当增益非负、分母为正,且评估所涵盖的项目范围定义一致时,NDCG 的取值介于 0 和 1 之间。分数为 1 表示在所评估的截断位置上达到了理想排序;相关性相同的项目可以互换位置。
增益与折损的变体
NDCG 并非一个完全统一的公式,而是一组密切相关的约定。其一般形式为
其中, 是递增的增益函数, 是正值且非递增的位置权重。
两种常见的增益函数是:
- 线性增益:。
- 指数增益:。
指数增益更强调区分高度相关的项目与中度相关的项目。当相关性等级为二元值 时,这两个函数完全相同。
折损方式也有不同约定。早期的一种形式不对第一个结果进行折损,而对后续结果使用基于排名的对数折损。许多现代实现则统一使用 。采用不同约定计算出的分数不一定可以直接互换。
对于统一使用 的形式,改变对数底数会使 DCG 和 IDCG 同时乘以相同的常数,因此不会改变 NDCG。
计算示例
假设三个项目的相关性等级分别为 3、2 和 0,但系统返回的顺序为 2、3、0。采用指数增益,截断位置设为 3,则
理想顺序为 3、2、0:
因此,
这一排序包含的项目与理想列表相同,但由于最相关的项目排在第二位,得分较低。因此,即使返回的项目集合完全相同,NDCG 也能区分不同的排列顺序。
相关性判断与评估范围
分级相关性
相关性等级可以来自人工评判,也可以来自经转换后用作评估标签的行为观测。在搜索引擎中,评判人员可以判断一篇文档是完整回答了查询、提供了部分信息,还是与查询无关。推荐评估则可以使用显式评分,或根据交互行为生成的标签。
等级尺度与增益函数共同决定了这一指标的含义。对于 0 到 4 的等级,指数增益分别赋予 0、1、3、7 和 15 的增益。这些差异体现了对各相关性等级的一种特定价值设定;不能仅因标签具有先后顺序,就认为这种设定天然合理。
行为标签也需要谨慎使用。点击并非对相关性的直接测量:它可能受到呈现方式、先前的排名位置,以及用户是否注意到该项目等因素的影响。
理想排序
必须明确哪些项目可以纳入理想排序。在检索评估中,IDCG 可以根据某个查询下已被评判为相关的文档计算,其中包括系统返回列表中没有出现的文档。在重排序评估中,则可能仅根据一个固定候选集计算。
这些选择衡量的是不同能力。在候选集内部进行归一化,评估的是对该集合的排序能力,却不能充分衡量前面的检索阶段是否遗漏了有价值的项目。因此,如果允许不同系统使用不同的理想项目集,比较结果就可能产生误导。
截断位置与缺失结果
较小的截断位置侧重于前几个结果;较大的截断位置则评估列表中更靠后的部分。NDCG@5 与 NDCG@100 可能会给出不同的系统优劣排序。
对于长度小于 的列表,通常将缺失位置的增益视为零。不过,作为分母的理想增益仍应遵循指定的评估范围,而不应自动缩小到仅涵盖返回列表。
分母为零与负标签
如果所有可纳入评估的项目增益均为零,那么 IDCG 为零,这一比值在数学上没有定义。评估工具可能将其记为零、排除该查询,或采用其他明确约定。这一选择会影响汇总分数。
通常的有界解释以增益非负为前提。将负的相关性标签代入常见增益函数,可能会产生负增益,使 NDCG 不再适用取值介于 0 和 1 之间的标准解释。
汇总与实现
NDCG 通常针对每个查询或用户分别计算,然后取平均值:
其中, 是按照所选纳入规则筛选后,参与评估的查询或用户集合。
除非显式引入权重,否则这种宏平均会赋予每个评估单元相同的权重。它不同于将所有 DCG 值之和除以所有 IDCG 值之和;后者实际上赋予理想增益较大的评估单元更高的权重。
预测分数相同的情况也需要约定处理方式。具体实现可以采用确定性的规则打破并列,也可以计算并列组内各种可能排序下的期望值。不同的处理方式可能改变结果,尤其是在并列项目分布于截断位置两侧时。
因此,要进行有意义的比较,就需要明确截断位置、增益函数与折损函数、候选项目范围、相关性判断、未评判项目的处理方式、分母为零时的处理规则、并列处理方式,以及汇总方法。
在机器学习中的应用
NDCG 广泛用作机器学习排序模型的离线评估指标。当结果具有多个相关性等级,且排名靠前的错误比靠后的错误影响更大时,它尤为有用。
由于 NDCG 依赖离散的排名位置,它通常不是预测分数的光滑函数。分数的小幅变化可能不会改变排序,而一次位置交换却可能导致指标突变。因此,排序方法往往优化一个替代性的损失函数,而不是直接优化 NDCG。
一些方法会根据交换两个项目所引起的 NDCG 变化,对训练更新赋予权重。这类方法将模型训练与评估目标联系起来,而不把该指标视为普通的可微损失。
与其他评估指标一样,反复依据同一个测试集选择模型,会削弱它作为独立评估手段的作用。通常会使用单独的验证集来进行模型选择。
优点与局限
NDCG 支持分级相关性,强调靠前的结果,并通过归一化处理不同查询之间可获得增益总量的差异。不过,归一化并不意味着每个查询都同样困难,也不意味着所有数据集都可以直接比较。
其主要局限包括:
- **依赖评判结果。**不完整或不一致的评判会同时扭曲实际增益和作为分母的理想增益。将未评判项目视为不相关,可能使检索到此前未经评判材料的系统处于不利地位。
- **依赖候选集的构建方式。**基于抽样负例计算的分数,可能与基于完整项目库计算的分数有很大差异。
- **对位置效应作出假设。**对数折损体现的是价值随排名下降的一种特定模型,而不是对用户注意力的普遍描述。
- **项目价值具有可加性。**标准 NDCG 对各项目独立评分,不会直接惩罚冗余答案,也不会奖励对不同用户意图的覆盖。
- **分数差异的解释有限。**从 0.70 提高到 0.75,并不意味着用户满意度提高了五个百分点。
- **对系统质量的覆盖有限。**NDCG 本身不衡量延迟、公平性、新颖性、事实准确性或其他部署要求。
与通常使用二元相关性的平均精度相比,NDCG 直接支持多个相关性等级。不过,选择何种指标,仍取决于目标任务以及现有标签的含义。
历史发展
累积增益框架由卡勒沃·耶尔韦林(Kalervo Järvelin)和雅娜·凯凯莱宁(Jaana Kekäläinen)于 2000 年前后在信息检索研究中提出,并在他们 2002 年关于基于累积增益的评估的研究中得到进一步阐述。该框架针对的是以往评估方法的一项局限:即使已有分级评判,仍将相关性简化为二元区分。此后,折损累积增益和归一化累积增益等指标逐渐成为搜索评估、推荐以及学习排序研究中的常用工具。