推荐系统研究专区

协调过滤(1):Fast Matrix Factorizatio

2020-02-20  本文已影响0人  阿瑟_TJRS

20200914更新:把之前上传失败的图片重新上传了一遍

对相关研究感兴趣的朋友欢迎交流


简介

论文主要内容

问题及方法

问题

矩阵分解(Matrix Factorization,MF) 是推荐中常用的算法,隐式反馈数据是实际场景常见的数据,隐式反馈可简单为用户与物品的间接交互关系(如点击、收藏等,无法直接反映用户对物品的喜好程度)。

论文针对当前针对隐式反馈的MF研究中存在的两个关键问题:

  1. 在推荐中,数据存在严重的稀疏性,由于数据缺失严重,目前的MF方法中常常会给缺失的数据赋统一的权重以降低计算复杂度。
  2. 大多数的MF方法只适用于线下(静态数据),无法适应线上的动态数据。
提出的方法

论文针对上述隐式反馈MF方法研究中存在的问题,提出以下方法:

  1. 基于物品流行度(item-popularity)对缺失数据进行加权,比传统的统一权值更合理。
  2. 基于元素级交替最小二乘法(element-wise Alternating Least Squares,eALS) 提出新的MF求解方法;
  3. 在此基础上,设计了参数增量更新策略,以支持在线推荐。

相关知识

该篇论文属于推荐领域内的专业论文,需要一些相关的基本知识,在此对几个关键的知识进行总结回顾:

隐式反馈

(1) 没有负反馈。通过观察用户的行为,我们可以推断出他们可能喜欢哪些项目,从而选择消费。然而,很难可靠地推断出用户不喜欢哪些项目。例如,没有观看某个节目的用户可能是因为她不喜欢该节目,或者只是因为她不知道该节目或无法观看该节目。这种基本的不对称性不存在于明确的反馈中,用户告诉我们他们喜欢什么,不喜欢什么。
(2)隐式反馈本质上充满噪声。当我们被动地跟踪用户的行为时,我们只能猜测他们的偏好和真正的动机。例如,我们可以查看个人的购买行为,但这并不一定表示对产品有正面的看法。该商品可能是作为礼物购买的,或者用户对该产品感到失望。
(3)显式反馈的数值表示偏好,而隐式反馈的数值表示置信The numerical value of explicit feedback indicates preference, whereas the numerical value of implicit feedback indicates confidence. 基于显式反馈的系统允许用户表达他们的偏好水平,例如1(“完全不喜欢”)到5(“真正喜欢”)之间的星级。另一方面,隐式反馈的数值描述了动作的频率,例如,用户观看某个节目的时间、用户购买某个节目的频率等等。值越大并不表示偏好越高。例如,最受欢迎的节目可能是用户只看一次的电影,而有一个用户非常喜欢的系列,因此每周都在看。
然而,反馈的数值肯定是有用的,因为它告诉我们在某个观察中的信心。一次性事件可能由与用户首选项无关的各种原因引起。但是,重复发生的事件更可能反映用户的意见。
(4)对隐式反馈推荐的评价需要适当的措施

矩阵分解(MF)

矩阵分解算法是推荐中最为基础而常用的算法,能够很好地解决推荐中评分预测的问题。
基本思想是:将用户-物品交互矩阵R_{N×M},N个 用户,K个物品,分解成为两个矩阵U_{N×K}V_{M×K}的乘积:
U_{N×K}V_{M×K}^T\approx R

UV分别代表用户潜在特征矩阵和物品潜在特征矩阵(Latent Factor matrix).(注:此处用到的矩阵分解算法为常见的Latent Factor形式)

在实际推荐计算中不再利用R推荐,而是利用分解得到的两个矩阵选取相关用户物品的向量,利用向量乘积做推荐。如计算用户u对于其未交互的物品(unobeserved data)的评分值可以如下式表示:

\hat{r}_{ui}=u_iv_j^T+b_u+b_i

其中后两项b_u,b_i为偏置项,反映用户u和物品i的偏置信息,u_i,v_j则为从特征矩阵中获取的向量

