一、UBR4CTR [2020]

《User Behavior Retrieval for Click-Through Rate Prediction》

1. CTR prediction 在现代的 online personalization services 中起着关键作用。在实践中，需要通过对用户行为序列进行建模来捕获用户的兴趣变化，以构建准确的 CTR prediction 模型。然而，随着用户在平台上积累越来越多的行为数据，对 sequential models 而言，利用每个用户的 whole behavior history 变得并非易事。

   • 首先，直接馈入长的行为序列将使在线推理时间和系统负载变得不可行。

   • 其次，如此长的历史行为序列中存在大量噪音，导致 sequential model learning 的失败。

   当前的业界的解决方案主要截断序列并仅将近期行为馈入 prediction model ，这导致一个问题，即：周期性或长期依赖性等 sequential patterns 未被纳入近期的若干个behaviors中，而是包含在很久以前的历史中。为了解决这些问题，在本文中，我们从数据的角度考虑它，而不仅仅是设计更复杂的模型，并提出了 User Behavior Retrieval for CTR prediction: UBR4CTR 框架。在 UBR4CTR 中：

   • 首先使用可学习的搜索方法从整个用户历史序列中检索最相关、最合适的user behavior。

   • 然后将这些被检索到的行为（而不是简单地使用近期行为）馈入到 deep model 中以进行最终预测。

   以低成本将 UBR4CTR 部署到 industrial model pipeline 中是非常可行的。在三个真实世界大型数据集上的实验证明了我们提出的框架和模型的优越性和有效性。

2. CTR prediction 在当今的在线个性化平台（例如电商、在线广告、推荐系统）中起着关键作用，其目标是预测用户在特定情境下点击特定 item 的概率。在线个性化平台经过十多年的发展，平台上记录的user behaviors数量迅速增长。23% 的用户在六个月内在淘宝上有超过 1000 次 behaviors（《Lifelong Sequential Modeling with Personalized Memorization for User Response Prediction》）。由于user behavior中存在丰富的时间模式（temporal patterns ），因此建立一个有效且高效的模型，利用user behavior序列来获得准确的 CTR prediction 成为业界和学术界的一个重要问题。

   在深度学习时代，有许多 DNN-based 的 CTR prediction 模型，例如 Wide&Deep、FNN、DeepCross、DeepFM、PNN 和 xDeepFM，其中大多数已部署在商业的个性化平台上。这些模型强调挖掘特征交互（feature interactions ），并被用于更好地利用数据的 multi-categorical features 。然而，这些模型忽略了user behavior的序列模型或时间模式（sequential or temporal patterns）。

   如《Spatio-temporal models for estimating click-through rate》、《Vista: a visually, socially, and temporally-aware model for artistic recommendation》、《Recurrent neural networks with top-k gains for session-based recommendations》、《Collaborative filtering with temporal dynamics》 所示，user behavior的 temporal dynamics 在预测用户未来兴趣方面起着关键作用。这些序列模式（sequential patterns ）包括概念漂移（concept drifting ）、长期behavior依赖性（long-term behavior dependency ）、周期性模式（periodic patterns ）等。因此，在 CTR prediction 和序列推荐任务中，人们提出了一些模型来捕获用户的序列模式。

   • 对于 CTR prediction ，有 attention-based 的模型，如 DIN 和 DIEN ；有 memory network-based 的模型，如HPMN。

   • 对于序列推荐，人们提出了更多的 user behavior modeling 方法，这是一项与 CTR prediction 非常相似的任务。有 RNN-based 的模型、CNN-based 的模型、Transformer-based 的模型、以及 memory network-based 的模型。

   然而，上述大多数序列模型在实际应用中都有一个共同的问题。当平台记录了大量的user behavior时，常见的工业解决方案是截断整个行为序列，只使用最近的 $N$$N$ 个behavior作为 prediction model 的输入，如 Figure 1 上半部分所示。online serving time 的严格要求，加上系统负载和计算能力的瓶颈，限制了可使用的用户序列的长度。因此，在大多数情况下，使用的近期行为不超过 50 个（《Deep interest evolution network for click-through rate prediction》）。 使用最近 $N$$N$ 个behavior的传统框架可能会带来负面问题。很明显，有效的序列模式可能不仅仅包含在最近的行为序列中。它可以追溯到更远的历史，如周期性和长期依赖性。然而，如果我们尝试使用更长的序列，可能会引入大量不相关的behavior和噪音。更不用说更长的历史带来的时间复杂性和空间复杂性了。 在本文中，为了解决上述实际问题，我们尝试从数据的角度解决问题，而不是设计更复杂更精密的模型。具体来说，我们的目标是设计一个框架来检索对每个 CTR prediction target 最有用的有限数量的历史行为。如 Figure 1 所示，prediction target 由三部分组成，即：target user 、target item 和相应的上下文。prediction target 的特征包括用户的位置、性别、职业，以及item 的 category 、品牌、商家，以及时间和场景等上下文特征。然后我们使用模型选择这些特征的一个子集，该子集构建一个 query 来检索相关的历史行为。用户的所有behavior都作为information items 来存储在搜索引擎中，我们使用所生成的 query 从历史记录中进行搜索。被检索到的behavior用于 CTR prediction 。 对于同一用户的每个不同 target item ，我们将检索不同的 behaviors 来用于 prediction ，因为所生成的 queries 不同。对同一用户的不同 items 上的预测而言，与使用完全相同的最近 $N$$N$ 个behavior的传统框架相比，这是一个重大变化。

   最终的解决方案框架称为 User Behavior Retrieval for CTR: UBR4CTR。在 UBR4CTR 中，任务分为两个模块：

   • 第一个是可学习的检索模块，它由两个组件：

     • 一个 self-attentive network ，用于选择特征并形成 query 。

     • 以及一个搜索引擎，其中以倒排索引的方式存储user behavior。

   • 另一个模块是 prediction 模块，其中构建了一个 attention-based deep neural network ，从而根据检索到的user behavior、以及 prediction target 的特征进行最终预测。

   本文的贡献可以概括为三点：

   • 我们揭示了一个重要事实，即在 user response prediction 中，检索更相关的user behavior比仅仅使用最近的behavior更重要。我们没有设计更复杂的模型，而是将更多注意力放在检索用户的behavior数据上。

   • 我们提出了一个名为 UBR4CTR 的新框架，该框架可以检索不同的 behaviors 从而用于同一用户在不同上下文中对不同 items 的 CTR prediction 。所有先前的序列模型仅使用用户最近的behavior。我们提出了一种 search engine based 的方法和一种有效的训练算法来学习检索适当的behavior数据。

   • 我们在三个现实世界的大型电商数据集上进行了大量的实验，并将我们的框架与传统框架中几个强大的 baselines 进行了比较。结果验证了 UBR4CTR 框架的有效性。

   UBR4CTR 是 SIM(hard) 的扩展。在 SIM(hard) 中，我们使用 catgory of target item 作为 query 从而执行检索。而在 UBR4CTR 中，我们根据不同的 input 来自动选择合适的 query 来执行检索。但是，更复杂的 query 引入了更复杂的检索系统（一个搜索引擎客户端），增加了工程量。

   

