精排序列建模经典方案综述

引言

在互联网应用的精排模型中，往往在特征工程、样本构建、Loss 设计、模型结构等方向进行迭代优化。其中，涉及特征与结构的用户行为序列建模是近几年的热点之一。

序列建模一般有2大方向：

• 检索的序列更长；
• 建模的更精准。

下面梳理近几年的经典序列建模方案，基本也是围绕上述 2 大方向进行不断优化的。

1 DIN

1.1 概述

论文：DIN: Deep Interest Network for Click-Through Rate Prediction
来源：2018，阿里

思想：为了序列建模的更精准，通过 DIN 的 Attention 结构来替换 Base Model 的 Sum-Pooling 结构。

1.2 方案

1.2.1 DIN 的序列检索结构

历史行为中的不同物品对候选物品影响应该是有差异的，Attention 结构正是想打破 Sum-Pooling 的这种缺点。即在 Sum-Pooling 前，基于 Activation Unit （图右上）算出 Weight，然后做 Weighted-Pooling。

值得注意的是，Activation Unit 中的 Out Product 部分，在实践中往往如下处理（供参考），主要是为了增加非线性：

tf.concat([query, seq, query - seq, query * seq])

1.2.2 Dice 替代 PReLU

PReLU 激活函数更容易出现参数更新缓慢甚至梯度消失的问题，论文使用更具泛化性的 Dice 激活函数。其二者的公式和函数图像如下所示：

PReLU：

$$f(s)= \begin{cases} s & \mathrm{if~}s>0 \\ \alpha s & \mathrm{if~}s\leq0. & \end{cases}=p(s) \cdot s+(1-p(s))\cdot\alpha s$$

其中， $p(s)=I(s < 0)$ 为指示函数

Dice：

$$f(s)=p(s) \cdot s+(1-p(s)) \cdot \alpha s,p(s)=\frac{1}{1+e^{-\frac{s-E[s]}{\sqrt{Var[s]+\epsilon}}}}$$

其中，$\epsilon$一般取$10^{-8}$。可以发现：

• Dice 是 PReLu 的推广，当 E[s] = 0，Var[s]=0 时，Dice 退化为 PReLU;
• 其核心思想是根据输入数据的分布自适应地调整校正。

1.2.3 GAUC 替代 AUC

AUC 代表模型对样本整体的排序能力，不区分用户类型，比如高低活。

而实际线上应用的时候，不同用户之间是不需要对比的，更重要的是：同一个用户下，不同 item 能否区分准确。

故论文提出了 GAUC：

