看16年recsys的best paper，Local Item-Item Models for Top-N Recommendation 中提到的SLIM方法，最近抓着这个方法研究了一下。然后还发现了Xia Ning和George Karypis这两位，这两位一直是SLIM相关论文的主要作者，XiaNing应该是George Karypis的学生，从最早的SLIM方法开始，到后面也有两篇（好像是，没仔细搜）相关改进的文章，都是XiaNing的一作，George Karypis署名二作或者三作。恩，对UMN有些好感。

SLIM

SLIM全称是Sparse Linear Methods，Xia Ning和George Karypis两位第一次在2011年提出，主要思想就是通过一个稀疏矩阵作为权重，来给矩阵打分： \[ \widetilde{A}=AW \]

\[ \widetilde{a}_{ij}=a_i^{T}w_j \]

具体的目标函数为： \[ \begin{aligned} \min_W &\frac{1}{2}\|A-AW\|^2_F+\frac{\beta}{2}\|W\|^2_F+\lambda\|W\|_1\\ \text{s.t. }&W\geq0\\ &\text{diag}(W)=0\\ \end{aligned} \] 其中后面的正则项用来保证矩阵\(W\) 的稀疏性，第一个约束保证权重矩阵是用来学习物品之间的相关正相关关系，第二个约束是为了确保不会用已有打分去预测。这样做有以下几个特点：

两个正则项保证了模型的稀疏性，同时避免了过拟合的风险（我认为此处的正则项可以改变一下，毕竟在推荐系统中，稀疏性还是比较重要的）
\(W\) 各列之间是相互独立的，所以我们可以做到并行训练的扩展，作者此处提到优化的方法可以用坐标下降和软阈值(coordinate descent and soft threshold)

\[ \begin{aligned} \min_{w_j}& \frac{1}{2}\|a_j-Aw_j\|^2_2+\frac{\beta}{2}\|w_j\|^2_2+\lambda\|w_j\|_1\\ \text{s.t.}&w_j\geq 0\\ &w_{j,j}=0\\ \end{aligned} \]

SLIM可以融合一些特征选择的方式作为权重\(w_j\) 的先验，如提前计算一些相似的物品等等，作者提出用itemkNN 做出相似的物品，与之结合，称之为fsSLIM
SLIM方法足够高效，因为\(W\) 十分稀疏，所以只需要计算少数几个数字即可，总的复杂度为\(\mathcal{O}(n_{a_i}\times n_w +N\log(N))\) ，前一项为计算预测的时间，后一项为排序推荐的时间。
与其它线性方法相比具有些优势（此处感觉就是作者的自夸了，老套路，拿自己的优势比他人的劣势，主要还是从稀疏性与物品相似性计算方式上说的）
可以认为是矩阵分解方法的特例

作者后面就开始了实验部分，不详细说了。初看这个模型会觉得是对打分矩阵的估计，然后细细思考，是通过一种线性的方式，学习物品之间的相似度，而且能够通过迭代的方式做类似协同过滤的事，十分巧妙的思路，最重要的是，能够并行，这就有很好的扩展性。

SSLIM

SSLIM这篇论文题目是利用side information做SLIM，但总给我感觉是在水论文...然后水出了cSLIM,rcSLIM,fSLIM,f2SLIM...这里不展开细说了，主要的想法就是通过相似的结构去学习side information中所含有的潜在相似性，一并作为最后打分排序的根据。不管怎么说，实验的量的确很大，看来学校的设备真的不错...

FISM

由于模型本身的限制，SLIM只能描述出有共现的物品之间的关系，所以在稀疏数据中表现受到限制，所以提出了FISM，通过学习物品之间的相似矩阵来改进推荐结果。当物品\(i\) 与物品\(j\) 没有同时被任意一个用户购买时，物品之间的相似性为\(0\) ，但这样的两个物品，却可以通过第三个物品相似而又关联，也就是SLIM无法去刻画物品之间的传递相似关系，与之相似的矩阵分解方法，将数据映射到低维空间，一定程度上解决了这个问题。在FISM中，未打分的推荐评分由矩阵分解得到的估计代替 \[ \widetilde{r}_{ui}=b_u+b_i+(n_u^+)^{-\alpha}\sum_{j\in\mathcal{R}^+_u}p_jq_i^{\mathrm{T}} \] 其中\((n_u^+)^{-\alpha}\) 是用来控制估计值与真实值的一致程度，当\(\alpha=1\) 时，预测分数是相似物品评分的均值，当所有的物品都相似于预测物品时，就会得到一个很高的评分，反之\(\alpha=0\) 时，即使只有很少的物品与预测物品相似，预测物品仍然可以给出较高的评分估计。其实说白了，就是平衡用户所打分物品中，大概有多少可能会是相似的。之后作者提出了不同loss下的两种不同模型，FISMrmse和FISMauc，前者的估计值为： \[ \widetilde{r}_{ui}=b_u+b_i+(n_u^+-1)^{-\alpha}\sum_{j\in\mathcal{R}^+_u/\{i\}}p_jq_i^{\mathrm{T}} \] \(\mathcal{R}^+_u/\{i\}\) 为用户\(u\) 所打分的物品，包括正在计算的物品\(i\) 。

