← COMP5511 全部讲次
L08e · 第 8 周

L08e NDCG@K:给一份排好的推荐列表打分

从位置折损讲起:为什么排得越靠后越不值钱;DCG 怎样一名一名累加增益;为什么要除以理想排序的 DCG;以及 HR、MRR 这些排序指标和 MAE、RMSE 怎样配对记。

一句话版

NDCG@K 给一份推荐列表的前 K 名打分。高分物品排得越靠前,得分越高;同样的物品排到后面要打折扣。最后除以「完美排序」的得分,结果落在 0 到 1 之间。

上一页 L08d 的 BPR 学的是顺序,MAE 和 RMSE 量不了顺序好坏,所以要换一个指标。

先认识这几个词

词 全称 / 读法 一句人话
增益 gain 一个物品本身值多少,评分越高越值钱
折损 discount 排得越靠后,打的折扣越多
DCG Discounted Cumulative Gain,折损累计增益 前 K 名打完折的增益加起来
理想排列 ideal ordering,πₛ 把真实评分从大到小排的那个顺序
NDCG Normalized DCG,归一化折损累计增益 DCG 除以理想排列的 DCG
@K 读「at K」 只看列表的前 K 名

一个类比:搜索结果第一页

在网上搜东西,大多数人只看前几条,很少往下翻。最想要的那条排第一,体验最好;排第五,还能找到但费劲;排到第二页,几乎等于没有。

所以评价一份结果列表,不能只看「好结果有没有出现」,还要看它出现在第几位。NDCG 就把这种「越靠后越不值钱」写成了公式:每个位置有一个折扣系数,第一名不打折,后面逐渐打折。

类比在哪里失效:

  • 真人的注意力可能在第三条后突然断掉,NDCG 的折扣是一条平滑曲线,没有断崖。
  • 搜索结果通常只分相关和不相关,NDCG 可以用多档评分,评分越高增益越大。

从零讲起

1. 位置折损:越靠后越不值钱

它解决什么问题

一份列表里,同一个好物品排第一和排第五,对用户的价值差很多。评估指标得能分出这种差别,于是给每个位置定一个折扣系数。

从哪来(补充)

DCG 出自 Järvelin 与 Kekäläinen 2002 年的论文《Cumulated gain-based evaluation of IR techniques》(ACM TOIS),最早用在信息检索里评搜索结果。

出处:Wikipedia: Discounted cumulative gain

直觉

折扣系数是 1/log₂(位次 + 1)。第 1 名是 1,完全不打折;之后慢慢变小,但下降得越来越慢。前几名之间差得多,后面几名之间差得少。

一步一步看

目标:逐个算第 1 到第 5 名的折损系数,看排名越靠后,同样的增益打折越多。

  1. 课件公式里位置编号 i 从 0 开始,第 1 名 i = 0,分母是 log₂(0 + 2) = log₂2 = 1。

  2. 第 2 名 i = 1,分母 log₂3 ≈ 1.585,折扣系数约 0.631。

  3. 第 3 名 i = 2,分母 log₂4 = 2,折扣系数 0.5。

  4. 继续往后:第 4 名约 0.431,第 5 名约 0.387。

    NDCG 位置折损:五根柱子是第 1 到第 5 名的折损系数 1/log₂(i+2),依次为 1.000、0.631、0.500、0.431、0.387;第 1 名不打折,描成青绿

怎么算

折扣系数 = 1 / log₂(i + 2),i 是从 0 开始的位置编号。

意思是:第 i + 1 名的物品,它的增益要先除以 log₂(i + 2) 再计入总分。用 i + 2 而不是 i + 1,是因为 i 从 0 起,log₂1 = 0 不能当分母。

常见误解

以为第 1 名的分母是 log₂1

i 从 0 开始,第 1 名的分母是 log₂(0 + 2) = log₂2 = 1。log₂1 = 0,当分母会除以零。

以为折扣是线性的,每往后一名少一样多

不是线性的。第 1 名到第 2 名掉得最多,越往后掉得越少。

试一下

第 4 名在公式里 i 等于几?分母是多少?

i = 3,分母 log₂(3 + 2) = log₂5 ≈ 2.32。

2. DCG:一名一名累加打完折的增益

它解决什么问题