$$\mathrm{GAUC}=\frac{\sum_{i=1}^n\#impression_i\times\mathrm{AUC}_i}{\sum_{i=1}^n\#impression_i}$$

其中，$n$ 表示 User 的数量。

实际中，建议 AUC 和 GAUC 结合一起判断，且后者一般要求 user 级别正负样本兼有。

1.2.4 Mini-batch Aware Regularization

是一种 Adaptive 的正则化方法。行为物品的参数空间大，使得模型容易过拟合，但传统的 L2 正则会对所有参数应用，效率低。
故论文提出了 Mini-batch Aware Regularization 方案：

$$\begin{aligned} & L_{2}\left(w\right)=\left|\left|w\right|\right|^{2}=\sum_{j=1}^{K}\left|\left|w_{j}\right|\right|^{2}=\sum_{\left(x,y\right)\in S}\sum_{j=1}^{K}\frac{I\left(x_{j}\neq0\right)}{n_{j}}\left|\left|w_{j}\right|\right|^{2} \\ & =\sum_{j=1}^{K}\sum_{m=1}^{B}\sum_{(x,y)\in B_{m}}\frac{I(x_{j}\neq0)}{n_{j}}||w_{j}||^{2} \\ & =\sum_{j=1}^{K}\sum_{m=1}^{B}\frac{max_{(x,y)\in B_{m}}[I(x_{j}\neq0)]}{n_{j}}\left|\left|w_{j}\right|\right|^{2} \end{aligned}$$

其中，

• K：特征空间的维度；
• S：全局样本；
• B：mini-batch 的个数；
• $x_j$：每个样本第 j 个特征值；
• $I(x_j \ne 0)$：mini-batch 内，第 j 个特征值均为0的时候该值为0，否则为1；
• $n_j$：样本中第 j 个特征出现的次数。

最后一步，将所有的 $w_j$ 相加转为了只加最大（非0）的一次，如此高频（更重要）的特征正则权重就会变小，衰减慢一些。

1.3 小记：

• DIN 优化了序列中不同 item 的权重、激活函数、正则方案以及评估指标；
• 但没有考虑序列先后关系、兴趣变化，且一般仅适用于短序列（论文中 14 天，序列长平均 35）。

2 DIEN

2.1 概述

论文：Deep Interest Evolution Network
来源：2019，阿里

思想：引入 GRU 构建抽取兴趣层，使用 AUGRU 结构来做兴趣演化层，意在改善 DIN 没有考虑的行为先后关系和兴趣演变过程。

2.2 方案

2.2.1 兴趣提取层（Interest Extractor Layer）

实际中，行为序列可能比较长（14天平均30+），用户兴趣也在不断变迁。所以使用 GRU 来对用户行为之间的依赖进行建模。

选择 GRU 的原因是：

• 克服了 RNN 的梯度消失问题；
• 速度比 LSTM 快。

结合模型图，GRU 的结构如下所示：

$$\begin{aligned} & \mathbf{u}_{t}=\sigma(W^{u}\mathbf{i}_{t}+U^{u}\mathbf{h}_{t-1}+\mathbf{b}^{u}), \\ & \mathbf{r}_{t}=\sigma(W^{r}\mathbf{i}_{t}+U^{r}\mathbf{h}_{t-1}+\mathbf{b}^{r}), \\ & \tilde{\mathbf{h}}_{t}=\mathrm{tanh}(W^{h}\mathbf{i}_{t}+\mathbf{r}_{t}\circ U^{h}\mathbf{h}_{t-1}+\mathbf{b}^{h}), \\ & \mathbf{h}_{t}=(\mathbf{1}-\mathbf{u}_{t})\circ\mathbf{h}_{t-1}+\mathbf{u}_{t}\circ\tilde{\mathbf{h}}_{t} \end{aligned}$$

其中，

• $\sigma$是 simoid 激活函数；
• $\circ$是元素乘；
• $W^u,W^r,W^h \in \mathbb{R}^{n_H \times n_I}$，$U^z,U^r,U^h \in n_H \times n_H$，$n_H,n_I$分别是隐层和输入层的 size；
• $i_t = e_b[t]$是序列中第 t 个物品的 embedding，也是 GRU 的输入。

2.2.2 辅助 Loss

使用辅助 Loss 想要解决的问题：

• GRU 只能学习行为间的依赖，不能有效地学习用户兴趣；
• $L_{target}$ 只包含最终的目标信息，GRU 的隐层没有有效地监督信息；
• 辅助 item embedding 的学习更有效的信息。

具体做法（结合上图）：用户 $i$ 的序列为 $b$，$t$ 时刻的$e_b^i[t]$对应的隐层状态为$h_t$，给其找一个正样本和一个负样本来构建辅助 Loss。

正样本：点击序列的下一个 item，记为$e_b^i[t+1]$；
负样本：除正样本$e_b^i[t+1]$之外的随机采样，记为$\hat e_b^i[t+1]$。

则辅助 Loss 为：

$$L_{aux}= - \frac{1}{N}(\sum_{i=1}^N\sum_{t} \log \sigma {(h_t^i,e_b^i[t+1])} + \log (1 - \sigma{(h_t^i,\hat e_b^i[t+1]))})$$

故整体 Loss 为：

$$L=L_{target}+α \ast L_{aux}$$

2.2.3 兴趣演进层（Interset Evolving Layer）

该层是对 target item 相关的兴趣演化进行建模，使用的是带注意力更新门的 GRU，称为 AUGRU，即通过使用兴趣状态和 target item 计算得到的注意力权重。计算方式如下：

$$a_t = \frac{\exp{(h_t \cdot W \cdot e_a)}}{\sum_{j = 1}^T \exp{(h_j \cdot W \cdot e_a)}}$$

其中，$e_a$ 是 target Ad 的 embedding。

针对此注意力，作者有 3 种用法：

1. AIGRU（GRU with attentional input）
   直接与 Interset Evolving Layer 的输入相乘，即$i_t’ = h_t \asrt a_t$。
2. AGRU（Attention based GRU）
   替换 GRU 种的更新门，即 $ht’ = (1 - a_t) \ast h{t-1}’ + a_t \ast \tilde h_t’$。
3. AUGRU（GRU with attentional update gate） $$\begin{aligned} & \tilde{\mathbf{u}}_{t}=a_{t}*\mathbf{u}_{t}, \\ & \mathbf{h}_{t}=(1-\tilde{\mathbf{u}}_{t})\circ\mathbf{h}_{t-1}+\tilde{\mathbf{u}}_{t}\circ\tilde{\mathbf{h}}_{t} \end{aligned}$$

这里我们将公式各项表示跟前述的 GRU 做了对齐利于理解，实际上就是构建了 $\tilde{\mathbf{u}}{t}$ 来代替 $\mathbf{u}{t}$。

2.3 小记

• GRU 和 AUGRU 增加了模型的复杂度，一定程度能够提高对兴趣的学习，辅助 Loss 的作用不可忽视；
• 结构复杂带来的算力瓶颈是一大要害，作者提到作者提到了 GPU 优化、并行化、模型压缩等缓解方式，整体依然只能扛住 30-50 长度的序列；
• 作者有提过，DIN 的 Attention 在序列变长（>100）后容易出现信息淹没，此处 GRU 也做了不少优化；
• 该模型叠加了不少复杂结构，是否真的有效用，这可能需要以具体场景中的时间为准。

3 BST

3.1 概述

论文：Behavior Sequence Transformer for E-commerce Recommendation in Alibaba
来源：2019，阿里

思想：将当时比较火热的 Transformer 种的 Multi-head Self-attention 结构应用在用户行为序列建模中。

3.2 方案

Transformer 模型的细节这里不过多介绍，其 Encoder 中的每个 Layer 一般由 4 个子层构成，如上图右上。作者核心就是应用了这一部分。简单阐述为下面2块：

• 将用户序列和 target item 看作整个 sequence 作为 Transformer Layer 的输入；
• 引入时序位置信息。

其中，时序位置信息构建如下：

$$pos(v_i) = t(v_t) - t(v_i)$$

实际上就是序列中每个点击行为距离 targte item 的时间差。

3.3 小记

客观上，这篇文章或多或少引起了一些争议：是不是为了蹭 Transformer 热度，水分大不大。

至于到底如何，每个算法工程师可能都有自己的见解。这里我们罗列一些相对比较重要的疑问，供思考和讨论：

1. Transformer 后做 concat 入模，是否合适？
2. 为了做到上述1，限制了序列长度为20，是否具有效性？
3. 时序位置信息的引入，在单位、分桶等处理细节上没有披露。
4. 为何选择将 target item 并入一起做 Multi-head Self-attention，而没有做 Target Attention？

4 DSIN

4.1 概述

论文：Deep Session Interest Network for Click-Through Rate Prediction
来源：2019，阿里

思想：用户在不同的 session 中行为差异明显，这是 DIEN 等没有考虑的，DSIN 中将序列分成多个 session 来处理。

4.2 方案

DSIN 网络结构分为四层

4.2.1 Session划分层（Session Division Layer）

Session 的划分方法：用户在行为序列中，超过半小时间隔处作为 Session 的切分点。

4.2.2 Session兴趣抽取层（Session Interest Extractor Layer）

引入 bias encoding，如下所示：

$$\mathbf{BE}_{(k,t,c)} = \mathbf{w}_k^K + \mathbf{w}_t^T + \mathbf{w}_c^C$$

其中，

• $\mathbf{w}^K \in \mathbb{R} ^{K}$ 是 session 的 bias；
• $\mathbf{w}^T \in \mathbb{R} ^{T}$ 是 session 内行为位置的 bias；
• $\mathbf{w}^C \in \mathbb{R} ^{d_{model}}$ 是行为序列 item 的 embedding 每个元素的 bias。

最终的序列 embedding 为：

$$\mathbf{Q} = \mathbf{Q} +\mathbf{BE}$$

注意：虽然$\mathbf{BE}$维度是$K \times T \times d{model}$，但实际上参数个数为$K + T + d{model}$。

最后针对用户序列应用 Multi-head Self-attention 来抽取兴趣，该结构不再赘述，输出记为 $\mathbf{I}$。

4.2.3 Session兴趣交互层（Session Interest Interacting Layer）

对用户 Session 的兴趣迁移进行建模，作者使用了 Bi-LSTM 结构，该层的最终隐层状态是前后向隐层状态的融合：

$$\mathbf{H}_t=\overrightarrow{\mathbf{h}_{ft}} \oplus \overleftarrow{\mathbf{h}_{bt}}$$

其中，$\overrightarrow{\mathbf{h}{ft}}$ 和 $\overleftarrow{\mathbf{h}{bt}}$ 分别是前向和后向的 LSTM 隐层输出状态。而 $\oplus$ 文中没有明确解释，但我们结合模型图符号惯例以及 Bi-LSTM 的原理，很容易理解其应该是 concat。

4.2.4 Session兴趣激活层（Session Interest Activating Layer）

该层主要就是通过 2 个 Activation Unit 结构来抽取和 target Itemv相关的 Session 兴趣 embedding。可以看到，图中 Activation Unit 是一个经典的 Target Attention 结构。

黄色的部分（更浅层）：

$$\begin{aligned} & a_k^{I}=\frac{\exp(\mathbf{I}_{k}\mathbf{W}^{I}\mathbf{X}^{I}))}{\sum_{k}^{K}\exp(\mathbf{I}_{k}\mathbf{W}^{I}\mathbf{X}^{I})} \\ & \mathbf{U}^{I}=\sum_k^Ka_k^I\mathbf{I}_k \end{aligned}$$