目标函数为： \[ \min_{P,Q}\frac{1}{2}\sum_{u,i\in R}\|r_{u,i}-\widetilde{r}_{u,i}\|^2_F+\frac{\beta}{2}(\|P\|^2_F+\|Q\|^2_F)+\frac{\lambda}{2}\|b_u\|^2_F+\frac{\gamma}{2}\|b_i\|^2_F \] 在训练时，进行非负项的采样迭代训练，训练过程如下：

FISMauc是一种贝叶斯个性化排序（BRP）的思路，同时利用打分和未打分的物品，来优化AUC，主要想法是先用FISMrmse做出初步结果，再去优化成对的目标损失： \[ \min_{P,Q}\frac{1}{2}\sum_{c\in \mathcal{C}}\sum_{i\in\mathcal{R}^+_u,j\in\mathcal{R}^-_u}\|(r_{u,i}-r_{u,j})-(\widetilde{r}_{u,i}-\widetilde{r}_{u,j})\|^2_F+\frac{\beta}{2}(\|P\|^2_F+\|Q\|^2_F)+\frac{\gamma}{2}\|b_i\|^2_F \] 具有优化算法大家见论文，总体上跟FISMrmse相似。

FISM全称为Factored Item Similarity Methods，大家别拼错了哈哈哈哈，这篇文章看到这里我才发现这个跟SLIM一点屌关系都没有，只不过后面二作、三作是Xia Ning和George Karypis，往下看参考文献列表发现里面也没有这篇，恩，这种心情简直逼了个狗，大概看错以为是SLIM改进的只有我吧。

说一些读后感，感觉这种两阶段的优化在实际中就很不实用了，可能一定程度上能提到上文所解决的问题，但过程实在复杂，并没有SLIM那种简单好用的快感了。

HOSLIM