1.1 基础知识

1. 在本节中，我们将问题公式化并引入符号。在 CTR prediction 任务中，有 $M$$M$ 个用户 $\mathcal{U}=\{u_1,\cdots ,u_M\}$$\mathcal U = \{u_1,\cdots,u_M\}$，有 $N$$N$ 个 items $\mathcal{V}=\{v_1,\cdots ,v_N\}$$\mathcal V = \{v_1,\cdots,v_N\}$。user-item interactions 记作 $\mathcal{Y}=\{y_{u,v}\mid u\in \mathcal{U},v\in \mathcal{V}\}$$\mathcal Y = \{y_{u,v}\mid u\in \mathcal U, v\in \mathcal V\}$，并且：

   $$\begin{array}{c}{y}_{u,v}=\{\begin{array}{ll}1,& u\text{ has clicked }v\\ 0,& \text{else}\end{array}\end{array}$$

   此外，每个 user-item interaction 都有一个时间戳和一个上下文，时间戳和上下文是 interaction 发生时刻的。因此数据被公式化为四元组，即 $\{u,v,c,ts\}$$\{u,v,c,ts\}$，表示用户 $u$$u$ 在时刻 $ts$$ts$ 在上下文 $c$$c$ 的情况下点击了 item $v$$v$ 。

   为了建模用户不断变化的兴趣，我们将用户历史行为组织为 $H_u=\{b_1^u,b_2^u,\cdots ,b_T^u\}$$H_u=\left\{b_1^u,b_2^u,\cdots,b_T^u\right\}$，其中 $b_i^u$$b_i^u$ 代表用户 $u$$u$ 的第 $i$$i$ 条behavior记录，按时间戳升序排序。点击率本质上是用户、item 、以及上下文之间的匹配概率，因此每条behavior $b_i^u$$b_i^u$ 由以下三部分组成：$b_i^u=[u,v_i,c_i]$$b_i^u=[ u,v_i,c_i]$，其中 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 是被用户 $u$$u$ 点击的第 $i$$i$ 个 item ，$c_i$$c_i$ 是发生交互的上下文。

2. 在特征层面，每个用户 $u$$u$ 由一组特征表示，$\mathbf{u}=[f_1^u,\cdots ,f_{K_u}^u]$$\mathbf u=\left[f_1^u,\cdots,f_{K_u}^u\right]$，其中 $f_p^u$$f_p^u$ 表示 $u$$u$ 的第 $p$$p$ 个特征。通常所有特征都是 multiple categorical 特征。如果有 numerical 特征，则将其离散化为 categorical 特征。

   类似地，$\mathbf{v}=[f_1^v,\cdots ,f_{K_v}^v]$$\mathbf v=\left[f_1^v,\cdots,f_{K_v}^v\right]$ 和 $\mathbf{c}=[f_1^c,\cdots ,f_{K_c}^c]$$\mathbf c=\left[f_1^c,\cdots,f_{K_c}^c\right]$。$K_u,K_v,K_c$$K_u,K_v,K_c$ 分别为用户、item、以及上下文的特征数量。

   这里的特征数量就是 field 数量。例如，$f_i^u$$f_i^u$ 就是 user $u$$u$ 的第 $i$$i$ 个 field 。

3. CTR prediction 的目标是：根据 $u$$u$ 在上下文 $c$$c$ 下的历史行为，预测 target user $u$$u$ 点击 target item $v$$v$ 的概率。其公式为

   $${\hat{y}}_{u,v}=f(u,v,c\mid H_u;\theta )$$

   其中： $f(\cdot ;\theta )$$f(\cdot;\theta)$ 是具有参数 $\theta$$\theta$ 的函数。

4. 我们在 Table 1 中总结了符号和相应的描述。

   

1.2 方法论

1. 本节将详细描述我们提出的 UBR4CTR （User Behavior Retrieval for CTR prediction ）框架。我们首先给出整体框架的总体概述，然后详细描述 user behavior retrieval 模块和 prediction 模块。此外，以下各节将给出训练方法和一些时间复杂度分析。

1.2.1 整体框架

1. UBR4CTR 的整体框架如 Figure 2 所示。该框架可分为两个主要模块：user behavior retrieval 模块和 prediction 模块。

   • user behavior retrieval 模块由一个 feature selection model 、一个 search engine client 和一个 user history archive 组成。所有用户历史行为都存储在 archive 中，并以 feature-based 的倒排索引方式组织，这将在后续章节中详细说明。

     如 Figure 2 所示，当我们需要在特定上下文中预测 target user 和 target item 之间的点击率时，所有这三部分信息结合在一起形成 prediction target 。prediction target 本质上是由 target user 、 target item 和上下文的一系列特征组成。因此， prediction target 随后被馈入到 feature selection model 中，该模型将选择适当的特征来形成一个 query 。feature selection model 的详细设计见后续章节。然后，我们使用该 query 通过搜索 search engine client 在 user history archive 中进行搜索。

   • search engine client 检索出一定数量的user behaviors，然后这些被检索到的 behaviors 被 prediction 模块使用。在 prediction 模块中，我们使用 attention-based 的深度模型来区分每个behavior对点击概率的影响，并做出最终预测，这将在后续章节中讨论。

   feature selection model 和 prediction model 轮流进行训练。feature selection model 的目标是选择最有用的特征子集。该子集的特征将组合起来生成一个 query ，该 query 用于检索与 final prediction 最相关的user behavior。

   

1.2.2 User Behavior Retrieval Module

1. 在本节中，我们介绍用 user behavior retrieval module ，该模块由 feature selection model 和 behavior searching 过程组成。

2. Feature Selection Model ：如 Figure 3 所示，我们将 target user $u$$u$ 、target item $v$$v$ 和对应的上下文 $c$$c$ 的所有特征作为 feature selection model 的输入。不失一般性，我们将 $f_1^u$$f_1^u$ 设置为 user id 特征。 user id 是一个特殊的特征，我们必须选择它，因为我们想要检索用户 $u$$u$ 自己的behavior。所有其他特征都拼接成一个整体。为简单起见，我们将所有特征 $[f_2^u,\cdots ,f_{K_u}^u,f_1^v,\cdots ,f_{K_v}^v,f_1^c,\cdots ,f_{K_c}^c]$$\left[f_2^u,\cdots,f_{K_u}^u,f_1^v,\cdots,f_{K_v}^v,f_1^c,\cdots,f_{K_c}^c\right]$ 表示为 $[f_1,\cdots ,f_{K_q}]$$[f_1,\cdots,f_{K_q}]$，其中 $K_q=K_u+K_v+K_c-1$$K_q=K_u+K_v+K_c - 1$。

   注意：这里的 $f_i$$f_i$ 对应于一个 field。每个 field 的取值都是离散值。

   为了更好地建模特征之间的关系和交互模式，我们使用 self-attention 机制。具体来说，我们定义：

   $$\begin{array}{c}\mathbf{Q}=\mathbf{K}=\mathbf{V}=\left[\begin{array}{c}{\overrightarrow{\mathbf{f}}}_1\\ ⋮\\ {\overrightarrow{\mathbf{f}}}_{K_q}\end{array}\right]\in {\mathbb{R}}^{K_q\times d}\end{array}$$

   其中：${\overrightarrow{\mathbf{f}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec f}_i\in \mathbb R^d$ 为第 $i$$i$ 个特征 $f_i$$f_i$ 的 dense embedding representation ；$d$$d$ 为 embedding size 。

   这里的 feature embedding 是否与 Prediction Module 共享？根据 Prediction Module 章节的描述，读者认为是共享的。

   self-attention 定义为：

   $$\text{SA}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}}{\sqrt{d}}\right)\mathbf{V}$$

   multi-head self-attention 定义为：

   $$\begin{array}{c}\mathbf{E}=\text{Multihead}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{Concat}({\text{head}}_1,\cdots ,{\text{head}}_h){\mathbf{W}}^O\in {\mathbb{R}}^{K_q\times d}\\ {\text{head}}_i=\text{SA}(\mathbf{Q}{\mathbf{W}}_i^Q,\mathbf{K}{\mathbf{W}}_i^K,\mathbf{V}{\mathbf{W}}_i^V)\end{array}$$

   其中：$h$$h$ 为 head 数量；${\mathbf{W}}^O\in {\mathbb{R}}^{hd\times d},{\mathbf{W}}_i^Q\in {\mathbb{R}}^{d\times d},{\mathbf{W}}_i^K\in {\mathbb{R}}^{d\times d},{\mathbf{W}}_i^V\in {\mathbb{R}}^{d\times d}$$\mathbf W^O\in \mathbb R^{hd\times d}, \mathbf W_i^Q\in \mathbb R^{d\times d},\mathbf W_i^K\in \mathbb R^{d\times d},\mathbf W_i^V\in \mathbb R^{d\times d}$ 为投影矩阵。

   然后，multi-head self-attention 的输出 $\mathbf{E}$$\mathbf E$ 被馈入到具有 $\text{ReLU}(x)=max(0,x)$$\text{ReLU}(x) = \max(0,x)$ 激活函数的 multi-layer perceptron：

   $$\hat{\mathbf{E}}=\text{MLP}\left(\mathbf{E}\right)\in {\mathbb{R}}^{K_q\times 1}$$

   相应特征被选择的概率通过取 sigmoid 函数获得：

   $$\begin{array}{c}\mathbf{P}=\left[\begin{array}{c}{p}_1\\ ⋮\\ p_{K_q}\end{array}\right]=\sigma \left(\hat{\mathbf{E}}\right)\in {\mathbb{R}}^{K_q\times 1}\end{array}$$

   其中：$\sigma (x)=\frac{1}{1+\exp (-x)}$$\sigma(x) = \frac{1}{1+\exp(-x)}$ 。

   然后我们根据这些概率对特征进行采样，从而得到选择好的特征子集。请注意，user id 特征始终在子集中，因为我们必须从 target user 自己的behavior中检索。

   实际上被采样到的是 field ；但是在下一步检索时，将这个 field 在这个样本上的取值作为条件。

   