其中，$\mathbf{X}^{I}$ 就是 Query 部分，来自图左侧的 Item Filed 构建的 Embedding，$\mathbf{W}^{I}$是转换矩阵。
而对于蓝色部分（更深层），则就是把$\mathbf{X}^{I}$、$\mathbf{W}^{I}$换成对应的深层参数$\mathbf{X}^{H}$、$\mathbf{W}^{H}$，其余计算保持不变。

4.3 小记

DSIN 本身也是循着提升序列检索精度的方向：

• 将序列拆分成不同的 Session 提供了一定的先验信息；
• 使用 MHTA、 Bi-LSTM 以及 Target Attention 一系列操作，具体有无效用，见仁见智，以具体的时间结果为准。

5 MIMN

5.1 概述

论文：Practice on Long Sequential User Behavior Modeling for Click-Through Rate Prediction
来源：2019，阿里

思想：基于 DIEN 和 DSIN 的优势，MIMN 构建独立的 UIC 模块来更新用户兴趣 embedding，更新只依赖行为 event，不依赖 request。

5.2 方案

5.2.1 挑战

• 序列建模中使用的用户行为序列越长，收益越大。（这点相信大多数场景经验都满足）
• 直接扩增序列会带来显著的 存储问题 和 性能问题。（论文披露：序列150-1k时，存储1T-6T，QPS=500时性能14ms-200m，要求<30ms）