有了折扣,还要知道每个物品「值多少」。DCG 把每个物品的价值打完折再加起来,得到一份列表的总分。

从哪来(补充)

分子写成 2^评分 − 1 的做法出自 Burges 等人 2005 年的《Learning to rank using gradient descent》(ICML)。这种写法让高评分物品的增益涨得更快,更突出最相关的那几个。

出处:Wikipedia: Discounted cumulative gain

直觉

增益 2^评分 − 1:评分 0 增益 0,评分 1 增益 1,评分 2 增益 3,评分 3 增益 7。评分每多 1,增益差不多翻倍。

所以 DCG 最怕的是把高分物品排到后面:它的增益最大,被打的折扣也最心疼。

一步一步看

目标:对模型排出的前三名逐名算增益、除以折损再累加,看 DCG 怎样得到 9.131。

自拟数据:k = 3,模型排出的前三名,真实评分依次是 3、1、2。

  1. 第 1 名,评分 3:增益 2³ − 1 = 7,除以 log₂2 = 1,得 7.000,累计 7.000。

    DCG 第 1 步:模型排出的前三名真实评分 3、1、2;这一步算第 1 名,增益 7 除以 log₂2,得 7.000,这一格描成青绿;右边累计 DCG 为 7.000

  2. 第 2 名,评分 1:增益 2¹ − 1 = 1,除以 log₂3 ≈ 1.585,得 0.631,累计 7.631。

    DCG 第 2 步:模型排出的前三名真实评分 3、1、2;这一步算第 2 名,增益 1 除以 log₂3,得 0.631,这一格描成青绿;右边累计 DCG 为 7.631

  3. 第 3 名,评分 2:增益 2² − 1 = 3,除以 log₂4 = 2,得 1.500,累计 9.131。

    DCG 第 3 步:模型排出的前三名真实评分 3、1、2;这一步算第 3 名,增益 3 除以 log₂4,得 1.500,这一格描成青绿;右边累计 DCG 为 9.131

怎么算

DCG(Y, k, π) = Σᵢ₌₀ᵏ⁻¹ (2^(Y_π[i]) − 1) / log₂(i + 2)

意思是:Y 是物品的真实评分列表,π 是模型给出的排列,Y_π[i] 是排在第 i + 1 位的物品的真实评分。对前 k 个位置,各自算「增益 / 折损」,再全部加起来。

注意用的是真实评分。模型只决定顺序,每个物品值多少由真实评分说了算。

常见误解

以为 DCG 里的评分是模型的预测分

是真实评分。模型的预测分只用来排出顺序 π,排好之后按真实评分算增益。

以为增益就是评分本身

课件的写法是 2^评分 − 1。评分 3 的增益是 7,不是 3。

试一下

k = 2,前两名真实评分是 2、3,DCG@2 是多少?

(2² − 1)/1 + (2³ − 1)/log₂3 = 3 + 7/1.585 ≈ 3 + 4.416 = 7.416。

3. NDCG:除以理想排序,压到 0 到 1

它解决什么问题

DCG 的大小和物品本身有关:一个用户的候选全是高分物品,DCG 怎么排都大;另一个用户的候选都是低分,怎么排都小。两个 DCG 没法直接比。除以「这批物品能拿到的最高 DCG」,就统一到了 0 到 1。

直觉

理想排列 πₛ 就是把真实评分从大到小排。它的 DCG 是这批物品能拿到的满分。模型的 DCG 除以满分,就是「拿到了满分的几成」。

一步一步看

目标:把模型排序的 DCG 除以理想排序的 DCG,看只排反两名时 NDCG 为什么仍接近 1。

  1. 模型排序:3、1、2,DCG ≈ 9.131(上一节算过)。

  2. 理想排序:把 3、1、2 从大到小排成 3、2、1。

  3. 理想 DCG:7/1 + 3/1.585 + 1/2 ≈ 7 + 1.893 + 0.5 = 9.393。

  4. 相除:NDCG@3 ≈ 9.131 / 9.393 ≈ 0.972。只是第 2、3 名排反了,所以接近 1。

    NDCG 归一化:上行模型排序 3、1、2,DCG 约 9.131;下行理想排序 3、2、1,DCG 约 9.393;右边青绿框 9.131/9.393,NDCG@3 约 0.972;只是第 2、3 名排反了,所以接近 1