3. Behavior Searching ：我们使用典型的搜索引擎方法来存储和检索user behavior。我们将每个user behavior视为一个文档，将每个特征视为一个 term 。倒排索引用于跟踪所有behavior，如 Figure 4 所示。每个 feature value 都与一个 posting list 相关联，该列表由具有此特定 feature value 的所有behavior组成。例如：

   • "user_id_1" 包含 user id = 1 的用户的所有behavior的 posting list。

   • "Nike" 具有由 brand id = "Nike" 的所有behavior组成的 posting list。

   query 的逻辑本质上表述为：

   $$f_1^u\text{ AND }(f_1\text{ OR }{f}_2\text{ OR }\cdots \text{ OR }{f}_n)$$

   其中：$f_1^u$$f_1^u$ 为 user_id ；所选中的 query feature set 为 $\mathcal{Q}=\{f_1,f_2,\cdots ,f_n\}$$\mathcal Q = \{f_1,f_2,\cdots,f_n\}$。

   $n$$n$ 怎么选择？论文没有说明，实验部分也没有消融分析。

   我们将 $f_1^u$$f_1^u$ 的 posting list与 $f_1\text{ to }{f}_n$$f_1 \text{ to } f_n$ 的 posting lists 的并集进行相交，交集的结果就是 candidate behavior set 。然后我们使用 BM25 对候选集中的每个 behavior document 进行评分，并检索出 top S 个 behavior document 。 query $q$$q$ 与 behavior document $D$$D$ 之间的相似度 $s$$s$ 计算如下：

   $$s=\sum _{i=1}^n\text{IDF}(f_i)\times \frac{\text{tf}(f_i,D)\times (k_1+1)}{\text{tf}(f_i,D)+k_1\times (1-b+b\times \frac{|D|}{\text{avgdl}})}$$

   其中：

   • $\text{tf}(f_i,D)$$\text{tf}(f_i,D)$ 为特征 $f_i$$f_i$ 在 $D$$D$ 中的频次，取值为 1 或 0 。

   • behavior document 的长度 $|D|$$|D|$ 定义为该behavior中的特征数量，因此所有 behavior document 的长度相同。因此平均长度是每个文档的长度，并且 $\frac{|D|}{\text{avgdl}}=1$$\frac{|D|}{\text{avgdl}} = 1$，其中 $\text{avgdl}$$\text{avgdl}$ 为平均的文档长度。

   • $k_1$$k_1$ 和 $b$$b$ 是自由参数。我们选择 $k_1=1.2$$k_1 = 1.2$ 、$b=0.75$$b=0.75$ 。

     可以进一步化简为： $s=\sum _{i=1}^n\text{IDF}(f_i)\times \frac{\text{tf}(f_i,D)\times (k_1+1)}{\text{tf}(f_i,D)+k_1}$$s = \sum_{i=1}^n\text{IDF}(f_i)\times \frac{\text{tf}\left(f_i, D\right)\times (k_1 + 1)}{\text{tf}\left(f_i, D\right) + k_1}$ 。似乎 $b$$b$ 参数没什么用？

     考虑到 $\text{tf}(f_i,D)$$\text{tf}(f_i,D)$ 取值为 0 或 1 ，因此：

     $$\begin{array}{c}\frac{\text{tf}(f_i,D)\times (k_1+1)}{\text{tf}(f_i,D)+k_1}=\{\begin{array}{ll}0& \text{if }\text{tf}(f_i,D)=0\\ 1& \text{else}\end{array}\end{array}$$

     因此 $k_1$$k_1$ 也没什么用？

   IDF 定义为：

   $$\text{IDF}(f_i)=\log \frac{\mathcal{N}-\mathcal{N}(f_i)+0.5}{\mathcal{N}(f_i)+0.5}$$

   其中： $\mathcal{N}$$\mathcal N$ 是所有用户的所有 behavior documents 的总数，$\mathcal{N}(f_i)$$\mathcal N (f_i)$ 是包含特征$f_i$$f_i$ 的 behavior documents 总数。

   IDF 项赋予常见特征比罕见特征更少的重要性。与常见特征相比，罕见特征对用户偏好的暗示更强，这是有道理的。 通过使用 BM25 对 candidate behaviors 进行排序，我们获得了 top S 的 behavior documents 作为所检索到的behavior，记作 ${\mathcal{B}}^u$$\mathcal B^u$。

   实际应用时会采用双层索引，最外层为 user_id，最内层为各个特征的取值，从而降低存储需求。

   

1.2.3 Prediction Module

1. 对于 prediction module ，我们使用 attention-based 的深度神经网络来建模不同user behavior对 final prediction 的重要性。

   如 Figure 5 所示，我们通过加权池化得到 user representation ${\overrightarrow{\mathbf{r}}}^u$$\mathbf{\vec r}^u$：

   $$\begin{array}{c}{\overrightarrow{\mathbf{r}}}^u=\sum _{i=1}^S{\alpha }_i\times {\overrightarrow{\mathbf{b}}}_i^u,{\overrightarrow{\mathbf{b}}}_i^u\in {\mathcal{B}}^u\\ {\alpha }_i=\frac{\exp (w_i)}{\sum _{j=1}^S\exp (w_j)},w_i=\text{Att}({\overrightarrow{\mathbf{b}}}_i^u,\overrightarrow{\mathbf{t}})\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{b}}}_i^u=[\overrightarrow{\mathbf{u}}||{\overrightarrow{\mathbf{v}}}_i||{\overrightarrow{\mathbf{c}}}_i]$$\mathbf{\vec b}_i^u = \left[\mathbf{\vec u}||\mathbf{\vec v}_i||\mathbf{\vec c}_i\right]$ 为针对user behavior $b_i^u$$b_i^u$ 的拼接后的 embedding 向量，$\cdot ||\cdot$$\cdot||\cdot$ 表示向量拼接。

   • $S$$S$ 为所选择的behavior document 的数量。

   • ${\alpha }_i$$\alpha_i$ 为权重，用于刻画user behavior $b_i^u$$b_i^u$ 对于 ${\overrightarrow{\mathbf{r}}}^u$$\mathbf{\vec r}^u$ 的重要性。

   • $\overrightarrow{\mathbf{t}}=[\overrightarrow{\mathbf{u}}||\overrightarrow{\mathbf{v}}||\overrightarrow{\mathbf{c}}]$$\mathbf{\vec t} = \left[\mathbf{\vec u}||\mathbf{\vec v}||\mathbf{\vec c}\right]$ 为 prediction target 向量。Att() 是一个具有 ReLU 激活函数的多层深度网络。

     这个 prediction target 向量 $\overrightarrow{\mathbf{t}}$$\mathbf{\vec t}$ 的内容和 $\mathbf{Q},\mathbf{K},\mathbf{V}$$\mathbf Q,\mathbf K,\mathbf V$ 几乎相同，区别在两个地方：

     • $\overrightarrow{\mathbf{t}}$$\mathbf{\vec t}$ 包含了 user ID 特征 $f_1^u$$f_1^u$ ，而 $\mathbf{Q},\mathbf{K},\mathbf{V}$$\mathbf Q,\mathbf K,\mathbf V$ 不包含。

     • $\overrightarrow{\mathbf{t}}$$\mathbf{\vec t}$ 是向量拼接而成，维度为 $(K_q+1)d\times 1$$(K_q+1)d\times 1$ ；而 $\mathbf{Q},\mathbf{K},\mathbf{V}$$\mathbf Q,\mathbf K,\mathbf V$ 为向量堆叠而成，维度为 $K_q\times d$$K_q\times d$ 。

   final prediction 计算如下：

   $${\hat{y}}_{u,v}=f_{\varphi }({\mathcal{B}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}})=f_{\varphi }({\overrightarrow{\mathbf{r}}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}})$$

   其中： $f_{\varphi }$$f_\phi$ 实现为三层感知器，宽度分别为 $200/80/1$$200/80/1$ ，$\varphi$$\phi$ 为参数；输出层采用 sigmoid 函数，其他层采用ReLU 作为激活函数。

   