为了求解出两个矩阵,将损失函数定义如下(使用了基本的平方误差):
L=\sum_{(i,j)\in R_{observed}}[(r_{i,j}-u_i^Tv_j)^2+\lambda(\left \| u_i \right \|^2+\left \| v_j \right \|^2))]

针对上式,常规解法是利用随机梯度下降算法(SGD)进行参数迭代求解;另一种算法则是交替最小二乘法,下小节将具体介绍ALS。

ALS

首先回顾最小二乘法的知识

给定数据S={(x_i,y_i)|i取0,...n}
求线性关系 y=ax+b中的参数a,b


推广更普遍的情况,用矩阵形式进行表示,所求线性关系为Y=X\theta,X为?×m向量,\theta为m×1向量
\theta=(X^TX)^{-1}X^TY
以上即为最小二乘法的基本公式

矩阵分解的损失函数中待求量为U,I,两个变量,单一的最小二乘法仅能解决只有一个待求矩阵形式的问题;

在此需要对问题做转换以利用最小二乘法,
ALS的基本思想是固定其中一个变量,对剩下的变量利用最小二乘法求解
具体步骤如下:

  1. 初始化U,I
  2. 计算用户矩阵for \quad i \quad in \quad 1,...,N,固定I do
    \frac{\partial L}{\partial U_i}=-2\sum_{j=1}^{M}I_j(r_{i,j}-U_i^TI_j)+2\lambda U_i
    =-2I_{k×m}r_i+2I_{k×m}I_{k×m}^TU_i+2\lambda U_i
    U_i,I_j为向量,大小为k×1
    矩阵求导中
    y=aX^Tb=b^TXa
    y的转置等于y
    令偏导等于0得到:
    U_i=(I_{k×m}I_{k×m}^T+2\lambda E)^{-1}I_{k×m}r_i
    E为单位矩阵
    end\quad for
  3. 计算物品矩阵 for \quad j \quad in \quad 1,...,M,固定U do
    \frac{\partial L}{\partial I_j}=-2\sum_{i=1}^{N}U_i(r_{i,j}-U_i^TI_j)+2\lambda I_j
    =-2U_{k×n}r_i+2U_{k×n}U_{k×n}^TI_j+2\lambda I_j
    令偏导等于0得到:
    I_j=(U_{k×n}U_{k×n}^T+2\lambda E)^{-1}U_{k×n}r_i
    E为单位矩阵
    end\quad for
  4. 重复步骤2和3,对矩阵进行不断迭代更新,至满足停止条件

注意上式公式中的一些小细节,主要是利用矩阵求导的一些知识,
https://blog.csdn.net/L_15156024189/article/details/84952633
以及对原始损失函数的分析。

处理隐式反馈的MF

传统方法

对于交互矩阵\mathbf{R} \in \mathbb{R} ^{M\times N},M,N为用户和物品数量
\mathit{R}表示矩阵中非0的元素集合,即观察到的数据
向量\mathbf{p} _u表示用户u的潜在特征向量,\mathit{R_u}表示用户u交互过的物品集合
向量\mathbf{q} _i 表示物品i的潜在特征向量,\mathit{R} _i 表示与物品i交互过的用户集合
\mathbf{P} \in \mathbb{R} ^{M\times K} 为用户特征矩阵
\mathbf{P} \in \mathbb{R} ^{M\times K} 为物品特征矩阵
K表示特征向量的维度,\mathbf{R} 中每个元素 r_{ui} 可以数学表示为:

\hat{r}_{ui}=<\mathbf{p} _u,\mathbf{q} _i>=\mathbf{p}_u\mathbf{q}_i^T.

在物品推荐中,最终要跟评分函数值\hat{r}_{ui}对推荐结果进行排序,可以添加偏置信息
\hat{r}_{ui}=b_u+b_i+<\mathbf{p}_u^B,\mathbf{q}_i^B>.

