论文笔记 | ICDM2018 | Self-Attentive

作者: ktulu7 | 来源:发表于2019-06-28 23:31 被阅读0次

SASRec-title.png

论文地址：https://arxiv.org/abs/1808.09781

官方代码：https://github.com/kang205/SASRec

一为什么读这篇

搜索用self-attention做推荐的相关文章，本篇算是比较相关的而且排名较高，作者开放的源码也是基于transformer那个第三方的开源实现，算是一脉相承，看看别人是怎么改transformer，应用到推荐里的。

二截止阅读时这篇论文的引用次数

2019.6.25 15次。

三相关背景介绍

中了18年IEEE的ICDM，同年8月挂到arXiv上。算是跟进比较及时的，transformer出来一年后就应用到自己工作的领域并发了paper。两位作者来自加州圣地亚哥大学，一作Wang-Cheng Kang是个华人小哥PHD，16年本科毕业于南大，期间受周志华教授指导，PHD是推荐系统和CV双修，CVPR和RecSys的论文都发过，又是一个强人。。二作Julian McAuley是Kang的老板，还在coursera上开了一门专项课程Python Data Products for Predictive Analytics

四关键词

Sequential Recommendation

self-attention

五论文的主要贡献

1 将Transformer应用在序列推荐问题上

2 做了细致的剥离对比实验

六详细解读

0 摘要

动态序列是许多推荐系统的关键特征，为了利用这一点，主要有马尔科夫链（MCs）和RNN方法。其中MC适用于短序列，稀疏数据集，模型简单；RNN原则上适用于长序列，密集数据集，不过模型更复杂。本文目标是平衡这两个目标，通过提出基于序列模型的self-attention(SASRec)，使之可以捕获长期语义(像RNN那样)，但是使用attention机制，使预测基于相关的少数行为(像MC那样)。在每一个时间步，SASRec从用户的历史行为中寻找哪些item是"相关的"，并基于它们来预测下一个item。

1 介绍

序列推荐研究主要涉及到如何简便地捕获高阶动态。本文主要就是探索将self-attention机制应用到序列推荐问题上。希望这个想法可以解决MC和RNN的两个问题，一方面能够从过去的所有行为中获取context(像RNN)，另一方面能够以少量的行为进行预测(像MC)。本文提出的SASRec（Self-Attention based Sequential Recommendation）如图1所示。

SASRec-fig1.png

2 相关工作

2.1 常规推荐

基于point-wise，pairwise的方法来解决隐式反馈关于"未观察到"这种二义的解释。主要都是基于矩阵分解（MF）的方法来发现用户偏好和item属性。还有近年的深度学习方法用于提取特征或用来替代传统的MF方法。如NeuMF，AutoRec。

2.2 时序推荐

TimeSVD++通过将时间划分为几个段，并分别对user和item建模达到了很好的效果。

2.3 序列推荐

有一阶的MC方法，高阶的MC方法。基于CNN的Caser，基于RNN的GRU4Rec。

2.4 Attention机制

Attention机制背后的本质理念是，顺序输出的每项都依赖于模型应该连续关注的某些输入的"相关"部分。还有个优势是基于attention的方法更容易解释。例如AFM(Attentional Factorization Machines)学习每个特征交互对于内容感知推荐的重要性。

本文工作受transformer启发，提出基于self-attention的序列推荐模型。因为序列推荐的问题与机器翻译有很大差异，所以需要对模型进行特殊设计。

3 方法

定义用户行为序列为 $\mathcal{S}^{u}=\left(\mathcal{S}_{1}^{u}, \mathcal{S}_{2}^{u}, \ldots, \mathcal{S}_{\left|\mathcal{S}^{u}\right|}^{u}\right)$ ，在时间步 $t$ ，模型预测的下一个item取决于之前的 $t$ 个item。模型输入可以视为 $\left(\mathcal{S}_{1}^{u}, \mathcal{S}_{2}^{u}, \ldots, \mathcal{S}_{\left|\mathcal{S}^{u}\right| - 1}^{u}\right)$ ，其期望输出是同样序列的"偏移"版本： $\left(\mathcal{S}_{2}^{u}, \mathcal{S}_{3}^{u}, \ldots, \mathcal{S}_{\left|\mathcal{S}^{u}\right|}^{u}\right)$ 。所用符号如表1所示。