1.2.4 Model Training

1. 由于目标是准确估计点击率，我们使用对数似然作为目标函数，其定义为：

   $$J^{{\pi }_{\theta },f_{\varphi }}=\underset{\theta }{max}\underset{\varphi }{max}\sum _u\sum _v{\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}\left[\text{LL}(y_{u,v},f_{\varphi }({\mathcal{B}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}}))\right]$$

   其中：

   • LL(.) 是在给定所检索到的user behavior ${\mathcal{B}}^u$$\mathcal B^u$ 以及上下文 $c$$c$ 的情况下，对 target user-item pair $(u,v)$$(u,v)$ 的预测分数的对数似然。其定义为： $\text{LL}(y,\hat{y})=y\log \hat{y}+(1-y)\log (1-\hat{y})$$\text{LL}\left(y,\hat y\right) = y\log \hat y + (1-y)\log\left(1-\hat y\right)$ 。

   • $q$$q$ 是由所选定的特征组成的 query 。我们使用抽样来选择特征，然后被选中的特征形成 query string 。query string 形成后，搜索结果（即，检索到的behavior）是确定性的。因此，我们可以认为这些behavior是从概率分布 ${\pi }_{\theta }({\mathcal{B}}^u\mid q)$$\pi_\theta\left(\mathcal B^u\mid q\right)$ 中采样的。

