一、LightSAN [2021]

《Lighter and Better: Low-Rank Decomposed Self-Attention Networks for Next-Item Recommendation》

1. 自注意力网络（self-attention network: SAN ）已广泛应用于序列推荐，但其仍受限于以下问题：

   • (1) ：自注意力的平方复杂度及对过参数化（over-parameterization ）的敏感性。

   • (2)：隐式的 position encoding 导致的序列关系（sequential relations ）建模不准确。

   本文提出低秩分解自注意力网络（low-rank decomposed self-attention network: LightSAN ）以解决这些问题。具体而言，我们引入低秩分解自注意力，将用户历史行为投影到少量恒定数量的潜在兴趣（latent interests ）中，并通过 item-to-interest interaction 生成 context-aware representation 。该方法在时间和空间复杂度上均与用户历史序列的长度呈线性关系，且对过参数化更具鲁棒性。此外，我们设计了 decoupled position encoding 以更精确地建模 items 之间的序列关系。在三个真实数据集上的实验表明，LightSAN 在效果和效率上均优于现有 SANs-based 的推荐模型。

2. 序列推荐因其在电商、影视等在线服务中的广泛应用而备受关注。尽管基于 RNN 和 CNN 的方法（如 GRU4Rec 和 Caser ）已被提出，近年来自注意力网络（self-attention network: SAN ）展现出更大潜力，因其能通过让 items 充分关注上下文（用户过去交互过的所有 items ），从而更好地从用户历史行为中建模 sequential dynamics。然而，SANs-based 的推荐模型（如 SASRec 和 BERT4Rec ）存在两大缺陷：

   • SAN 要求用户的 historical items 直接相互关注（称为 item-to-item interaction），这需要的时间和空间会随着历史序列长度呈二次方增长 。因此，在实际应用中，运行成本可能过高。

     此外，直接的 item-to-item interaction 也容易出现过参数化（over-parameterization ）问题。一个典型的序列推荐器涉及对大量 items 的建模。然而，由于 items 的长尾属性，许多 items 没有足够的交互。因此，低频 items 的 embeddings 将无法得到很好的训练，其相关的 attention weights （由 item-to-item interaction 所生成）可能不准确。

   • 传统 SAN 直接将 item embeddings 与 position embeddings 相加。近期研究（《Rethinking Positional Encoding in Language Pre-training》）表明，item 与 absolute position 之间缺乏强相关性。因此，此类处理可能引入 noisy correlations ，并限制模型在捕获用户的 sequential patterns 上的能力。

   一些先前的工作，如 Linformer 和 Performer ，尝试提升 SAN 效率。但这些方法主要关注通用加速，未考虑用户行为的特性，在 recommendation 场景中效果有限。

   在这项工作中，我们提出了一种新颖的方法 LightSAN ，它利用用户历史的 low-rank 属性来加速。具体来说，我们假设用户的 historical items 的大部分可以被归类为不超过 $k$$k$ （一个小的常数）个潜在兴趣。潜在兴趣（ latent interest ）代表用户对某一组 items 的偏好；在这项工作中，潜在兴趣是一个从 user’s item embeddings 的序列中所生成的向量。基于这一属性，我们引入了低秩分解自注意力机制（low-rank decomposed self-attention ）：将用户历史投影到 $k$$k$ 个潜在兴趣中，并且用户 historical items 中的每个 item 只需要与这 $k$$k$ 个潜在兴趣进行交互，以建立其 context-awareness （称为 item-to-interest interaction）。这使得 SAN 的时间和空间复杂度相对于用户历史序列的长度呈线性关系。同时，它避免了 item-to-item interaction，使模型对 over-parameterization 更具抗性。另一方面，我们通过所提出的 decoupled position encoding 单独计算 position correlations ，这显式地对 items 之间的 sequential relations 进行了建模。因此，它通过消除 noisy correlations ，有利于建模用户的 sequential patterns。我们的主要贡献总结如下：

   本文贡献如下：

   • 一种新颖的 SANs-based 的序列推荐器 LightSAN ，具有两个优点：

     • (1)：低秩分解的自注意力机制，用于更高效、更精确地建模 context-aware representations 。

     • (2)：decoupled position encoding ，用于更有效地建模 items 之间的序列关系。

   • 在三个基准推荐数据集上进行了广泛的实验，LightSAN 在有效性和效率方面均优于各种 SANs-based 的方法。

