一、ETA [2021]

《End-to-End User Behavior Retrieval in Click-Through Rate Prediction Model》

1. CTR prediction 是推荐系统的核心任务之一。它预测每个 user-item pair 的个性化的点击概率。最近，研究人员发现，通过考虑用户行为序列，尤其是长期用户行为序列，可以大大提高 CTR 模型的性能。某电商网站的报告显示，23% 的用户在过去 5 个月内点击次数超过 1000 次。尽管有大量工作专注于建模用户行为序列，但是由于现实世界系统中严格的 inference time 的限制，很少有工作能够处理长期用户行为序列。人们提出了两阶段方法来突破极限以获得更好的性能：

   • 在第一阶段，设计一个辅助任务来从长期用户行为序列中检索 top-k 相似的 items 。

   • 在第二阶段，在 target item 和第一阶段选择的 k 个items 之间进行经典的注意力机制。

   然而，检索阶段和主体的 CTR 任务之间存在 information gap 。这种目标分歧会大大降低长期用户序列的性能增益。在本文中，受 Reformer 的启发，我们提出了一种局部敏感哈希（locality-sensitive hashing: LSH ）方法，称为 End-to-end Target Attention: ETA ，它可以大大降低训练和推理成本，并使得采用长期用户行为序列进行端到端的训练成为可能。离线和在线实验都证实了我们模型的有效性。我们将 ETA 部署到一个大型的真实世界电商系统中，与两阶段的长用户序列的 CTR 模型相比，商品交易总额（Gross Merchandise Value: GMV ）额外提高了 3.1% 。

2. 推荐系统被广泛用于解决信息过载问题。在推荐系统中使用的所有深度学习模型中，CTR prediction 模型是最重要的模型之一。为了提高推荐系统的在线性能，工业界和学术界都非常重视提高CTR 模型的 AUC。在过去的十年中，CTR 模型的性能得到了很大的提高。其中一个显著的里程碑是引入用户行为序列，特别是长期用户行为序列。根据 《Lifelong Sequential Modeling with Personalized Memorization for User Response Prediction》 的报告，电商网站中 23% 的用户在过去 5 个月内点击次数超过 1000 次。如何有效利用大量的且信息丰富的user behavior变得越来越重要，这也是本文的目标。

   人们提出了各种方法来建模用户行为序列。

   • 早期的方法，如 sum/mean pooling方法、RNN-based 的方法、CNN-based 的方法、以及 self-attention-based ，将不同长度的用户行为序列编码为固定维度的 hidden vector 。然而，它们在对不同的 target items 进行打分时无法捕获用户的动态局部兴趣（dynamic local interests ）。这些方法还通过编码所有的用户历史行为从而引入了噪音。

   • 为了克服全局池化方法的缺点，人们提出 DIN 方法。DIN 通过 target attention 机制根据不同的 target items 生成 various user sequence representations ，其中 target item 充当 query $\mathbf{Q}$$\mathbf Q$，序列中的每个 item 充当 key $\mathbf{K}$$\mathbf K$ 和 value $\mathbf{V}$$\mathbf V$ 。然而，由于昂贵的计算和存储资源，DIN 使用最近的 50 个behavior用于 target attention ，这忽略了长用户行为序列中的丰富信息，显然是次优的。

   • 最近，人们提出 SIM 和 UBR4CTR 等 SOTA 方法。这些方法从较长的用户行为序列中捕获用户的动态兴趣。这些方法分两阶段进行：

     • 在第一阶段，设计一个辅助任务从长期用户行为序列中检索 top-k 相似的 items ，以便提前准备好 top-k 相似的 items 。

     • 在第二阶段，target item 和第一阶段选定的 k 个 items 之间进行 target attention 。

     然而，用于检索阶段的信息与 main CTR model 不一致或已过时。例如：

     • UBR4CTR 和 SIM 使用 category 等属性从用户行为序列中选择与 target item 共享相同属性的 items ，这与 CTR 模型的目标不一致。

     • SIM 还尝试基于 pre-trained embedding 来构建离线倒排索引（offline inverted index ）。在训练和推理过程中，模型可以搜索 top-k “相似” 的 items 。但大多数 CTR 模型都采用 online learning 范式，并且 embedding 会不断被更新。因此，与在线 CTR 模型中的embedding 相比，离线倒排索引中的 pre-trained embedding 已经过时。

     无论是不一致的目标还是过时的 retrieval vector ，都会阻止长期用户行为序列得到充分利用。

   在本文中，我们提出了一种称为 ETA 的方法，可以实现端到端的长期用户行为的检索，以缓解 CTR prediction 任务中上述 information gap （即不一致的目标和过时的 embedding ）。我们使用 SimHash 为用户行为序列中的每个 item 生成指纹。然后使用汉明距离来帮助选择 top-k 的item 从而用于 target attention 。我们的方法将 retrieval 复杂度从 $O(LBd)$$O(LBd)$ 的乘法操作降低到 $O(LB)$$O(LB)$ 的汉明距离计算，其中 $L$$L$ 是用户行为序列的长度，$B$$B$ 是每次推荐时 CTR 模型要评分的 target items 数量，$d$$d$ 是 item embedding 的维度。复杂度的降低有助于我们在训练和服务过程中移除离线辅助模型并进行实时检索。与 SOTA 模型相比，这大大提高了 ranking improvements 。我们论文的贡献可以概括为三点：

   • 我们针对 CTR prediction 任务提出了一种端到端的 Target Attention 方法，称为 End-to-end Target Attention: ETA 。据我们所知，ETA 是第一个以端到端方式使用 CTR 模型对长期用户行为序列进行建模的工作。

   • 离线实验和在线 A/B tests 都表明，与 SOTA 模型相比，ETA 实现了显著的性能提升。与两阶段 CTR 模型相比，将 ETA 部署到大型现实世界电商平台后，GMV 额外提高了3.1% 。

   • 进行了全面的消融研究，以揭示在 inference time 限制的约束下更好地建模用户行为序列的实际经验。

   • 我们的方法还可以扩展到其他场景，扩展到需要处理极长序列的其他模型，例如长序列的时间序列预测模型。

   其核心思想就是：用近似的 similarity （embedding 经过 LSH 之后的汉明距离）来代替精确的 similarity （embedding 向量的内积）。

