揭开Top-N 经典算法 SLIM 和 FISM 之谜

今天要介绍的是KDD13年的一篇论文《FISM:Factored Item Similarity Models for Top-N Recommender Systems》属于 top-N 推荐算法中的经典方法，也作为下次要分享的 SVD++ 的一个过渡。

模拟经营单机游戏

该论文也属于传统算法中协同过滤中矩阵分解，即traditional > collaborative filtering > matrix factorization(也叫 model-based CF)。

目录：论文主要贡献点相关算法研究，对应 Review of relevant research：SLIM (也很重要的方法，重点介绍)NSVDFISM算法介绍：与SLIM与NSVD的异同点FISM评分估计详细介绍：FISMrmseFISMauc实验结果介绍：评估指标methodologymetrics结果对比：有无 Bias 的影响Neighborhood Agreement 的影响对S进行 Sparse 的影响Estimation Approach 的影响Non-negativity 的影响与其他方法的效果对比下期预告

下面进入今天分享的论文正题：

1. 论文的主要贡献

包括以下四个方面：

将 item-based 的隐因子的方法扩展到 top-N 问题，这使得能够有效地处理稀疏数据集。使用结构方程建模方法来解item-based的隐因子。同时使用rmse和ranking loss来评估该模型。因其与Bias、neighborhood agreement和模型的稀疏性相关，实验观察了各种参数的影响。2. 相关算法研究-Review of relevant research：

FISM主要受到两个模型的启发：

SLIM(不是tensorflow里的slim哦) NSVD

所以今天把SLIM、NSVD、FISM搁到一起说说。

2.1 SLIM:

全称《SLIM: Sparse linear methods for top-n recommender systems》由作者为 X. Ning 和 G. Karypis 在2011年提出，主要思想是通过一个稀疏矩阵作为权重，来给矩阵打分。SLIM是一种很重要的方法，值得认真说一下。在16年RecSys的best paper www-users.cs.umn.edu/~chri2951/recsy368-christakopoulouA.pdf 中也提到了SLIM。

上周分享MF的文章里我们提到协同过滤推荐算法一般分为两大类：Neighborhood-based和Model-based。Neighborhood-based用各种距离度量方式计算出user之间或item之间的相似度，类似于KNN算法。根据与user最相似的k个user来进行推荐。这种算法中只用到了用户行为数据，但解释力强，实现容易。并且得益于用户行为矩阵的稀疏性，运算贼快。

Model-based一般指根据user-item评分矩阵进行矩阵分解或者用模型来学习user和item的latent vector。用学习到的低秩的user和item matrices来进行预测。经典的包括SVD,SVD++等。SLIM与SVD相似，区别在于SVD是把矩阵分解成两个low rank的子矩阵，而SLIM是直接用矩阵R当做要学习得到的用来相乘的两个矩阵中的一个。

总结来说:

Neighborhood-based效果快，但相对来说效果差一些。Model-based算法效果好一些但是训练时间大幅增加。

SLIM算法就是这样一种奇葩的存在，既能提升neighborhood-based效果又能提升model-based的运行效率。

Notation：

r_{u} : user在所有items上的rating vector S ： m * m 的系数的聚合系数表，可以理解成item与item相似度。 R 是一个binary的矩阵，user对item有过历史行为则为1，无则为0。size为 n*m 。 r_{i}^{T} 为矩阵的一行，即user u 对所有items的历史评分记录。r_{j} 代表矩阵的一列，婚纱设计师即所有user对item j的评分记录。 \tilde{r_{ij}} 为预测的结果.

SLIM的预测公式为:

\tilde{r_{ij}} = r_{i}^{T}s_{j} ，写成矩阵形式即 \tilde{R} =RS

S 也就是我们需要训练学习的权重矩阵。本质上，权重矩阵 S 是物品之间的相似度矩阵。

具体的目标函数为：美规车

\min_{S}{ \frac{1}{2}||R-RS||_{F}^{2} + \frac{\beta}{2}||S||_{F}^{2} + \lambda |吸音|S||_{1} }

s.t. S \geq 0, diag(S)=0

值得注意的是两个约束条件：

要求 S 非负，约束保证权重矩阵学习到物品之间的正相关关系限制对角线能确保不会用已有的打口臭怎么办分去进行预测学习

那SLIM的高效体现在哪呢？

