本文是作者开发gorse过程中做的笔记,主要偏向于算法和思想,具体的实现见GitHubGoDoc,如有错误,恳请指正。

前言

在前一篇博文《实现推荐系统引擎(一):评分预测》中已经简单地介绍了一些常用的评分预测算法,其中基于矩阵分解的算法已经到达了非常高的准确度,虽然之后有很多人提出了准确度更高的建模方法,但是提升的效果非常有限。然而,上一篇文章介绍的方法在很多现实情况中通常没有什么用,主要原因有:

  • 评分数据不常见:虽然非常多的网站都向用户提供了评价的功能,但是积极参与评价的用户还是少数,毕竟很多人连收货都懒得确认。如果一定要使用评分,那么可用的数据将会非常稀少,况且很多场景下甚至不存在用户评分。
  • 最终目的是排名:推荐系统在做完预测之后,最终需要将物品展示给用户,最好是用户需要的物品,至于用户最终会给物品打多少分并没有那么重要。

因此,本文主要介绍使用隐式反馈进行物品排序的推荐模型。隐式反馈也就是常见的用户交互记录,例如淘宝的购买记录、Steam游戏的游戏时间等不显式体现用户喜好程度的数据。排名模型也会产生一个评分,具体的数值用于最终的排序而不是拟合用户评分。

评估验证

在介绍物品排序的推荐算法之前,首先了解一下物品排序的一些评估方法。评分预测模型可以根据评分对物品进行排名,而针对物品排序的推荐算法则可以选择直接以评估方法作为损失函数进行模型优化,例如BPR优化AUC、CLiMF优化MRR。

用户能够接收的推荐的条目也是非常有限的,因此每个用户的推荐内容就是取N个最有可能受用户喜爱的物品(Top-N列表),记得要将已经在训练集中出现的物品去掉,最后与测试集中用户选择的物品进行比较,给出评估结果。为了表述方便,数学符号的定义如下

符号 含义
全体物品集合
测试集中和用户产生交互的物品集合
向用户推荐的物品列表(不包含在训练集中出现过的物品)
  • Precision:准确率评估的是推荐列表里包含了多少用户“想要”的物品,整个测试集的准确率取所有用户准确率的平均值
  • Recall:召回率评估的是用户“想要”的物品有多少被包含在了推荐列表里,整个测试集的召回率取所有用户召回率的平均值
  • MRR:平均倒数排名更像是为搜索引擎设计,将针对每个用户的推荐视为一次查询,将首个有关物品的排名的倒数作为本次查询的评估标准,因此对于$\mid U\mid$个用户而言,

显然排名从1开始到N,如果没有一个物品匹配,那么结果为0,排名等于无穷。

  • MAP:平均准确率均值,向一个用户推荐的平均准确率定义为

其中表示到第i个物品为止的准确率 简单地说就是将推荐列表中所有到每个匹配物品为止的准确率想加,最后除以测试集中用户选择的物品的数量。

  • NDCG:NDCG的定义为,DCG为

而iDCG为最佳的DCG情况,也就是用户喜爱的物品全部位于推荐列表前部,整个测试集的NDCG为所有用户的NDCG平均值。

  • AUC:AUC意为曲线下面积,直观上的理解就是用户喜爱的物品的排名要比其他物品高

推荐算法

BPR1:贝叶斯个性化排名

之前介绍的矩阵分解算法使用SGD或者ALS来优化平方差损失函数,优化的目标是尽可能拟合用户的评分。然而,在排序问题中,准确预测用户的评分其实并不重要,而且隐式反馈是没有评分的,因此BPR算法以AUC为损失函数对模型进行优化。对于用户以及物品,优化目标函数为

其中,由矩阵分解模型产生。从而BPR训练算法每次更新参数的方法为:

  1. 从训练数据集中采样三元组,其中i为正样本(和用户u有过交互),j为负样本(和用户u没有交互)
  2. 更新参数:

反复执行上述步骤直到算法收敛,参数的梯度为

WRMF2:带权正则矩阵分解

在有些场景下,虽然没有得到用户具体的评分,但是能够得到一些类似于“置信度”的信息,例如用户的游戏时长、观看时长等数据。虽然时长信息不能直接体现用户的喜好,但是能够说明用户喜欢的概率更大。在此场景下,用户-物品记录可以表示为一个置信度和一个0-1指示量(用户-物品是否有交互),如果用户-物品没有交互,那么置信度就为0。“带权”就是根据置信度计算每条记录对应损失的权重,优化的目标函数就是

权重通过置信度计算得到,可以使用。由于未发生的交互也存在于损失函数中,因此惯用的随机梯度下降存在性能问题,为此采用ALS来优化模型,一次训练过程如下:

  1. 更新每个用户的向量:
  2. 更新每个物品的向量:

其中分别为n个用户向量和m个物品向量组成的矩阵,f为向量长度。中只有在对角线上,其他位置上均为0,类似。另外,这两个矩阵非常巨大,因此可以分解为,矩阵中大部分为0,只需要计算非零部分即可。

总结

以上就是gorse中实现的两个排序专用模型,除此之外还有很多排序模型还有提及,例如针对MRR优化的CLiMF3、以及改进训练采样的AoBPR4等,由于精力有限无法一一实现。

参考文献

  1. Rendle, Steffen, et al. “BPR: Bayesian personalized ranking from implicit feedback.” Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence. AUAI Press, 2009. 

  2. Hu, Yifan, Yehuda Koren, and Chris Volinsky. “Collaborative filtering for implicit feedback datasets.” Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on. Ieee, 2008. 

  3. Shi, Yue, et al. “CLiMF: learning to maximize reciprocal rank with collaborative less-is-more filtering.” Proceedings of the sixth ACM conference on Recommender systems. ACM, 2012. 

  4. Rendle, Steffen, and Christoph Freudenthaler. “Improving pairwise learning for item recommendation from implicit feedback.” Proceedings of the 7th ACM international conference on Web search and data mining. ACM, 2014.