评估推荐系统通常需要比单纯判断相关条目是否存在更为细致的指标。许多评估方法在衡量推荐列表中条目位置的相对价值时会遇到挑战。例如,排名第一的条目通常比排名第十的条目更有价值,但某些方法却对它们一视同仁。此外,准确评估相关性意味着要识别不同程度的效用,而不仅仅是二元的“相关”或“不相关”。
在许多实际应用中,相关性并不是二元的。用户可能非常喜欢一部电影,对另一部评价尚可,而觉得第三部仅仅是可以接受。归一化折损累计增益 (NDCG) 是一种专门为这些场景设计的强力排名指标。它通过结合以下两个核心思想来评估推荐列表的质量:
- 高相关的条目比低相关的条目更有价值。
- 出现在列表靠前位置的相关条目比出现在靠后位置的更有用。
为了理解 NDCG,我们将从它的组成部分逐步构建:累计增益 (CG)、折损累计增益 (DCG),以及最后的归一化版本。
从累计增益到 DCG
让我们从最简单的形式开始:累计增益 (CG)。CG 是推荐列表中直到特定排名 k 的条目相关性得分的总和。它不考虑条目的顺序,只考虑它们的相关性。
在位置 k 处的 CG 公式为:
CGk=i=1∑kreli
这里,reli 是位于位置 i 的条目的相关性得分。例如,如果我们有一个相关性得分为 [5, 2, 3] 的前 3 名列表,则 CG3 仅仅是 5+2+3=10。这告诉了我们累积的总相关性,但它没有因为模型将最相关的条目(得分 5)放在顶部而给予奖励。
为了解决这个问题,我们引入了一项惩罚,针对将相关条目放在列表较低位置的情况。这就引出了 折损累计增益 (DCG)。DCG 根据条目的排名系统地对相关性得分进行折减。最常用的方法是使用对数折损。
在位置 k 处的 DCG 公式为:
DCGk=i=1∑klog2(i+1)reli
分母中的 log2(i+1) 随着位置 i 的增加而增大。这意味着较高排名(如位置 1 或 2)的条目其相关性得分除以一个较小的数字,而较低排名的条目则除以一个较大的数字,从而有效地“折抵”了它们对总分的贡献。
应用于条目相关性得分的折损因子随着其排名位置的增加而减小。位于位置 10 的条目的影响不到位置 1 条目的三分之一。
让我们回顾一下相关性得分为 [5, 2, 3] 的示例列表。
- 位置 1:rel1=5。折损因子:log2(1+1)1=1。贡献:5×1=5。
- 位置 2:rel2=2。折损因子:log2(2+1)1≈0.631。贡献:2×0.631=1.262。
- 位置 3:rel3=3。折损因子:log2(3+1)1=0.5。贡献:3×0.5=1.5。
DCG3 是这些贡献的总和:5+1.262+1.5=7.762。
现在,考虑如果我们的模型产生了一个较差的排名 [2, 3, 5] 会发生什么:
- 位置 1:rel1=2。贡献:2×1=2。
- 位置 2:rel2=3。贡献:3×0.631=1.893。
- 位置 3:rel3=5。贡献:5×0.5=2.5。
这个列表的 DCG3 是 2+1.893+2.5=6.393。如你所见,DCG 分数较低,正确地惩罚了模型将最相关的条目放在列表底部的行为。
归一化 DCG 以获得 NDCG
DCG 是一个很好的关注位置的指标,但它还有一个问题:它的值不容易解释。最大可能的 DCG 取效于特定用户和可用的相关条目。一个拥有十个高相关条目的用户比一个只有三个低相关条目的用户拥有更高的潜在 DCG。这使得跨用户平均分数或比较不同数据集上的表现变得困难。
解决方案是对 DCG 分数进行归一化。我们将模型的 DCG 除以 理想折损累计增益 (IDCG)。IDCG 是一个完美(或“理想”)排名的 DCG。要计算它,你需要获取某个用户的所有相关条目,按相关性降序排列,然后计算该完美列表的 DCG。
归一化折损累计增益 (NDCG) 的最终公式为:
NDCGk=IDCGkDCGk
得到的 NDCG 分数始终介于 0.0 和 1.0 之间。NDCG 为 1.0 意味着模型的排名是完美的,而得分为 0.0 则意味着推荐的条目中没有一个是相关的。
让我们完成示例。用户的相关性得分为 [5, 2, 3]。
-
模型的排名: [5, 2, 3]
- DCG3=7.762(如前所述)。
-
理想排名: 首先,按降序排列相关性得分:[5, 3, 2]。这是完美的排名。
- 计算此理想列表的 IDCG3:
- 位置 1 (rel=5):5/log2(2)=5.0
- 位置 2 (rel=3):3/log2(3)≈1.893
- 位置 3 (rel=2):2/log2(4)=1.0
- IDCG3=5.0+1.893+1.0=7.893。
-
计算 NDCG:
- NDCG3=IDCG3DCG3=7.8937.762≈0.983。
这个分数非常接近 1.0,表明模型的排名几乎是完美的。
何时使用 NDCG
NDCG 是评估排名列表最有参考价值的离线指标之一。在以下情况下你应该使用它:
- 推荐的顺序非常重要。 如果确保前 3 个条目准确比第 8 到 10 个条目准确更有意义,那么 NDCG 是个极佳的选择。
- 可以为条目分配不同的相关级别。 这在使用显式反馈(如 1-5 星评分)时非常直观。对于隐式反馈,你可以将“购买”事件分配比“点击”事件更高的相关性。
通过同时捕捉相关性和位置,NDCG 比更简单的指标能更全面地反映推荐系统的表现。它已成为信息检索中的标准指标,也是任何致力于优化推荐系统的人员必备的工具。