2. 优化 Prediction Module：为了优化 attention-based 预测网络 $f_{\varphi }$$f_\phi$ ，我们有：

   $$\begin{array}{c}{\varphi }^{\ast }=\arg \underset{\varphi }{min}(L_{\text{ce}}+\lambda L_r)=\\ \arg \underset{\varphi }{min}\sum _u\sum _v{\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}[-\text{LL}(y_{u,v},f_{\varphi }({\mathcal{B}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}}))]+\frac{1}{2}\lambda (||\varphi |{|}_2^2)\end{array}$$

   其中：$L_{\text{ce}}$$L_\text{ce}$ 是交叉熵损伤，$L_r$$L_r$ 为正则化，$\lambda$$\lambda$ 为正则化系数。

   注意，这里是负的对数似然，所以是 min 。

   当我们优化 prediction network 时，检索模块保持不变，因此如果函数 $f_{\varphi }$$f_\phi$ 关于 $\varphi$$\phi$ 是可微分的，则上述优化可以通过典型的随机梯度下降算法解决。

3. 优化检索模块：对于检索模块，只需要优化 feature selection model 。随着采样过程的发展，我们不能直接使用 SGD 来优化它。相反，我们使用 REINFORCE 算法来处理离散优化（discrete optimization ）。 具体而言，在保持 prediction network $f_{\varphi }$$f_\phi$ 固定的同时，通过执行最大化如下公式来优化 feature selection model ：

   $${\theta }^{\ast }=\arg \underset{\theta }{max}\sum _u\sum _v{\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}\left[\text{LL}(y_{u,v},f_{\varphi }({\mathcal{B}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}}))\right]$$

   我们将 $\text{LL}(y_{u,v},f_{\varphi }({\mathcal{B}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}}))$$\text{LL}\left(y_{u,v},f_\phi\left(\mathcal B^u , \mathbf{\vec u}, \mathbf{\vec v}, \mathbf{\vec c}\right)\right)$ 记作 $\text{LL}(\cdot )$$\text{LL}(\cdot)$ ，因为它没有参数 $\theta$$\theta$ 。对于每个query $q$$q$ ，我们将目标函数表示为 $J^q$$J^q$，即：

   $$J^q={\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}[\text{LL}(\cdot )]$$

   我们将检索模块 ${\pi }_{\theta }({\mathcal{B}}^u\mid q)$$\pi_\theta\left(\mathcal B^u\mid q\right)$ 视为一种策略，并使用 likelihood ratio 来估计其梯度：

   $$\begin{array}{c}{\mathrm{\nabla }}_{\theta }\left(J^q\right)={\mathrm{\nabla }}_{\theta }{\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}[\text{LL}(\cdot )]\\ =\sum _{{\mathcal{B}}_i^u\sim \mathcal{B}}{\mathrm{\nabla }}_{\theta }{\pi }_{\theta }({\mathcal{B}}_i^u\mid q)[\text{LL}(\cdot )]\\ =\sum _{{\mathcal{B}}_i^u\sim \mathcal{B}}{\pi }_{\theta }({\mathcal{B}}_i^u\mid q){\mathrm{\nabla }}_{\theta }\log \left({\pi }_{\theta }({\mathcal{B}}_i^u\mid q)\right)[\text{LL}(\cdot )]\\ ={\mathbb{E}}_{{\mathcal{B}}^u\sim {\pi }_{\theta }({\mathcal{B}}^u\mid q)}{\mathrm{\nabla }}_{\theta }\log \left({\pi }_{\theta }({\mathcal{B}}_i^u\mid q)\right)[\text{LL}(\cdot )]\\ \simeq \frac{1}{L}\sum _{l=1}^L{\mathrm{\nabla }}_{\theta }\log \left({\pi }_{\theta }({\mathcal{B}}_l^u\mid q)\right)[\text{LL}(\cdot )]\end{array}$$

   这是对 $J^q$$J^q$ 的梯度的无偏估计。其中 $L$$L$ 为采样的 query 数量。

   由于整个检索模块的不确定性实际上来自 feature selection model ，我们可以得出：

   $${\pi }_{\theta }({\mathcal{B}}^u\mid q)=\prod _{j=1}^{n}p(f_j)$$

   其中：$f_j\in \{f_1,\cdots ,f_n\}$$f_j\in \{f_1,\cdots,f_n\}$ ，$p(f_j)$$p(f_j)$ 为采样概率。因此：

   $${\mathrm{\nabla }}_{\theta }\left(J^q\right)\simeq \frac{1}{L}\sum _{j=1}^n\sum _{l=1}^L{\mathrm{\nabla }}_{\theta }\log \left(p\left(f_j^l\right)\right)[\text{LL}(\cdot )]$$

   其中：其中 $f_j^l$$f_j^l$ 是第 $l$$l$ 个 query 的第 $j$$j$ 个特征。

   为了使用reward 训练一个更好的模型，我们在这里用相对信息增益 （Relative Information Gain: RIG ）替换 LL(·) 作为奖励函数。 RIG 定义为 RIG = 1 − NE ，其中 NE 是归一化熵：

   $$\text{NE}=\frac{\text{LL}(\cdot )}{p\log p+(1-p)\log (1-p)}$$

   其中 $p$$p$ 是平均经验 CTR 。

   可以参考 UBR 模型，它是 UBR4CTR 的升级版。