HOSLIM主要为了在描述物品与物品之间的关系基础上，同时抓住物品和物品集之间的关系，用户物品交互矩阵为\(R\) ，用户-物品集交互矩阵为\(R'\) ，当用户购买了一个物品集中的全部物品，则该对应项为\(r'_{i,j}=1\) ，对评分的估计值为： \[ \widetilde{r}_{u,i}=r^{\mathrm{T}}_us_i+r'^{\mathrm{T}}_us'_i \] 目标函数变为： \[ \begin{aligned} \min_{s_i,s'_i}& \frac{1}{2}\|r_i-Rs_i-R's'_i\|^2_2+\frac{\beta}{2}(\|s_i\|^2_2+\|s'_i\|^2_2)+\lambda(\|s_i\|_1+\|s'_i\|)\\ s.t.& s_i\geq0\\ &s_{ii}=0\\ &s'_i\geq0\\ &s'_{ii}=0 \end{aligned} \] 后面除了实验部分，作者论证了一下这种与物品集相联系的关系的存在性，不过物品集的好坏会很大程度上影响模型的效果，同时论文中好像并没有说物品集是如何产生的，可能其引用的论文中提到过，我猜测可能是通过关联分析做出来物品集，然后在推断购买情况的。

LRec

LRec是SLIM的一种变形，将个性化推荐问题变成一个无约束的凸优化问题，定义矩阵\(X\) \[ X=R^{\mathrm{T}} \] 其中打分矩阵\(R\in \{0,1\}\) ，同时将打分矩阵做转换，变为\(\{-1,1\}\) \[ y^{(u)}=2R_{u:}-1 \] 定义损失函数为 \[ \min_{\theta}\sum_{u\in\mathcal{U}}\sum_{i\in\mathcal{I}}\ell(y_i^{(u)},X_{i:}w^{(u)})+\Omega(\theta) \] 其中\(\ell\) 是凸损失函数，后面为正则项，文章中作者用对率回归函数作为损失函数，二范数为正则项，最后矩阵的估计值为 \[ \hat{R}(\theta)=W^{\mathrm{T}}R \] 这个模型可以看作是对用户的一个分类，与之前的物品关系不同，这里主要是来刻画用户购买行为之间的关系。

作者总结LRec有以下几个优点：

采用对率回归时可以高效并行计算；
特征矩阵十分稀疏，方便了模型训练；
当用户数量很大时，采用L2正则化规避了过拟合风险；
如果采用对偶的形式求解，则变量数量仅有物品数个，某些情况下是远远小于用户数量的；
目标函数为凸函数，不会有局部极值；
用未评分向量作为负例加入训练；

文章后面，作者还分析了LRec与之前SLIM、MF等模型的关系和区别。

Local SLIM Ensemble

用SLIM做局部特征，然后进行Ensemble，作者是根据一种LLORMA，local low-rank matrix approximation的方法改进，该方法随机选出多个子集，然后训练子集模型，最后结果做子集结果的加权平均，论文中作者对训练数据对的选择和局部的划分都给出了一些自己的建议，模型的效果有所改进，但给我感觉不是很impressive，毕竟我是看见ensemble才点进来的，插句题外话，目前ensemble方法在推荐系统中用的比较少，以后可以考虑一下怎么结合。

Local Item-Item Models

这篇文章是recsys的best，在没看SLIM之前，我就被这篇文章的思路惊艳到了，虽然是个局部相似是个老问题，但也是大家容易忽视的盲区之一，这篇文章用SLIM同时去刻画全局和局部的物品潜在联系，然后作为最终的预测，如果把SLIM的贡献加进来，这篇文章的确是实至名归的best paper，具体详情见论文吧，这里不赘述了，对于局部用户的分割采用的是CLUTO ，基本上就是SLIM+local SLIM。

CSLIM

之后的这几篇是一位叫Yong Zheng的年轻人在2014年的作品，这篇思路很简单，之前的SLIM模型，不管是针对物品还是针对用户，都属于协同过滤的思路，去做线性推广，这篇文章中提到，在SLIM的基础上，考虑上下文信息，并且认为在估计最后得分时，有上下文信息的评分和没有的之前会有一些差距 \[ \hat{R}_{i,j,c}=R_{i,j}+\sum^L_{l=1}D_{j,l}c_l \] 其中矩阵\(D\) 就是用来刻画上下文信息的矩阵，打分的估计应该是 \[ \hat{S}_{i,j,c}=\sum^N_{h=1,h\neq j}\hat{R}_{i,j,c}W_{h,j}=\sum^N_{h=1,h\neq j}(R_{i,j}+\sum^L_{l=1}D_{j,l}c_l)W_{h,j} \] 最后用SGD训练模型。

LorSLIM

这篇文章还是在做一般的SLIM模型，但是更改了一下后面的正则项，将目标函数变为 \[ \begin{aligned} \min_W &\frac{1}{2}\|A-AW\|^2_F+\frac{\beta}{2}\|W\|^2_F+\lambda\|W\|_1+z\|W\|_*\\ \text{s.t. }&W\geq0\\ &\text{diag}(W)=0\\ \end{aligned} \] 最后一项正则项为nuclear norm，这样的得到的解更为稀疏，同时如果加上这个正则项之后，目标函数的求解就不能用glmnet了，所以作者引入了一个凸优化的经典算法ADMM，Alternating Direction Method of Multipliers，ADMM本来是为了优化 \[ \min_{x,z}f(x)+g(z)\\ s.t. Ax+Bz=c \] 这样的约束极值问题，ADMM求其增广拉格朗日模型 \[ L_{\rho}(x,z,\mu)=f(x)+g(z)+\mu^{T}(Ax+Bz-c)+\frac{\rho}{2}\|Ax+Bz-c\|^2_2 \] 迭代式为 \[ x^{k+1}=\min_xL_{\rho}(x,z^k,\mu^k)\\ z^{k+1}=\min_xL_{\rho}(x^{k+1},z,\mu^k)\\ \mu^{k+1} = \mu^{k}+\rho(x^{k+1}-z^{k+1}) \] 具体推导过程见我之后的博客~通过这样方式计算出来的矩阵\(W\) 会更加稀疏，同时效果也较好。果然凸优化算法还是魅力满满呀。

GSLIM

这篇文章稍微弯弯饶了一下，是一篇将SLIM于MF模型融合的文章，先根据矩阵分解模型计算出隐向量矩阵 \[ \min_{U,V}\|A-U^TV\|^2_F+\lambda_1(\|U\|^2_F+\|V\|^2_F) \] 再根据用户的隐向量矩阵\(U\) 有 \[ \min_{P,W}\|U-PW\|^2_F+\lambda_2\|W\|_1 \] 其中\(P\) 是SLIM模型中的权重，\(W\) 代表了稀疏编码的相关系数，最后的评分估计为 \[ \hat{r}_{i,j}=u'_i\cdot v_j=[P\mathop{\arg\max}_{w}{(u_i-Pw)}]v_j \] 总的来说就是做了两步矩阵分解，只不过第二步比较像SLIM而已，看到这里我也是一头雾水，我猜作者这么做的目的是为了尽可能去刻画相似用户对评分的影响。

TODO

[9]和[11]涉及到一些基于矩阵补全与低秩分解的内容，留个坑，之后把基于矩阵的推荐模型总结一下，然后查阅相关内容的时候，看见了知乎上覃含章的回答，打算下一阶段好好研究一下这个。
[1]是去年的best paper，简单浏览过一次，做全局和局部的SLIM，我等着过一阵细细再品味一下。
其实参考文献本来有20+，但是有些我下载不到就删掉了。

BTW，牢骚写在最后，我对SLIM已经审美疲劳了，到了看见想吐的地步，大概所有这些看了两周多点，现在整个人都不好了，怎么说呢，大概就是天天回家看老婆的那种感觉吧...现在只想换个方向论文看一看。。大概可能去看看CV的。。

SLIM资料汇总

刚好看见别人博客里总结了，复制过来。