1.1 方法

1. 在这项工作中，我们专注于 next-item recommendation 。给定用户 $u$$u$ 在时间戳 $t$$t$ 之前的有序历史 items 序列 $\{i_1^u,\cdots ,i_t^u\}$$\left\{i_1^u, \cdots,i_t^u\right\}$，我们需要预测 next item ，即 $i_{t+1}^u$$i_{t+1}^u$。我们旨在改进经典的 SAN ，使其更轻量、更出色。具体来说，我们提出了 LightSAN ，它利用低秩分解的自注意力机制（low-rank decomposed self-attention ）对 items’ relevance 进行精确建模，并使用 decoupled position encoding 对 items 的 sequential relations进行显式建模。LightSAN 的整体框架如 Figure 1 所示，接下来将介绍其细节。

   这篇论文价值不大，虽然号称是序列长度的线性复杂度，但是这个线性复杂度仅仅是左侧的 Self-Attention 部分，右侧的 Position Encoding 仍然是序列长度的平方复杂度。

   

1.1.1 Low-Rank Decomposed Self-Attention

1. 我们使用 low-rank decomposed self-attention 来生成 context-aware representations。它将 items 投影到 $k$$k$ 个潜在兴趣中，并通过与潜在兴趣的交互从而将 item 与 context 进行整合。这样的工作流程将复杂度从 $O(n^2)$$O(n^2)$ 降低到 $O(nk)$$O(nk)$ ，并有效地缓解了 over-parameterization 问题。

   实际上，受限于 positional attention，整体复杂度仍然是 $O(n^2)$$O(n^2)$ 而不是 $O(nk)$$O(nk)$ 。

2. Item-to-Interest Aggregation ：我们假设用户历史 items 的大多数可以被归类为不超过 $k$$k$ （一个小的常数）个潜在兴趣。因此，我们提出一个可学习的投影函数 $f:{\mathbb{R}}^{n\times d}\to {\mathbb{R}}^{k\times d}$$f:\mathbb R^{n\times d}\rightarrow \mathbb R^{k\times d}$，从而将历史 items 聚合为潜在兴趣。给定 item embedding matrix $\mathbf{H}\in {\mathbb{R}}^{n\times d}$$\mathbf H\in \mathbb R^{n\times d}$ 作为输入，其中 $n$$n$ 为 items 数量、$d$$d$ 为 hidden-dimension size，我们首先计算 item-to-interest 的 relevance 分布：

   $$\mathbf{D}=\text{softmax}\left(\mathbf{H}{\mathbf{\Theta }}^{\mathrm{\top }}\right)\in {\mathbb{R}}^{n\times k}$$

   其中：$\mathbf{\Theta }\in {\mathbb{R}}^{k\times d}$$\mathbf \Theta\in \mathbb R^{k\times d}$ 是一个可学习的参数。

   $\mathbf{D}$$\mathbf D$ 刻画了 $n$$n$ 个 item 与 $k$$k$ 个兴趣的相似度（通过 softmax 归一化）；然后通过这个相似度来反推 interest embedding，即 $\tilde{\mathbf{H}}$$\tilde{\mathbf H}$ 。

   然后，我们使用分布 $\mathbf{D}$$\mathbf D$ 对输入的 item embedding matrix 进行聚合，得到 interest representation matrix ：

   $$\tilde{\mathbf{H}}=f(\mathbf{H})={\mathbf{D}}^{\mathrm{\top }}\mathbf{H}={\left(\text{softmax}\left(\mathbf{H}{\mathbf{\Theta }}^{\mathrm{\top }}\right)\right)}^{\mathrm{\top }}\mathbf{H}\in {\mathbb{R}}^{k\times d}$$

   • 首先，得益于函数 $f$$f$ ，item embedding matrix $\mathbf{H}$$\mathbf H$ 被转换为低秩的 interest representation $\tilde{\mathbf{H}}$$\tilde{\mathbf H}$ 。这种聚合将有效地帮助减小 attention matrix 的大小，从而使网络的 feed-forward pass 更加高效。

   • 此外，与潜在兴趣的 interaction ，要比直接关注 items 更可靠。因为根据 $\tilde{\mathbf{H}}$$\tilde{\mathbf H}$ 的公式，潜在兴趣捕获了item 序列所反映的用户整体偏好。因此，在 item-to-interest interaction 下，与低频 items 相关的注意力权重将更加准确，这缓解了 over-parameterization 问题。

   我们的 item-to-interest aggregation 在形式上与 Linformer 的低秩线性映射（low-rank linear mapping）类似。然而，它们之间有两个主要区别。

   • 首先，我们的模型由一个 $(k\times d)$$(k\times d)$ 维的矩阵 $\mathbf{\Theta }$$\mathbf\Theta$ 来参数化，而 Linformer 中的映射矩阵是 $(n\times k)$$(n\times k)$ 维度的。我们认为固定的 $n$$n$ 值使得模型难以适应不同的序列长度。

   • 其次，item-to-interest aggregation 通过一个可学习的 item-to-interest relevance distribution 从而将 items 投影到潜在兴趣空间，而 Linformer 通过直接的线性映射来实现。我们通过实验证明，基于线性映射的性能是有限的，因为 items 和 latent interests 并不遵循简单的线性关系。