核心解决思路如下图：

• 不存储用户原始的行为序列，只存储用户的兴趣 embedding；
• 用户的兴趣 embedding 是可迭代更新的，并且其只依赖用户行为的 event，独立于 Server，在 request 时直接获取可降低 RT。

5.2.2 神经元图灵机（Neural Turing Machine）

使用记忆参数 $\mathbf{Mt}$来存储序列信息，且有 $m$ 个槽位（slot），$\left {\mathbf{M_t}(i) \right } |{i=1}^m$。

其更新和读取主要由下面2部分构成。

1. 记忆读取（Memory Read）
控制器生成一个寻址的 key 为 $k_t$，针对所有的 memory slot 计算权重：

$$\mathbf{w}_t^r(i)=\frac{\exp(K(\mathbf{k}_t,\mathbf{M}_t(i)))}{\sum_j^m\exp(K(\mathbf{k}_t,\mathbf{M}_t(j)))},for \ i=1,2,...m$$

其中，

$$K\left(\mathbf{k}_t,\mathbf{M}_t(i)\right)=\frac{\mathbf{k}_t^T\mathbf{M}_t(i)}{\|\mathbf{k}_t\|\|\mathbf{M}_t(i)\|}$$

最后输出为：

$$\mathbf{r}_t=\sum_i^mw_t^r(i)\mathbf{M}_t(i)$$

2. 记忆写入（memory write）
首先控制器也会类似 Memory Read 生成一个 $\mathbf{w_t^w}$，此外还会生成加和向量项$\mathbf{a_t}$和衰减向量项$\mathbf{e_t}$。记忆矩阵$\mathbf{M_t}$的更新如下：

$$\mathbf{M_t=(1-E_t)\odot M_{t-1}+A_t}$$

其中，

• $\mathbf{E_t} = \mathbf{w}_t^w \otimes \mathbf{e}_t$；
• $\mathbf{A}{\mathbf{t}}=\mathbf{w}{t}^{\mathbf{w}} \otimes \mathbf{a}_{t}$；
• $\odot$，$\otimes$ 分别表示向量内积和外积。

5.2.3 内存利用率正则（Memory utilization regularization）

原始的 NTM 往往有内存利用不均衡问题，文章的解决方案是：根据不同记忆槽位的写入权重的方差来进行正则。

$$\mathbf{g}_t=\sum_{c=1}^t\mathbf{w}_c^{\tilde{w}}$$

如上所示是截止时间步$t$的累积更新权重，其中$\mathbf{w}_c^{\tilde{w}}$如下构建：

$$\begin{aligned}&P_t= softmax(W_g \mathbf{g}_t) \\ & \mathbf{w}_t^{\tilde{w}}=\mathbf{w}_t^wP_t\end{aligned}$$

其中，$\mathbf{w}_t^w$是上述提到的原始写入权重，$P_t$是转换矩阵，$W_g$是由下列正则 Loss 学习得到：

$$\begin{aligned}&\mathbf{w}^{\tilde{w}}=\sum_{t=1}^T\mathbf{w}_t^{\tilde{w}},\\&\mathbf{L}_{reg}=\lambda\sum_{i=1}^m\left(\mathbf{w}^{\tilde{w}}(i)-\frac{1}{m}\sum_{i=1}^m\mathbf{w}^{\tilde{w}}(i)\right)^2\end{aligned}$$

5.2.4 记忆感知单元（Memory Induction Unit）

NTM 的 memory 一般是存储原始信息的，而 MIMN 的此模块的设计是为了捕捉高阶信息。如下图，UBS 会被分成多个 Channel，即 slot，假设 $m$ 个。
那么在第$\mathbf{t}$时间步的时候，会从 m 个 channel 中根据$\mathbf{w}_t^r(i)$选择 topK 个 channel，对于其中的每一个 channel i 按照下述更新：

$$\mathrm{S}_t(i)=\mathrm{GRU}(\mathrm{S}_{t-1}(i),\mathrm{M}_t(i),e_t)$$

其中，

• $\mathrm{M}_t(i)$是 NTM 的第 i 个 memory slot；
• $e_t$表示新增行为 item 的 embedding。

需要注意：不同 channel 的 GRU 参数是共享的。

5.3 小记

• 开篇的存储问题降到了 2.7T，性能压力降到了 19ms；
• 但模块上的独立，在效果上是否会有一定的折损，不同场景可能有一定差异；
• 普适度上也有一定限制，作者提到2点：行为数据较丰富；行为 event 量 < 模型 request 量（否则 UIC 起不到缓解性能的作用）。

此外，其团队提到由于资源占用、迭代受限，该框架不久后就放弃了这条路线。

6 SIM

6.1 概述

论文：Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction
来源：2020，阿里

思想：为了处理更长的行为序列，构建 GSU（泛检索）+ESU（精检索）两阶段的框架，是一个非常有实战价值的做法。

6.2 方案

6.2.1 挑战

• 序列越长效果越好，尤其是用户行为活跃度高时，长序列就更重要；
• MIMN 处理的序列超过 1k 时效果变差，缺少和 target item 的交互。