J=\sum_{u=1}^M\sum_{i=1}^Nw_{ui}(r_{u,i}-\hat{r}_{u,i})^2+\lambda(\sum_{u=1}^M\left \| \mathbf{p}_u \right \|^2+\sum_{i=1}^N\left \| \mathbf{q}_i \right \|^2))
其中w_{ui}即表示权重因子,用\mathbf{W}=[w_{ui}]_{M\times N}代表权重矩阵
后两项则是L2正则化项。从上式中可以看出,这种算法将缺失值设为0,且缺失值权重非0;这一设定会严重影响算法的性能。

基于物品流行度非统一赋权的MF

论文指出:由于物品的量级较大,缺失值往往包涵负向反馈或者未知反馈,因此为缺失值和观察值简单地赋同样的权重是不合理的
因此论文提出利用物品的属性进行赋权操作:对观察到的值和缺失值分别赋权:

L=\sum_{(u,i)\in \mathit{R}}^Mw_{ui}(r_{u,i}-\hat{r}_{u,i})^2+\color{red}{\sum_{u=1}^M\sum_{i \notin \mathit{R}}c_i\hat{r}_{u,i}}$$ + \lambda(\sum_{u=1}^M\left \| \mathbf{p}_u \right \|^2+\sum_{i=1}^N\left \| \mathbf{q}_i \right \|^2))

其中c_i表示确信用户u没有看过的物品i是真正的负向样本(用户不喜欢),可以用作对从业人员的领域知识进行编码的一种手段。
显然,第二项解释缺失数据的作用,它充当否定实例的角色,对于隐式反馈的建议至关重要。

关于c_i的赋值策略,论文提出基于物品流行度进行确定
目前网络中通常来说流行的物品更有可能被用户了解,因此可以进行一个合理推测:对于一个用户而言,忽略掉一个流行的物品很有能是因为用户不喜欢该物品
基于这个推测,对c_i参数化:
c_i=c_0\frac{f_i^\alpha}{\sum_{j=1}^N f_j^{\alpha}}

其中f_j表示物品j的流行度(计算频率即可),c_0定义缺失数据的总权重,用于控制缺失数据对模型的影响程度;

指数\alpha控制着流行物品相对于不流行物品的显着性水平---当\alpha> 1时,促进流行物品的权重以加强与不受欢迎商品的区别,在(0; 1)的较低范围内设置时,可以抑制受欢迎商品的重量,并具有平滑效果。

论文中根据经验取值0.5。

eALS

通用eALS方法

ALS算法主要的计算瓶颈在于矩阵操作矩阵求逆,矩阵转置,这样设计的好处在于可以一次性更新一条特征向量。
很自然地可以想到从元素级别进行更新,而非向量级,即固定特征向量的其他维度,优化某一维。
对普通的MF方法的损失函数进行简单修改:
J=\sum_{u=1}^M\sum_{i=1}^Nw_{ui}(r_{uu}-\color{red}{\sum_{t=1}^Kp_{ut}q_{it} }$$)^2+\lambda(\color{red}\sum_{u=1}^M\sum_{t=i}^Kp_{ut}^2+\sum_{i=1}^N\sum_{t=i}^Kq_{it}^2))
将向量乘积的形式重新表示成元素和式的形式,如上式所示;则可以从元素级进行求导计算(注:本部分为个人对公式的理解推导,论文中的公式省去了很多推导过程
J=\sum_{u=1}^M\sum_{i=1}^Nw_{ui}(r_{ui}-\color{red}{\sum_{t \neq f}^Kp_{ut}q_{it}-p_{uf}q_{if} }$$)^2+\lambda(\color{red}\sum_{u=1}^M\sum_{t=i}^Kp_{ut}^2+\sum_{i=1}^N\sum_{t=i}^Kq_{it}^2))

\hat{r}_{ui}^f=\sum_{t=1}^Kp_{ut}q_{it}-p_{uf}q_{if}
,这样转换的目的是为了直接得到与某一维元素相关的数据,利于后续求导:
J=\sum_{u=1}^M\sum_{i=1}^Nw_{ui}(r_{ui}-\color{red}{\hat{r}_{ui}^f-p_{uf}q_{if} }$$)^2+\lambda(\color{red}\sum_{u=1}^M\sum_{t=i}^Kp_{ut}^2+\sum_{i=1}^N\sum_{t=i}^Kq_{it}^2))