L1正则化约束可以使得 S 稀疏，保证了模型的稀疏性。弗罗贝尼乌斯范数类似于L2，用来防止数据过拟合。S 各列之间是相互独立的，所以可以做扩展并行训练。作者此处提到优化的方法可以用坐标下降和软阈值: \min_{S}{ \frac{1}{2}||r_{j}-Rs_{j}||_{F}^{2} + \frac{\beta}{2}||s_{j}||_{F}^{2} + \lambda ||s_{j}||_{1} }，s.t. s_{j} \geq 0, s_{j,j}=0。可以将 S 的学习过程分解为小过程，对 S 中的每一列单独求解。SLIM可以融合一些特征选择的方式作为 S_{j} 的先验，如提前计算一些相似的物品等等，作者提出用itemKNN做出相似的物品阈值结合，训练过程会大大缩短。矩阵 R 中每一列的含义是所有user对item j的行为，取那些和 R_{j}相似度高的列，也就是取那些user行为和item j相似的i笑到最后的人tem的向量。这里很像item-based。 因为 S 非常稀疏，SLIM方法足够高效。考虑利用item之间的相似度来缩短训练时间，又利用学习训练过程提升了精度。通过一种线性的方式，学习物品之间的相似度，而且能够通过迭代的方式做类似协同过滤的事情。2.2 NSVD

全称《Improving regularized singular value decomposition for collaborative filtering》发布于07年的KDD，作者是 A. Paterek。是一种用于评分预测的factored item-item CF方法，以RMSE方法为evaluation。 通物联网公司过学习两个low-rank的矩阵P和Q， P\in R^{m * k} ,Q\in R^{m * k}，item与item的similarity sim(i,j) = p_{i}·q_{j}^{T}为对应P和Q中的latent vector的点积。

user u对应item i的评分估计为： \hat{r_{ui}} = \tilde{r_{ui}} = b_{u} + b_{i} + \sum_{j\in R_{u}^{+}}^{}{ p_{j} q_{i}^{T}}

b_{u} 和 b_{i} 对应user 和item的bias， R_{u}^{+} 是user历entp型人格史评分过的items。

求解对应的最优化问题得到P,Q：

\min_{P,Q}{ \sum_{u\in C}^{}{}\sum_{i\in R_{u}^{+}}^{}{}||r_{ui}-\hat r_{ui}||_{F}^{2} + \frac{\beta}{2}||P||_{F}^{2} + \frac{\beta}{2}||Q||_{F}^{2} }

3. FISM：3.1 与SLIM与NSVD的异同点：

由于模型本身的限制，SLIM只能描述有共现物品之间的关系。当item i 和item j 没有同时被任一用户购买时，物品之间的相似性为0，SLIM无法刻画item之间的传递相似性关系。作者提出FISM，通过学习物品之间的相似矩阵来改进推荐结果，将两个未被同时购买的item通过第三个物品关联起来。

通过上面我们知道SLIM不能计算未被同一用户同时评分后的item与item之间的相似度。但比如像matrix factorization方法，将数据映射到低维空间，在一定程度上就解决了这个问题。但矩阵分解方法的效果一致都逊色于SLIM。FISM在这方面就受到NSVD和SVD++的启发。学习低维的隐向量空间，来帮助捕获item之间的关联相似度。

FISM与NSVD的差异在于：

FISM是top-N推荐而NSVD解决的是rating prediction问题。FISM采用基于结构方程建模的回归方法。评估某个item时，不使用用户对于该item的评分信息。绿色物业3.2 FISM评分估计

在FISM中，user u对未评分的妮可罗宾item i的评分由对应矩阵分解得到的估计代替：

\tilde{r_{ui}} = b_{u} + b_{i} + (n_{u}^{+})^{-\alpha}\sum_{j\in R_{u}^{+}}^{}{ p_{j} q_{i}^{T}}

这里 (n_{u}^{+})^{-\alpha} 是用来控制估计值与真实值的一致程度的。 举个极端例子：

当α=1时，预测分数是相似物品评分的平均值。当所有物品都相似于预测物品时，就会得到一个很高的分数。 当α=0时，预测分数是相似物品评分的总和。当只有少量物品与预测物品相似时，仍会得到一个很高的分数。 大多数情况下，最优的选择往往都在两者之间。α就是用来平衡用户打过分的items中大概有多少会是相似的。3.3 作者提出了两种不同loss function的FISM模型：FISMrmseFISMauc3.3.1 FISMrmse

rmse loss的计算公式为： L(\cdot) = \sum_{i \in D}^{}{}\sum_{u \in C}^{}{} (r_{ui} - \hat r_{ui})^{2}

r_{ui} 是实际观测值， \hat r_{ui} 是估计值： \tilde{r_{ui}} = b_{u} + b_{i} + (n_{u}^{+} -1)^{-\alpha}\sum_{j\in R_{u}^{+} - {i} }^{}{ p_{j} q_{i}^{T}}

