协调过滤(1):Fast Matrix Factorizatio
20200914更新:把之前上传失败的图片重新上传了一遍
对相关研究感兴趣的朋友欢迎交流
简介
- 阅读论文:Fast Matrix Factorization for Online Recommendation with Implicit Feedback
- 由于个人研究的方向为推荐算法,因此阅读分享该篇论文;该文提出了针对隐式反馈数据的快速矩阵分解方法,具有实际应用价值。
- 相关领域:信息检索-推荐领域Recommender System
- 关键词: Matrix Factorization,Implicit Feedback,Online Learning,ALS
- 论文类型: 信息检索顶级会议论文(ACM SIGIR2016)
- 引用量:323
论文主要内容
问题及方法
问题
矩阵分解(Matrix Factorization,MF) 是推荐中常用的算法,隐式反馈数据是实际场景常见的数据,隐式反馈可简单为用户与物品的间接交互关系(如点击、收藏等,无法直接反映用户对物品的喜好程度)。
论文针对当前针对隐式反馈的MF研究中存在的两个关键问题:
- 在推荐中,数据存在严重的稀疏性,由于数据缺失严重,目前的MF方法中常常会给缺失的数据赋统一的权重以降低计算复杂度。
- 大多数的MF方法只适用于线下(静态数据),无法适应线上的动态数据。
提出的方法
论文针对上述隐式反馈MF方法研究中存在的问题,提出以下方法:
- 基于物品流行度(item-popularity)对缺失数据进行加权,比传统的统一权值更合理。
- 基于元素级交替最小二乘法(element-wise Alternating Least Squares,eALS) 提出新的MF求解方法;
- 在此基础上,设计了参数增量更新策略,以支持在线推荐。
相关知识
该篇论文属于推荐领域内的专业论文,需要一些相关的基本知识,在此对几个关键的知识进行总结回顾:
隐式反馈
(1) 没有负反馈。通过观察用户的行为,我们可以推断出他们可能喜欢哪些项目,从而选择消费。然而,很难可靠地推断出用户不喜欢哪些项目。例如,没有观看某个节目的用户可能是因为她不喜欢该节目,或者只是因为她不知道该节目或无法观看该节目。这种基本的不对称性不存在于明确的反馈中,用户告诉我们他们喜欢什么,不喜欢什么。
(2)隐式反馈本质上充满噪声。当我们被动地跟踪用户的行为时,我们只能猜测他们的偏好和真正的动机。例如,我们可以查看个人的购买行为,但这并不一定表示对产品有正面的看法。该商品可能是作为礼物购买的,或者用户对该产品感到失望。
(3)显式反馈的数值表示偏好,而隐式反馈的数值表示置信。The numerical value of explicit feedback indicates preference, whereas the numerical value of implicit feedback indicates confidence. 基于显式反馈的系统允许用户表达他们的偏好水平,例如1(“完全不喜欢”)到5(“真正喜欢”)之间的星级。另一方面,隐式反馈的数值描述了动作的频率,例如,用户观看某个节目的时间、用户购买某个节目的频率等等。值越大并不表示偏好越高。例如,最受欢迎的节目可能是用户只看一次的电影,而有一个用户非常喜欢的系列,因此每周都在看。
然而,反馈的数值肯定是有用的,因为它告诉我们在某个观察中的信心。一次性事件可能由与用户首选项无关的各种原因引起。但是,重复发生的事件更可能反映用户的意见。
(4)对隐式反馈推荐的评价需要适当的措施
矩阵分解(MF)
矩阵分解算法是推荐中最为基础而常用的算法,能够很好地解决推荐中评分预测的问题。
基本思想是:将用户-物品交互矩阵,个 用户,个物品,分解成为两个矩阵和的乘积:
和分别代表用户潜在特征矩阵和物品潜在特征矩阵(Latent Factor matrix).(注:此处用到的矩阵分解算法为常见的Latent Factor形式)
在实际推荐计算中不再利用R推荐,而是利用分解得到的两个矩阵选取相关用户物品的向量,利用向量乘积做推荐。如计算用户u对于其未交互的物品(unobeserved data)的评分值可以如下式表示:
其中后两项为偏置项,反映用户u和物品i的偏置信息,则为从特征矩阵中获取的向量
为了求解出两个矩阵,将损失函数定义如下(使用了基本的平方误差):
针对上式,常规解法是利用随机梯度下降算法(SGD)进行参数迭代求解;另一种算法则是交替最小二乘法,下小节将具体介绍ALS。
ALS
首先回顾最小二乘法的知识
给定数据
求线性关系 中的参数
推广更普遍的情况,用矩阵形式进行表示,所求线性关系为
以上即为最小二乘法的基本公式
矩阵分解的损失函数中待求量为,两个变量,单一的最小二乘法仅能解决只有一个待求矩阵形式的问题;
在此需要对问题做转换以利用最小二乘法,
ALS的基本思想是固定其中一个变量,对剩下的变量利用最小二乘法求解。
具体步骤如下:
- 初始化
-
计算用户矩阵,固定
为向量,大小为
矩阵求导中
y的转置等于y
为单位矩阵
-
计算物品矩阵 ,固定
为单位矩阵
- 重复步骤2和3,对矩阵进行不断迭代更新,至满足停止条件
注意上式公式中的一些小细节,主要是利用矩阵求导的一些知识,
https://blog.csdn.net/L_15156024189/article/details/84952633
以及对原始损失函数的分析。
- 时间复杂度:
ALS为:。
与SGD相比,ALS算法复杂度比较高;但主要优势在于可以进行并行计算,大数据平台spark中就包含ASL算法的实现。
对于电商系统,数据量非常大,利用SGD训练MF几乎不可能。这时就需要使用ALS进行MF训练计算。
处理隐式反馈的MF
传统方法
对于交互矩阵,M,N为用户和物品数量
表示矩阵中非0的元素集合,即观察到的数据
向量表示用户u的潜在特征向量,表示用户u交互过的物品集合
向量 表示物品i的潜在特征向量, 表示与物品i交互过的用户集合
为用户特征矩阵
为物品特征矩阵
K表示特征向量的维度, 中每个元素 可以数学表示为:
在物品推荐中,最终要跟评分函数值对推荐结果进行排序,可以添加偏置信息
其中即表示权重因子,用代表权重矩阵
后两项则是L2正则化项。从上式中可以看出,这种算法将缺失值设为0,且缺失值权重非0;这一设定会严重影响算法的性能。
基于物品流行度非统一赋权的MF
论文指出:由于物品的量级较大,缺失值往往包涵负向反馈或者未知反馈,因此为缺失值和观察值简单地赋同样的权重是不合理的
因此论文提出利用物品的属性进行赋权操作:对观察到的值和缺失值分别赋权:
其中表示确信用户u没有看过的物品i是真正的负向样本(用户不喜欢),可以用作对从业人员的领域知识进行编码的一种手段。
显然,第二项解释缺失数据的作用,它充当否定实例的角色,对于隐式反馈的建议至关重要。
关于的赋值策略,论文提出基于物品流行度进行确定:
目前网络中通常来说流行的物品更有可能被用户了解,因此可以进行一个合理推测:对于一个用户而言,忽略掉一个流行的物品很有能是因为用户不喜欢该物品
基于这个推测,对参数化:
其中表示物品j的流行度(计算频率即可),定义缺失数据的总权重,用于控制缺失数据对模型的影响程度;
指数控制着流行物品相对于不流行物品的显着性水平---当> 1时,促进流行物品的权重以加强与不受欢迎商品的区别,在(0; 1)的较低范围内设置时,可以抑制受欢迎商品的重量,并具有平滑效果。
论文中根据经验取值0.5。
eALS
通用eALS方法
ALS算法主要的计算瓶颈在于矩阵操作矩阵求逆,矩阵转置,这样设计的好处在于可以一次性更新一条特征向量。
很自然地可以想到从元素级别进行更新,而非向量级,即固定特征向量的其他维度,优化某一维。
对普通的MF方法的损失函数进行简单修改:
将向量乘积的形式重新表示成元素和式的形式,如上式所示;则可以从元素级进行求导计算(注:本部分为个人对公式的理解推导,论文中的公式省去了很多推导过程)
令
,这样转换的目的是为了直接得到与某一维元素相关的数据,利于后续求导:
在此式基础上,(仍然是ALS的思想)对目的矩阵的各个元素进行求导,即某向量的某维度进行求导:
上述求导过程中,原式最后一项相当于常数项可以忽略,第一项求导稍有点麻烦,可以把平方式拆开进行计算,最后得到上式。
令导数为0,即得到:
同理得到:
基于该推导结果进行MF的求解,完整步骤如下图所示:
时间复杂度分析
传统ALS对一个大小的矩阵求逆需要,那么更新一个用户潜在向量需要,那么完成所有迭代更新的复杂度为
由于省去了大量的矩阵计算过程(求逆),那么时间复杂度将会消去,下降到的量级,由此可见eALS的高效性
Fast eALS
对于本文提出的MF:
按照ALS的思想对两变量分别计算:
其中计算瓶颈在于对缺失值的处理,需要对整个负空间求和,对相关部分公式逐一考察:
先考察分子上的项,对其进行拆分,转换成整体减去正例的形式:
[图片上传失败...(image-e106a5-1582186303713)]
上式中主要计算量是,每次都会迭代计算该项;然而该项与u无关,因此可以提前计算并存储,之后的每次运算只需从cache中查找即可,这将大大提升计算速度。
定义cache ,提前计算该部分并存储,用于后续的向量值更新:
[图片上传失败...(image-c4f548-1582186303713)]
计算复杂度为,同理对分母的式子做相同的优化:
[图片上传失败...(image-e2d4d7-1582186303713)]
最终的计算公式为:
[图片上传失败...(image-64cddc-1582186303713)]
时间复杂度
Fast eALS的复杂度为
并行学习与在线更新
论文也指出 Fast eALS支持并行计算:
- 计算S缓存时,矩阵乘法可以使用很多工具包实现并行
- 在更新不同用户/物品的潜在向量时,共享参数独立或保持不变,因此可以利用并行计算。
论文同时提出了eALS的在线更新算法,即增量学习算法:
[图片上传失败...(image-314f2e-1582186303713)]
对于新的交互数据,进行局部更新,对于新数据赋于新的权重。
实验效果
论文在Yelp和Amazon两个数据集上进行大量的对比实验,包括线下和线上实验,与一些经典的算法进行了对比(ALS,RCD,BPR)佐证了提出的算法的推荐质量高和速度快。在此仅展示部分:
[图片上传失败...(image-c86b37-1582186303713)]
使用了推荐领域常用的评价指标HR,NDCG进行评价,可以看出eALS迭代速度快,且效果优于其他两类算法。
[图片上传失败...(image-95a325-1582186303713)]
总结
该论文针对隐式反馈MF中的问题,从基本原理出发,对求解算法进行了细节优化,提升了计算速度;同时也改进了MF算法对缺失数据的处理,提升了推荐效果;此外该算法也具备并行计算和在线更新的优点,具有实用价值。
论文作者在发表该文后,对该算法进行了进一步的推广,在期刊《IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS》(SCI 1区)发表了《Fast Matrix Factorization with Non-Uniform Weights on Missing Data》。