KDD‘20 Best Paper | 推荐系统中采样测试的误区
阅读更多，欢迎关注公众号：论文收割机（paper_reader）
因为排版问题，很多图片和公式无法直接显示，欢迎关注我们的公众号点击目录来阅读原文。
CSDN上排版不好，可以直接点击链接阅读原文
Walid Krichene and Steffen Rendle. 2020. On Sampled Metrics for Item Recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '20). DOI:https://doi.org/10.1145/3394486.340322
引言
这篇论文是推荐系统大佬Rendle的新作，在投KDD之前，就已经挂在网上了。这篇论文主要对现在推荐系统（recommender system）中常用的基于sample的evaluation方法进行探究。基于sample的evaluation其实是为了解决计算资源不足的问题。
尤其在推荐系统中，最终测试的时候一般需要对item进行排序（ranking），然后计算出rank at K的score，比如[email protected]，[email protected]。item数量往往会很多，比如benchmark的item数量，一般10k级别的，而一些企业级的item数量可能达到million级的。
所以如果每个user ranking的结果都要计算所有对item的score，对于计算资源的要求是非常高的。因此，evaluation的时候，例如在NCF[He, Xiangnan, et al. "Neural collaborative filtering." ]中，往往先sample出100个negative items，再与ground truth item一起进行ranking排序，如果ground truth item排序高于sample出来的negative items，则表示模型的performance好，若比sample出来的negative item ranking低，则表示模型的performance差。
这种基于sample的evaluation方法，按照通常的思路，如果多做几次实验，从期望上来看可以得到与完整测试（full evaluation）一样的score。但是通过这篇文章，rendle对这种Sampled Metrics提出了质疑，并且从理论和实验中得出了sampled metrics和exact metrics之间可能并不一致的结论，同时还设计了校正的算法（correction algorithm）。
可以说，这篇文章，是推荐系统领域一个非常重要的工作，部分推翻了已有的很多工作的结论，并且也为以后的工作提供了理论上的支持。
Evaluation Metrics
推荐系统中对模型的evaluation一般是基于ranking的，即一个推荐算法，对每个user会有排好序的推荐item list。而评估这个ranking的质量，是通过给定ground truth items，也就是用户有过交互，但是没有出现在训练集中的items，也叫做相关items（relevant items）。评估一个推荐算法的质量，是将这些相关items排序比不相关的items靠前，即算法会对一个user产生一个ranking R，例如R=｛3，5｝代表user的两个相关的items分别排第3和第5。此时，只需要计算该ranking R的score，就可以评估该推荐算法的质量。
基于这样的评估方法， 我们可以设计不同的evaluation metrics：
AUC：模型将相关items排序高于不相关items的可能性（likelihood）
Precision at k：前k个items中，相关items所占的比例
Recall at k：前k个items中相关的items，占所有相关items的比例
Average Precision（AP）at k：前k个items中每个相关item在rank的precision的均值
NDCG at k：与AP类似，但是越靠前的relevant item评分更高：
为了便于分析evaluation中存在的问题，可以将R简化成，只有一个relevant item的ranking，因此|R|=1，同时对应的metrics简化为：
另外，其他一些主流的metrics也可以用这些metric表达出来，比如reciprocal rank与AP相等，hit ratio与Recall相等，accuracy与[email protected]和[email protected]
例如，将一个相关item放在不同的rank（总共10000个item）上，我们计算对应的metric，可以得到如下的图
缩小观察1<rank<100中的图像为
可以看出，除了AUC，其他metrics，只对rank靠前的结果给出不错的score，而靠后的（tail）的rank基本上没有值。这也是推荐系统中的一个特性，用户基本上不会看到推荐列表靠后的item，所以给出很低的score也是合理的。
为了讲清楚之后的问题，以及如何通过metrics来对比不同的推荐系统，我们给出一组示例：
表1 三个推荐系统的结果及对应的metrics值
通过表1可以看到三个推荐系统ABC，对5个relevant items的排序是不同的，此时算出来的metrics也是完全不同的，A系统在AUC这个指标下表现最好，而C系统在另外三个指标下的表现更好。
这个三个系统的不同点在于：
-
A系统对相关items排序基本上都不高不低，但是因为item数量很多（10K）所以AUC表现很好，而其他三个指标，尤其是recall，都是比较低的值。
-
B系统对其中两个relevant items排序比A系统要好，排到了40，而其他的都很差，所以整体的AUC表现很差。
-
C系统只对一个相关item排序很好，排到了rank 2，其他的表现都很差，所以此时AUC也是较差，但是另外三个指标都很好。所以可以看出其他三个指标是对靠前的相关item更加敏感，会给出更高的score，这也符合推荐系统的衡量标准——越靠前越好。
Sampled Metrics (采样评估)
由于items数量太多，每个item的rank都算出来再找到相关item的排序位置是不现实的，所以往往会进行采样评估来近似评估不同推荐系统的质量。sampled metrics需要保持对原始评估的一致结果，即A系统在原始metrics下好于B系统，那么A系统在sampled metrics也应该好于B系统。因此，可以得到这样的一致性（consistency）定义：
定义1（一致性）：如果评估数据是固定的，在某个metric M下，如果两个推荐系统的相对关系在采样评估和非采样评估时是在数学期望下相同的，则该metric是具有一致性的。也就是说，对任意两个推荐系统A和B，有：
M(R(A,x))是指在M metric下，A推荐系统的ranking R; 是指在sampled metric M下， A推荐系统的ranking。
那么，问题来了。之前提出的metrics在采样的情况，是否还能保持这样的一致性呢？
还是表1中的例子，ABC三个推荐系统，分别使用采样评估，也就是说我们不再算所有item的score之后再排序找到relevant item的rank，而是只sample 99个negative items，再与该relevant item放在一起排序。
通过计算该sampled ranking的score，来评估三个推荐系统的质量。那么采样评估的结果是怎么样的？如下表
表二 采样评估的metrics值
可以发现，除了AUC仍然维持不变，其他的指标与之前exact metric（表一）完全不一样了。表一中C在AP, NDCG, Recall三个指标下都是最好的模型，而采样评估中的表二显示，C比A差了很多，所以sampled metrics在评估推荐系统质量上，得出了与exact metrics完全相反的结论。甚至，sample的数量对评估推荐系统质量的影响是至关重要的，如下图
随着sample数量从0增加到1000，三个推荐系统的NDCG逐渐变化，显示A最好，后来逐渐变成C最好，中间BC还会有交点。而这样的sample数量的多少在之前的工作中从来都没有讨论过。
其实这样的结论也是很好理解的。A推荐系统将每个item都排在100的位置，这时候sample出来的99个negative items，因为总共10,000个item，所以都大概率（99%）都是在rank 100之后的。此时sampled metrics会高很多。除了NDCG意外，其他的几个metric的一致性也是与samples的数量高度相关。
而只有AUC的一致性是与sample数量无关的
所以可以看到，使用sampled metrics来分析推荐系统的质量，本身就是一个不准确的评估，只有当sample的数量足够多，才能保证与exact metrics是一致的。因此，可以看出已有的一些工作，往往只sample一个negative一百个negative items，其实是非常不可靠的评估。
采样评估的数学期望
为了进一步研究采样评估（sampled metrics）的特性，我们将relevant item的排序设置为一个随机变量r。此时任意sample出来一个item j，它的rank比r靠前的概率为：
而重复采样，可以将sample出来的不相关item靠前看成是n次二项分布，而m次二项分布为1，也就是最后sample metrics中这个相关item的排序为m+1（因为sample出了m个比相关item靠前的不相关item）。所以，sampled metrics中，该相关item的排序$\Tilde{r}$的期望为
可以看出该数学期望是sample总数m，以及相关item真实排序r的函数，即E=f(m,r)。画出不同metrics的曲线，分别为
可以看到，其他metics当sample 数量m比较小的时候，都表现出与r呈线性相关的特性，而实际上的值（sample数量大时）其实变化是非常剧烈的（sharp）。有了sampled metrics中ranking的分布，其实就可以得到所有metrics的数学期望了：
同时，因为有了sampled metric的期望，那就可以针对sampled metrics来设计新的metrics，从而得到更好的基于sample的metrics。因此，有了对采样评估的校正（correction）。
采样评估的校正
为了解决采样评估中不准确的问题，可以设计三种不同的校正方法：无偏估计（unbias），最小偏置（minimal bias），BV-权衡（bias-variance trade-ff）。
无偏估计比较直接，其实就是对该随机变量$\Tilde{r}$找到它的无偏估计量，直接按照公式计算可以得到：
最小偏置估计，需要将这个bias最小化，引起是一个优化问题，最后的解就是所需的校正metrics。最小偏置因为是一个优化问题，也被叫做CLS（constrained least squared）方法：
BV-权衡估计是将bias和variance共同考虑进sampled metrics的计算中，最后得到：
如果γ=1时，BV估计写成：
实验
通过实验验证sampled metrics与corrected metrics之间的对比：
可以看出，直接sampled metric与exact metric之间差距较大，而校正过的metrics与exact metric之间差距很小。
表三 在movielens数据集上，XYZ三个推荐系统在不同metrics下的值
上表三，也证明了经过校正之后的metrics，与实际值之间更加接近。
结论
本文研究了推荐系统中在测试时经常用到的sampled evaluation的方法，并且对该方法进行了严格的理论分析。结论证明基于ranking的sampled metrics会对评估推荐系统的质量造成很大的影响。sample的数量也会直接影响对比两个推荐系统的好坏。所以，之前的很多文章，直接使用一个negative sample，或者哪怕几十上百个negative sample，都是非常错误的评估方法。同时，本文还提出了三种不同的校正方法，这个在未来的研究工作中，也是非常具有实际价值的。在无需非常严格的计算数值，而只是需要找到合理的评价推荐系统或者说ranking质量的好坏时，只需要使用本文设计的几种针对性的校正metrics 就可以得到较为准确的评估结果。
这篇文章出发点非常好，思路看起来简单，但是得出的结论又是非常有趣的，同时研究问题非常深入，解决的方法也是直接有效。整个文章读起来也是非常舒服。所以强烈推荐大家点击阅读原文来下载原文阅读。
阅读更多，欢迎关注公众号：论文收割机（paper_reader）
因为排版问题，很多图片和公式无法直接显示，欢迎关注我们的公众号点击目录来阅读原文。
往期文章：