R_类固醇激素{u}^{+}是user评分过的item除去要被估计的item i 。这样做是为了保证FISM采用基于结构方程建模的回归方法。

对应的加上正则的最优化问题为： \min_{P,Q}{ \sum_{u,i \in R}^{}{}||r_{ui}-\hat r_{ui}||_{F}^{2} + 富察皇后\frac{\beta}{2}||P||_{F}^{2} + \frac{\beta}{2}||Q||_{F}^{2} + \frac{\lambda}{2}||b_{u}||_{2}^{2} + \frac{\lambda}{2}||b_{i}||_{2}^{2} }

我们依然使用SGD来进行求解。 top-N区别于rating prediction，有评分和无评分的数据我们都要使用到。那么就需要对未评分的数据进行负采样。作者提到负样本选取量一般在已经评分数量的(3-15)倍之间就可以。

下面给出FISMrmse的伪代码： (对应的数学都很简单，就不细描写了)

3.3.2 FISMauc

FISMauc 优质大米loss的计算公式为： L(\cdot) = \sum_{u \in C}^{}{}\sum_{i \in R_{u}^{+}, j \in R_{u}^{0} }^{}{} ((r_{ui} -r_{uj}) -(\hat r_{ui} - \hat r_{uj}) )^{2}

FISMauc是一种贝叶斯个性化排序的思路，同时利用打分和未打分的items来优化AUC。主要想法就是先用FISMrmse做出初步结果，再去优化成动漫网站对的目标损失：

\min_{P,Q}{ \sum_{u \in C}^{}{}\sum_{i \in R_{u}^{+}, j \in R_{u}^{0} }^{}{} ||(r_{ui} -r_{uj}) -(\hat r_{ui} - \hat r_{uj}) ||_{F}^{2} + \frac{\beta}{2}||P||_{F}^{2} + \frac{\beta}{2}||Q||_{F}^{2} + \frac{\lambda}{2}||b_{i}||_{2}^{2} }

对应的伪就业问题代码为：(对应的数学都很简单，就不细描写了)

4. 实验介绍：4.1 评估指标：4.1.1 methodology:

5-fold Leave-One-Out-Cross-Validation (LOOCV)

4.1.2 metrics:

评估预测质量使用到Hit Rate(HI)和Average Reciprocal Hit Rank (ARHR) 。

HR:HR = \frac{\#晚上失眠怎么办hits}{\#users} ,其中#users是测试用户的总数，而#hits是模型成功能够在大小为N的推荐列表中调用测试项目的用户数。ARHR: ARHR = \frac{1}{\#users}\sum_{i=1}^{\#hits}{\frac{1}{pos_{i}}} ,其中 pos_{i} 是第i个命中的排名推荐列表中测试项目的位置。 ARHR表示HR的加权版本，因为它测量排名列表延边大学怎么样中推荐项目的位置的倒数。4.2 实验部分：无特殊说明均基于FISMrmse。effects of bias:分了四种情况：NoBias，UserBias，ItemBias和User&Item Bias。Bias会影响整体的效果表现，ItemBias能带来最大的效果提升。effect of neighborhood性爱大师第1季 agreement就是前面说的α。这里对比了FISMauc和FISMrmse。最好的效果是在α介于0.4与0.5之间取得的。另外一个点是，随着α的增大，FISMauc比FISMrmse更稳定。对S做稀疏操作，观察HR指标和预测时间的变化。Effect of Estimation Approach 使用不同的latent vector的长度k，控制是否想NSVD一样训练时使用user对该item的评分。 k值越小，FISM和FISM(F)越相似。随着k的增长，FISM的效果就会远超出FISM(F)。Effect of Non-Negativity SLIM有一个non-negative的限制条件。在FISM中，没有这么严格的条件。作者实验了给FISM加上non-negative的限制，发现效果并没有提升。 (HR of 0.0933 for ML100K and 0.0848 for Yahoo, compared to 0.1281 and 0.0974 without the constra时擦ints)。通过观察S中的正负比例，模型是在negative entries明显与non-negative的时候取得的。 Comparison With Other Approaches 做了大量的与其他视频加速方法的对比结果。 6. 总结：

FISM使用user历史评分过的items对应的matrices aggregation作为user representation，本质上还是item与item之间的similarity。

7. 下期预告SVD++：

传统推荐模型还有两期，包括下一次的SVD++和feature-based方法FM。

觉得有用有收获的话，关注我吧！多谢多谢！