3. Item-to-Interest Interaction：我们通过线性投影 ${\mathbf{W}}_Q,{\mathbf{W}}_K,{\mathbf{W}}_V\in {\mathbb{R}}^{d\times d}$$\mathbf W_Q,\mathbf W_K,\mathbf W_V \in \mathbb R^{d\times d}$ 将 input embedding sequence $\mathbf{X}$$\mathbf X$ 转换为三个矩阵 $\mathbf{Q},\mathbf{K},\mathbf{V}\in {\mathbb{R}}^{n\times d}$$\mathbf Q, \mathbf K, \mathbf V\in \mathbb R^{n\times d}$ ，并将它们馈入到我们的 low-rank decomposed self-attention中。普通多头自注意力中的原始 $\mathbf{K}\in {\mathbb{R}}^{n\times d}$$\mathbf K\in \mathbb R^{n\times d}$ 和 $\mathbf{V}\in {\mathbb{R}}^{n\times d}$$\mathbf V\in \mathbb R^{n\times d}$ 通过 item-to-interest aggregation $f$$f$ 映射为 $\tilde{\mathbf{K}}\in {\mathbb{R}}^{k\times d}$$\tilde{\mathbf K}\in \mathbb R^{k\times d}$ 和 $\tilde{\mathbf{V}}\in {\mathbb{R}}^{k\times d}$$\tilde{\mathbf V}\in \mathbb R^{k\times d}$ ：

   $${\tilde{\mathbf{S}}}_i=\text{softmax}\left(\frac{{\mathbf{Q}}_i{\tilde{\mathbf{K}}}_i^{\mathrm{\top }}}{\sqrt{d/h}}\right){\tilde{\mathbf{V}}}_i=\text{softmax}\left(\frac{{\mathbf{Q}}_{i}f({\mathbf{K}}_i{)}^{\mathrm{\top }}}{\sqrt{d/h}}\right)f({\mathbf{V}}_i)\in {\mathbb{R}}^{n\times d}$$

   其中：$h$$h$ 为 attention heads 的数量，$i$$i$ 是 head ID 。

   为什么这里是先线性投影再进行 item-to-interest aggregation （包含非线性），而不是先进行 item-to-interest aggregation 再进行线性投影？如果是后者，那么 ${\tilde{\mathbf{S}}}_i$$\tilde{\mathbf S}_i$ 将是 ${\mathbb{R}}^{k\times d}$$\mathbb R^{k\times d}$ ，变成了 interest-level 而不是 item-level 的。

   $\{{\tilde{\mathbf{S}}}_1,\cdots ,{\tilde{\mathbf{S}}}_h\}$$\left\{\tilde{\mathbf S}_1,\cdots,\tilde{\mathbf S}_h\right\}$ 被拼接起来，从而作为最终的 $\tilde{\mathbf{S}}$$\tilde{\mathbf S}$ ，这就是 context-aware representation 。我们应用上述自注意力机制的 multiple layers ，以促进 item 和 context 的深度融合。

   我们的自注意力机制的复杂度从 $O(n^2)$$O(n^2)$ 降低到了 $O(nk)$$O(nk)$，因为 item 只需要关注固定数量的潜在兴趣。

   • 虽然许多高效的Transformer （如 Linformer ）实现了相同的复杂度降低，但它们要求 $n$$n$ 为固定值，这在处理不同序列长度时缺乏灵活性。

   • 一些高效的 Transformer 也尝试从 hidden-dim 的角度降低复杂度（即从 $n\times d$$n\times d$ 到 $n\times k$$n\times k$）。然而，运行成本仍然容易受到长序列的影响，并且这种加速是以 context representation 质量的潜在损失为代价的。