4. 训练过程的伪代码：在本小节中，我们给出了训练过程的详细伪代码。

   • 首先，我们使用 feature selection model 对预测网络进行预热。

     feature selection model 如何初始化？如果是随即初始化是否会带来不利影响？作者没有提及。读者猜测是不影响的，因为后续的迭代训练会对 feature selection model 进行优化。

     为什么要预热？因为 prediction model 是 feature selection model 的奖励函数，它必须要有一定的准确性才能指导 feature selection model 的学习。

   • 预训练后，我们轮流优化两个模型，每个模型被训练一个 epoch 之后，再训练另一个模型一个 epoch，轮流往复。

   Algorithm 1 显示了训练过程。

   

1.2.5 模型分析

1. 本节分析了该方法的时间复杂度和可行性。我们使用 $\mathcal{N}$$\mathcal N$ 表示所有user behavior的总数，使用 $F$$F$ 表示整个数据集中出现过的 unique features （相当于 term ）的总数。然后，user history archive 中 posting lists 的平均长度为 $\mathcal{N}/F$$\mathcal N/F$ 。

   • 回想一下之前内容所描述的搜索操作，我们首先检索 $q$$q$ 中特征的所有 postings ，这需要 $O(1)$$O(1)$ 时间。

   • 然后交互操作需要 $O(T+K_q\times \mathcal{N}/F)$$O(T+K_q\times \mathcal N/F )$ 时间，其中 $T$$T$ 是用户序列的平均长度，$K_q=K_u+K_v+K_c-1$$K_q =K_u +K_v +K_c −1$ 是 selected features 数量的上限。

   • 接下来的 scoring 操作不会增加复杂度，因为它与 $O(T+K_q\times \mathcal{N}/F)$$O(T+K_q\times \mathcal N/F )$ 成线性关系。

   • feature selection model 中的 self-attention 的复杂度为 $O(K_q^2)$$O(K_q^2)$ 。

   • attention-based prediction network 需要 $O(\mathcal{C})$$O(\mathcal C)$ 时间，其中 $\mathcal{C}$$\mathcal C$ 是计算个 $w_i=\text{Att}({\overrightarrow{\mathbf{b}}}_i^u,\overrightarrow{\mathbf{t}})$$w_i = \text{Att}\left(\mathbf{\vec b}_i^u, \mathbf{\vec t}\right)$ 操作的成本，因为所有 attention 操作都可以并行执行。

   两个常数可以忽略，因此 UBR4CTR 的总时间复杂度为 $O(T+K_q\times \mathcal{N}/F)$$O(T+K_q\times \mathcal N/F )$ 。

1.3 实验

1. 在本节中，我们详细介绍了我们的实验设置和相应的结果。我们将我们的模型与几个强大的 baselines 进行了比较，并实现了 SOTA 的性能。此外，我们已经发布了代码用于复现（https://github.com/qinjr/UBR4CTR ）。 我们从三个研究问题（research question: RQ ）开始，并用它们来引导以下讨论。

   • RQ1 ：与其他 baselines 相比，UBR4CTR 是否实现了最佳性能？

   • RQ2 ：Algorithm 1 的收敛性能如何？训练过程是否有效且稳定？

   • RQ3 ：UBR4CTR 中的检索模块有什么影响，retrieval size 如何影响性能？