1.1 基础知识

1. 在本节中，我们首先给出 CTR prediction 任务的公式。然后我们介绍如何通过 SimHash 机制生成 $d$$d$ 维 embedding 向量的指纹。

1.1.1 Formulation

1. CTR prediction 任务广泛应用于在线广告、推荐系统和信息检索。它旨在解决以下问题：给定一个 impression $j\in \mathcal{I}$$j\in \mathcal I$ ，其中一个 item 被展示给一个用户，使用特征向量 ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ 来预测 user click （标记为 $y_j$$y_j$）的概率。

   $$p_j=P(y_j=1\mid {\overrightarrow{\mathbf{x}}}_j;\theta ),j\in \mathcal{I}$$

2. CTR 任务通常被建模为二分类问题。对于每个 impression $j\in \mathcal{I}$$j\in \mathcal I$ ，根据该 item 是否被点击从而标记一个二元标签 $y_j$$y_j$。然后以监督学习的方式训练 CTR 模型以最小化交叉熵损失：

   $${\mathcal{L}}_{\text{CTR}}(\theta )=-\frac{1}{N}\sum _{j=1}^N[y_j\log (p_j)+(1-y_j)\log (1-p_j)]$$

   其中：$N$$N$ 为 impression 的总数；${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ 为特征向量，$y_j$$y_j$ 为 label ；$\theta$$\theta$ 为模型的可训练参数。

1.1.2 SimHash

1. SimHash 算法最早由 《Similarity estimation techniques from rounding algorithms》 提出，其中一个著名应用是 《Detecting near-duplicates for web crawling》，它通过 SimHash based 的指纹检测重复的网页。SimHash 函数将 item 的 embedding vector 作为输入，并生成其二进制指纹。Algorithm 1 显示了 SimHash 的一种可能的实现的伪代码。

   不用那么啰嗦，可以直接用矩阵乘法来实现：

   $${\text{sig}}_k=\text{sign}\left({\overrightarrow{\mathbf{e}}}_k\mathbf{H}\right)$$

   

2. SimHash 满足局部敏感特性（locality-sensitive properties ）：如果输入向量彼此相似，则 SimHash 的输出也相似，如 Figure 1 所示。

   Figure 1 中的每个 random rotation 都可以看作一个“哈希函数”。旋转是通过将 input embedding vector 与随机投影列向量 $\mathbf{H}(i)$$\mathbf H(i)$ 相乘来实现的，如 Algorithm 1 的第2 行所示。随机旋转后，球面上的点被投影到 signed axes 上（ Algorithm 1 中的第 3-7 行）。在Figure 1 中，我们使用 4 个哈希函数和两个 projection axes ，将每个向量映射到一个具有 4 个元素的 signature vector 。signature vector 中的每个元素要么是1 ，要么是 0 。可以进一步使用一个整数对该向量进行解码，以节省存储成本并加快后续的汉明距离计算。

   例如，1001 可以解码为整数 9 = 1*8 + 0*4 + 0*2 + 1 。

   从 Figure 1 中我们可以观察到，附近的 embedding 向量可以以很高的概率获得相同的哈希签名（hashing signature ），参见 Figure 1 下半部与 Figure 1 上半部的比较。这种观察结果就是所谓的“局部敏感”特性。利用局部敏感特性，embedding 向量之间的相似性可以由哈希签名之间的相似性取代。换句话说，两个向量之间的内积可以用汉明距离代替。

   值得注意的是，SimHash 算法对每个旋转的 “哈希函数” 的选择不敏感。任何固定的 random hash vectors 就足够了（参见 Algorithm 1 中的 $\mathbf{H}(i)$$\mathbf H(i)$）。它易于实现，可以轻松应用于批量的 embedding vectors 。

   “ 4 个哈希函数和两个 projection axes ”？图中看起来只有一个轴啊，水平轴下方为 1 、上方为 0 。

   

1.2 模型

1. 在本节中，我们首先介绍我们的 End-to-End Target Attention: ETA 模型的详细架构。然后介绍 ETA 模型的不同子模块。最后，我们介绍部署 ETA 的实际经验。

1.2.1 模型概况

1. 如 Figure 2 所示，我们的模型以 user/item-side features 作为输入，输出某个 user-item pair 的点击概率。

   • 长期用户行为序列 ${\mathcal{H}}_{\text{lu}}$$\mathcal H_\text{lu}$ 、短期用户行为序列 ${\mathcal{H}}_{\text{su}}$$\mathcal H_\text{su}$ 、user profile $x_u$$x_u$ 、target item $x_t$$x_t$ 和上下文信息 $x_c$$x_c$ 是原始输入特征。$\theta$$\theta$ 表示可训练参数。

     注意：长期用户行为序列 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 不包含短期用户行为序列 ${\mathcal{H}}_{\text{su}}$$\mathcal H_\text{su}$ ，它们是正交的。

     在 SIM 模型中，长期用户行为序列是否包含短期用户行为序列？这个不清楚，SIM 的原始论文未说明。

     在 MIMN 和 UBR4CTR 模型中，只有长期用户行为序列，没有短期用户行为序列。

   • 有了这些特征，我们使用长期兴趣提取单元（Long-term Interest Extraction Unit）、多头目标注意力（Multi-head Target Attention）和 Embedding Layer 分别将 ${\mathcal{H}}_{\text{lu}}$$\mathcal H_\text{lu}$、${\mathcal{H}}_{\text{su}}$$\mathcal H_\text{su}$ 、$x_u$$x_u$ 、$x_t$$x_t$ 和 $x_c$$x_c$ 转换为 hidden vectors 。然后将 hidden vectors 拼接在一起并馈入到 Multi-layer Perception: MLP 部分。

   • 在 MLP 的最后一层，使用 sigmoid 函数将 hiddenvector 映射为标量 $p(y_j\mid {\mathcal{H}}_{lu},{\mathcal{H}}_{su},x_u,x_t,x_c;\theta )$$p(y_j\mid \mathcal H_{lu}, \mathcal H_{su}, x_u,x_t,x_c;\theta)$，表示某个 user-item pair 的点击概率。此概率可作为下游任务的 ranking score 。

   

2. 本文中这些符号的含义：

   

1.2.2 Embedding Layer

1. 对于不同类型的特征，我们采用不同的 embedding 技术。原始输入特征主要分为两类：categorical 特征和 numerical 特征。

   • 在我们的模型中，我们对 categorical 特征使用 one-hot encoding 。

   • 对于 numerical 特征，我们首先将特征划分到不同的 numerical buckets 中。然后我们应用 one-hot encoding 来识别不同的桶，这与 《Interpretable Click-Through Rate Prediction through Hierarchical Attention》 的方式类似。

   请注意，由于有数十亿个 item ids ，one-hot encoding vectors 可能非常稀疏。因此，我们将所有 one-hot embedding vectors 映射到低维 hidden vectors 以减少参数数量。我们使用 ${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^{d\times 1}$$\mathbf{\vec e}_i\in \mathbb R^{d\times 1}$ 来表示 item $i$$i$ 的 embedding vector 。然后将所有user behavior items 的 embedding vectors 打包成矩阵 ${\mathbf{E}}_s\in {\mathbb{R}}^{L\times d}$$\mathbf E_s\in \mathbb R^{L\times d}$ ，其中 $L$$L$ 是用户行为序列的长度，$d$$d$ 是 embedding size ：

   $$\begin{array}{c}{\mathbf{E}}_s=\left[\begin{array}{c}{\overrightarrow{\mathbf{e}}}_1^{\mathrm{\top }}\\ {\overrightarrow{\mathbf{e}}}_2^{\mathrm{\top }}\\ ⋮\\ {\overrightarrow{\mathbf{e}}}_L^{\mathrm{\top }}\end{array}\right]\end{array}$$

1.2.3 Multi-head Target Attention

1. 多头注意力机制由 《Attention Is All You Need》 首次提出，并广泛应用于 CTR prediction 任务。在 CTR prediction 任务中，target item作为 query $\mathbf{Q}$$\mathbf Q$，用户行为序列中每一个 item 作为 key $\mathbf{K}$$\mathbf K$ 和 value $\mathbf{V}$$\mathbf V$。我们将这种多头注意力结构称为多头目标注意力机制（multi-head target attention ），缩写为 TA 。

   multi-head target attention 的计算如下：

   $$\begin{array}{c}\text{TA}({\mathbf{E}}_t,{\mathbf{E}}_s)=\text{Concat}({\text{head}}_1,\cdots ,{\text{head}}_h){\mathbf{W}}^O\\ {\text{head}}_i=\text{Attention}({\mathbf{E}}_t{\mathbf{W}}_i^Q,{\mathbf{E}}_s{\mathbf{W}}_i^K,{\mathbf{E}}_s{\mathbf{W}}_i^V),\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}}{\sqrt{d_k}}\right)\mathbf{V}\end{array}$$

   其中：

   • ${\mathbf{E}}_t\in {\mathbb{R}}^{1\times d}$$\mathbf E_t\in \mathbb R^{1\times d}$ 为 target item 的 embedding 矩阵；${\mathbf{E}}_s\in {\mathbb{R}}^{L\times d}$$\mathbf E_s\in \mathbb R^{L\times d}$ 为用户行为序列的 embedding 矩阵。$L$$L$ 为用户行为序列的长度，$d$$d$ 为每个 item 的 embedding size 。注意，为了清晰起见，我们只选择了一个样本（即，一个 target item ），而不是一个 batch 的样本。

   • ${\mathbf{W}}^O\in {\mathbb{R}}^{h{d}_v\times d}$$\mathbf W^O\in \mathbb R^{hd_v\times d}$ 为投影矩阵，$h$$h$ 为 head 数量。

   • 矩阵 $\mathbf{Q},\mathbf{K},\mathbf{V}$$\mathbf Q, \mathbf K, \mathbf V$分别表示 query 、key、value 。

   • ${\mathbf{W}}_i^Q\in {\mathbb{R}}^{d\times d_k},{\mathbf{W}}_i^K\in {\mathbb{R}}^{d\times d_k},{\mathbf{W}}_i^V\in {\mathbb{R}}^{d\times d_v}$$\mathbf W^Q_i\in \mathbb R^{d\times d_k}, \mathbf W^K_i\in \mathbb R^{d\times d_k}, \mathbf W^V_i\in \mathbb R^{d\times d_v}$ 为投影矩阵，它们分别将 ${\mathbf{E}}_t,{\mathbf{E}}_s,{\mathbf{E}}_s$$\mathbf E_t, \mathbf E_s, \mathbf E_s$ 投影到 query, key, value 。$d_k$$d_k$ 为 query 中每一行的维度，也是 key 中每一行的维度；$d_v$$d_v$ 为 value 中每一行的维度。

   • $\sqrt{d_k}$$\sqrt{d_k}$ 用于避免内积值过大。softmax 函数用于将内积值转化为 $\mathbf{V}$$\mathbf V$ 的加权权重。