1.1.2 Decoupled Position Encoding

1. 传统的 SANs-based 的推荐器将 item embeddings （$\mathbf{E}$$\mathbf E$）和 position embeddings （$\mathbf{P}$$\mathbf P$）混合起来以引入序列关系（sequential relations），即 $(\mathbf{E}+\mathbf{P})$$(\mathbf E + \mathbf P)$ 。结果，两个 items （例如 item $i$$i$ 和 item $j$$j$）之间的相关性为 $({\overrightarrow{\mathbf{e}}}_i+{\overrightarrow{\mathbf{p}}}_i){({\overrightarrow{\mathbf{e}}}_j+{\overrightarrow{\mathbf{p}}}_j)}^{\mathrm{\top }}$$\left(\mathbf{\vec e}_i + \mathbf{\vec p}_i\right)\left(\mathbf{\vec e}_j + \mathbf{\vec p}_j\right)^\top$ ，其中 ${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec e}_i\in \mathbb R^d$ 为 $\mathbf{E}\in {\mathbb{R}}^{n\times d}$$\mathbf E\in \mathbb R^{n\times d}$ 的第 $i$$i$ 行，${\overrightarrow{\mathbf{p}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec p}_i\in \mathbb R^d$ 为 $\mathbf{P}\in {\mathbb{R}}^{n\times d}$$\mathbf P\in \mathbb R^{n\times d}$ 的第 $i$$i$ 行。这等价于 它等于：

   $${\overrightarrow{\mathbf{e}}}_i{\overrightarrow{\mathbf{e}}}_j^{\mathrm{\top }}+{\overrightarrow{\mathbf{p}}}_i{\overrightarrow{\mathbf{p}}}_j^{\mathrm{\top }}+{\overrightarrow{\mathbf{e}}}_i{\overrightarrow{\mathbf{p}}}_j^{\mathrm{\top }}+{\overrightarrow{\mathbf{p}}}_i{\overrightarrow{\mathbf{e}}}_j^{\mathrm{\top }}$$

   然而，item-to-position correlations（即，${\overrightarrow{\mathbf{e}}}_i{\overrightarrow{\mathbf{p}}}_j^{\mathrm{\top }}$$\mathbf{\vec e}_i\mathbf{\vec p}_j^\top$ 和 ${\overrightarrow{\mathbf{p}}}_i{\overrightarrow{\mathbf{e}}}_j^{\mathrm{\top }}$$\mathbf{\vec p}_i\mathbf{\vec e}_j^\top$）并不是很强，它们可能会限制模型从序列中捕获 sequential relations 的能力。在这项工作中，我们提出 decoupled position encoding 来对 items 之间的 sequential relations 进行建模，它独立于 modeling context-aware representations ：

   $$\tilde{\mathbf{S}}={\tilde{\mathbf{A}}}_{\text{item}}f(\mathbf{E}{\mathbf{W}}_V)+{\tilde{\mathbf{A}}}_{\text{pos}}(\mathbf{E}{\mathbf{W}}_V)$$

   其中：

   • $f(\cdot )$$f(\cdot)$ 为 $f(\mathbf{H})={\mathbf{D}}^{\mathrm{\top }}\mathbf{H}={\left(\text{softmax}\left(\mathbf{H}{\mathbf{\Theta }}^{\mathrm{\top }}\right)\right)}^{\mathrm{\top }}\mathbf{H}$$f(\mathbf H) = \mathbf D^\top\mathbf H = \left(\text{softmax}\left(\mathbf H \mathbf \Theta^\top\right)\right)^\top \mathbf H$ 。

   • ${\tilde{\mathbf{A}}}_{\text{item}}$$\tilde {\mathbf A}_\text{item}$ 为注意力矩阵：${\tilde{\mathbf{A}}}_{\text{item}}=\text{softmax}\left(\frac{\mathbf{Q}f(\mathbf{K}{)}^{\mathrm{\top }}}{\sqrt{d/h}}\right)$$\tilde {\mathbf A}_\text{item} = \text{softmax}\left(\frac{\mathbf Q f(\mathbf K )^\top}{\sqrt{d/h}}\right)$ 。$\mathbf{Q}=\mathbf{E}{\mathbf{W}}_Q,\mathbf{K}=\mathbf{E}{\mathbf{W}}_K$$\mathbf Q=\mathbf E\mathbf W_Q, \mathbf K = \mathbf E\mathbf W_K$ 。

   • ${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 为：${\tilde{\mathbf{A}}}_{\text{pos}}=\text{softmax}\left(\frac{{\mathbf{P}}_Q{\mathbf{P}}_K^{\mathrm{\top }}}{\sqrt{d/h}}\right)$$\tilde{\mathbf A}_\text{pos} = \text{softmax}\left(\frac{\mathbf P_Q \mathbf P_K^\top}{\sqrt{d/h}}\right)$ 。${\mathbf{P}}_Q=\mathbf{P}{\mathbf{U}}_Q,{\mathbf{P}}_K=\mathbf{P}{\mathbf{U}}_K$$\mathbf P_Q = \mathbf P\mathbf U_Q, \mathbf P_K = \mathbf P\mathbf U_K$ ，其中 ${\mathbf{U}}_Q,{\mathbf{U}}_K\in {\mathbb{R}}^{d\times d}$$\mathbf U_Q, \mathbf U_K\in \mathbb R^{d\times d}$ 是可学习的参数。

   注意：

   • 第一项是 item-to-interest interaction ，其中 ${\tilde{\mathbf{A}}}_{\text{item}}\in {\mathbb{R}}^{n\times k}$$\tilde {\mathbf A}_\text{item}\in \mathbb R^{n\times k}$、$f(\mathbf{E}{\mathbf{W}}_V)\in {\mathbb{R}}^{k\times d}$$f(\mathbf E\mathbf W_V) \in \mathbb R^{k\times d}$ 。计算复杂度为 $O(nkd)$$O(nkd)$ 。

   • 第二项是 item-to-item 的 position 相关性，其中 ${\tilde{\mathbf{A}}}_{\text{pos}}\in {\mathbb{R}}^{n\times n}$$\tilde{\mathbf A}_\text{pos}\in \mathbb R^{n\times n}$、$(\mathbf{E}{\mathbf{W}}_V)\in {\mathbb{R}}^{n\times d}$$(\mathbf E\mathbf W_V)\in \mathbb R^{n\times d}$ 。计算复杂度为 $O(n^{2}d)$$O(n^2d)$。

   为了加速第二项的计算，作者提出${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 可以预先计算一次，并在同一 batch 内的所有用户中共享。然而，即使${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 可以预先计算好，${\tilde{\mathbf{A}}}_{\text{pos}}(\mathbf{E}{\mathbf{W}}_V)$$\tilde {\mathbf A}_\text{pos} (\mathbf E\mathbf W_V)$ 的计算复杂度仍然是 $O(n^{2}d)$$O(n^2d)$，是计算瓶颈。因此，整个模型的计算复杂度仍然是 $O(n^{2}d)$$O(n^2d)$ ，而不是 $O(nkd)$$O(nkd)$ 。

2. 根据上述公式，${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 与 ${\tilde{\mathbf{A}}}_{\text{item}}$$\tilde {\mathbf A}_\text{item}$ （ item-to-interest interaction ）并行独立地计算。通过这样做，sequential relations 被显式地指定，而不会受到 item-to-position correlations 的影响，这提高了我们 low-rank decomposed self-attention 的 representation 的质量。

   此外，${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 可以预先计算一次，并在同一 batch 内的所有用户中共享，因为它与具体的 input 无关。换句话说，在训练阶段和测试阶段，${\tilde{\mathbf{A}}}_{\text{pos}}$$\tilde{\mathbf A}_\text{pos}$ 的计算成本几乎可以忽略不计。

1.1.3 Prediction Layer and Loss Function

1. 与 Transformer 一样，为了赋予模型非线性，我们在每个自注意力层 $l$$l$ 中对 ${\tilde{\mathbf{S}}}^l$$\tilde{\mathbf S}^l$ 应用一个全连接前馈网络，并得到结果 ${\tilde{\mathbf{F}}}^l\in {\mathbb{R}}^{n\times d}$$\tilde{\mathbf F}^l\in \mathbb R^{n\times d}$。在对前 $t$$t$ 个 items 进行编码后，基于第 $t$$t$ 个 item 的最后一层输出（ $L$$L$ 是自注意力层的数量）来预测 next item 。我们使用内积来衡量用户对任意 item $i$$i$ 的偏好：

   $$\text{Pr}(i\mid \{i_1^u,\cdots ,i_t^u\})=⟨{\tilde{\mathbf{f}}}_t^L,{\overrightarrow{\mathbf{e}}}_i⟩$$

   其中：<> 表示内积；${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ 为 item $i$$i$ 的 embedding ；${\tilde{\mathbf{f}}}_t^L$$\tilde{\mathbf f}^L_t$ 为 ${\tilde{\mathbf{F}}}^L$$\tilde{\mathbf F}^L$ 的第 $t$$t$ 行，$1\le t\le n$$1\le t\le n$。

2. 最后，我们采用交叉熵损失来训练我们的模型：

   $$\mathcal{L}=-\log \frac{\exp \left(⟨{\tilde{\mathbf{f}}}_t^L,{\overrightarrow{\mathbf{e}}}_g⟩\right)}{\sum _{i=1}^{|I|}\exp \left(⟨{\tilde{\mathbf{f}}}_t^L,{\overrightarrow{\mathbf{e}}}_i⟩\right)}$$

   其中：item $g$$g$ 为 ground truth item ，$|I|$$|I|$ 为所有 items 的数量。

1.2 实验

1. 数据集和评估方式：我们使用了三个真实世界的基准数据集，包括Yelp 、Amazon Books 和 ML-1M ，其统计信息如 Table 1 所示。遵循先前的工作，我们采用留一法（leave-one-out ）进行评估，并使用 HIT@K 和 NDCG@K 来评估性能。

   对于每个用户，我们将测试集中的 ground truth item 与数据集中的所有其他 items 一起进行排序。模型基于流行的开源推荐框架 RecBole 实现。所有代码、数据集和参数设置均已开源。

   

2. 基线模型：我们考虑了两种类型的基线模型：

   • 1)：通用推荐方法：Pop 、FPMC、GRU4Rec 、NARM 、SASRec 和 BERT4Rec 。

   • 2)：高效的 Transformers：Synthesizer、LinTrans 、Linformer 和 Performer 。

   我们主要介绍第二类方法：

   • (1)：Linformer 通过 $n\times k$$n\times k$ 的线性映射将 $\mathbf{K}$$\mathbf K$ 和 $\mathbf{V}$$\mathbf V$ 的长度维度从 $n$$n$ 减少到 $k$$k$ 。然而，由于线性映射的参数需要固定的值 $n$$n$ ，因此当给定不同的序列长度时，mapping 组件必须重新训练。

   • (2)：Synthesizer 利用合成的注意力权重，这些权重是两个随机初始化的低秩矩阵的分解。Performer 利用 Fast Attention via positive Orthogonal Random features 方法（FAVOR+ ）来近似全尺度 attention kernels 。这两种方法都降低了 hidden-dim 的基数（从到 $d$$d$ 到 $k$$k$ ），与 LightSANs 和 Linformer 降低序列length cardinality （从 $n$$n$ 到 $k$$k$ ）形成对比。

   • (3)：线性 Transformer （LinTrans ）使用 self-attention 的 kernel-based formulation 、以及矩阵乘积的结合律来计算注意力权重。其复杂度 $O(n^2)$$O(n^2)$ 从变为 $O(nd)$$O(nd)$，这意味着它仅适用于 $n\ge d$$n\ge d$ 的情况。

   LightSANs 的时间和空间复杂度（$O(nk)$$O(nk)$）与 Linformer 和 Performer 相同。

1.2.1 主要结果

1. 有效性评估：整体性能如 Table 2 所示，我们有以下观察结果。

   • 所有基于 SANs 的方法都优于其他方法，这得益于多头自注意力机制生成的高质量的 context-aware representations 。

   • LightSANs 和 LightSANs-ape （这个变体用普通 SANs 中的 absolute position encoding 替换了 decoupled position encoding ，以评估我们 low-rank decomposed self-attention 的性能）在所有评估指标上都比其他方法产生了更具竞争力的结果。

     这些结果表明：我们提出的以 item-to-interest interaction 为突出特点的自注意力机制，生成了更有效的 context-aware representation。此外，由于 decoupled position encoding ，LightSANs 优于 LightSANs-ape 。

   其他观察结果：

   • GRU4Rec 和NARM 比 Pop 和 FPMC 表现更好，这得益于神经网络的使用。

   • NARM 比 GRU4Rec 表现更好，因为它在每个 session 中使用注意力机制对用户的序列行为进行建模。

   

2. 效率评估：对 SASRec （原始自注意力机制的代表）和 LightSANs 的效率进行了比较。计算成本是通过在 self-attention module with position encoding 上的 gigabit floating-point operations: GFLOPs 来衡量的；同时，还给出了模型规模（用参数数量衡量）。如 Table 3 所示：

   • 不同模型的参数数量几乎相同，因为 item embedding layer 和 feed-forward networks 是主要组成部分。

   • 尽管模型规模相似，但所提出的方法实现了显著的加速。特别是在序列比其他数据集更长的 ML-1M 数据集上，LightSANs-ape 实现了超过 2 倍的加速性能。LightSANs 比 LightSANs-ape 慢，这是因为我们的 decoupled position encoding 需要额外的计算成本来对用户的 sequential patterns 进行建模。这是在模型效率和额外性能提升之间的权衡。同时，LightSANs 仍然比原始的自注意力机制更高效。

   

   此外，我们绘制了 LightSANs 和其他 SANs-based 的方法在固定 items 总数的情况下，内存使用和推理时间随序列长度的变化情况（均在 Tesla P40 GPU 上进行测试）。如 Figure 2 所示：

   • 随着序列长度的增加，由于其平方复杂度，SASRec 的成本急剧增加。

   • 此外，对于 LightSANs-ape 、LightSANs 和其他方法（LinTrans、Linformer、Performer ），内存使用保持相对较低，并且在长序列上推理速度更快。尽管LightSANs 的模型规模略大于 SASRec ，但我们的方法将注意力矩阵的复杂度从 $O(n^2)$$O(n^2)$ 降低到 $O(nk)$$O(nk)$，这显著降低了内存成本。

   

1.2.2 详细性能分析

1. 我们对 LightSANs 中关键设计进行了有效性分析，结果如 Table 4 所示。

   • decoupled position encoding 的有效性：position encoding 直接影响 SANs 中 items 的 sequential relations 的建模。在这里，我们研究了应用于我们自注意力机制的三种 position encoding 类型。

     • 首先，没有 position encoding 时，两个数据集上的性能都大幅下降，特别是在序列更长的 ML-1M 数据集上。这意味着位置信息对自注意力机制至关重要。

     • 此外，绝对位置编码（LightSANs-ape ）和相对位置编码都比 decoupled position encoding 更差，这验证了将 items 的 relevance 和 sequential relations 解耦的合理性。

   • item-to-interest aggregation 的有效性：由于我们的 item-to-interest aggregation 是对 context-aware representation 进行建模的重要组成部分，我们研究了与简单分解方法相比，它对最终性能的影响。

   • 我们从 LightSANs 中移除低秩分解的部分，性能显著下降。此外，与 SASRec 相比，在 Yelp 数据集上准确率下降，而在 ML-1M 数据集上表现相似。在这两种情况下，低秩分解所实现的加速对 prediction质量没有负面影响。

   • 我们还对 $\mathbf{K}$$\mathbf K$ 和 $\mathbf{V}$$\mathbf V$ 应用奇异值分解（SVD ），从序列中选择具有较大奇异值的 item embedding 。然而，这种简化方法效果不佳，因为它很难进行端到端的优化。