Slim召回介绍

Reading time ~2 minutes

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)的最优化问题可以被解耦成以下的最优化问题的集合:
\[\underset{w_j}{minimize} \frac{1}{2} \| a_j - A w_j \|_2^2 + \frac{\beta}{2} \| w_j \|_2^2 + \lambda \| w_j \|_1 \\ subject \ to \ w_j >=0 \\ w_{jj} = 0\]

…(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上最好的效果。

参考

PLE介绍

tx在《Progressive Layered Extraction (PLE): A Novel Multi-TaskLearning (MTL) Model for Personalized Recommendations》提出了PLE模型:# 1.介绍个性化推荐在在线...… Continue reading

DTS介绍

Published on January 02, 2021

taobao Privileged Features Distillation介绍

Published on December 16, 2020