作者提出了 GSU（General Search Unit） + ESU（Exact Search Unit） 的方案，如上模型图所示，可以说开辟了序列建模又一新范式。

6.2.2 一阶段 GSU（General Search Unit，通用搜索单元）

该阶段很明显是要从行为序列中粗筛 topK 个与 target item 相关的 candidate item，作者在这里介绍了2种方法，hard-seach 和 soft search。

$$r_i=\begin{cases}Sign(C_i=C_a)&hard-search\\(W_b\mathbf{e}_i)\odot(W_a\mathbf{e}_a)^T&soft-search&\end{cases}$$

1. hard-seach
顾名思义，相对比较粗糙但直接有效，即行为序列中与 target item 具有同类目的就可以作为 candidate item（如模型图中上所示）。

这里有一个点：类目也是一种泛指，具体用几级类目？能不能用其他维度？都需要根据实际场景来选择。

但经验上，选择的维度一定要在业务场景中举足轻重，当然也可以是多个。比如电商的根类目、叶子类目、品牌，内容社区的话题、语言等。

2. soft-search

上述 hard 方式虽然简单直接，但依赖检索类目的质量，相关性无法保障。

一个朴素的想法便是：使用 target item 的 embedding 去检索序列中 item emebdding 距离近的 topK。

如上公式所示，

• $W_b,W_a$ 均是变换矩阵；
• $e_a,e_i$ 分别是 target item 和 candidate item 的 embedding；
• $\odot$ 表示内积。

需要注意，作者提出因短期兴趣和长期兴趣分布有差异，故它们的 item embedding 不能 share，针对 soft-search 模块单独构建了一个网络来辅助学习，如上图左所示。

6.2.3 二阶段 ESU（Exact Search Unit，精准搜索单元）

经过 GSU，序列长度一般下降一个量级以上，该阶段能够应用相对比较复杂的序列建模结构，如模型图右所示。

• 短序列使用的是 DEIN 结构；
• 长序列经过 GSU 检索的 topK 则使用 Multi-head Attention 结构。

最后则是将两个阶段进行联合 training (soft-search 的时候)：

$$Loss=\alpha Loss_{GSU} + \beta Loss_{ESU}$$

6.3 小记

• 文章使用 180 天数据构建长期序列，最长 54000，比 MIMN 提升 54 倍，性能增加 5ms；
• 在 GSU 部分，hard-search 方案几乎没有性能问题，针对 soft-search 文章提到可以使用 MIPS 指令集优化等加速；
• 该方案思路新颖，实践效果佳，也为业界开启了 GSU+ESU 的迭代方向。

7 ETA

7.1 概述

论文：End-to-End User Behavior Retrieval in Click-Through RatePrediction Model
来源：2021，阿里

思想：用 LSH 来加速 GSU 环节，并将 GSU 融入到 ESU 环节，构建端到端，相对两阶段来增加检索一致性。

7.2 方案

7.2.1 SimHash

这个是 ETA 在 GSU 加速的核心，SimHash 是一种局部敏感哈希(LSH)方法，能够近似的计算向量间的相似度，说白了就是为了改善向量内积检索的速度。

文章通过伪代码和向量旋转来解释 SimHash 的原理，我们这里直接讲实操可能更利于理解。假设 $\mathbf{e} \in \mathbb{R^{n \times d}}$表示行为序列的 item embedding，$n,d$ 是序列长度和 embedding size。

那么，SimHash 步骤如下：

• 固定一个随机生成的 Hash 矩阵 $\mathbf{H} \in \mathbb{R}^{d \times m}$，其中 m 是超参数，代表 Hash 编码后的维度；
• 对于每个$e_k$，按照如下方式构建 SimHash 的编码 $sig_k \in \mathbb{R}^{1 \times m}$：

$$temp_k[i] =\sum_{j=1}^{d}\mathrm{sgn}(e_{k}[j]*H[j][i])$$ $$sig_{k}[i] = 1 \ if \ temp_k[i] < 0 \ else \ 0$$

相当于所有的 $d$ 维的 item embedding 都经过 $\mathbf{H} \in \mathbb{R}^{d \times m}$ 编码成了 $m$ 维的二进制向量了。

7.2.2 模型

如上模型图所示:

• 针对每个 target item（$e_t$），对其进行 SimHash 编码成二进制向量$h_t$；
• 对用户行为序列中的 candidate item（$e{k+1}$）也进行同样的 SimHash 编码成二进制向量$h{k+1}$；
• 基于上述，使用汉明距离来检索与 target item 最近的 topK 个candidate item，完成 GSU 部分；
• 将上述 topK 个 item 作为 ESU 的输入，构建 Multi-head Target Attention，其余雷同。

需要注意的是：

• Offline Training 时，ETA 中的 SimHash、GSU、ESU 这整个过程是一个 End-to-End 的，即每一 step，除了 Hash 映射不变外，其他参数都在 update；
• Online Serving 时，因为不管是 target 还是 candidate item，它们的 embeding 和 Hash Matrix 都是不变的，故可以提前计算它们的 SimHash Sig，线上直接 lookup 即可使用。

7.3 小记