2. 数据集：我们使用三个真实的、大型的 users online behaviors 数据集，它们来自阿里巴巴集团三个不同平台。数据集的统计数据可以在 Table 2 中找到。

   • Tmall 数据集：由阿里巴巴集团提供，其中包含 2015 年5 月至2015 年11 月天猫电商平台上的user behavior历史记录。

   • Taobao 数据集：包含来自中国最大的电商平台之一淘宝中检索到的user behavior数据。它包含 2017 年 11 月25 日至 12月3日的user behavior，包括点击、购买、添加到购物车、以及喜欢商品等几种behavior类型。

   • Alipay 数据集：由在线支付应用程序支付宝收集。用户的在线购物behavior是从 2015 年7 月1日到2015年 11 月 30日。

   

3. 数据集预处理：

   • 对于 UBR4CTR ，数据集被处理成逗号分隔特征的格式。包含 user, item and context features 的一行被视为一个 behavior document 。

   • 对于 baselines ，user behavior仅按时间戳排序。由于数据集不包含特定的上下文特征，我们使用 behavior timestamp 手动设计一些特征，以便能够捕获周期性。我们设计了一些特征，例如 season id （春季、夏季等）、是否是周末、以及是哪个半月（上半月还是下半月）。

4. 搜索引擎：数据集预处理后，使用逗号分隔的 tokenizer 将它们插入搜索引擎。我们使用基于 Apache Lucene 的 Elastic Search 作为搜索引擎客户端。

5. Train & Test Splitting ：我们使用 time step 来拆分数据集。

   • 训练集包含第 $1$$1$ 到 $(T-2)$$(T - 2)$ 个user behavior，其中第 $1$$1$ 到 $(T-3)$$(T - 3)$ 个behavior用于预测第 $(T-2)$$(T - 2)$ 个behavior。

   • 类似地，验证集使用第 $1$$1$ 到 $(T-2)$$(T - 2)$ 个behavior来预测第 $(T-1)$$(T - 1)$ 个behavior；测试集使用第 $1$$1$ 到$(T-1)$$(T - 1)$ 个behavior来预测第 $T$$T$ 个behavior。

6. 超参数：

   • UBR4CTR 的 feature selection model 的学习率从 $\{1\times {10}^{-6},1\times {10}^{-5},1\times {10}^{-4}\}$$\{1\times 10^{−6}, 1\times10^{−5}, 1\times10^{−4}\}$ 中搜索，attention based prediction network 的学习率从 $\{1\times {10}^{-4},5\times {10}^{-4},1\times {10}^{-3}\}$$\{1\times 10^{−4}, 5\times10^{−4}, 1\times10^{−3}\}$ 中搜索，正则化项从 $\{1\times {10}^{-4},5\times {10}^{-4},1\times {10}^{-3}\}$$\{1\times 10^{−4}, 5\times10^{−4}, 1\times10^{−3}\}$ 中搜索。

   • baseline 模型的学习率和正则化项的搜索空间与 UBR4CTR 的 prediction network 相同。

   • 所有模型的 batch size 均从 $\{100,200\}$$\{100, 200\}$ 中搜索。

   每个模型的超参数都经过调优并报告最佳性能。

7. 评估指标：CTR 、Logloss 。

8. Baselines：我们将我们的框架和模型与来自 sequential CTR prediction 和推荐场景的七个不同的强基线进行比较。

   • GRU4Rec 基于 GRU ，它是第一个工作使用 recurrent cells 建模user behavior序列从而用于 session-based 推荐。

   • Caser 是一个 CNNs-based 的模型，它将用户序列视为图像，因此使用 horizontal and vertical convolutional layers 来捕获user behavior的时间模式。

   • SASRec 使用Transformer。它将user behavior视为 tokens 的一个序列，并使用自注意机制和 position embedding 来捕获behavior之间的依赖关系。

   • HPMN 是一个 hierarchical periodic memory network ，旨在处理非常长的用户历史序列。此外，user memory state 可以增量更新。

   • MIMN 基于 Neural Turing Machine ，它建模了用户兴趣漂移的 multiple channels 。该模型作为 user interest center 的一部分实现，可以对非常长的user behavior序列进行建模。

   • DIN 是第一个在在线广告 CTR prediction 中使用注意力机制的模型。

   • DIEN 使用具有注意力机制的双层 RNN 来捕获不断变化的用户兴趣。它使用所计算出的 attention values 来控制第二个 recurrent layer ，称为 AUGRU 。

   • UBR4CTR 是我们提出的框架和模型。

1.3.1 性能比较：RQ1

1. 我们对 UBR4CTR 和基线模型进行了两组比较。

   • 在第一组实验中，所有模型都使用相同数量的user behavior，对三个数据集分别为 20 、20 、12 。唯一的区别是：baselines 使用的是最近的behavior（约占总长度的 20% ），而 UBR4CTR 从整个序列中检索了 20% 的behavior。实验结果如 Table 3 所示。

     从表中，我们可以发现以下事实：

     • (i)：与 baseline 相比，UBR4CTR 的性能显著提高。在三个数据集上 AUC 分别提高了 4.1%、10.9% 和 22.3%，Logloss 分别改善了 9.0%、12.0% 和 32.3%。

     • (ii)：巨大的改进表明最近的behaviors没有包含足够的时间模式（temporal patterns ），因此 baselines 无法有效地捕获它们。尽管有些 baselines 模型相当复杂和 fancy ，但如果它们试图捕获的模式不包含在最近的行为序列中，它们就无法很好地发挥作用。

     根据 MIMN 论文的报告，MIMN 的效果是优于 DIEN 的。这里 MIMN 效果反而更差，因为这里对 MIMN 近使用最近的 20 个 behaviors ，而没有用所有的 behaviors 。这是不公平的比较。

     

   • 在第二组实验中，我们对 baselines 模型使用不同的设置，对 UBR4CTR 的设置与第一组实验完全相同。我们将整个序列馈入到所有的 baseline 模型，其中这三个数据集的序列长度分别为 100、100、60 。它们是这些数据集中user behavior的最大长度。对于 UBR4CTR ，检索到的behavior大小保持不变，分别为 20、20 和12 。

     结果如 Table 4 所示。在 Table 4 中，UBR4CTR 的性能与 Table 3 中相同，因为我们没有更改任何设置。从表中，我们可以发现以下事实：

     • (i)：UBR4CTR 使用的behavior比其他 baselines 少 80% ，但仍然具有最佳性能。这表明较长的序列可能包含更多噪音和不相关信息，因此有必要从整个序列中仅获取最有用的数据。

     • (ii)：与 Table 3 相比，大多数 baselines 都取得了比其自身更好的性能，尤其是 DIN 和 DIEN 。这表明来自更远历史的behavior确实包含更丰富的信息和模式。并且这些模式更容易通过 attention 机制被捕获。

     • (iii) ：虽然由于性能更好的 baselines 导致 AUC 的改进要小得多，但 Logloss 仍然有显著改善。原因是 retrieval module 的优化目标为 RIG （相当于对数损失）。

       retrieval module 的优化目标会影响最终模型的指标。

     