SASRec-table1.png

3.1 Embedding层

将训练序列 $\left(\mathcal{S}_{1}^{u}, \mathcal{S}_{2}^{u}, \ldots, \mathcal{S}_{\left|\mathcal{S}^{u}\right| - 1}^{u}\right)$ 转为固定长度序列 $s=\left(s_{1}, s_{2}, \dots, s_{n}\right)$ 。如果序列长度超过 $n$ ，则用最近的 $n$ 个行为。如果不足，则从左补足直到长度为 $n$ 。

位置Embedding

因为self-attention并不包含RNN或CNN模块，因此它不能感知到之前item的位置。本文给输入Embedding插入可学习的位置Embedding $\mathbf{P} \in \mathbb{R}^{n \times d}$ ：
$\widehat{\mathbf{E}}=\left[\begin{array}{c}{\mathbf{M}_{s_{1}}+\mathbf{P}_{1}} \\ {\mathbf{M}_{s_{2}}+\mathbf{P}_{2}} \\ {\cdots} \\ {\mathbf{M}_{s_{n}}+\mathbf{P}_{n}}\end{array}\right]$
本文也试了transformer中固定的位置Embedding，不过效果更糟。

3.2 Self-Attention块

Transformer中的缩放点积attention定义如下：
$\text { Attention }(\mathbf{Q}, \mathbf{K}, \mathbf{V})=\operatorname{softmax}\left(\frac{\mathbf{Q} \mathbf{K}^{T}}{\sqrt{d}}\right) \mathbf{V}$

Self-Attention层

本文中，self-attention以embedding $\widehat{\mathbf{E}}$ 作为输入，通过线性投影将它转为3个矩阵，然后输入attention层：
$\mathbf{S}=\operatorname{SA}(\widehat{\mathbf{E}})=\text { Attention }\left(\widehat{\mathbf{E}} \mathbf{W}^{Q}, \widehat{\mathbf{E}} \mathbf{W}^{K}, \widehat{\mathbf{E}} \mathbf{W}^{V}\right)$

Causality

为了避免穿越问题，需要禁止 $Q_{i}$ 和 $\mathbf{K}_{j}(j>i)$ 之间所有的连接。

Point-wise前馈网络

尽管self-attention能够用自适应权重聚集之前所有item的embedding，最终它仍然是个线性模型。为了增加非线性同时考虑不同隐式维度之间的交互，用了一个两层的point-wise前馈网络：
$\mathbf{F}_{i}=\mathrm{FFN}\left(\mathbf{S}_{i}\right)=\operatorname{ReLU}\left(\mathbf{S}_{i} \mathbf{W}^{(1)}+\mathbf{b}^{(1)}\right) \mathbf{W}^{(2)}+\mathbf{b}^{(2)}$

3.3 Self-Attention块的堆叠

堆叠公式如下：
$\mathbf{S}^{(b)}=\mathrm{S} \mathrm{A}\left(\mathbf{F}^{(b-1)}\right) \\ \mathbf{F}_{i}^{(b)}=\operatorname{FFN}\left(\mathbf{S}_{i}^{(b)}\right), \quad \forall i \in\{1,2, \ldots, n\}$
然而随着网络的加深也出现几个问题：

模型容量的增加导致过拟合
由于梯度消失训练过程变得不稳定
更多的参数需要更长的训练时间

受Transformer启发，用了LayerNorm，Dropout，残差连接：
$g(x)=x+\text { Dropout }(g(\text { LayerNorm }(x)))$
其中 $g$ 表示self-attention层或前馈网络。