怎么算

NDCG(Y, k, π) = DCG(Y, k, π) / DCG(Y, k, πₛ)

意思是:分子是模型排列的 DCG,分母是理想排列的 DCG,两者用的是同一批物品、同一个 k。比值在 0 到 1 之间,1 表示模型排得和理想排列一样好。NDCG 越大越好。

常见误解

以为理想排列要从所有物品里挑

理想排列是把同一批真实评分重新从大到小排。换了物品,分母就不是同一个标准了。

以为 NDCG 可能大于 1

理想排列是这批物品 DCG 的最大值,模型的 DCG 不可能超过它,所以 NDCG 最大是 1。

试一下

模型排出的前三名真实评分是 3、2、1,NDCG@3 是多少?

1。它本身就是理想排列,分子分母相等。

4. 两类评估指标怎样配对

它解决什么问题

到这里已经有两套指标:评分预测用的 MAE、RMSE,排序用的 NDCG。考试常让你说某个任务该用哪个、越大好还是越小好,配错了整题都错。

直觉

看任务输出什么。输出一个分数、要和真实分数比,就是误差类指标,越小越好。输出一个列表、要看顺序对不对,就是排序类指标,越大越好。

一步一步看

目标:先判断任务是猜评分还是排列表,看两类任务各配哪些指标,指标是越小越好还是越大越好。

  1. 先判断任务:猜具体评分,还是排出列表?

  2. 猜评分 → MAE、RMSE,误差越小越好。

  3. 排列表 → NDCG@K,以及课件只列了名字的 HR、MRR、MAP、Recall、Precision,越大越好。

    任务 典型方法 指标 方向
    评分预测 矩阵分解(逐点) MAE、RMSE 越小越好
    排序 BPR(成对) NDCG@K、HR、MRR、MAP、Recall、Precision 越大越好

怎么判断

指标名里带 Error(误差)的,越小越好;带 Gain、Rate、Precision、Recall 的,越大越好。

意思是:误差类量的是「错了多少」,所以要压小;排序类量的是「排对了多少」,所以要做大。

常见误解

把 NDCG 和 RMSE 混用

RMSE 评分数准不准,越小越好;NDCG 评顺序对不对,越大越好。BPR 这类只学顺序的模型,分数本身没有意义,拿 RMSE 去评它不对路。

以为课件详细讲了 HR、MRR 这些指标

课件只列了名字,没给公式。考试大概率只要求认出它们是排序指标。

试一下

一个模型的 RMSE 从 0.9 降到 0.85,另一个模型的 NDCG@10 从 0.6 升到 0.65。哪个是变好了?

两个都变好了。RMSE 越小越好,NDCG 越大越好。

把它们串起来

推荐列表的价值集中在前几名,所以评估要看位置。每个位置有一个折扣 1/log₂(i + 2),第 1 名不打折,越往后打折越多。

每个物品的增益是 2^评分 − 1,评分越高涨得越快。把前 K 名的增益打完折加起来,就是 DCG。

DCG 的大小受物品本身影响,不同用户之间没法比。除以理想排列的 DCG,压到 0 到 1,就是 NDCG。

评分预测配 MAE、RMSE,越小越好;排序配 NDCG 等,越大越好。前面讲的模型都还在用内积打分,下一页换成神经网络。

课件里的坑

  • [读图提醒] 求和下标 i 从 0 到 k − 1,第 1 名对应 i = 0,所以分母是 log₂(i + 2)。有的教材让位置从 1 开始、分母写 log₂(i + 1),两种写法算出来一样,只是编号起点不同,答题跟课件的写法(p.43)。
  • [课件留白] HR、MRR、MAP、Recall、Precision 课件只列了名字,没给公式和例子(p.43)。
  • [页码提醒] 课件右下角页脚数字比 PDF 页序小 1,本页的 p.N 都按 PDF 页序。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写 DCG 和 NDCG 两个公式;再读必背 5 条;然后做课件例题;最后用完整例题和变式题把 NDCG 完整算两遍,log₂3 ≈ 1.585 要记住。