2. multi-head target attention 的主要部分是 dot-product attention 。dot-product attention 由两步组：

   • 首先，根据 $\mathbf{Q}$$\mathbf Q$ 和 $\mathbf{K}$$\mathbf K$ 计算 target item 和每个behavior item 的相似度。

   • 其次，以归一化的相似度作为注意力权重，并计算所有 behavior items 的 weighted sum embedding 。

1.2.4 Long-term Interest Extraction Unit

1. 这部分是我们 ETA 模型的主要贡献。它将用户行为序列的长度从数十扩展到数千甚至更长，从而捕获长期用户兴趣。如前所述，multi-head target attention的复杂度为 $O(LBd)$$O(LBd)$，其中 $L$$L$ 是用户序列的长度，$B$$B$ 是 target items 的数量（也就是 batch size ），$d$$d$ 是 representation 维度。在大型在线系统中， $B$$B$ 接近 1000 ，$d$$d$ 接近 128 。因此，直接对数千个长期的user behavior进行 multi-head target attention 是不可行的。 根据 $\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})$$\text{Attention}(\mathbf Q, \mathbf K, \mathbf V)$ 的公式，softmax 由最大元素主导；因此，对于每个 query ，我们只需要关注与 query 最相似的 key ，这也得到了 《Reformer:Theefficient transformer》 、《Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction》 、《User Behavior Retrieval for Click-Through Rate Prediction》 的证实。因此我们可以首先从行为序列中检索 top-k items ，并对这些 k 个behavior进行 multi-head target attention 。

   然而，一个好的检索算法应该满足两个约束：

   • 1)：检索部分的目标应该与整个 CTR 模型保持一致。只有这样，检索到的 top-k items 才能对 CTR 模型做出最大贡献。

   • 2) ：检索时间应满足严格的 inference time 限制，以确保该算法可以应用于实际系统，从而每秒处理数百万个 request 。

   我们在 Table 2 中比较了不同的检索算法。

   • SIM 和 UBR4CTR 构建离线倒排索引（offline inverted index ），以便在训练和推理期间进行快速搜索。然而，它们用于构建索引的输入是 item 的属性信息（例如 category ）或 item 的 pre-trained embedding ，这与 CTR 模型中使用的 embedding 不同。这种差距违反了上述约束 1） ，并可能导致性能下降。

   • 如果直接使用 CTR 模型中的 embedding 并通过内积搜索 k-nearest neighbor，则需要 $O(LBd)$$O(LBd)$ 次乘法，推理时间会大大增加。这将违反上述约束 2) ，并且无法在线部署。

   • 我们的 ETA 使用 SimHash 将两个向量的内积转换为汉明距离计算，如 Figure 2 所示。这使得它可以部署在现实世界的推荐系统中。此外，SimHash 的局部敏感特性可以确保 fingerprint 始终可以与 CTR 模型中的 original embedding 保持同步。实验章节的评估部分表明这种兼容性可以大大提高性能。

     如何选择正确的哈希函数、以及检索部分和 ETA 其余部分之间的联合学习将在后续章节中说明。

   

