Introduce and achieve NDCG

本文主要介绍一个 Search 和 Recommend 中常用的一个评估指标：NDCG。
NDCG（Normalized Discounted Cumulative Gain）可以翻译为归一化折损累计增益，通常用来衡量和评价 ranking 的准确性。比如在电商系统，用户一个 query 会返回一个商品列表，假设列表长度为 N，可以用 NDCG@N 评价该列表的排序与真实交互列表的差距。

Cumulative Gain#

CG (累计增益) 是搜索结果列表中所有文档的分级相关性得分的总和。CG 只考虑了搜索结果列表中结果的相关性，而没有考虑这些文档在结果列表中的位置因素。给定一个结果列表的排序位置 $p$ ，可定义为：

$CG_p = \sum_{i=1}^p rel_i$

其中 $rel_i$ 表示第 $i$ 位置上的相关性。
比如用户在某个电商平台搜索「手机」。结果的前 6 个结果分别是：iPhone，xiaomi，Huawei，OPPO, VIVO，三星。而用户更倾向于选择的是 Huawei，这时候无论华为手机排在前 6 的任何一位，对于累计增益都是等价的。但是对于 search，recommend 系统来说，最好的结果是 Huawei 手机放在第一个，因此引出下一个指标，折损累计增益。

Discounted Cumulative Gain#

DCG (折损累计增益) 提出，在搜索结果列表较后面位置出现相关性较高的结果时，应该对评测得分施加惩罚。惩罚比例与文档的所在位置的对数值相关。给定一个列表结果的排序位置为 $p$ ，DCG 可以定义为：

$DCG_p = \sum_{i=1}^p \frac{rel_i}{log_2(i+1)}$

还有一个比较常用的公式，它能用来增加相关度影响的比重：

$DCG_p = \sum_{i=1}^p \frac{2^{rel_i}-1}{log_2(i+1)}$

后面这个公式更常用，在多数的搜索公司和电商平台。
当相关性得分 $rel_i\in(0,1)$ ，即取值只有 0 和 1 时，上面两个公式是等价的。

Normalized Discounted Cumulative Gain#

NDCG (归一化折损累计增益) , 回到文章开始提到的 NDCG。NDCG 认为搜索结果的长度因 query 而异，仅使用 DCG 对不同 query 的 performance 的比较不具有一致性。因此，对于所选择的 $p$ 值，每个位置的 CG 应该在 query 上做规范化，首先对库里所有相关的结果按相关性排序，在通过位置 $p$ 生成最大可能的 DCG , 通常称为 IDCG (理想 DCG) 。对于一个 query，NDCG 可以如下计算：

$NDCG_p = \frac{DCG_p}{IDCG_p}$

其中 IDCG 为理想状态下的 DCG，计算方式为：

$IDCG_p = \sum_{i=1}^{|REL_p|} \frac{2^{rel_i}-1}{log_2(i+1)}$

$REL_p$ 表示库里相关性最高的 $p$ 个结果列表（按相关性排序后）。
对所有 query 的 NDCG 值取平均，来评判搜索引擎 Ranking 算法的平均 performance。NDCG 值越大，Ranking 算法 performance 越好。在一个完美的 Ranking 算法里， $DCG_p$ 和 $IDCG_p$ 应该是相等的，此时 NDCG 的值为 1。而 NDCG 值最小为 0，所以 NDCG 的值分布在 0 到 1 之间。它是一个相对值，因此可以跨 query 进行比较。

计算举例#

按前文提到的用户搜索 query 为「手机」并返回 6 个结果为例，按结果为：iPhone，xiaomi，Huawei，OPPO, VIVO，三星，分别对应相关性得分为 3，2，3，0，1，2
那么，对应的 CG 为：

$CG_6 = \sum_{i=1}^6 rel_i = 3 + 2 + 3 + 0 + 1 + 2 = 11$

改变任意两个结果的顺序并不会影响 CG 计算的最终结果。DCG 用于强调出现在结果列表前面的高度相关的结果。使用对数进行归约，每个结果的 DCG 依次为：

${i}$	${rel_i}$	$2^{rel_i} - 1$	${log_2(i + 1)}$	$\frac{rel_i}{log_2(i+1)}$	$\frac{2^{rel_i}-1}{log_2(i+1)}$
1	3	7	1	3	7
2	2	3	1.585	1.262	1.893
3	3	7	2	1.5	3.5
4	0	0	2.322	0	0
5	1	1	2.585	0.387	2.585
6	2	3	2.807	0.712	1.069

用第一个 DCG 公式计算如下：

$DCG_6 = \sum_{i=1}^6 \frac{rel_i}{log_2(i+1)} = 3+1.262+1.5+0+0.387+0.712 = 6.861$

再用第二个 DCG 公式计算如下：

$DCG_6 = \sum_{i=1}^6 \frac{2^{rel_i}-1}{log_2(i+1)} = 7+1.893+3.5+0+2.585+1.069=16.047$

现在将第 3 个结果和第 4 个结果位置交换，会导致 DCG 降低。因为相关性较低的结果在排序中排名靠前，也就是说，一个更相关的结果被放在一个较低的位置上被更多地折损。
这个 query 的 performance 在这种情况下是没法比较的的，因为另一个 query 可能有更多的结果，导致更大的 DCG，但不一定代表这个 query 的 performance 更好。为了进行比较，必须对 DCG 值进行归一化。
为了归一化 DCG 的值，需要对给定 query 进行理想的排序。在本示例中，该排序将是所有已知相关性判断的单调递减排序。除了这个示例中的 6 个结果之外，假设我们还知道有一个结果 7 的相关性分数为 3，而一个结果 8 的相关性分数为 2。那么理想的排序是：

$3, 3, 3, 2, 2, 2, 1, 0$

m 没有第 7、8 个结果时，理想排序是

$3, 3, 2, 2, 1, 0$

理想排序的 DCG 或称为 IDCG, 计算前 6 个位置

$IDCG_6 = 3/1+3/1.585+2/2+2/2.322+0.387+0/2.807=7.141$

所以给定这个 query 的 NDCG 可计算为：

$NDCG_6 = \frac{DCG_6}{IDCG_6} =\frac{6.861}{7.141} = 0.961$

Python 代码计算 NDCG#

import numpy as np

def get_dcg(rec_list):
    log_2 = np.log2(np.arange(2, len(rec_list) + 2))
    mi = np.power(2, rec_list) - 1
    dcg = np.array(mi / log_2).sum()
    return dcg

if __name__ == "__main__":
    rec_list = [3, 2, 3, 0, 1, 2]
    sort_rec_list = [3, 3, 2, 2, 1, 0]
    dcg = get_dcg(rec_list)
    idcg = get_dcg(sort_rec_list)
    print("ndcg = dcg / idcg = ", dcg/idcg)

Reference#

https://en.wikipedia.org/wiki/Discounted_cumulative_gain