1.3.2 学习过程：RQ2

1. 为了说明我们框架的收敛性，我们绘制了 UBR4CTR 的 learning curves。在 Figure 6 中，

   • 上面的三个子图分别是在三个数据集上训练时 attentive prediction network 的 AUC 曲线。x 轴的每个 step 对应于超过 4% 的训练集的迭代。

   • 下面的三个子图显示了 REINFORCE 算法相对于检索模块的 feature selection model 的 “奖励”。“奖励”本质上是 RIG ，它是对数似然的一种变体。x 轴的每个 step 表示超过 4% 的训练集的迭代。在训练过程中，奖励会增加，这意味着 feature selection model 实际上学习了有用的模式。

   从 AUC 图中，我们可以发现我们的模型有效地收敛了。对于 prediction network ，我们可以观察到在训练过程的中间有平坦区域，然后快速增加，尤其是在第二和第三个 AUC 图中。回想一下我们在 Algorithm 1 中描述的训练过程，检索模块是在 prediction network 之后训练的。这意味着当 prediction network 即将收敛时，检索模块开始训练，之后 prediction network 的性能将有所突破。

   

1.3.3 广泛研究：RQ3

1. 在本节中，我们对我们的框架进行了一些广泛的和消融的研究。

   采样的特征数量 $n$$n$ 、采样的 query 数量 $L$$L$ ，作者都没有进行消融分析。

2. Figure 7 说明了不同 retrieval sizes 对预测性能的影响。从图中可以看出，AUC 和 Logloss 的波动在绝对值方面并不是很严重。然而，每个数据集都存在一个最佳大小。这表明：

   • 太少的 retrieved behaviors 可能未包含足够的behavior和信息。

   • 而太多的 retrieved behaviors 也不总是提高性能，因为它会引入太多噪音。

   

3. 为了说明我们框架的检索模块的重要性，我们绘制了 sum pooling model 和 attention network ，分别在具备和不具备 user behaviors retrieval 的情况下的性能比较。 sum pooling model 只是对user behavior做了一个非常简单的 sum 池化操作。结果如 Figure 8 所示。从图中我们发现：

   • 没有检索的 sum 池化模型（SP ）表现很差。一旦配备了检索模块，它的性能就会显著提高（UBR_SP ）。

   • 同样的现象也适用于注意力网络，当配备了 behavior retrieval module 时，其性能会大大提高（ATT vs. UBR4CTR ）。

   

1.4 部署

1. UBR4CTR 已在某主流银行旗下的 daily item recommendation 平台的 engineering schedule 中部署。本节主要讨论 UBR4CTR 框架在工业应用中的可行性。

   • 首先，将目前的模型流程切换到 UBR4CTR 并不困难，因为 UBR4CTR 带来的主要变化是如何获取历史user behavior。要将 model pipeline 更新为 UBR4CTR ，需要构建历史user behavior的一个搜索引擎，而整个 CTR prediction model pipeline 基本保持不变，但增加了一个额外的检索模块。如 Figure 2 所示，prediction module 与传统解决方案的 prediction module 并无不同。

     

   • 效率是工业应用中的另一个重要关注点。我们在 ”模型分析“ 章节中分析了 UBR4CTR 的时间复杂度，为$O(T+K_q\times \mathcal{N}/F)$$O(T+K_q\times \mathcal N/F )$ 。对于大多数基于 RNN 的 sequential CTR models ，它们的时间复杂度为 $O(\mathcal{C}\times T)$$O(\mathcal C\times T)$，其中 $T$$T$ 是用户序列的平均长度，$\mathcal{C}$$\mathcal C$ 是一次操作（例如 GRU rolling ）的成本。UBR4CTR 的时间复杂度并非完全不可行，因为 $F$$F$ 是一个大数，因此 $\mathcal{N}/F$$\mathcal N/F$ 非常接近常数。

   • 从系统负载的角度来看，UBR4CTR 更好，因为它不需要在内存中维护所有 $T$$T$ 个behavior。为维护所有 $T$$T$ 个behavior，这是传统方法的常见做法。

   • 此外，我们在实验中比较了我们的 UBR4CTR 和其他 sequential CTR baselines 之间的实际 inference time 。模型的平均 inference time 如 Figure 9 所示。时间是通过将测试数据集上的总时间（仅包含前向计算和behavior搜索的时间）除以 prediction targets 的数量来计算的。

     从图中可以看出，UBR4CTR 在三个数据集上的推理时间绝对值小于 1ms ，这对于 online serving 来说已经足够高效了。UBR4CTR 的inference time 是所有 sequential CTR models 中最长的，但差距并不大。具体而言，与已在阿里巴巴在线广告平台中部署的 DIEN 相比，UBR4CTR 的平均inference time 大约增加了 15% 到 30% ，可以通过进一步的 infrastructure implementation 来进行优化。