2. 经过 SimHash 函数和 hamming distance layer 后，我们从 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 中选择出 top-k 相似的 behavior items ，然后执行前面提到的 multi-head target attention 以生成 hidden vector 。该向量作为长期用户兴趣的 representation ，并与其他向量一起输入到 MLP layers 中。long-term user interest extraction unit 的公式如下：

   $$\begin{array}{c}\text{LTI}({\mathbf{E}}_t,{\mathbf{E}}_s)=\text{TA}({\mathbf{E}}_t,{\mathbf{E}}_s^{\prime })\\ {\mathbf{E}}_s^{\prime }=\left[\begin{array}{c}{\overrightarrow{\mathbf{e}}}_1^{\mathrm{\top }}\\ {\overrightarrow{\mathbf{e}}}_2^{\mathrm{\top }}\\ ⋮\\ {\overrightarrow{\mathbf{e}}}_k^{\mathrm{\top }}\end{array}\right],{\overrightarrow{\mathbf{e}}}_i\in \text{topk}\left(\text{HammingDistance}({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_t)\right)\\ {\overrightarrow{\mathbf{h}}}_i=\text{SimHash}\left({\overrightarrow{\mathbf{e}}}_i\right),{\overrightarrow{\mathbf{h}}}_t=\text{SimHash}\left({\overrightarrow{\mathbf{e}}}_t\right)\end{array}$$

   其中：

   • LTI 和 TA 分别是 long-term user interest extraction unit 和 multi-head target attention 的缩写。

   • ${\mathbf{E}}_s\in {\mathbb{R}}^{|{\mathcal{H}}_{lu}|\times d}$$\mathbf E_s\in \mathbb R^{|\mathcal H_{lu}|\times d}$ 是长期用户行为序列 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 的 embedding 矩阵。${\mathbf{E}}_s^{\prime }$$\mathbf E_s^\prime$ 由从 ${\mathbf{E}}_s$$\mathbf E_s$中选择 $k$$k$ 行而来，这些行与 target item ${\mathbf{E}}_t\in {\mathbb{R}}^{1\times d}$$\mathbf E_t\in \mathbb R^{1\times d}$ 具有最大的汉明距离。

3. 相似度函数：如 Figure 2 所示，我们使用 SimHash 函数和汉明距离来计算两个 embedding 向量的相似度，而不是内积。SimHash 函数将上述 embedding layer 的输出作为输入。对于每个输入的 embedding向量，SimHash 函数生成其 compressed number 作为指纹（fingerprint ）。 SimHash 满足局部敏感特性：如果 input features 彼此相似，则 hashing output 也相似。因此，embedding 向量之间的相似性可以用 hashed fingerprints 之间的相似性来代替。$d$$d$ 维 embedding 向量可以编码为 m-bit number。然后可以通过汉明距离来测量两个指纹之间的相似性。

4. Top-K Retrieval ：与基于内积的模型相比，top-k retrieval layer 可以通过汉明距离更有效地找到与 target item 的 top-k 相似的 user behavior items 。两个整数的汉明距离定义为对应 bits 不同的不同 bits positions 的数量。

   为了得到两个 m-bit numbers 的汉明距离，我们首先进行 XOR 运算，然后计算取值为 1 中的bits 数量。如果我们将乘法定义为原子操作，则两个 m-digit numbers 的汉明距离的复杂度为 $O(1)$$O(1)$。基于汉明距离的 top-k retrieval 的总复杂度为 $O(L\times B\times 1)$$O(L\times B\times 1)$，其中 $L$$L$ 是序列长度，$B$$B$ 是 target items 的数量。

   值得注意的是，每次执行 SimHash 函数时，hashed fingerprints 都可以与模型一起存储在 embedding table 中。在推理期间，只需要 embedding lookup ，其复杂性可以忽略不计。

1.3 部署

1. 在本节中，我们展示了如何训练具有检索部分的 ETA 。然后我们介绍如何选择 SimHash 算法中使用的“哈希函数”。然后我们介绍工程优化技巧。

2. Joint learning of retrieval part ：在训练阶段，检索部分不需要更新梯度。检索的目标是为接下来的 multi-head target attention 部分选择 query 的最近邻的 keys 。在选择了 query 的 top-k 最近邻的 keys 之后，对这些 top-k items 的 original embedding vectors 进行正常的注意力机制和反向传播。检索的唯一事情是在训练开始时初始化一个固定的随机矩阵 $\mathbf{H}\in {\mathbb{R}}^{d\times m}$$\mathbf H\in \mathbb R^{d\times m}$（参见 Algorithm 1 ）。只要 input embedding vector ${\overrightarrow{\mathbf{e}}}_k\in {\mathbb{R}}^{1\times d}$$\mathbf{\vec e}_k\in \mathbb R^{1\times d}$ 被更新，SimHash 的签名就会相应更新。局部敏感特性确保在每次迭代中，使用 CTR 模型的 latest embedding 无缝地选择 query 的 top-k nearest keys 。因此，检索和 CTR 模型之间的 gap of goal 比其他检索方法（例如 Table 2 中所示的基于离线倒排索引的方法）小得多。

   从 CTR 模型的角度来看，检索部分是透明的，但可以确保模型使用最邻近的 items 进行 multi head attention。实验章节表明，这种无需任何 pre-training 或 offline inverted index building 的端到端训练可以大大提高 CTR prediction 任务的性能。

3. “哈希函数”的选择：SimHash 是一种著名的局部敏感哈希 （locality-sensitive hashing: LSH）算法。SimHash 的实现如 Algorithm 1 所示，其中我们使用固定的 random hash vector 作为“哈希函数”。任何将字符串映射为随机整数的传统散列函数都可以使用。但是，在我们的算法中，出于对矩阵计算的可扩展性和效率的考虑，我们选择了 random hash vector 和 Algorithm 1 的实现，这与Reformer 相同。

   局部敏感哈希是通过随机旋转和投影实现的。随机旋转是指 embedding vector 与一个固定的 random hashing vector $\mathbf{H}(j)$$\mathbf H(j)$ 相乘。这里可以使用任何随机的 $d$$d$ 维向量。值得注意的是，由于我们需要将内积的结果投影到两个 singed axes 上从而获得 binary signature ，$\mathbf{H}(j)$$\mathbf H(j)$ 中的元素应该在 0 附近随机生成。

4. 工程优化技巧：当在线部署模型时，SimHash 的计算可以进一步减少一步。针对 embedding 向量 ${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$，对于 Algorithm 1 计算出的长度为 $m$$m$ 的 signature vector ${\mathbf{sig}}_k$$\mathbf{sig}_k$ ，我们可以使用一个 $\log (m)$$\log(m)$ 位的整数来表达 signature vector ，因为 ${\mathbf{sig}}_k$$\mathbf{sig}_k$ 中的每个元素要么为 1 要么为 0 。因此，这样可以大大减少内存开销，加快汉明距离的计算速度。两个整数的计算时间可以在 $O(1)$$O(1)$ 时间复杂度下进行，可以忽略不计。

1.4 实验

1. 在本节中，我们进行实验来回答以下研究问题：

   • RQ1 ：我们的 ETA 模型是否优于 baseline 模型？

   • RQ2：与 baseline 模型相比，我们的 ETA 模型的推理时间是多少？推理时间和性能一样重要，因为它决定了模型是否可以在线部署以供服务。

   • RQ3：我们的 ETA 模型的哪一部分对性能和推理时间贡献最大？

2. 数据集：为了对我们的 ETA 模型和 baseline 模型进行全面比较，我们使用了公共数据集和工业数据集。还进行了在线 A/B test 。对于公共数据集，我们选择了 Taobao 数据集，baseline 模型 SIM 和 UBR4CTR 也采用了该数据集。我们也准备了一个工业数据集作为公共数据集的补充。Table 3 简要介绍了数据集。

   • Taobao 数据集：该数据集由 《Joint optimization of tree-based index and deep model for recommender systems》 首次发布，被广泛用作 CTR prediction 任务和序列推荐任务的公共基准。它由 Taobao Mobile App 的user behavior日志组成。user behavior包括点击、收藏、添加到购物车、以及购买。该数据集包含 100M 个实例。平均而言，每个用户大约有 101 次交互，每个item 受到超过 24 次交互。最近的 16 个behavior作为短期用户行为序列，最近的 256 个behavior作为长期用户行为序列。

   • 工业数据集：该数据集是从我们自己的在线推荐系统收集的，它是我国顶级的移动 app 之一。我们的工业数据集有三个优势：

     • (i) ：我们的数据集包含 impression interaction ，这表示 item 展示给用户但未被用户点击。 impression interaction 自然是 CTR 模型的负样本。因此，不需要棘手的负采样。

     • (ii) ：我们的工业数据集中的用户行为序列更长。有超过 142B 个实例，平均长度达到 938 ，比公开的 Taobao 数据集长 9 倍。

     • (iii) ：我们的工业数据集具有由多位软件工程师设计的更多特征，更接近现实世界的推荐系统模型。最近的48 个behavior作为短期用户行为序列，最近的 1024 个behavior作为长期用户行为序列。在消融研究中，我们还尝试了长度为 {256, 512, 2048} 的长期用户行为序列。

   

3. baseline ：我们将我们的模型与以下主流的 CTR prediction baselines 。选择每个 baseline 来回答上述一个或多个相关的研究问题。

   • Avg-Pooling DNN ：利用用户行为序列的最简单方法是均值池化，它将不同长度的用户行为序列编码为 fixed-size hidden vector 。该 baseline 可以看作是DIN 的变体，用均值池化代替 target attention ，类似于 YouTube 。与 DIN 相比，该 baseline 主要用于显示 target attention 的必要性。

   • DIN：DIN 通过注意力机制来建模具有不同 target items 的个性化用户兴趣，该注意力机制称为 target attention 。但是，DIN 仅利用短期用户行为序列。

   • DIN (Long Sequence) ：是配备长期用户行为序列 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 的 DIN 。 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 由均值池化来编码。与 DIN 相比，此 baseline 用于衡量长期用户行为序列本身的信息增益。

   • SIM(hard) ：SIM 是 CTR prediction 模型，它提出了一个 search unit ，以两阶段的方式从长期用户行为序列中提取用户兴趣。SIM(hard) 是 SIM 的一种实现，它在第一阶段按 category id 搜索 top-k behavior items 。

   • UBR4CTR ：UBR4CTR 也是一种两阶段方法，它在 CTR prediction 任务中利用长期用户行为序列。在 UBR4CTR 中，通过一个 feature selection model 准备好 query，从而检索最相似的 behavior items 。它还准备了一个倒排索引以供在线使用。由于 UBR4CTR 和 SIM 几乎同时发布，因此它们无法相互比较。在我们的论文中，我们首次比较了 UBR4CTR 和 SIM。

   • SIM(hard)/UBR4CTR + timeinfo ：是在对用户行为序列进行编码时带有 time embedding 的 SIM(hard)/UBR4CTR 。

   在 《Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction》 中，作者提出 SIM(soft) 作为基础算法 SIM(hard) 的变体。他们最终采用 SIM(hard) 方法作为 online serving 算法，并在线部署 SIM(hard)+timeinfo 来服务主要流量。这是因为SIM(hard) 不需要 pre-training，对系统演进和维护更友好。此外，SIM(hard)+timeinfo 可以实现与 SIM(soft) 相当的性能。因此，我们选择 SIM(hard) 和 SIM(hard)+timeinfo 作为我们的强基线。 MIMN 与 DIN 是由同一个团队提出的。MIMN 提出了一个 multi-track offline user interest center 来提取长期用户兴趣。在发布时，它通过利用长期用户行为序列实现了 SOTA 的性能。然而，MIMN 被同一支队伍的 SIM 所击败。由于 MIMN 对我们的研究问题贡献不大，由于篇幅限制，我们省略了这个基线。

4. 评估指标：

   • 离线实验：AUC 作为主要指标，推理时间作为补充指标。

     推理时间定义为：对某个模型请求的 a batch of items 进行评分时的往返时间。我们通过在线部署被测试的模型来服务用户请求从而测量推理时间，这些用户请求是从产品环境中复制而来。为了比较公平性，机器和用户请求数量控制相同。

   • 在线 A/B test：CLICK 和 CTR 。

     • CLICK：被点击 items 的总数。

     • CTR：衡量平台中用户的点击意愿。它的定义为 CLICK/PV ，其中 PV 定义为被展示的 items 的总数。

5. 数据预处理：

   • Taobao 数据集仅包含 positive 交互，例如评论、点击、收藏、添加到购物车、以及购买。我们使用与MIMN 相同的数据预处理方法。

     • 首先，对于每个用户，我们选择最后一个behavior作为正样本。

     • 然后，对于该用户，我们随机采样一个与正样本相同 category 的新 item 作为负样本。

     • 其余的 behavior items 用作特征。

     根据正样本的时间戳 $t$$t$ ，将样本分为训练集（80%）、验证集（10%）和测试集（10%）。

   • 我们的工业数据集自然有正样本和负样本，因为我们记录了每个用户的所有 impressions 。如果用户点击了该 item ，则 impression 被标记为正样本；否则，它被标记为负样本。

     我们使用过去两周的日志作为训练集，following day 的日志作为测试集，这与 SIM 类似。

6. 实验设置：对于不同数据集上的每个模型，我们使用验证集来调优超参数以获得最佳性能。学习率从 $1\times {10}^{-4}$$1\times 10^{-4}$ 到 $1\times {10}^{-2}$$1\times 10^{-2}$ 搜索。L2 正则化项从 $1\times {10}^{-4}$$1\times 10^{-4}$ 到 $1$$1$ 搜索。所有模型都使用Adam 优化器。Taobao 数据集和我们的工业数据集的 batch size 分别为 256 、1024 。

1.4.1 性能比较

1. Taobao 数据集：Taobao据集上的评估结果如 Table 4 所示。从表中我们发现：

   • 与所有 baselines 相比，我们的 ETA 具有一致的性能改进。

     • ETA 比 SIM(hard) 好 0.46% ，比 DIN(Long Se-sequence) 好 0.6% 。

     • 添加 time embedding 后，ETA+timeinfo 的性能比 SIM(hard)+timeinfo 高 0.38% ，比 DIN(Long Sequence) 高 0.85% 。在 UBR4CTR 上也可以观察到类似的结果（即，添加 time embedding 的效果更好）。

   • 观察到 DIN(Long Sequence) 与 DIN 相比，AUC 提高了0.35% ，这表明对长期用户行为序列进行建模对于 CTR prediction 是有效的。

   • 我们还发现 UBR4CTR 的性能比 DIN(Long Sequence) 差。这是因为 UBR4CTR 的 feature selection model 仅选择特征（例如category 、星期几）与 target item 相同的behavior。UBR4CTR 中的这种过滤有助于从序列中去除噪音，但也会导致用户序列变短，当没有足够的 items 进行 top-k retrieval 时，这是有害的。

   • 我们发现DIN 比 Avg-Pooling DNN 的性能高出 1.84% ，这表明使用 target attention 来编码用户行为序列可以大大提高性能。

   

2. 工业数据集：我们自己的工业数据集上的评估结果如 Table 5 所示。请注意，CTR 模型在 AUC 上的 0.1% 改进，可以在我们的在线推荐系统中带来数百万的真实点击和收入。与所有 baselines 相比，我们的 ETA 实现了最佳性能。

   • 与 SIM(hard) 和 UBR4CTR 相比，我们的 base ETA 分别实现了 0.34% 和 0.43% 的改进。

   • 与 SIM(hard)+timeinfo 和 UBR4CTR+timinfo 相比，我们的 ETA+timeinfo 分别实现了 0.35% 和 0.42% 的改进。

   • 与Taobao 数据集不同，在工业数据集上 SIM(hard)+timeinfo 成为最强的 baseline ，比 DIN(Long Sequence) 高出 0.27% 。这有两个原因。

     • 一方面，工业数据集中的用户序列长度足够大，对基于长期用户序列的模型友好。工业数据集的平均长度达到了 938 ，是 Taobao 数据集的 9 倍。

     • 另一方面，DNN(Long Sequence) 采用均值池化对整个序列进行无选择性地编码，与 UBR4CTR 、SIM 、ETA 等基于检索的模型相比，可能会引入噪音。

     Taobao 数据集上的最强 baseline 也是 SIM(hard)+timeinfo 。所以这个结论是错误的，其解释也是不可信的。

   • 我们还可以发现 SIM(hard) 比 UBR4CTR 有 0.09% 的性能提升，这主要是由于对用户行为序列的处理方法不同造成的。

     • 在 SIM(hard) 中，用户序列被拆分为两个独立的子序列，与 Figure 2 中的 ETA 类似：短期用户行为序列 ${\mathcal{H}}_{su}$$\mathcal H_{su}$ 由最近的 k 个user behavior组成，从 item 1 到 item k ；长期用户行为序列 ${\mathcal{H}}_{lu}$$\mathcal H_{lu}$ 由从 item k+1 到 item n 中选择的其他 k 个behavior而组成。

     • 但是，UBR4CTR 从 item 1 到 item n 选择 $2k$$2k$ 长度的行为序列。因此，最近的 $k$$k$ 个 item （Figure 2 中的 ${\overrightarrow{\mathbf{e}}}_1$$\mathbf{\vec e}_1$ 到 ${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$）被 SIM(hard) 以 100% 的概率选中，被 UBR4CTR 以 feature selection model 所决定的 $p$$p$ 概率选中。然而，timeinfo 在用户兴趣建模中起着重要作用，因为用户兴趣是动态的并且经常变化。因此 SIM(hard) 的表现优于UBR4CTR 。

   

3. 在线 A/B Test ：在线 A/B Test 的评估结果如 Table 6 所示。 Table 6 显示了与 DIN-based 的方法相比的性能改进，其中 DIN-based 的方法没有长期用户行为序列。从 Table 6 中我们发现：

   • 与 DIN-based 的方法相比，我们的 ETA+timestamp 在 CTR 上实现了6.33% 的改进，并带来了 9.7% 的额外 GMV 。

   • 与最强的基线 SIM(hard)+timeinfo 相比，我们的 ETA+timeinfo 在 CTR 上额外提高了 1.8% ，在 GMV 上提高了3.1% 。

   请注意，GMV 上 1% 的改进是一个显著的改进，因为这意味着为推荐系统带来了数百万的收入。

   

1.4.2 推理时间比较

1. 虽然使用长期用户行为序列可以提高 CTR prediction 的性能，但模型复杂度也会相应增加。我们测量了不同模型的推理时间，如 Table 5 所示。

   • Avg-Pooling DNN 的推理时间最短，为 8 ms 。它仅使用均值池化方法来编码近期的 behavior items 。

   • 将均值池化替换为 target attention 后，DIN 的推理时间增加了 3ms （ 8ms 到 11ms ）。

   • 引入长期用户行为序列后，DIN (Long Sequence 的推理时间又增加了 3ms （11ms 到14ms ）。

   • SIM 和我们的 ETA 的推理时间相当，约为 19 ~ 21 ms 。

   • UBR4CTR 的推理时间最长，因为在检索阶段之前使用了额外的 feature selection model ，并且在线进行了相对耗时的 IDF and BM25 based 的程序来获取 top-k items 。

   

1.4.3 消融研究

1. 消融研究结果如 Table 7 所示，以回答问题 RQ3 。我们使用编码方式来区分 ETA 模型的不同版本（v0到v4 ）。请注意，v0 是 ETA 的基本版本。编码方式列在 Table 7 的第二列中，其中：

   • avg(·) 和 ta(·) 分别表示通过均值池化和 target attention 对user behavior进行编码。

   • ta(1024 -s- 48) 表示对从 1024 长度的用户行为序列中选择的 top-48 user behaviors 进行 target attention 。

   • ta(1024 -s- 48) 中的符号 s 表示 SimHash 用于从1024 个user behavior中选择 top-48 ；类似地，ta(1024 -i- 48) 中的符号i 表示内积用于从1024 个user behavior中选择 top-48 。

   从 Table 7 中，可以得出以下观察结果：

   • (i) ：直接在原始 1024 长度的用户行为序列上进行 multi-head target attention （v4）可以获得最佳性能，但同时具有最长的推理时间。

     与v4 相比，我们的 base ETA （v0） 选择 top-k behaviors进行 attention ，牺牲了大约 0.1% 的 AUC ，并将推理时间减少了 46% 。

   • (ii) ：将 v3 与 v0 进行比较，在检索阶段用内积替换 SimHash 可使 AUC 提高 0.07% 。然而，推理时间增加了 68% ，这是我们严格的在线 service level agreement: SLA 所不可接受的。

   • (iii) ：当我们改变用户行为序列的长度（v2.x 与 v0 ）时，观察到 AUC 和推理时间之间的权衡。可以根据在线推理时间的要求决定合适的序列长度。

   

2. 在 Figure 3 中，我们还评估了SimHash 所生成的哈希指纹 $\overrightarrow{\mathbf{h}}$$\mathbf{\vec h}$ 在不同 bit-length 下的性能。如前文所述，指纹的 bit-length 可以通过 SimHash 中使用的哈希函数数量来控制。我们可以发现：

   • 通过增加 $\overrightarrow{\mathbf{h}}$$\mathbf{\vec h}$ 的 bit-length 可以提高 AUC 。

   • 但是，当 $\overrightarrow{\mathbf{h}}$$\mathbf{\vec h}$ 的 bit-length 大于 2 倍 embedding size 时，AUC 的改进变得微不足道。