• 文章提到 ETA 效果优于 SIM，且 SimHash 检索后 Attention 和直接全序列 Attention 在 AUC 只差 0.1%；
• 也提到 ETA 性能相比于 dot-product 更优（32ms-19ms），因为将检索依赖的 embedding 转换成了更低维的二进制向量，使得检索时速度增加；
• 加速 GSU、提高 GSU 和 ESU 环节的一致性，确实是沿着两阶段方向的一个重点迭代思路，当然这种改善具体提升多少还依赖实践情况。

8 SDIM

8.1 概述

论文：Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction
来源：2022，美团

思路：结合 SIM 和 ETA 的优势，提出使用 Hash Transform 和 Sample-Based Attention 来替换 GSU+ESU 的框架（如模型图右侧所示），直接构建 End-to-End 模型。

8.2 方案

8.2.1 挑战

• GSU 的存在，使得检索 topK 可能会存在信息堵塞的情况，比如相似 item 占位太多；
• 既然 SimHash 已经应用到了 GSU 部分，有没有可能打通 ESU 部分构建 End-to-End。

作者的解决方案的关键点是：既然 target item 和 candidate item 都可以通过 SimHash 来编码，并且还可以计算近似的相似度，如果基于此还能获取到 embedidng 就完成了全局 Attention 的替换。

SDIM 模型的全称是 Sampling-based Deep Interest Modeling。

如模型图左上所示，实际上是通过2步：

• 将 UBS 进行 Hashing 后编码成签名映射表；
• 将 target item 也进行 Hashing 编码成签名，去上述映射表直接检索聚合成最终的 Attention Embedding。

8.2.2 Multi-Round Hash

这里的思路与 ETA 极其相似，但为了打通 ESU 部分，做了一些改进。

针对 UBS 中任一 item 的 embedding 记为 $x$，先构建基础的 SimHash 编码，这一步与 ETA 一致：

$$h(\mathbf{x},\mathbf{R})=\mathrm{sign}(\mathbf{R}\mathbf{x})$$

其中，

• $\mathbf{R} \in \mathbb{R}^{m \times d}$是 Hash 矩阵，m 是 Hash 编码后的维度，d 是 item embedding size；
• $h(\mathbf{x},\mathbf{R}) \in \mathbb{R}^{m}$是 Hash 编码结果，m 维。

假设 UBS 长度为 T，我们就可以得到 T 个 m 维的 Hash Code。如下模型图左下，$T=4,\ m = 4$。

给定超参数 $\tau$，代表需要将 Hash Code 分组的宽度，如下图中 $\tau=2$，则每个 item 的 Hash Code 可以被分成 2 组，图中黄色和绿色部分。

然后我们将每个 item 同组的 Hash Code 聚合成一张 Hash SigSignature Table，其中：

• sig. 存储的是该组去重的 Hash Code；
• value 存储的是对应的 norm embedding，它是由相同 sig. 对应的 item embedding 进行归一化（norm）得到。

可以看到，这里的思想是基于 Hash Code ，将局部位置相似的 item embedding 聚合作为局部信息的表征，实际上是一种聚类的思想，容易联想到向量检索算法中的 PQ（乘积量化）。

8.2.3 Hash-Based Sampling

有了上述的基础，这里就比较明朗了：

• 首先针对 target item 也行同样的 Hash 编码并按照 $\tau$ 宽度进行分组
  （理论上组数应该与前述的 Hash SigSignature Table 个数一样。）
• 将每一组的 sig. 作为 key 去对应的 Hash SigSignature Table 中查询 value，作为结果 embedding；
• 将所有查到的 value 进行 pooling，得到最终 Target Attention 的结果 Embedding。

至此，完成了对 GSU+ESU 的替换，是一种 End-to-End 的对长序列进行 Target Attention 建模的结构。

8.3 小记

实际上，个人直观的思路是直接用 SimHash 后的汉明距离倒数作为 Attention Weight 来计算，但作者没有选择，可能存在的原因：

• 汉明距离作为召回可能尚可，作为 weight 可能噪声大，序的分辨度也许不高；
• 相似度计算简单了，但需要处理的长度依然太长。

回到 SDIM，作者提到：

• 效果上，对比 ETA 由 AUC+0.6%-1%；
• 性能上，较 ETA 快 3 倍。
• 如下图所示，SDIM 与传统的 Target Attention 的结果对比，相似度很高。
• 参数 m 越大效果越好，但过大性价比不高；
• 参数$\tau$的增大，AUC 先增后减。因为：太小，分组太多，泛化不够；太大，分组太少，组内区分度不够。

9 TWIN

9.1 概述

论文：TWIN: TWo-stage Interest Network for Lifelong User Behavior Modeling in CTR
来源：2023，快手

思想：ESU 是 Target Attention，GSU 的检索方式越对齐一致性越好。将 GSU 的 Target Attention 计算进行拆分，固有属性部分做缓存后 Lookup，交叉部分降维后作 Bias。

9.2 方案

9.2.1 挑战

ESU 和 GSU 往往存在一致性问题： GSU 和 ESU 在序列 Item 与 Target Item 的相似计算方式上不一样, 从而导致 GSU 检索的 topK 往往与 ESU 有差异。（如下图）