LayerNorm公式如下：
$\text { LayerNorm }(\mathbf{x})=\alpha \odot \frac{\mathbf{x}-\mu}{\sqrt{\sigma^{2}+\epsilon}}+\boldsymbol{\beta}$
其中 $\odot$ 为element-wise积(Hadamard product)， $x$ 为包含所有特征的一个样本。

3.4 预测层

采用MF层来预测相关的item $i$ ：
$r_{i, t}=\mathbf{F}_{t}^{(b)} \mathbf{N}_{i}^{T}$
其中 $r_{i, t}$ 是给定 $t$ 个items，下一个item $i$ 的相关性。 $\mathbf{N} \in \mathbb{R}^{|\mathcal{I}| \times d}$ 是一个item embedding矩阵。

共享Item Embedding

为了减少模型尺寸及避免过拟合，用一个item embedding $\mathrm{M}$ ，即：
$r_{i, t}=\mathbf{F}_{t}^{(b)} \mathbf{M}_{i}^{T}$

显式用户建模

为了提供个性化推荐，当前主要有两种方法：

学习显式的用户embedding表示用户偏好(MF，FPMC，Caser)
考虑用户之前的行为，通过访问过的item的embedding推测隐式的用户embedding

本文采用第二种方式，同时额外在最后一层插入显式用户embedding，例如通过加法实现 $r_{u, i, t}=\left(\mathbf{U}_{u}+\mathbf{F}_{t}^{(b)}\right) \mathbf{M}_{i}^{T}$ 。但是通过实验发现增加显式用户embedding并没有提升效果。。

3.5 网络训练