必背

  1. DCG(Y, k, π) = Σᵢ₌₀ᵏ⁻¹ (2^(Y_π[i]) − 1) / log₂(i + 2):分子是增益,分母是位置折损
  2. i 从 0 起,第 1 名分母 log₂2 = 1 不打折,越靠后打折越多
  3. NDCG = DCG(π) / DCG(πₛ),πₛ 是把真实评分从大到小排的理想排列,结果在 0 到 1 之间,1 表示排序完美
  4. 评分预测用 MAE/RMSE,越小越好;排序用 NDCG@K 等,越大越好
  5. 其他排序指标:HR、MRR、MAP、Recall、Precision

课件例题

例 1(课件 p.43):NDCG@K 公式怎么读?

题面:DCG = Σᵢ₌₀ᵏ⁻¹ (2^(Y_π[i]) − 1) / log₂(i + 2);NDCG = DCG(π) / DCG(πₛ),πₛ 是从大到小的理想排序。

提示

i 从 0 开始,第一名的分母是 log₂2。

解答

分子是增益,评分越高越大;分母是位置折损,第一名 log₂2 = 1 不打折,越往后打折越多。除以理想排序的 DCG 做归一化,结果在 0 到 1 之间,越大越好。

完整例题

题面(自编情境):k = 3,模型给出的前三名真实评分为 (3, 1, 2),求 NDCG@3。

解法:

  1. 增益:2³ − 1 = 7,2¹ − 1 = 1,2² − 1 = 3。
  2. 折损:log₂2 = 1,log₂3 ≈ 1.585,log₂4 = 2。
  3. DCG:7/1 + 1/1.585 + 3/2 ≈ 7 + 0.631 + 1.5 = 9.131。
  4. 理想 DCG:顺序 (3, 2, 1),7 + 3/1.585 + 1/2 ≈ 7 + 1.893 + 0.5 = 9.393。
  5. NDCG@3 ≈ 9.131 / 9.393 ≈ 0.972。

要点:第 1 名分量最重,这里第 1 名排对了,只是后两名对调,所以只掉了一点。

答题格式:先列三项增益和折损,再写 DCG,再写理想排列和理想 DCG,最后相除,保留三位小数。

变式题(先自己做)

自编情境:

(a) k = 3,前三名真实评分为 (0, 2, 1),求 NDCG@3。 (b) k = 2,前两名真实评分为 (1, 3),求 NDCG@2。

提示

评分 0 的增益是 2⁰ − 1 = 0。先排出理想顺序,再分别算两个 DCG。

判分点与答案(非官方评分标准)

判分点:① 增益用 2^评分 − 1;② 分母 log₂(i + 2),i 从 0 起;③ 理想排列是同一批评分从大到小排。

(a) DCG = 0 + 3/log₂3 + 1/2 ≈ 1.893 + 0.5 = 2.393;理想 (2, 1, 0):3 + 1/1.585 + 0 ≈ 3.631;NDCG ≈ 0.659。

(b) DCG = 1/1 + 7/1.585 ≈ 1 + 4.416 = 5.416;理想 (3, 1):7 + 1/1.585 ≈ 7.631;NDCG ≈ 0.710。

闪卡自测

1. NDCG 的分母为什么是 log₂(i + 2)?

i 从 0 开始,第一名分母 log₂2 = 1 不打折,越靠后折损越多(p.43)。

2. DCG 的增益怎么写?评分 3 的增益是多少?

2^评分 − 1,评分 3 的增益是 7(p.43)。

3. πₛ 是什么?

把真实评分从大到小排的理想排列(p.43)。

4. NDCG 的取值范围和方向?

0 到 1,越大越好,1 表示排序完美(p.43)。

5. 课件还列了哪些排序指标?

HR、MRR、MAP、Recall、Precision(p.43)。

6. 评分预测和排序分别用什么指标?

评分预测用 MAE、RMSE,越小越好;排序用 NDCG@K 等,越大越好(p.34、p.43)。

下一讲

下一页 L08f 讲深度推荐模型:把矩阵分解画成神经网络,再用多层网络替换固定的内积,得到 NCF 和 NeuMF;最后看工业推荐引擎怎样用多级漏斗把千万级候选缩到几十个。

下一讲 →
L08f L08f NCF 与 NeuMF:让神经网络来学用户和物品怎么匹配

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。