诸如 ETA、SDIM 都是通过使用其他近似算法来优化 GSU 过程，使得 GSU 可以处理更长序列，同时逼近 Target Attention。但，上述近似算法始终与 MHTA 算法有一定差异，TWIN 则是通过将 Attention 进行拆解，将 GSU 的 Target Attention 部分更进一步的逼近于 MHTA。

9.2.2 Behavior Feature Splits and Linear Projection

序列特征的分解与线性映射，是为了提升 Attention 模块性能。因 Multi-Head Target Attention（MHTA）的主要耗时在于两部分：序列信息做线性映射、内积加权和。

序列特征可以分为：

• 固有特征（如标题、作者、视频ID等）；
• 交互特征（如点击时间、观看时长等）。

其中，

• 固有特征独立于 user，包括其行为序列，可以提前计算存储下来，线上直接 lookup 即可。
• 交叉特征不能使用缓存方案，与 user 行为序列有关，但每个 user 最多只看每个 item 一次。

基于上述特性，我们将交叉特征线性映射为 1 维。

假设 UBS 为$[s_1,s_2,…,s_L]$ ，对应的特征矩阵为 $K$。则$K$可以拆分为两部分，如下：

$$K\triangleq[K_h,K_c]\in R^{L\times(H+C)}$$

其中 $K_h \in R^{L \times H}$ 是固有特征， $K_c \in R^{L \times C}$ 是则是交互特征部分。

如上所述， $K_h$ 可以提前离线计算并缓存供线上 Lookup 使用。
对于交互特征 $K_c$，假设有$J$个，每个 8 维，文章提到可将其均映射为 1 维，如下所示：