在此式基础上,(仍然是ALS的思想)对目的矩阵的各个元素进行求导,即某向量的某维度进行求导:
\frac{\partial J}{\partial p_{uf}}=-2\sum_{i=1}^Nw_{ui}(r_{ui}-\hat{r}_{ui}^f)q_{if}+2p_{uf}\sum_{i=1}^Nw_{ui}q_{if}^2+2\lambda p_{uf}

上述求导过程中,原式最后一项相当于常数项可以忽略,第一项求导稍有点麻烦,可以把平方式拆开进行计算,最后得到上式。

令导数为0,即得到:
p_{uf}=\frac{\sum_{i=1}^Nw_{ui}(r_{ui}-\hat{r}_{ui}^f)q_{if}}{\sum_{i=1}^Nw_{ui}q_{if}^2+\lambda}

同理得到:
q_{if}=\frac{\sum_{i=1}^Mw_{ui}(r_{ui}-\hat{r}_{ui}^f)p_{uf}}{\sum_{i=1}^Mw_{ui}p_{uf}^2+\lambda}

基于该推导结果进行MF的求解,完整步骤如下图所示:

时间复杂度分析
传统ALS对一个K\times K大小的矩阵求逆需要O(K^3),那么更新一个用户潜在向量需要O(K^3+NK^2),那么完成所有迭代更新的复杂度为O((M+N)K^3+NK^2)
由于省去了大量的矩阵计算过程(求逆),那么时间复杂度将会消去O((M+N)K^3),下降到O(MNK^2)的量级,由此可见eALS的高效性

Fast eALS

对于本文提出的MF:
L=\sum_{(u,i)\in \mathit{R}}^Mw_{ui}(r_{u,i}-\hat{r}_{u,i})^2+\color{red}{\sum_{u=1}^M\sum_{i \notin \mathit{R}}c_i\hat{r}_{u,i}}$$ + \lambda(\sum_{u=1}^M\left \| \mathbf{p}_u \right \|^2+\sum_{i=1}^N\left \| \mathbf{q}_i \right \|^2))

按照ALS的思想对两变量分别计算:
p_{uf}=\frac{\sum_{i \in \mathit{R}_u}w_{ui}(r_{ui}-\hat{r}_{ui}^f)q_{if} - \sum_{i \notin \mathit{R}_u }\hat{r}_{ui}^f c_iq_{if}} {\sum_{i \in \mathit{R}_u}w_{ui}q_{if}^2+\lambda+\sum_{i \notin \mathit{R}_u }c_iq_{if}^2}
其中计算瓶颈在于对缺失值的处理,需要对整个负空间求和,对相关部分公式逐一考察:
先考察分子上的项,对其进行拆分,转换成整体减去正例的形式
[图片上传失败...(image-e106a5-1582186303713)]
上式中主要计算量是\sum_{i=1}^Nc_iq_{if}q_{ik},每次都会迭代计算该项;然而该项与u无关,因此可以提前计算并存储,之后的每次运算只需从cache中查找即可,这将大大提升计算速度。
定义cache \mathbf{S}^q=\sum_{i=1}^Nc_iq_iq_i^T,提前计算该部分并存储,用于后续的向量值更新:
[图片上传失败...(image-c4f548-1582186303713)]
计算复杂度为O(K+|\mathit{R}_u|),同理对分母的式子做相同的优化:
[图片上传失败...(image-e2d4d7-1582186303713)]
最终的计算公式为:
[图片上传失败...(image-64cddc-1582186303713)]
时间复杂度
Fast eALS的复杂度为O((M+N)K^2+|\mathit{R}|K)

并行学习与在线更新

论文也指出 Fast eALS支持并行计算:

  1. 计算S缓存时,矩阵乘法可以使用很多工具包实现并行
  2. 在更新不同用户/物品的潜在向量时,共享参数独立或保持不变,因此可以利用并行计算。
    论文同时提出了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》

paper_title.png
上一篇下一篇

猜你喜欢

热点阅读