定义 $O_{t}$ 为时间步 $t$ 的期望输出：
$o_{t}=\left\{\begin{array}{ll}{<\mathrm{pad}>} & {\text { if } s_{t} \text { is a padding item }} \\ {s_{t+1}} & {1 \leq t<n} \\ {\mathcal{S}_{\left|S^{u}\right|}^{u}} & {t=n}\end{array}\right.$
用二元交叉熵损失作为目标函数：
$-\sum_{\mathcal{S}^{u} \in \mathcal{S}} \sum_{t \in[1,2, \ldots, n]}\left[\log \left(\sigma\left(r_{o_{t}, t}\right)\right)+\sum_{j \notin \mathcal{S}^{u}} \log \left(1-\sigma\left(r_{j, t}\right)\right)\right]$

3.6 复杂度分析

空间复杂度

总参数量为： $O\left(|\mathcal{I}| d+n d+d^{2}\right)$

时间复杂度

主要是self-attention层和前馈网络，占 $O\left(n^{2} d+n d^{2}\right)$ 。但是因为self-attention层可以完全并行化，所以 $O\left(n^{2} d\right)$ 也不是什么问题。实验发现速度10倍于基于RNN和基于CNN的方法。

处理长序列

虽然通过实验经验性地验证了本文方法的效率，但最终还是无法扩展到很长的序列。未来的工作可能有：

使用restricted self-attention『A time-restricted self-attention layer for asr』
将长序列切分为段『Personalized top-n sequential recommendation via convolutional sequence embedding』

3.7 讨论

本文发现SASRec可以视为某种经典CF模型的泛化。

退化为已有模型

经过简化SASRec可以视为FMC，FPMC，FISM。(这里感觉好牵强)

基于MC的推荐

本文解决了MC的问题(长序列)

基于RNN的推荐

本文解决了RNN的问题(并行计算，最大路径长度)

4 实验

实验设计是为了回答下面4个问题：

SASRec是否超过了当前包括基于CNN/RNN模型的方法，达到了SOTA

SASRec架构中各种组件的影响是什么

训练效率和扩展性如何

Attention权重是否能学到有意义的模式，关于位置或item属性

4.1 数据集

SASRec-table2.png

数据集划分为3个部分。最后一次行为为测试集，倒数第二次行为为验证集，剩下的为训练集。测试时也用了验证集的数据。

4.2 比较方法

将对比方法分为三类。

第一类为只考虑用户反馈不考虑序列行为顺序的常规推荐方法。包括PopRec，BPR

第二类为基于一阶马尔科夫链的序列推荐，考虑了最后访问的一个item。包括FMC，FPMC，TransRec

第三类为深度学习方法，考虑之前几个或全部的item。包括GRU4Rec，GRU4Rec+，Caser

4.3 实现细节

SASRec的默认版本，用了2个self-attention块(b=2)，经学习获得的位置embedding，embedding层中的item embedding和预测层中的是共享的。优化器是Adam，学习率为0.001，batch_size=128，MovieLens-1M数据集的dropout比率为0.2，由于稀疏性其他数据集的比率为0.5。MovieLens-1M的最大序列长度n设置为200，其他数据集设置为50。粗略来看大概是每个用户的平均行为数。

4.4 评估指标

采用两种常见的Top-N指标，Hit Rate@10和NDCG@10。为了避免过重的计算量，对每个用户随机采样100个负item，加上ground-truth item，对这101个item排序计算其指标。

4.5 推荐效果

这里回答了问题1。

SASRec-table3.jpg

效果如表3所示，发现非神经网络方法(a-e)在稀疏数据集上表现好点，神经网络方法(f-h)在密集数据集上表现更好。而本文方法在两种数据集上表现都更好。

SASRec-fig2.jpg

图2分析了关键超参隐式维度 $d$ 的影响，发现本文方法 $d$ 越大效果越好，对所有的数据集，当 $d \geq 40$ 达到满意的效果。

4.6 剥离实验

这里回答了问题2。默认方法和8个变种方法(d都是50)的效果如表4所示。

SASRec-table4.jpg

移除位置embedding

除了稀疏数据集Beauty，效果变差。这个变种也许适合稀疏数据集，这种情况下通常用户序列都很短。
不共享Item Embedding

性能严重下降，有可能是因为过拟合
移除残差连接

性能严重下降
移除dropout

dropout在稀疏数据集上更有效，也说明密集数据集上过拟合问题更少点
块的个数

块越多更适合于密集数据集
Multi-head

2个头的效果比1个头的稍微糟点，没有像Transformer原文用那么多头，因为d的维度只有50，不像Transformer有512，所以不适合分解为更小的子空间。

4.7 训练效率和扩展性

从训练速度和闭合时间两方面来回答问题3。

SASRec-fig3.jpg

序列越长，效果越好，如表5所示。

SASRec-table5.jpg

4.8 可视化Attention权重

这里回答问题4。

SASRec-fig4.jpg

通过a和c的对比，发现模型在稀疏数据集上更倾向关注最近的item，而在密集数据集上对最近的item较少关注。这说明本文方法可以自适应的处理稀疏和密集数据集。

通过b和c的对比，说明位置embedding的影响，没有它们attention权重基本上是均匀分布。

通过c和d的对比，说明模型的层次性，更高的层倾向于关注最近的位置。可能是因为第一个self-attention块已经考虑了之前所有的item，所以第二个块无需考虑更远的位置。

总之，通过可视化可以说明self-attention机制是自适应的，有位置感知以及有层次性的。

七小结

本文整个感觉其实就是将transformer的self-attention应用到推荐上来，没有什么特别创新的地方，属于应用型论文。以现在的观点来看，好像很普通，不过考虑到transformer出来不久后本文工作就跟上了，这点还是很厉害的。感慨一下搞科研也得追热点，而且不能只盯着自己那一块东西，得看大领域的热点。此外，通过查找作者的背景资料，根据作者过往产出成果，感觉本文应该不是坑，是可以借鉴应用的。

素质四连

要解决什么问题

序列推荐问题

用了什么方法解决

transformer的self-attention机制

效果如何

超过了基于马尔科夫链，CNN/RNN的方法，速度也快很多

还存在什么问题

没有特别创新的改造，就是应用了一下self-attention

算法背后的模式和原理

拿来主义，将不同领域的方法工具拿来用，针对要解决的具体问题细致的调参

八补充

同一天在arXiv上发表的AttRec：Next Item Recommendation with Self-Attention