Xia Ning 和 George Karypis在《SLIM: Sparse Linear Methods for Top-N Recommender Systems》提出了SLIM。我们来看下具体的内容：
摘要
本paper关注于开发高效且有效的top-N推荐算法。提出了一种新的Sparse Linear Method，它通过从用户购买/rating 信息中进行聚合，来生成top-N推荐。通过求解一个l1-norm和l2-norm正则的优化问题，从SLIM中可以学到一个稀疏聚合系数矩阵W（sparse aggregation coefficient matrix）W。W可以用来生成高质量推荐，它的稀疏性（sparsity）允许SLIM来快速生成推荐。我们通过实验对比了SLIM与SOTA的方式。实验表明SLIM可以在运行时间和推荐质量上达到很大提升。
一.介绍
电商快速出现、成长很快，提供大量商品和详细信息，改变着用户购买商品的习惯。这使得在线交易更为方便。然而，由于符合用户期望的商品数目快速增加，如何高效快速地帮助用户筛选符合用户品味的商品变得越来越重要。特别的，给定用户的purchase/rating profies，为用户推荐一个关于items的ranked list很重要，这就是广泛使用的top-N推荐系统。
最近，在许多top-N推荐算法提出。这些算法被归类成两类：neghborhood-based CF方法和model-based方法。在neighborhood-based方法中，它们基于item neighborhoods可以快速生成推荐，但会牺牲一定的推荐质量。另一方面，model-based方法，特别是基于latent factor models生成推荐的开销高些，但这些推荐的质量更高，它们在大型推荐任务中达到了最好的效果。
在本paper中，我们提出了一种新的sparse linear method来进行top-N推荐，它们可以快速做出高质量的推荐。SLIM会从用户的purchase/rating profiles中，通过求解一个正解最优化问题，为items学习一个sparse coefficient matrix。在coefficient matrix中会引入Sparsity，它允许我们高效生成推荐。特征选择方法使得SLIM可以大量减少所需时间来学习coefficient matrix。另外，SLIM可以被用来做top-N的推荐。
SLIM方法解决了高质量/高效的topN推荐，它很适合实时应用。我们开展了大量线上实验。结果表明，比起SOTA方法，SLIM可以生成更好的推荐，并且很快速。另外，它在使用ratings做top-N推荐上达到了很好的效果。
二.相关工作
略.
三.定义与概念
在本paper中的符号：
- u和t：会用来表示users和items
- \((u_i, t_j)\)：表示单个users和items
- U\((\mid U\mid = m)\)和T \((\mid T\mid = n)\)：分别表示所有users和items
- 矩阵A：整个user-item的parchases/ratings的集合，会分别通过一个m x n的user-item purchase/rating matrix A来表示，其中(i,j)的entry（表示为\(a_{ij}\)）是1或者一个正值，如果用户\(u_i\)对item \(t_j\)做过购买或评分行为，否则就会标记为0
- \(a_i^T\)：表示A的第i行，表示user \(u_i\)在所有items T上的购买和评分历史
- \(a_j\)：表示A的第j列，表示所有用户U在item \(t_j\)上的购买/评分历史
在本paper中，
- 所有vectors（例如：\(a_i^T\)和\(a_j\)）都被表示成粗体小写字母，
- 所有matrics（比如：A）则是大写。
- 行向量（row vectors）则通过转置T表示，否则缺省就是列向量（column vectors）。
- 一个预测/近似值则通过\(\sim\)来表示。
我们会使用相应的matrix/vector概念来替代user/item的purchase/rating profiles。
四.SLIM
4.1 Slim topN推荐
在本paper中，我们提出了一种SLIM来做top-N推荐。在SLIM方法中，在用户\(u_i\)在一个未购买/未评分过item \(t_j\)上的推荐分，可以通过计算\(u_i\)已经购买/评分过的items的一个稀疏聚合（sparse aggregation）来计算得到：
\[\hat{a}_{ij} = a_i^T w_j\]…(1)
其中：
- \(a_{ij}=0\),
- \(w_j\)是一个稀疏的关于聚合系数（aggregation coefficients）的size-n column vector。
因此，SLIM使用的模型可以表示为：
\[\hat{A} = AW\]…(2)
其中：
- A：是二元的user-item购买/评分矩阵，
- W：是一个\(n \times n\)的sparse matrix的聚合系数（aggregation coefficients），第j列对应于等式(1)中的\(w_j\)，
- \(\hat{a}_i^T(\hat{a}_i^T = a_i^T W)\)：表示用户\(u_i\)在所有items上的推荐分
用户\(u_i\)的top-N推荐通过对\(u_i\)的未购买/未评分items上、基于在\(\hat{a}_i^T\)基于推荐分递减来达到，并推荐top-N个items
4.2 为SLIM学习W
在A中，我们将user \(u_i\)在item \(t_j\)上的购买/评分行为（例如：\(a_{ij}\)）看成是ground-truth的item推荐分。给定一个user-item 购买/评分矩阵A（size为\(m \times n\)），我们可以学到等式（2）中sparse \(n \times n\)的matrix W，可以通过下面的正则最优化问题进行minimizer：
\[\underset{W}{minimize} \frac{1}{2} \| A - AW \|_F^2 + \frac{\beta}{2} \| W \|_F^2 + \lambda \| W \|_1 \\ subject\ to \ W >= 0, diag(W) = 0\]…(3)
其中：
- \(\| W \|_1 = \sum\limits_{i=1}^n \sum\limits_{j=1}^{n} \mid w_{ij} \mid\) ：是W的entry-wise l1-norm
- \(\| \cdot \|_F\)：是matrix Frobenius norm（弗罗贝尼乌斯范数）
- AW：是推荐得分的预估矩阵（例如：\(\hat{A}\)） 乘以 等式2的sparse linear model
- 第一项\(\frac{1}{2} \| A - AW \|_F^2\) （例如：平方residual sum）：用来衡量linear model是如何拟合训练数据的，
- \(\| W \|_F^2\)和\(\| W \|_1^2\)分别是\(l_F\)-norm和l1-norm正则项
- 常数\(\beta\)和\(\lambda\)是正则参数。参数越大，正则化越强
约束条件：
- 在W上会使用非负（non-negativity constraint）约束，若存在，学到的W表示了在items间的正向关系
-
约束条件 diag(W)=0 也会被使用，以避免trivial solutions（例如：optimal W是一个identical matrix，以便一个item总能推荐它本身，以便最小化 \(\frac{1}{2} \| A - AW \|_F^2\)）。另外，约束 diag(W)=0 确保了\(a_{ij}\)不会被用于计算 \(\hat{a}_{ij}\)
- 1） Slim的l1-norm和\(l_F\) norm正则：为了学到一个sparse W，我们需要引入W的\(l1-norm\) 作为等式(3)的regularizer。众所周知，\(l1-norm\)正则化会将sparsity引入到solutions中【12】
除了l1-norm外，我们还有W的\(l_F\)-norm作为另一个regularizer，它会导致该最优化问题变成一个弹性网眼(elastic net)问题[13]。\(l_F\)-norm可以衡量模型复杂度，并阻止overfitting（在ridge regression中）。另外，\(l_1\)-norm和\(l_F\)-norm regularization一起隐式地将solutions中的相关items进行了group【13】
- 2) 计算W：因为W的列是独立的，等式(3)的最优化问题可以被解耦成以下的最优化问题的集合：
…(4)
这允许W的每一列可以被独立求解。在等式(4)中：
- \(w_j\)是W的第j列
- \(a_j\)是A的第j列
- \(\| \cdot \|_2\)是vectors的\(l_2\)-norm
- \(\| w_j \|_1 = \sum\limits_{i=1}^n \mid w_{ij} \mid\)是vector \(w_j\)的entry-wise \(l_1\)-norm。
由于W的column-wise独立特性，学习W的过程可以很方便并行化。等式(4)的最优化问题可以使用坐标下降法和soft thresholding来进行求解。
- 3） 具有Feature Selection的SLIM：等式(4)中的\(w_j\)的估计可以被看成是一个正则回归问题的解，其中：A的第j列是等估计的依赖变量，可以看成是A的其余n-1列（独立变量）的一个函数。该观点建议：feature selection方法可以潜在用于：在计算\(w_j\)之前，减小独立变量的数目。这些feature selection方法的优点是：他们会减少A中列的数目，它可以实质上减少SLIM学习所需的整体时间。
受其它observations的启发，我们将SLIM方法扩展成包含feature selection。我们将这些方法称为“fsSLIM”。尽管可以使用许多feature selection方法，在本paper中，受itemkNN top-N推荐算法的启发，我们只研究了一种方法。特别的，由于目标是学习一个线性模型（linear model）来估计A(\(a_j\))的第j列，接着A的列与\(a_j\)最相似，可以被用于selected features。我们的实验会在后面展示，使用cosine相似度和这种feature selection方法，会产生一个方法：它具有更低计算要求，具有最小的质量退化。
4.3 对于SLIM，高效的topN推荐
等式（2）中SLIM方法以及W的稀疏性，使得在topN推荐上更快。在等式（2）中，\(a_i^T\)总是非常稀疏（例如：用户通常只会对少量的items进行购买/评分），并且当W也稀疏时，通过利用W的稀疏结构，\(\hat{a}_i^T\)的计算可以非常快（例如：沿着W在它行中的非零值上的列进行一个”gather”操作，对应于在\(a_i^T\)中的非零值）。因此，对于user \(u_i\)的推荐的计算复杂度是：
\[O(n_{a_i} \times n_w + N log(N))\]其中：
- \(n_{a_i}\): 是在\(a_i^T\)中的非零值数目
- \(n_w\): 是在W中行的非零值的平均数目
- \(N log(N)\)项：是用于对N个items最高分进行排序，它可以从在\(\hat{a}_i^T\)潜在的\(n_{a_i} \times n_w\)的非零条目中使用线性选择以线性时间被选中。
4.4 SLIM vs. 已存在的线性方法
线性模型已经在topN推荐中被使用。例如，在[2]中的itemkNN方法具有一个线性模型，它与SLIM相似。itemkNN的模型是一个knn item-item cosine相似度矩阵S，也就是说，每行\(s_i^T\)具有精准的k个非零值，它表示在item \(t_j\)和它的k个最相似邻居间的cosine相似度。在itemkNN和SLIM的线性模型间的基本不同点是：前者高度依赖于预指定的item-item相似度measure（它用于区分neighbors）；后者通过求解等式（3）中的最优化问题来生成W。在这种方式中，W可以潜在编码items间丰富且微妙的关系，它们通常不能被常见的item-item 相似度metrics轻易衡量。在第4节中，通过实验结果验证表明，W要胜过S。
Rendle[11]讨论了一个adaptive k-NN方法，它使用与在itemkNN相似的模型，但会可适应性地学习item-item相似矩阵。然而，在[11]中的item-item相似度矩阵是 完整的稠密、对称矩阵，并且具有负值。W与Rendle的item-item相似度矩阵不同，除了它的稀疏性外，它还会产生更快的推荐，并且存储要求更低，由于最优化过程，W不是必需是对称的，因此对于推荐来说允许更灵活。
对于每个item的rating评测，Paterek[15]引入了一个线性模型（linear model），其中，一个user \(u_i\)在一个item \(t_j\)上的评估，可以通过对\(u_i\)在所有其它items上的评分的聚合（aggregation）来进行计算。它们会学习聚合系数（aggregation coefficients），对于每个item，通过求解一个\(l_2\)-norm正则的最小二乘问题来进行。学到的系数是fully dense的。对比起Paterek方法，SLIM的优点是在学习期间采用了\(l_1\)-norm正则，它强制要求W是稀疏的，因此，在W中最具信息量的信号来自所有购买/评分行为，以便可以更好融合信息，对比Paterek方法，它只使用一个购买/评分活动的特定集合。
4.5 在SLIM和MF方法间的关系
对于top-N推荐来说，MF方法是这样一个模型：
\[\hat{A} = U V^T\]…(5)
其中，\(U\)和\(V^T\)分别是user和item因子。对比在等式(5)中的MF模型、以及等式(2)中的SLIM方法，我们可以看到：SLIM模型可以被看成是MF模型的一个特例（例如：A等同于U，并且W等同于\(V^T\)）
等式（5）中的U和\(V^T\)，在一个latent space，它的维度通常被指定成一个参数。”latent”空间这时完全变成等式(2)中的item space，因此，在SLIM中没必要学习在”latent” space中的用户表示，因此，学习过程可以被简化。另一方法，\(U\)和\(V^T\)通常具有低维度，因此，在A中的\(U\)和\(V^T\)的低秩近似（low-rank approximation），有用的信息可能被潜在丢失。相反，在SLIM中，由于在users上的信息在A中完全保留，在items上的counterpart可以通过learning进行最优化，SLIM可以潜在的给出比MF方法更好的推荐。
另外，由于等式（5）中的\(U\)和\(V^T\)，通常是dense的，\(a_i^T\)的计算需要对来自\(U\)和\(V^T\)的dense vectors的每个\(\hat{a}_{ij}\)进行计算。这比起MF方法，会产生一个高计算复杂度，其中k是latent factors的数目，n是items的数目。通过使用在[16,17,18]中的稀疏MF算法，计算复杂度可以被潜在减小。然而，这些稀疏MF算法没有一个可以被用来求解top-N推荐问题，由于它们的高度计算开销。
五.方法
5.1 数据集
我们在8个不同的真实数据集上评估了SLIM的效果，这些数据集如表1所示。可以归为两大类。
第一类：（包括：ccard、ctlg2、ctlg3以及ecmrc[2]）来自于顾客的购买交易（purchasing transactions），这4个数据集只有二元购买信息。
- ccard dataset:对应于在主要商场的信用卡（credit card）购买交易，每个card具有至少5笔交易
- ctlg2和ctlg3数据集对应于在两个主要的邮购目录零售商（mail-order catelog retailers）上的catalog购买交易
- ecmrc dataset对应于基于web电商网站的购买交易。
第二类：（BX、ML10M、Netflix和Yahoo）包含了多值评分（multi-value rating）。所有的ratings会被转化成二元索引。
- BX数据集是来自Book-Crossing dataset上的一个子集，其中每个user会对20个items进行评分，每个item会被至少5个users和最多300个users进行评分过。
- 电影评分的ML10M dataset，从MovieLens研究项目中获得。
- Netflix dataset则从Netflix Price dataset中抽取获得，每个user会对20-250个电影进行评分，每个电影会被20-50个users进行评分。- Yahoo dataset是从Yahoo Music 用户对歌曲的ratings中抽取得到，其中：每个user会对20-200个歌曲评过分，每首music会至少被10个users和至多5000个users评过分。
5.2 评估方法 & metrics
我们使用5倍的 Leave-One-Out交叉验证（LOOCV）来评估SLIM方法的效要。在每个run中，datasets会被split成一个training set和一个testing set，它通过随机选择每个user的非零entries之一，并将它放置到testing set中。training set会被用于训练一个模型，接着对于每个user，模型会生成一个size-N的ranked list的推荐items。该evaluation会通过对比每个user的推荐列表以及用户在testing set上的item。结果的主要部分等于10. 然而，我们也会报告对于N的不同值的一些有限结果。
推荐质量通过HR（Hit Rate）、以及平均倒数命中排序（ARHR：Average Reciprocal Hit-Rank）进行评估【2】。HR的定义如下：
\[HR = \frac{\# hits}{\# users}\]…(6)
其中：
- \(\#users\)是users的总数目
- \(\#hits\)是在testing set中users的item命中size-N的推荐列表的总数目。
第二个measure指标是：ARHR，它的定义如下：
\[ARHR = \frac{1}{\#users} \sum\limits_{i=1}^{\#hits} \frac{1}{p_i}\]…(7)
其中：
- 如果一个user的一个item被命中（hit），p就是该item在ranked推荐结果中的position。
ARHR是HR的加权版本，它可以用来measure一个item被推荐有多强烈，其中weight是在推荐列表中hit position的倒数（reciprocal）。对于使用评分（ratings）的实验，我们通过查看他们推荐items是否好，并且具有一个特别的rating value，来评估该方法的效果。出于该目的，我们也定义了per-rating Hit Rate（rHR）以及cumulative Hit Rate（cHR）：
- rHR的计算成：在items上的hit rate，它们具有一个特定的rating value
- cHR可以计算成：在items上的hit rate，它们的rating value不低于一个特定的rating threshold
注意：在top-N推荐文献中，已经存在其它metrics来进行评估。比如：包括AUC（area under the ORC曲线），它会对在一整个ranked list中的true postives和false postives的相对位置进行measure。AUC的variances可以measure在一个randed list中的top部分的位置。另一个流行的metric是召回率（recall）。然而，在top-N的推荐场景中，我们相信，HR和ARHR是最直接和最有意义的measure，因为users只会关注：一个短推荐列表是否有感兴趣的items、而非一个非常长的推荐列表。因此，我们会使用HR和ARHR进行评估。
六、实验结果
对应于parmas的列为：对于itemkNN和userkNN，参数分别是neighbors的数目。对于itemprob方法，参数是neighbors数目和transition参数\(\alpha\)。对于PureSVD，参数是：sigular values的数目以及在SVD期间的迭代次数。对于WRMF方法，参数是latent space的维度以及在购买时的weight。对于BPRMF方法，参数是latent space的维度和学习率。对于BPRkNN方法，参数是learning rate和正则参数\(\lambda\)。对于方法slim，参数是l2 norm正则参数\(\beta\)以及l1-norm正则参数lambda。对于方法fsSLIM，参数是neighbors的数目和l1-norm正则参数\(\lambda\)。对应于HR和ARHR的列：表示了hit rate和average reciprocal hit-rank. 对应于mt和tt的列，分别表示模型学习和推荐所使用的时间。mt/tt数目（s, m, h）表示秒、分钟、小时。粗体数目是分个dataset上最好的效果。