$$K_{c}W^{c}\triangleq[K_{c,1}W_{1}^{c},\ldots,K_{c,J}W_{J}^{c}$$

其中 $K_{c,j} \in R^{L \times 8}$ 为第 $j$ 个交互特征，$W_j^c \in R^8$ 则是对应的权重参数。

9.2.3 Target Attention in TWIN

上述的操作主要都是为了提速，当然在 Attention 部分也做了适配改造。

• Q、K 的固有属性部分直接 Lookup 缓存得到；
• 降维后的交叉特征部分则作为 Bias 项；
• Target Item 仅与固有特征做内积（快手曝光频控一次，故 Target Item 没有交叉特征）。

$$\alpha = \frac{(K_h W^h)(q^T W^q)^T}{\sqrt{d_k}}+(K_c W^c) \beta$$

则，这里的 $\alpha$ 实际上就是 Target Attention 的内积结果。

• GSU 阶段用这个对序列 Item 做粗筛 Top100；
• ESU 阶段对这 Top100 再做一次简化的 Target Attention。

如下所示：

$$Attention(q^{T} W^{q},K_{h} W^{h},K_{c} W^{c},K W^{v})=Softmax(\alpha)^{T}K W^{v}$$

注意：ESU 的$\alpha$实际上是重新计算的，不是 GSU 中的。

文章提到，实际业务中使用 MHTA，且 head 数为 4，所以最终如下：

$$TWIN=Concat(\mathrm{head}_1,...,\mathrm{head}_4)W^o$$ $$\mathrm{head}_a=\mathrm{Attention}(\mathbf{q}^\top W_a^q,K_hW_a^h,K_cW_a^c,KW_a^v),a\in\{1,...,4\}$$

其中，$W^o$是 head 之间的权重，也是模型学习得到。

9.3 小记

TWIN 的有效性主要得益于 3 点：

1. 作者将序列特征 拆分成了 固有属性 和 交互特征，分别使用缓存（命中率99.3%）和降维分而治之；
2. 基于上述，对 Target Attention 做了简化；
3. 业务上，Target Item 与 UBS 没有交互提供了上述可拆分的支持。

TWIN 进一步提高了 GSU 和 ESU 部分的一致性（如下图所示），GSU 也用上了 Target Attention，且能够支持 $10^5$的序列。

但这里有一个问题：如果 GSU 能够做到 Target Attention 为什么不统一成全局 ESU，还要保留 GSU 来粗筛 top100 来给 ESU？

实际上，这有 2 个原因：

1. Q、K 做了简化，V 的 Project、 Weight Pooling 以及 bp 都是很耗时的过程，且 100 后的$\alpha$往往都很小信息量不大，所以截取 top100 还是很具有性价比的；
2. 虽然 GSU 和 ESU 的 Attention 结构一样，但分数上依然存在些许差异。因为 GSU 是离线计算，其参数更新速度没有 ESU 部分快。故 ESU 部分重新计算$\alpha$，性能可支持、实时性更高、准确度更好。

10 TWIN-V2

10.1 概述

论文：TWIN V2: Scaling Ultra-Long User Behavior Sequence Modeling for Enhanced CTR Prediction at Kuaishou
来源：2024，快手

思想：为了使得 TWIN 可以支持到10^6量级，TWIN-V2 基于层次聚类，对 UBS 中的 Item 做聚类后得到簇序列，从而将序列量级从 Item 元素的$10^6$量级降到簇元素下的$10^5$量级，之后再应用 TWIN 即可。

10.2 方案

10.2.1 Hierarchical Clustering

Item 数量太多，则将 Item 聚类成簇，变成簇序列，量级下来后，以簇为 新 Item支持完成 TWIN 模型。

Item 分层：对 UBS 的各个 Item $v_j$，根据完播率$p_j=playing \ timevideo \ duration$分成 M 组(文章中M=5)，可以使用等宽分组。这里实际上是对用户偏好进行了显式分层。

Item 聚类成簇：这里文章给了算法的伪代码，这里简述要点。

• 逐个处理 M 组序列，分别对其进行聚类；
• 每个簇内部最多包含 $\gamma$个 Item，如某组序列的 Item 总数少于此，整体作为一簇；
• 数量够的，计算需要的聚类数 $\delta \leftarrow \lfloor |V|^{0.3} \rfloor$；
• 根据 Item 的 Embedding，将该组内的 Item 进行 Kmeans 聚类，聚类数为上述 $\delta$。

最终将原始 UBS 的 Item 序列即 $S=[s1,s_2,\cdots,s_T]$转化成了簇序列，即$C=[c{1},c{2},\cdots,c{\hat{T}}]$。

此外，文章提到：

• 层次聚类 2 周完整更新一次，毕竟是全生命周期的，计算量大；
• Embedding Server 来源 GSU 的固有属性, 每隔15分钟进行同步；
• 实践中簇的内部大小$\gamma=20$，而最终的簇个数平均为 10，相当于将序列量级下降1级。

10.2.2 Extracting Cluster Representation

在得到各个簇之后，需要构建簇的表征，否则下游的模型无法使用。逻辑上也是将簇内 Item 两种类型的特征单独分开处理。

连续型特征，取簇内各 Item 的均值:

$$\mathbf{c}_{1:N_2}^{(i)}=\frac{1}{|c_i|}\sum_{v\in c_i}\mathbf{x}_{1:N_2}^{(v)}$$

但分类型特征，均值就没意义了。文中提到从簇中选取一个代表性的 Item 来表示，筛选方案是：与聚类中心的距离最小的。

$$v=\arg\min_{v\in c_{i}}\|\mathrm{k}_{v}-\mathrm{k}_{\mathrm{centroid}}\|_{2}^{2}$$

最后将分类型和连续型特征 concat 即可作为簇的 Embedding 了。

10.2.3 Cluster-aware Target Attention

原始序列从$S$已经下降一个量级到$C$了，并且对应的 Embedding 也具备，可以直接应用 TWIN 模型了。

$$\alpha=\frac{(\mathrm{K}_h\mathrm{W}^h)(\mathrm{q}^\top\mathrm{W}^q)^\top}{\sqrt{d}_k}+(\mathrm{K}_c\mathrm{W}^c)\beta$$

注意力分数依然按照上述计算，但文章提到，这时候的元素已经不再是 Item 了，如果不同的类簇有相同的 Score，那么簇内 Item 数更多的理论上更置信。

故，对注意力分做了矫正：

$$\alpha^{\prime}=\alpha+\ln\mathbf{n}$$

其中$\mathbf{n}$是簇内 Item 的数量。在 GSU 和 ESU 环节均使用$\alpha^{\prime}$来计算注意力分，其余环节与 TWIN 保持一致。

10.3 小记

为了支撑更大的量级，在 TWIN-V2 中，选择将问题转化为 TWIN 能处理的量级，方法就是对原始的 Item 进行分层聚类，从而将原始的 Item 序列转化为低一个量级的聚类簇序列。

文章在实验部分提到效果较为显著，但聚类本身容易带来信息丢失，尤其是下面2个环节：

• $M,\gamma,\delta$的超参数选择；
• 簇的类型特征的表征。

故，该方法的实际效用如何，还需要以具体场景的实践结果为准。

其他

除了上述提到的一系列文章外，业内当然还有不少其他方面的研究成果。笔者没有再进一步整理，一方面考虑到篇幅过大，另一方面也是个人判断方案的普适性。

上述展开的一系列成果比较契合序列建模迭代的 2 大方向且成果往往也在多个场景实践落地，更具参考价值。

当然，这里也附上部分近年的相关文章供参考：
DGIN（2024，美团）
ASIF（2024，蚂蚁）
SUM（2024，META）
LURM（2023，阿里）
LCN（2024，腾讯）
Trinity（2024，字节）

参考文章：

抖音/阿里/美团/微信/快手长序列兴趣建模经典方案探索
一文梳理近年推荐长序列兴趣建模经典方案
阿里妈妈点击率预估中的长期兴趣建模
推荐系统——精排篇【3】
推荐系统中的注意力机制——阿里深度兴趣网络（DIN）
详解阿里之Deep Interest Evolution Network(AAAI 2019)
简析阿里 BST: 当用户行为序列邂逅Transformer
DSIN（Deep Session Interest Network ）分享
阿里妈妈长期用户历史行为建模——MIMN模型详解
[SIM论文] 超长兴趣建模视角CTR预估：Search-based Interest Model
阿里ETA(End-to-End Target Attention)模型
【论文解读|CIKM’2022】基于采样的超长序列建模算法 SDIM
快手终身序列建模方案—TWIN
精排最终也是样本的艺术

---