一、UBR [2023] (UBR4CTR V2)

《Learning to Retrieve User Behaviors for Click-through Rate Estimation》

1. CTR estimation 在现代在线个性化服务中起着至关重要的作用。通过建模用户行为序列来捕获用户兴趣的变化，对构建准确的 CTR estimation 模型至关重要。然而，随着用户在在线平台上积累了大量的behavior数据，当前的 CTR 模型必须截断用户行为序列并利用最近的behavior，这导致一个问题，即诸如周期性（periodicity ）或长期依赖性（long-term dependency ）之类的序列模式（sequential patterns ）不被包含在最近的behavior中，而是包含在遥远的历史中。然而，直接使用整个用户序列并对其进行建模并非易事，原因有二：

   • 首先，非常长的输入序列会使在线 inference time 和系统负载变得不可行。

   • 其次，非常长的序列包含很多噪音，因此 CTR 模型很难有效地捕获有用的模式。

   为了解决这个问题，我们从 input data 的角度来考虑它，而不是设计更精巧但更复杂的模型。由于整个用户行为序列包含很多噪音，因此没有必要输入整个序列。相反，我们可以只检索其中的一小部分作为 CTR 模型的输入。在本文中，我们提出了用户行为检索（User Behavior Retrieval: UBR ）框架，旨在根据每个 CTR estimation request 来学习从而检索最 informative 的user behavior。只检索一小部分behavior可以缓解 utilizing very long sequences 的两个问题（即推理效率和噪声输入）。UBR 的显著特性在于它支持任意且可学习的检索函数，而不是使用固定的且预定义的函数，这与当前 retrieval-based 的方法不同。

   在三个大型真实数据集上的离线评估证明了 UBR 框架的优越性和有效性。我们进一步在 Huawei App Store部署了 UBR，在线 A/B test 中实现了 6.6% 的 eCPM 增益，现在服务于 Huawei App Store 广告场景的主要流量。

2. CTR estimation 在当今的在线个性化平台（例如电商、在线广告、推荐系统）中起着关键作用，其目标是预测用户在特定上下文中点击特定 item 的概率。近年来，基于用户行为序列的 CTR estimation 模型引起了工业界和学术界越来越多的关注。这些基于user behavior的 CTR 模型旨在捕获包含在user behavior中的丰富的时间模式（temporal patterns ），并学习用户兴趣的变化，从而获得准确的 CTR estimations 。这些序列模式包括概念漂移（concept drifting ）、长期行为依赖性（long-term behavior dependency）、周期性模式（periodic patterns ）等等。

   Deep Interest Network: DIN 和 Deep Interest Evolution Network: DIEN 是在 CTR prediction 中，通过建模用户行为序列从而捕获用户兴趣的代表性模型。 DIN 结合了注意力机制来学习不同 user behaviors 的重要性，而 DIEN 利用 GRU 来捕获user behavior的 dynamics 。其他 user behavior-based 的 CTR estimation 模型（《Behavior sequence transformer for e-commerce recommendation in alibaba》、《Deep session interest network for click-through rate prediction》）具有相似的动机和结构。

   至于 CTR estimation 的类似文献，在序列推荐（sequential recommendation ）领域，有很多关于如何对用户行为序列进行建模的研究工作。有 RNN-based 的模型，如 GRU4Rec、GRU4Rec+ ；有 CNN-based 的模型，如 CaseR ；有 Transformer-based 的模型，如 SASRec、TiSASRec ；还有 memory network-based 的模型。

   随着在线个性化平台十多年的发展，平台上记录的user behavior数量迅速增长。在淘宝上，仅在六个月内，就有 23% 的用户积累了超过 1,000 次behavior（《Lifelong sequential modeling with personalized memorization for user response prediction》）。尽管上述基于user behavior的 CTR 模型取得了巨大成功，但它们无法处理非常长的用户序列。如 Figure 1 上半部分所示，仅使用最近的行为进行 CTR estimation （通常为 50 或 100）。但是，如果仅使用最近的行为，序列中可能不包含长期依赖性或周期性等序列模式（sequential patterns ）。一种直接的解决方案是将整个用户序列馈入到 CTR 模型中，但这不可行。它会给系统开销带来沉重的负担并牺牲推理效率。更糟糕的是，在非常长的行为序列中，这种做法会带来很多噪音。

   为了解决上述问题，一种解决方案是设计具有更多参数和更大容量的复杂模型，以支持更长的用户行为序列作为输入，如 Figure 1 上半部分所示。HPMN 和 MIMN 是两种用于处理长序列建模的 memory network 架构。然而，这些模型非常复杂，需要大量的工程工作才能在现实世界的在线系统中实现和部署。尽管 HPMN 或 MIMN 可以处理包含大约 1,000 个behavior的序列，但全量的用户序列通常要长得多。

   

   与上述解决方案不同，我们尝试从数据角度解决问题，而不是设计更精巧但更复杂的模型。由于非常长的序列包含很多噪音，因此没有必要输入整个序列。相反，只有一小部分behavior与 prediction 相关。因此，我们只需要检索相关的behavior。检索到的behavior取决于每个 CTR estimation request 。我们将每个 request 称为 prediction target 。如 Figure 1 所示，prediction target 由三部分组成，即 target user features （职业、地理位置等）、target item features （category 、品牌等）、以及相应的上下文特征（场景等）。然后，这些特征将被视为 query ，并被用于从整个用户序列中检索 behaviors 。检索系统的目标是学习检索最相关的 behavior data ，从而辅助特定的 request 的 prediction （即 prediction target ）。这样的检索过程利用索引结构，以整个用户历史行为作为检索池（retrieval pool ），效率很高。为此，通过检索user behavior，长的用户序列可以有效地纳入 CTR 模型，而不会引入太多噪音。

   在本文中，我们提出了用于 CTR estimation 的 User Behavior Retrieval: UBR 框架，从而对非常长的用户行为序列进行建模。由于现实世界在线个性化平台中的检索池通常很大，我们将检索过程分为两个子过程：matching 和 ranking ，类似于信息检索系统。

   • 对于matching 过程，通过访问存储 behaviors 的索引可以快速检索一组候选behavior。此过程本质上是获取具有与 prediction target 所匹配特征的 behaviors 。

   • 获得 candidate behaviors 后，ranking 函数根据 candidate behaviors 与 prediction target 的相关性对其进行排序，并返回 top-k 个behavior。

   然后，被检索到的 behaviors 可以被任意 CTR 模型使用。

   本文的重点是整合可学习的参数化的检索函数，并提出相应的训练方法。在现有的 retrieval-based behavior models 中，检索函数总是采用某种预定义形式，例如特征匹配（《Retrieval and interaction machine for tabular data prediction》）、内积 （《Search-based user interest modeling with lifelong sequential behavior data for click-through rate prediction》）、余弦相似度（《Learn over past, evolve for future: Search-based time-aware recommendation with sequential behavior data》）或汉明距离（《End-to-end user behavior retrieval in click-through Rate Prediction model》）。检索函数是固定的，因此它们不够灵活；并且由于其 pre-defined form 所引入的 inductive bias ，可能导致次优性能。相反，在 UBR 框架中，我们使用 prediction 的性能作为信号来训练检索函数。behavior retrieval 过程本质上是获取相对于 prediction target （即 CTR request ）的 top-ranked behaviors 。使用参数化的结构（例如 DNN ）作为 ranking metric 可以大大提高检索函数的容量和表达能力。为实现该目标，我们提出了三种 UBR 变体：

   • UBR-M 利用 REINFORCE 来优化 retrieval function 的 matching 过程。

   • UBR-R 使用 learning-to-rank: LTR 技术来优化 retrieval function 中的 ranking 过程。

   • UBR-MR 是上述变体的混合版本，其中matching 和 ranking 过程都得到了优化。

   通过比较这些变体，我们得到了一些有趣的观察结果和有意义的见解，指导我们在实践中选择最佳变体。详细信息可参见实验章节。

   本文的贡献可以总结如下：

   • 对于长行为序列的建模，我们从数据角度提供了一种新的解决方案，即从整个用户序列中检索user behavior。这是一个实用的解决方案，它使当前的 CTR 系统在受到严格的效率约束的情况下能够使用整个用户序列。

   • 我们系统地数学化了 learning to retrieve user behaviors 的问题，并提出了一个有效的模型和相应的训练算法。UBR 是第一个支持可学习的任意检索函数（而不是预定义的检索函数）的工作。

   • 我们提出了更强大的变体：UBR-R 和 UBR-MR 。它们采用了由 LTR 技术优化的可学习的 ranking 函数。我们进一步证明 LTR optimization 函数可以引导 optimization 方向，从而获得更准确的 CTR estimation 模型。它为我们的优化算法提供了理论保证。

   • UBR 有效且易于部署。离线实验表明，它达到了 SOTA 的性能。此外，UBR 已成功部署在 Huawei App Store 的广告场景中。在线 A/B test 期间，它实现了 6.6% 的平均 effective cost per mille: eCPM （有效的每千次展示费用）的提升率。它现在服务于 Huawei App Store 的主要广告流量。

3. 本文是其会议版本 《User behavior retrieval for click-through rate prediction》 （即，UBR4CTR）的实质性扩展。期刊版本（本文）和会议文章（即 UBR4CTR）之间的主要区别在于：

   • 在本文中，我们提出 UBR-R 和 UBR-MR 作为 UBR 框架的更好实现，而不是会议文章中提出的框架（表示为 UBR-M ）。新版本加入了可学习的 ranking 函数，使检索模块更加强大。

   • 我们提出了一个 LTR optimization objective 来训练参数化的 ranking 函数，而不是会议文章中使用的 REINFORCE 算法。我们进一步对 LTR objective function 进行了广泛的理论分析。

   • 我们提供了与一些 retrieval-based 序列建模算法的比较实验的结果，这些算法比我们的会议文章更晚被提出。

   • UBR 已在实际应用中部署，而我们在会议版本中仅对公共数据集进行了实验。在工业数据集上进行的新实验验证了 UBR 可以与各种 CTR 模型结合使用。我们进一步提供了在线实验细节。这些事实表明，UBR 在实际应用中部署是高度可行的。

4. 未来工作：对于未来的工作，我们的目标是将 UBR 扩展为一个更通用的框架，不仅可以从单个用户那里检索，还可以从其他相似的用户那里检索。当前的 UBR 框架仅从 target user 自身的 behaviors 中检索。来自其他相似用户或 items 的协同过滤信息可能会进一步提高 UBR 的性能。在这种情况下优化其效率是另一个重要方向。

1.1 基础知识

1. 在本节中，我们将问题公式化并引入符号。对于 CTR estimation 任务，有 $M$$M$ 个用户构成的用户集 $\mathcal{U}=\{u_1,\cdots ,u_M\}$$\mathcal U = \{u_1,\cdots,u_M\}$、$N$$N$ 个 item 构成的 item 集 $\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 都与相应的上下文一起发生。我们分别使用 $ts$$ts$ 和 $c$$c$ 分别表示 timestamp 和其他的上下文特征。因此，每个数据点被公式化为 $\{u,v,c,ts,y_{u,v}\}$$\{u,v,c,ts,y_{u,v}\}$，表示在某个时刻 $t_s$$t_s$ ，用户 $u$$u$ 是否在上下文 $c$$c$ 中点击 item $v$$v$ 。

2. $u$$u$ 、$v$$v$ 和 $c$$c$ 由 multi-field features 组成，其中 $\mathbf{u}=[f_1^u,\cdots ,f_{K_u}^u]$$\mathbf u=\left[f_1^u,\cdots,f_{K_u}^u\right]$ 、$\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]$，其中：

   • $f_p^u,f_p^v,f_p^c$$f_p^u, f_p^v, f_p^c$ 分别表示用户、item 、以及上下文的第 $p$$p$ 个特征。

   • $K_u,K_v,K_c$$K_u ,K_v, K_c$ 分别表示用户、item 、以及上下文的 feature fields 的数量。

3. 为了建模用户不断变化的兴趣，我们将整个user behavior历史组织为 $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$ 表示用户的第 $i$$i$ 个behavior，按 timestamp 升序排序。用户 $u$$u$ 的behavior $b_i^u$$b_i^u$ 由 $u$$u$ 点击过的 item $v_i^u$$v_i^u$ 、以及对应的上下文 $c_i^u$$c_i^u$ 组成，即 $b_i^u=[v_i^u,c_i^u]$$b_i^u=\left[v_i^u,c_i^u\right]$。

   注意，在 UBR4CTR 中，$b_i^u=[u,v_i,c_i]$$b_i^u=[ u,v_i,c_i]$，包含了用户特征。

   CTR estimation 的目标是根据 target user $u$$u$ 在上下文 $c$$c$ 中的历史行为，预测 $u$$u$ 点击 target item $v$$v$ 的概率。它可以表示为：

   $${\hat{y}}_{u,v}={\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid H_u)$$

   其中：${\mathcal{F}}_{\mathrm{\Theta }}$$\mathcal F_\Theta$ 是带有参数 $\mathrm{\Theta }$$\Theta$ 的所学到的函数。 在实践中，广泛使用的框架是：利用 $H_u$$H_u$ 最近的 $k$$k$ 个连续behavior作为 prediction 函数 ${\mathcal{F}}_{\mathrm{\Theta }}$$\mathcal F_\Theta$ 的输入。因为整个用户行为序列 $H_u$$H_u$ 可能很长而且是 noisy 的。它表示为：

   $${\hat{y}}_{u,v}={\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid \mathcal{R}(H_u))$$

   其中：$\mathcal{R}(\cdot )$$\mathcal R(\cdot)$ 是一个固定的retrieval 函数，返回 $H_u$$H_u$ 的最近的 $k$$k$ 个behavior。

   无论 $v$$v$ 和 $c$$c$ 如何，retrieval 函数 $R(\cdot )$$R(\cdot)$ 返回完全相同的 set of user behaviors 。相比之下，对于我们的 UBR 框架，CTR estimation 任务的公式为

   $${\hat{y}}_{u,v}={\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid {\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c))$$

   其中：${\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c)$$\mathcal R_\Phi(H_u\mid v,c)$ 是一个可学习的 retrieval 函数，可以在给定 target item $v$$v$ 和上下文 $c$$c$ 的情况下从 $H_u$$H_u$ 中检索 informative 的user behavior（注意， target user $u$$u$ 通过 $H_u$$H_u$ 来给定了）。因此，UBR 能够根据不同的 target items 或上下文从而动态选择最合适的user behavior，而不是像以前的工作那样使用静态和固定的 selection 策略。

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

   

1.2 Behavior Retrieval 系统的架构

1. 在本节中，我们介绍了 UBR 框架的基本架构。本节介绍的检索过程是 UBR 的 basic 实现，是不可学习的。但它构成了系统的骨干。一些模块可以用参数化的组件替换，从而自动优化 UBR 。可学习的组件的详细信息将在下一个章节中描述。

1.2.1 UBR 的总体框架

1. 如 Figure 2 所示，UBR 由 retrieval 模块和 prediction 模块组成。

   • 顾名思义，retrieval 模块负责根据 prediction target 从 user history archive 中检索 behaviors 。 prediction target 由 CTR prediction request 中的 user, item, and context features 组成。prediction target 被用作 query 从而从 user history archive 中执行搜索。

   • retrieval engine 检索出一部分 behaviors ，这些被检索到的 behaviors 被馈入到 prediction 模块。prediction 模块由两部分组成。

     • 第一部分是 aggregation 网络，它将学习 retrieved behaviors 的一个 unified representation 。该 aggregated representation 可以与其他特征组合起来并输入到任意 CTR 模型中，

     • 第二部分是这个CTR 模型。由于 CTR 模型可以是任意结构，因此 UBR 具有很高的灵活性，可以与现有的 CTR estimation 系统一起部署。

   

2. 由于检索 user behaviors 类似于检索 recommender system literature 的 items ，我们使用 matching and ranking 来划分整个检索过程。

   • matching 子模块通过访问索引结构从而快速获取 candidate behavior 的一个集合。

   • 然后，接下来的 ranking 子模块将计算每个behavior的分数，从而返回 top-k behaviors。

1.2.2 Matching 子模块

1. matching 子模块的目的是：通过快速获取 candidates 的一个小集合，从而来降低计算复杂度。为了实现此目的，我们选择将其实现为 index accessing 过程。

2. 倒排索引（Inverted Index）：作为典型的搜索引擎系统，我们将每个 user behavior 视为一个文档，将每个特征视为一个 term 。 user behavior 以倒排索引的方式存储。如 Figure 3 所示，我们以一条 behavior 记录 $b_1^u$$b_1^u$ 为例，展示倒排索引的构建过程。$b_1^u$$b_1^u$ 有五个特征：user id, category id, brand id, purchase day, and item price 。在特征工程过程中，原始特征全部重新映射到 unique id 。numerical 特征被离散化，然后重新映射。user id （“ID-1” ）用作第一个索引，因为我们需要获取用户$u$$u$ 自己的 behaviors，而其他 remapped features 则以倒排索引的方式作为第二个索引。behavior $b_1^u$$b_1^u$ 被视为一个文档，并附加到相应的 posting lists 中。我们对每条behavior record遵循相同的协议并构建倒排索引。

   即，两层索引结构：最外层是 user-id，这一层索引将保存每个用户的所有行为。第二层是不同的 field，给定用户的不同 behavior 将根据特征取值的不同放入不同的索引。

   

3. query：prediction target $(u,v,c)$$(u,v,c)$ 被用作 query。retrieval 的 query $q$$q$ 表示为：

   $$q=\underset{v}{\underbrace{f_1^v\text{ OR }\cdots \text{ OR }{f}_{K_v}^v}},\underset{c}{\underbrace{f_1^c\text{ OR }\cdots \text{ OR }{f}_{K_c}^c}}=f_1\text{ OR }{f}_2\text{ OR }\cdots \text{ OR }{f}_n$$

   其中：$n=K_v+K_c$$n = K_v + K_c$ 。

   注意，这里不包含用户特征 $f_1^u,\cdots ,f_{K_u}^u$$f_1^u,\cdots, f_{K_u}^u$ 。但是，UBR4CTR 中包含了用户特征 $f_2^u,\cdots ,f_{K_u}^u$$f_2^u,\cdots, f_{K_u}^u$，但是不包含 user-id 特征 $f_1^u$$f_1^u$ 。

   matching 子模块本质上是一个特征匹配的布尔搜索过程。用户 $u$$u$ 在 $H_u$$H_u$ 中所有包含特征 $f_i\in q$$f_i\in q$ 的behaviors都将被检索出来。

1.2.3 Ranking 子模块

1. 从 matching 子模块获取 candidate behaviors后，我们执行 ranking 程序，从而返回 top-k 结果作为 final retrieved behaviors 。我们使用 BM25 来计算每个behavior的得分，因为它是搜索引擎系统中广泛使用的 ranking 函数。

   每个behavior $b_i^u$$b_i^u$ 都被视为一个文档，因此给定query $q$$q$ 的情况下 $b_i^u$$b_i^u$ 的 ranking score 定义为：

   $$s(b_i^u,q)=\sum _{f_j\in q}\text{IDF}(f_j)\times \frac{\text{TF}(f_j,b_i^u)\times (k_1+1)}{\text{TF}(f_j,b_i^u)+k_1\times (1-b+b\times \frac{|b_i^u|}{\text{avgdl}})}$$

   其中：

   • $\text{TF}(f_j,b_i^u)$$\text{TF}\left(f_j, b_i^u\right)$ 是特征 $f_j$$f_j$ 在 $b_i^u$$b_i^u$ 中的词频（term frequency ）。根据 $b_i^u$$b_i^u$ 中是否有 $f_j$$f_j$ 的match ，其取值为 1 或 0 。

   • behavior $b_i^u$$b_i^u$ 的长度定义为该 behavior中的特征数量，因此所有behavior都具有相同的长度 $n$$n$，$n=K_v+K_c$$n=K_v+K_c$ 。因此 $\frac{|b_i^u|}{\text{avgdl}}=1$$\frac{|b_i^u|}{\text{avgdl}} = 1$，其中 avgdl 代表平均的文档长度。

     可以进一步化简为： $s(b_i^u,q)=\sum _{f_j\in q}\text{IDF}(f_j)\times \frac{\text{TF}(f_j,b_i^u)\times (k_1+1)}{\text{TF}(f_j,b_i^u)+k_1}$$s\left(b_i^u,q\right) = \sum_{f_j\in q}\text{IDF}(f_j)\times \frac{\text{TF}\left(f_j, b_i^u\right)\times (k_1 + 1)}{\text{TF}\left(f_j, b_i^u\right) + k_1}$ 。似乎 $b$$b$ 参数没什么用？

     考虑到 $\text{TF}(f_j,b_i^u)$$\text{TF}(f_j,b_i^u)$ 取值为 0 或 1 ，因此：

     $$\begin{array}{c}\frac{\text{TF}(f_j,b_i^u)\times (k_1+1)}{\text{TF}(f_j,b_i^u)+k_1}=\{\begin{array}{ll}0& \text{if }\text{TF}(f_j,b_i^u)=0\\ 1& \text{else}\end{array}\end{array}$$

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

   • $k_1$$k_1$ 和 $b$$b$ 是自由参数。

   • IDF 定义为：

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

     其中：$\mathcal{N}$$\mathcal N$ 是所有用户的所有 behaviors 的总数，$\mathcal{N}(f_j)$$\mathcal N(f_j)$ 是包含特征 $f_j$$f_j$ 的文档的数量。

     IDF 项赋予常见特征比罕见特征更少的重要性。与常见特征相比，罕见特征意味着对用户偏好的更强信号，这是有道理的。

   top-k behaviors 构成 retrieval set ，即 ${\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid q)={\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c)=\{b_1^u,\cdots ,b_k^u\}$$\mathcal R_\Phi(H_u\mid q) = \mathcal R_\Phi(H_u\mid v,c) = \left\{b_1^u,\cdots,b_k^u\right\}$。这里 $\mathrm{\Phi }=\mathrm{\varnothing }$$\Phi = \empty$，因为它是一个固定的检索函数。 retrieval set 被下游 prediction 模块使用，如 Figure 2 所示。

   

1.2.4 Prediction 模块

1. 在本节中，我们介绍 UBR 的 prediction 模块。在 prediction 模块中，所检索到的 user behaviors被聚合起来，相应的 representation 与其他特征一起馈入到 CTR 模型中，如 Figure 2 所示。UBR 框架具有高度灵活性，因为它可以与任意 CTR prediction 模型一起使用，因此可以方便地部署到实际应用中。

2. Retrieved Behaviors 的聚合：为了聚合 retrieved behaviors 并获得全面的 representation ，我们使用注意力机制来聚合behavior representations ：

   $${\overrightarrow{\mathbf{r}}}^u=\sum _{i=1}^k{\alpha }_i\times {\overrightarrow{\mathbf{b}}}_i^u,{\overrightarrow{\mathbf{b}}}_i^u\in {\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c)$$

   其中：

   • ${\overrightarrow{\mathbf{r}}}^u$$\mathbf{\vec r}^u$ 是 aggregated behavior representation 。

   • ${\overrightarrow{\mathbf{b}}}_i^u=[{\overrightarrow{\mathbf{f}}}_1^v||\cdots ||{\overrightarrow{\mathbf{f}}}_{K_v}^v||{\overrightarrow{\mathbf{f}}}_1^c||\cdots ||{\overrightarrow{\mathbf{f}}}_{K_c}^c]\in {\mathbb{R}}^{d\times (K_v+K_c)}$$\mathbf{\vec b}_i^u = \left[\mathbf{\vec f}_1^v||\cdots||\mathbf{\vec f}_{K_v}^v||\mathbf{\vec f}_1^c||\cdots||\mathbf{\vec f}_{K_c}^c\right]\in \mathbb R^{d\times (K_v+K_c)}$ 为第 $i$$i$ 个 retrieved behavior 的 embedding， $d$$d$ 为特征的 embedding size ，$\cdot ||\cdot$$\cdot||\cdot$ 为向量拼接。

     注意：在 UBR4CTR 中，${\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]$ ，包含了用户特征。

   • ${\alpha }_i$$\alpha_i$ 为相应的 attention 权重：

     $${\alpha }_i=\frac{\exp (\tanh \left({\overrightarrow{\mathbf{q}}}^{\mathrm{\top }}\mathbf{W}{\overrightarrow{\mathbf{b}}}_i^u\right))}{\sum _{j=1}^k\exp (\tanh \left({\overrightarrow{\mathbf{q}}}^{\mathrm{\top }}\mathbf{W}{\overrightarrow{\mathbf{b}}}_j^u\right))}$$

     其中：

     • $\mathbf{W}\in {\mathbb{R}}^{d\times d}$$\mathbf W\in \mathbb R^{d\times d}$ 为 attention layer 的权重矩阵。

     • $\overrightarrow{\mathbf{q}}\in {\mathbb{R}}^{d(K_v+K_c)}$$\mathbf{\vec q}\in \mathbb R^{d(K_v+K_c)}$ 为 query $q$$q$ 的 dense embedding ，它是 feature embeddings 的拼接。

       注意：在 UBR4CTR 中，$\overrightarrow{\mathbf{q}}\in {\mathbb{R}}^{d(K_u+K_v+K_c)}$$\mathbf{\vec q} \in \mathbb R^{d(K_u+K_v+K_c)}$ ，包含了用户特征。

   aggregated retrieved behaviors 的 comprehensive representation ${\overrightarrow{\mathbf{r}}}^u$$\mathbf{\vec r}^u$ 与 prediction target 的其他特征一起输入到 CTR 模型中。

3. CTR Estimation Model ：UBR 可以配备任意的 CTR estimation 模型。在这里我们使用一个简单的 DNN 结构作为 CTR 模型，在实验章节，我们还基于其他工业级的 CTR 模型测试了性能。final prediction 的计算方式为：

   $${\hat{y}}_{u,v}={\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid {\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c))={\text{MLP}}_{\mathrm{\Theta }}({\overrightarrow{\mathbf{r}}}^u,\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}})$$

   其中：

   • $\overrightarrow{\mathbf{u}},\overrightarrow{\mathbf{v}},\overrightarrow{\mathbf{c}}$$\mathbf{\vec u},\mathbf{\vec v},\mathbf{\vec c}$ 分别是 user embedding、item embedding、context embedding 。

   • ${\overrightarrow{\mathbf{r}}}^u$$\mathbf{\vec r}^u$ 为 behavioral representation ，$\mathrm{\Theta }$$\Theta$ 为 MLP 的参数。

   由于我们的目标是准确地估计 CTR ，因此 prediction loss 的自然选择是广泛使用的交叉熵损失。带 L2 范数的 prediction loss 定义为：

   $$\begin{array}{c}{\mathcal{L}}_{\mathrm{\Theta }}={\mathcal{L}}_{\text{ce}}+{\mathcal{L}}_r\\ =-\sum _{(u,v,c)\in {\mathcal{D}}_{\text{tr}}}[y_{u,v}\times \log \left({\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid B^u)\right)+(1-y_{u,v})\times \log (1-{\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid B^u))]+\frac{1}{2}\lambda ||\mathrm{\Theta }|{|}_2^2\end{array}$$

   其中：

   • $\mathrm{\Theta }$$\Theta$ 包含 prediction 模块的所有参数，包括 CTR estimation 模型中的参数、以及 aggregation 函数中的参数。

   • ${\mathcal{D}}_{\text{tr}}$$\mathcal D_\text{tr}$ 是训练集。

   • $B^u={\mathcal{R}}_{\mathrm{\Phi }}(H_u\mid v,c)$$B^u = \mathcal R_\Phi(H_u\mid v,c)$ 是 retrieved behaviors。在优化 prediction 模块时，retrieval 模块是固定的。

   prediction 模块通过使用 SGD 来最小化 ${\mathcal{L}}_{\mathrm{\Theta }}$$\mathcal L_\Theta$ 从而被优化。

1.3 可学习的 Retrieval System

1. 在本节中，我们介绍如何使 retrieval system 成为参数化的和可学习的。我们提出了三种可学习的 UBR变体：UBR-M、UBR-R 和 UBR-MR。

   • UBR-M 和UBR-R ，顾名思义，是将 matching/ranking 过程分别转换为一个 parametric and learnable function 。

   • UBR-MR ，是同时优化 matching和 ranking 子模块的混合版本。

   可学习的 UBR 变体与 prediction 模块一起训练。在训练 retrieval 模块时，prediction模块是固定的，反之亦然。

2. 我们将首先为可学习的 retrieval system 公式化 optimization 问题，然后给出 UBR 变体及其相应 optimization 的实现细节。

1.3.1 Retrieval 模块的优化目标

1. 首先，我们为 retrieved behavior set 定义一个效用（utility ）。它表示一个 behavior set 有多 “有用”。

2. Utility 的定义：behavior set $B^u$$B^u$ 的效用是一个非正的标量（non-positive scalar ），可以反映 prediction 模块使用 $B^u$$B^u$ 作为输入时 CTR estimation 的准确性。在实现上，我们使用 negative log-likelihood 的倒数作为效用函数，即：

   $$U\left(B^u\right)=\frac{1}{\mathcal{L}(y_{u,v},{\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid B^u))}$$

   其中：$\mathcal{L}(y_{u,v},{\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid B^u))$$\mathcal L\left(y_{u,v}, \mathcal F_\Theta\left(u,v,c\mid B^u\right)\right)$ 为负的对数似然。

   效用越高， CTR 模型使用集合 $B^u$$B^u$ 时的预测性能越好。

3. retrieval 模块的 general objective 公式化为：

   $$\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}=\underset{\mathrm{\Phi }}{max}\sum _{q\in {\mathcal{D}}_{\text{tr}}}{\mathbb{E}}_{B^u\sim {\pi }_{\mathrm{\Phi }}(B^u\mid q)}U\left(B^u\right)$$

   其中：${\pi }_{\mathrm{\Phi }}(B^u\mid q)$$\pi_\Phi\left(B^u\mid q\right)$ 是生成 retrieved behaviors 的底层概率分布。

   令 ${\mathcal{J}}_{\mathrm{\Phi }}^q={\mathbb{E}}_{B^u\sim {\pi }_{\mathrm{\Phi }}(B^u\mid q)}U\left(B^u\right)$$\mathcal J_\Phi^q = \mathbb E_{B^u\sim \pi_\Phi\left(B^u\mid q\right)} U\left(B^u\right)$，因此 ${\mathcal{J}}_{\mathrm{\Phi }}=\sum _q{\mathcal{J}}_{\mathrm{\Phi }}^q$$\mathcal J_\Phi = \sum_q \mathcal J_\Phi^q$ 。 目标函数 ${\mathcal{J}}_{\mathrm{\Phi }}$$\mathcal J_\Phi$ 的 optimization 旨在找到最好的 retrieval 函数，从而能够最大化 CTR 模型的期望准确率。在以下小节中，我们将介绍 UBR 的不同变体及其相应的 optimizations 。

1.3.2 Matching 子模块的优化：UBR-M

1. 可学习的 UBR 的第一个变体是 UBR-M ，它提出了一个可学习的 matching 函数。

2. UBR-M 的结构：为了将 matching 过程变成一个可学习的子模块，我们选择将 query generation 参数化为一个可学习的 feature selection 过程。它将从 query $q$$q$ 中选择特征，所选中的特征用于 match the behaviors ，而不是 $q$$q$ 的所有特征。 如 Figure 4 所示，我们使用 self-attention network 来建模特征之间的交互和关系。具体来说，我们定义：

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

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

   自注意力机制定义为：

   $$\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\\ {\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}}^{n\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}}^{n\times 1}\end{array}$$

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

   然后我们根据这些概率对特征进行采样，从而得到所选的特征子集。

   原来有 $n$$n$ 个特征，那么采样后有多少个特征？作者没说。

   总而言之，UBR-M 使用 self-attentive feature selection function 来参数化 matching 子模块。至于 ranking ，UBR-M 仍然使用 BM25 ranking function 。

   

3. UBR-M Optimization ：由于上述 feature selection 函数通过使用概率来采样，从而涉及不确定性并且不可微，我们可以直接通过 REINFORCE （《Simple statistical gradient-following algorithms for connectionist reinforcement learning》）算法优化 $\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}$$\max_\Phi\mathcal J_\Phi$ 。

   我们给出了 $J_{\mathrm{\Phi }}^q$$J_\Phi^q$ 的梯度。retrieved behaviors 的概率 ${\pi }_{\mathrm{\Phi }}(B^u\mid q)$$\pi_\Phi\left(B^u\mid q\right)$ 可以视为一种策略，梯度可以用似然比（likelihood ratio ）来估计，如下所示：

   $$\begin{array}{c}{\mathrm{\nabla }}_{\mathrm{\Phi }}\left({\mathcal{J}}^q\right)={\mathrm{\nabla }}_{\mathrm{\Phi }}{\mathbb{E}}_{B^u\sim {\pi }_{\mathrm{\Phi }}(B^u\mid q)}U\left(B^u\right)\\ =\sum _{B_i^u\in {\mathcal{B}}_q}{\mathrm{\nabla }}_{\mathrm{\Phi }}{\pi }_{\mathrm{\Phi }}(B_i^u\mid q)U\left(B_i^u\right)\\ =\sum _{B_i^u\in {\mathcal{B}}_q}{\pi }_{\mathrm{\Phi }}(B_i^u\mid q){\mathrm{\nabla }}_{\mathrm{\Phi }}\log \left({\pi }_{\mathrm{\Phi }}(B_i^u\mid q)\right)U\left(B_i^u\right)\\ ={\mathbb{E}}_{B^u\sim {\pi }_{\mathrm{\Phi }}(B^u\mid q)}{\mathrm{\nabla }}_{\mathrm{\Phi }}\log \left({\pi }_{\mathrm{\Phi }}(B^u\mid q)\right)U\left(B^u\right)\\ \simeq \frac{1}{L}\sum _{l=1}^L{\mathrm{\nabla }}_{\mathrm{\Phi }}\log \left({\pi }_{\mathrm{\Phi }}(B_l^u\mid q)\right)U\left(B_l^u\right)\end{array}$$

   其中：$L$$L$ 为采样的次数；${\mathcal{B}}_q$$\mathcal B_q$ 包含所有可能的 retrieved sets 。

   $\frac{1}{L}\sum _{l=1}^L{\mathrm{\nabla }}_{\mathrm{\Phi }}\log \left({\pi }_{\mathrm{\Phi }}(B_l^u\mid q)\right)U\left(B_l^u\right)$$\frac{1}{L}\sum_{l=1}^L \nabla_\Phi \log \left( \pi_\Phi\left(B_l^u\mid q\right)\right)U\left(B_l^u\right)$ 是 ${\mathrm{\nabla }}_{\mathrm{\Phi }}\left({\mathcal{J}}^q\right)$$\nabla_\Phi\left(\mathcal J^q\right)$ 的无偏估计。由于 UBR-M 的不确定性实际上来自 feature selection model ，我们可以得出：

   $${\pi }_{\mathrm{\Phi }}(B^u\mid q)=\prod _{j=1}^{n}p(f_j{)}^{s_j}\times (1-p(f_j){)}^{(1-s_j)}$$

   其中：

   • $f_j\in \{f_1,\cdots ,f_n\}$$f_j\in \{f_1,\cdots,f_n\}$；$p(f_j)$$p(f_j)$ 为 $\mathbf{P}=\sigma \left(\hat{\mathbf{E}}\right)$$\mathbf P = \sigma\left(\hat{\mathbf E}\right)$ 第 $j$$j$ 个元素，表示采样概率。

   • 当 $f_j$$f_j$ 被选中时 $s_j=1$$s_j = 1$ ，否则 $s_j=0$$s_j = 0$ 。

   因此，我们得到：

   $${\mathrm{\nabla }}_{\mathrm{\Phi }}\left({\mathcal{J}}^q\right)\simeq \frac{1}{L}\sum _{l=1}^L\sum _{j=1}^n{\mathrm{\nabla }}_{\mathrm{\Phi }}[s_j^l\times \log p\left(f_j^l\right)+(1-s_j^l)\times \log (1-p\left(f_j^l\right))]\times U\left(B_l^u\right)$$

   其中：$f_j^l$$f_j^l$ 为第 $l$$l$ 次采样中的第 $j$$j$ 个特征。

   通过使用 REINFORCE 算法，可以在 prediction 模块固定的情况下优化 UBR-M 。

4. UBR-M 是我们在之前的文章 《User behavior retrieval for click-through rate prediction》 中提出的。虽然 UBR-M 提供了参数化的 retrieval 函数的实现，但它仍然是粗粒度的，因为特征对应的 posting list （例如 Figure 3 中的 “T-shirt” list ）的所有 behaviors 可能会被完全删除，并且不会被 prediction 模块使用。此外，UBR-M 的 ranking 模型是固定的 BM25 函数，这可能不是最佳选择。我们希望模型能够自动学习合适的 ranking 函数。

   matching 子模块本质上是为 ranking 子模块缩小候选空间。实验结果表明，优化 ranking 要比优化 matching 取得更好的效果。而优化 matching 的效果一般般。

   mathcing 子模块也可以认为是一种 ranking：将未被匹配的 behaviors 设置 ranking score = 0 。

   

1.3.3 Ranking 子模块的优化：UBR-R

1. UBR 的第二种变体是 UBR-R ，它提出了一个可学习的 ranking 函数。

2. UBR-R 的结构：固定的 ranking 函数不灵活，无法捕获每个 behavior 与 query 之间的复杂关系。因此，我们需要一个可学习的ranking 函数。对于 UBR-R ，我们将 ranking 函数从确定性的 BM25 更改为参数化的函数，同时保留前面章节中描述的固定的 matching 过程。参数化的 ranking 函数定义为：

   $$s(b_i^u,q)={\text{DeepModel}}_{\mathrm{\Phi }}(\overrightarrow{\mathbf{q}},{\overrightarrow{\mathbf{b}}}_i^u)$$

   其中：

   • $s(b_i^u,q)$$s\left(b_i^u, q\right)$ 是给定 $q$$q$ 的条件下，behavior $b_i^u$$b_i^u$ 的 ranking score 。

   • ${\text{DeepModel}}_{\mathrm{\Phi }}$$\text{DeepModel}_\Phi$ 可以实现为具有参数 $\mathrm{\Phi }$$\Phi$ 的任意结构，这里我们选择将其实现为 MLP 。，

3. UBR-R Optimization：由于 getting the top-k behaviors 的操作不可微，所以我们无法直接优化 ranking 函数的参数 $\mathrm{\Phi }$$\Phi$ 。为了解决这个问题，我们将 $\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}$$\max_\Phi\mathcal J_\Phi$ 中定义的期望效用的 optimization 转换为 LTR 问题，并将其用作 UBR-R 的优化函数。因为 LTR 是训练 ranking 函数最广泛的范式。

   作为 LTR 问题，我们要排名的 "items" 本质上是一个包含 $k$$k$ 个 behaviors 的集合。总共有 $C_{N_q}^k$$C_{N_q}^k$ 个集合，其中 $N_q$$N_q$ 是来自 matching 子模块的 behaviors 总数，这意味着我们有 $\{B_1^u,\cdots ,B_{C_{N_q}^k}^u\}$$\{B_1^u,\cdots,B^u_{C_{N_q}^k}\}$ 的 behavior 集合。

   如果我们将每个 behavior set $B_i^u$$B^u_i$ 作为 final retrieved behaviors 并将其输入到 prediction 模块，我们将得到效用 $U\left(B_i^u\right)=\frac{1}{\mathcal{L}(y_{u,v},{\mathcal{F}}_{\mathrm{\Theta }}(u,v,c\mid B_i^u))}$$U\left(B_i^u\right) = \frac{1}{\mathcal L\left(y_{u,v}, \mathcal F_\Theta\left(u,v,c\mid B_i^u\right)\right)}$。如 Figure 5 所示，CTR 模型给出的效用可以看作是 "relevance labels"。ranking 函数 $S_{\mathrm{\Phi }}(B_i^u\mid q)$$S_\Phi\left(B_i^u\mid q\right)$ 旨在根据使用 behavior sets 时的性能从而对 behavior sets 进行排名。

   

4. 在接下来的内容中，我们将分析 $\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}$$\max_\Phi\mathcal J_\Phi$ 的目标函数与LTR 目标函数之间的理论关系。我们证明对 LTR loss 进行优化可以优化方程 $\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}$$\max_\Phi\mathcal J_\Phi$ 。

   • 将原始问题转换为 LTR 任务：我们将 probabilistic choice model 定义为：选择 $B_i^u$$B_i^u$ 的概率 ${\pi }_{\mathrm{\Phi }}(B_i^u\mid q)$$\pi_\Phi\left(B_i^u\mid q\right)$ 与其 ranking score 成正比：

     $${\pi }_{\mathrm{\Phi }}(B_i^u\mid q)=\frac{\exp \left(S_{\mathrm{\Phi }}(B_i^u\mid q)\right)}{\sum _{j=1}^{C_N^k}\exp \left(S_{\mathrm{\Phi }}(B_j^u\mid q)\right)}$$

     其中： $S_{\mathrm{\Phi }}$$S_\Phi$ 是具有参数 $\mathrm{\Phi }$$\Phi$ 的非负的评分函数。

   • LTR objective function 的定义：给定 query $q$$q$ ，观察到 ranking list $B_1^u\succ B_2^u\succ \cdots \succ B_{C_N^k}^u$$B_1^u \succ B_2^u \succ \cdots \succ B_{C_N^{k}}^u$ 的似然为（不失一般性，我们假设 $U\left(B_1^u\right)\ge U\left(B_2^u\right)\ge \cdots \ge U\left(B_{C_N^k}^u\right)$$U\left(B_1^u\right)\ge U\left(B_2^u\right)\ge\cdots \ge U\left(B_{C_N^k}^u\right)$） ：

     $$\text{Pr}({\succ }_q;\mathrm{\Phi })=\prod _{B_i^u\in {\mathcal{B}}_q}\prod _{B_j^u:B_i^u\succ B_j^u}\text{Pr}(B_i^u\succ B_j^u;\mathrm{\Phi })=\prod _{B_i^u\in {\mathcal{B}}_q}\prod _{B_j^u:B_i^u\succ B_j^u}\sigma (S_{\mathrm{\Phi }}(B_i^u\mid q)-S_{\mathrm{\Phi }}(B_j^u\mid q))$$

     其中：

     • $B_i^u\succ B_j^u$$B_i^u\succ B_j^u$ （即，$B_i^u$$B_i^u$ 排名在 $B_j^u$$B_j^u$ 之前）的概率通过 sigmoid 函数 $\sigma (x)=\frac{1}{1+\exp (-x)}$$\sigma(x ) = \frac{1}{1+\exp(-x)}$ 来计算，sigmoid 函数的输入为 $S_{\mathrm{\Phi }}(B_i^u\mid q)-S_{\mathrm{\Phi }}(B_j^u\mid q)$$S_\Phi\left(B_i^u\mid q\right) - S_\Phi\left(B_j^u\mid q\right)$ 。

     • ${\succ }_q$$\succ_q$ 为 ${\left\{B_i^u\right\}}_{i=1}^{C_{N_q}^k}$$\left\{B_i^u\right\}_{i=1}^{C_{N_q}^k}$ 的 desired and latent ranking 。

     我们记 ${\mathcal{T}}_{\mathrm{\Phi }}^q=\log (\text{Pr}({\succ }_q;\mathrm{\Phi }))$$\mathcal T_\Phi^q = \log(\text{Pr}(\succ_q;\Phi))$，则 ${\mathcal{T}}_{\mathrm{\Phi }}^q$$\mathcal T_\Phi^q$ 是一个 LTR 任务的 general optimization goal 。

   • 定理：LTR objective function ${\mathcal{T}}_{\mathrm{\Phi }}^q$$\mathcal T_\Phi^q$ 是 ${\mathcal{Z}}_{\mathrm{\Phi }}^q$$\mathcal Z_\Phi^q$ 的一个下界，使得：

     $${\mathcal{T}}_{\mathrm{\Phi }}^q<{\mathcal{Z}}_{\mathrm{\Phi }}^q$$

     其中：${\mathcal{Z}}_{\mathrm{\Phi }}^q=C_q\sum _{B_i^u\in {\mathcal{B}}_q}{S}_{\mathrm{\Phi }}(B_i^u\mid q)$$\mathcal Z_\Phi^q = C_q\sum_{B_i^u\in \mathcal B_q} S_\Phi\left(B_i^u\mid q\right)$ 。

     并且：

     $$\underset{\mathrm{\Phi }}{max}{\mathcal{J}}_{\mathrm{\Phi }}^q\iff \underset{\mathrm{\Phi }}{max}{\mathcal{Z}}_{\mathrm{\Phi }}^q$$

     定理的证明参考论文的附录。

     由于定理的成立，原始的目标函数可以转换为最大化 LTR objective ${\mathcal{T}}_{\mathrm{\Phi }}^q$$\mathcal T_\Phi^q$ 。因此我们可以使用普通的 LTR 技术来优化它。我们进一步给出 LTR loss 的实现细节。

   • 实现细节：为了有效地 inference ，我们将 ranking 函数表述为：

     $$S_{\mathrm{\Phi }}(B_i^u\mid q)=\sum _{j=1}^{k}s(b_j^u\mid q),b_j^u\in B_i^u$$

     其中：$s(b_j^u\mid q)$$s\left(b_j^u\mid q\right)$ 为参数化的 scoring 函数。

     为了进行推理，我们可以只使用 top-k ranking behaviors （使用 $s(\cdot )$$s(\cdot)$ 函数）来形成 retrieved set $B_r^u$$B_r^u$（$S(B_r^u\mid q)$$S\left(B_r^u\mid q\right)$ 是最大值），而不是对所有 $B_i^u\in {\mathcal{B}}_q$$B_i^u\in \mathcal B_q$ 计算 scores 。

     我们使用lambda loss （《The lambdaloss framework for ranking metric optimization》）作为LTR loss 来优化UBR-R ：

     $${\mathcal{J}}_{\mathrm{\Phi }}^{\text{rank}}=\sum _{q\in {\mathcal{D}}_{\text{tr}}}\sum _{i,j:B_i^u\succ B_j^u}|\mathrm{\Delta }{U}_{i,j}|\times \log \sigma (\mathrm{\Delta }{S}_{i,j})$$

     其中：$\mathrm{\Delta }{U}_{i,j}=U\left(B_i^u\right)-U\left(B_j^u\right)$$\Delta U_{i,j} = U\left(B_i^u \right) - U\left(B_j^u \right)$，$\mathrm{\Delta }{S}_{i,j}=S_{\mathrm{\Phi }}(B_i^u\mid q)-S_{\mathrm{\Phi }}(B_j^u\mid q)$$\Delta S_{i,j} = S_\Phi\left(B_i^u\mid q \right) - S_{\Phi}\left(B_j^u \mid q \right)$ 。

     由于我们关心的是 top-1 behavior set ，并且为了快速训练，我们将损失函数简化为：

     $${\mathcal{J}}_{\mathrm{\Phi }}^{\text{rank}}=\sum _{q\in {\mathcal{D}}_{\text{tr}}}\sum _{j:B_1^u\succ B_j^u}|\mathrm{\Delta }{U}_{1,j}|\times \log \sigma (\mathrm{\Delta }{S}_{1,j})$$

     其中：$\mathrm{\Delta }{S}_{1,j}=S_{\mathrm{\Phi }}(B_1^u\mid q)-S_{\mathrm{\Phi }}(B_j^u\mid q)$$\Delta S_{1,j} = S_\Phi\left(B_1^u\mid q \right) - S_{\Phi}\left(B_j^u \mid q \right)$，$B_1^u$$B_1^u$ 由 top-k behaviors 组成（使用 $s(\cdot )$$s(\cdot)$ 评分函数），$B_j^u$$B_j^u$ 是随机的 behavior set 且它的 ranking score 低于 $B_1^u$$B_1^u$ 。

     虽然简化了，但是 $\sum _{j:B_1^u\succ B_j^u}$$\sum_{j: B_1^u\succ B_j^u}$ 仍然会非常耗时。读者猜测这里进行了采样，否则就是 $C_{N_q}^k$$C_{N_q}^k$，复杂度太高。

     实现方式：

     • 对于每个样本，计算它的 query $q$$q$ 。

     • 然后计算每个 behavior $b_j^u\in H_u$$b_j^u\in H_u$ 计算它的 score $s(b_j^u\mid q)$$s\left(b_j^u\mid q\right)$ 。

     • 然后选择 top-k scores 的 $k$$k$ 个 behaviors，得到 $B_1^u$$B_1^u$ ，以及对应的 $S_{\mathrm{\Phi }}(B_1^u\mid q)$$S_\Phi\left(B_1^u\mid q \right)$、$U\left(B_1^u\right)$$U\left(B_1^u \right)$ 。注意，为了得到 $U\left(B_1^u\right)$$U\left(B_1^u\right)$ ，需要进行一次 inference 。

     • 然后采样 $G$$G$ 组，每组随机采样 $k$$k$ 个 behaviors ，得到 $B_j^u,g_1\le j\le g_G$$B_j^u, g_1\le j\le g_G$ ，以及对应的 $S_{\mathrm{\Phi }}(B_j^u\mid q)$$S_\Phi\left(B_j^u\mid q \right)$、$U\left(B_j^u\right)$$U\left(B_j^u \right)$ 。注意，这里需要进行 $G$$G$ 次 inference 。

     • 最后，计算 $\sum _{j:B_1^u\succ B_j^u}|\mathrm{\Delta }{U}_{1,j}|\times \log \sigma (\mathrm{\Delta }{S}_{1,j})$$\sum_{j: B_1^u\succ B_j^u} |\Delta U_{1,j}|\times \log \sigma (\Delta S_{1,j})$ 。

1.3.4 同时优化两个子模块：UBR-MR

1. 在以上章节中，我们分别讨论了如何优化 matching 子模块和 ranking 子模块。将它们放在一起并尝试同时优化两个子模块是合理的。两个子模块的目标是统一的：prediction 模块更好的预测准确率。因此，可以如 Algorithm 1 所示，同时优化 matching 和ranking 函数。

   • 我们首先使用前面章节中描述的 fixed behavior retrieval system 对 prediction 模块进行预训练。由于 prediction 模块在 matching 和 ranking 子模块的训练过程中提供监督信号，因此首先对其进行热身并使其具有基本的判别能力非常重要。

   • 之后，轮流训练 retrieval 模块（第 4-8 行）和 prediction 模块（第 9行），直至收敛。

     是每个子模块训练一个 epoch 再轮流、还是每个子模块训练一个 batch 再轮流？作者未讲明这一点。UBR4CTR 是每个子模块训练一个 epoch，然后再训练另一个子模块一个 epoch 。

   如Algorithm 1 所示， matching 和 ranking 函数朝着同一目标一起优化。

   

1.4 模型分析

1. 本节分析了时间复杂度，并将我们的框架与现有的 retrieval-based 的 CTR 模型进行了比较。

1.4.1 时间复杂度分析

1. 我们关注 retrieval 过程的时间复杂度，因为它是 UBR 中最耗时的部分。

   • 对于 UBR ，由于 matching 过程只是简单地访问索引，因此其时间是一个常数 $n\mathcal{C}$$n\mathcal C$，其中 $n$$n$ 是 feature fields 的数量，$\mathcal{C}$$\mathcal C$ 是访问一条 inverted index entry 的时间。$\mathcal{C}$$\mathcal C$ 受存储系统的影响，在这里可以看作是一个常数。

   • 对于查找 top-k behaviors 的 ranking 过程，时间复杂度为 $O(\mathcal{K})$$O (\mathcal K)$ ，其中 $\mathcal{K}$$\mathcal K$ 是从 matching 子模块中获取的 candidate behavior set 的大小。因为评分过程的时间复杂度与列表长度成线性关系。

   因此，UBR 的总复杂度为 $n\mathcal{C}+O(\mathcal{K})$$n\mathcal C + O(\mathcal K)$ 。但 UBR 带来的主要耗时是 $n\mathcal{C}$$n\mathcal C$ 部分，因为它涉及磁盘访问操作；而另一部分 $O(\mathcal{K})$$O (\mathcal K)$ 可以由 GPU 或 CPU 在内存中计算。然而，大多数基于 behavior modeling 的 CTR 模型可能具有 $\mathcal{C}$$\mathcal C$ 部分，因为它们需要获取最近的 user behaviors 。此外，可以使用快速存储、更快的数据访问系统（如 Redis 等）对 $\mathcal{C}$$\mathcal C$ 部分进行优化。

   这只是 inference 的时间复杂度。而训练的时间复杂度相当高。

1.4.2 不同的 Retrieval-based 的方法的比较

1. 作为用于 CTR estimation 的 behavior modeling 的新研究方向，关于 retrieval-based 的 CTR 模型的研究很少。

   • 最相似的模型是 SIM 。SIM 有两个变体，SIM-Hard和 SIM-Soft。

     • SIM-Hard 是一个固定的搜索函数，它使用 category id 等单一特征从用户行为序列中进行搜索，这不够灵活，并且可能导致 retrieved behaviors 不是最优的。

     • SIM-Soft 使用局部敏感哈希 （local-sensitive hashing : LSH ）进行 MIPS 从而找到相对于 target item embedding 最邻近的 item embedding 。item embedding 使用辅助损失进行训练。

       SIM-Soft 的第一个缺点是它依赖于辅助任务，如果 user behaviors 太多，则需要随机采样。

       第二个缺点是LSH 使用的索引应该经常更新（但是实际上没有更新），因为 item embedding 在训练时会发生变化。

       最后，ranking 函数仅限于内积形式，缺乏建模能力。

   • ETA 使用 SimHash 生成 item embeddings 的二进制指纹，并计算 target item 指纹与 behaviors 指纹之间的汉明距离

   • STARec 利用 item embeddings 之间的余弦相似度作为 ranking 函数。

   因此，所有现有的 retrieval-based 的模型都遵循预定义的函数来检索 behaviors ，因此缺乏灵活性和学习能力。

   基于本文中描述的 matching 和 ranking ，我们在 Table 2 中总结了现有模型。SIM-Hard 本质上使用预定义的特征来匹配 user behaviors ，而 SIM-Soft 直接使用 MIPS 对 behaviors 进行排序，而无需matching 过程。 ETA 和 STARec 也在 Table 2 中进行了总结。

   

2. 总体而言，UBR 的检索机制与其他模型的比较如 Figure 6 所示。

   • 对于 UBR ，matching 子模块在很大程度上减少了 user behavior set 的大小。由于这个 reducing 过程本质上是访问 selected features 的倒排索引，因此可以非常快速地进行，效率很高。设计这样的 matching 过程最重要的原因是避免对整个用户历史序列 $H_u$$H_u$ 进行全面的计算，因为它可能非常长。

   • 相反，其他 one-stage retrieval models 选择对整个序列进行计算。为了快速地进行计算，它们实现尽可能简单的检索函数，例如汉明距离（ETA） 或余弦相似度 （STARec ）。因此，这些模型的检索函数都是非参数化的，并且基于某种预定义形式。尽管非参数化的检索函数的输入可以是 learnable embeddings，但函数的预定义形式限制了建模能力。因此，具有任意参数的可学习的检索函数是我们文章的主要关注点。

     此外，我们将检索函数实现为一个两阶段过程，以平衡有效性和效率。更多实验证据可在实验章节中找到。

   

3. 至于 UBR 的不同变体：

   • UBR-M 是由我们的会议文章（《User behavior retrieval for click-through rate prediction》）提出的，它使用 selected features 来匹配相应的 user behaviors 。feature selection 由 REINFORCE 算法优化。但它仍然使用固定的 ranking 函数。

   • UBR-R 是一种新模型，它使用所有特征来匹配 behaviors ，从而产生比UBR-M 更大的 candidate behavior set 。我们提出了一个参数化的 ranking 函数，它可以是任意结构，我们使用 LTR 对其进行优化。由于LTR 过程有效地训练了 ranking 函数，UBR-R 可以使用所有特征来匹配 candidate set 并准确获得 top-k behaviors 。

   • UBR-MR 是上述变体的混合版本，同时优化了 matching 子模块和 ranking 子模块。虽然 UBR-MR 同时优化了两个子模块并可以获得更好的性能，但它并不总是最好的选择。

     • 第一个原因是它的复杂性。在训练中，两个子模块都进行了优化，并且消耗的时间比 UBR-M 或 UBR-R 大得多。

     • 第二个原因是，如果数据集只有非常有限的特征（例如，item features 只有 item id 以及 category id ），那么在 matching 中选择特征并不总是一个好主意。在这种情况下，使用所有特征来匹配 behaviors 是更好的选择。

     实验章节中介绍了更多相应的结果，以及选择更好变体的见解。

1.5 实验

1. 本节将介绍大量实验的细节。我们将我们的模型与几个强大的 baselines 进行了比较，我们的模型在离线和在线评估中都取得了 SOTA 的性能。实现代码已发布（https://github.com/qinjr/UBR4CTR）。

2. 数据集：我们使用三个真实的、大型的 users online behaviors 数据集。数据集的统计数据可以在 Table 3 中找到。

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

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

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

   

3. 数据集预处理：对于 UBR ，数据集被处理成逗号分隔特征的格式。包含 user, item and context features 的一行被视为一个 behavior 。对于 baselines ，user behaviors 仅按时间戳排序。由于这三个数据集仅包含点击样本（即正样本），我们按照 《Deep interest evolution network for click-through rate prediction》、《Deep interest network for click-through rate prediction》 中的处理协议进行 1:1 负采样。

4. Basic Retrieval Engine：我们使用逗号分隔的 tokenizer 将数据集插入一个 retrieval engine 。我们使用ElasticSearch 作为 backbone retrieval engine client ，从而对公共数据集进行离线实验。Tmall 、Taobao、以及 Alipay 数据集的 posting list 平均长度分别为 6.9、7.3 和 8.9。

5. 训练集和测试集的拆分：我们使用 leave-one-out 策略（按时间顺序排序）来拆分数据集。

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

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

   • 测试集使用第 $1$$1$ 到 $(T-1)$$(T-1)$ 个behaviors 来预测第 $T$$T$ 个behavior 。

   $T$$T$ 表示用户行为序列的长度。

6. 评估指标：AUC、Logloss （简写为 LL ）。

7. baselines：我们将 UBR 与一些强基线进行比较，这些 baseline 来自 user behavior-based 的 CTR 模型、以及序列推荐模型。

   • DeepFM 是一种混合模型，以双塔方式结合了 FM 和深度神经网络。

   • PNN 是一种单塔模型，在深度网络中结合了基于内积的特征交互。

   • DCN 使用多层交叉网络来建模特征交互。

   • GRU4Rec 基于 GRU ，这是第一篇使用 recurrent cells 来建模 sequential user behaviors 从而用于 session-based recommendation 的工作。

   • Caser 是一种 CNNs-based 的模型，它将用户序列视为图像，因此使用水平的和垂直的卷积层来捕获 user behaviors 的时间模式。

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

   • HPMN 是一种分层周期性记忆网络（hierarchical periodic memory network ），旨在处理非常长的用户历史序列。此外， user memory state 可以增量地更新。

   • MIMN 基于神经图灵机（Neural Turing Machine ），可对建模用户兴趣漂移的 multiple channels 。该模型是作为 ser interest center 的一部分来实现的，可以建模非常长的用户行为序列。

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

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

   • R-Att 使用 $L_{\mathrm{\infty }}$$L_\infty$ 范数来正则化注意力的稀疏性。

   • Reformer 是针对 Transformer 结构提出的，可以有效地处理长序列。它使用 LSH 来降低自注意力的计算复杂度。

   • SIM 是 retrieve-based 的模型，其动机与 UBR 相似。SIM有两种变体：SIM-Hard 和 SIM-Soft，分别利用确定性的 hard search 、以及 embedding-based MIPS 。

   • ETA 利用 SimHash 算法生成 target item 的二进制指纹、以及 historical items 的二进制指纹。它使用汉明距离来获取 top-k nearest behaviors 从而作为 retrieved behaviors 。

   • STARec 直接根据 target item 的 embedding 和 behaviors embeddings 来计算余弦相似度。然后它检索与 target item 最相似的 behaviors 。

1.5.1 实验结果

1. 在本节中，我们对 UBR 进行了详细的实验，包括整体性能比较、消融研究和超参数研究。此外，还介绍了 UBR 的训练过程的比较、以及推理时间比较。

a. 整体性能

1. 我们对基线进行了两组实验。

   • 第一组：由于传统的 user behavior modeling 利用最近的连续行为，我们将最近的 $k$$k$ 个 behaviors 馈入基线。$k$$k$ 值设置为用户行为序列平均长度的 20% 。

   • 第二组：整个用户序列被馈入到基线模型中。

   为了公平比较，UBR 将从整个用户序列中检索 $k$$k$ 个 behaviors 。基线使用不同的网络结构来学习 user behaviors 的 unified representation ，而 UBR 聚合 retrieved behaviors 。不同模型计算出的 representation of user behaviors 和其它特征一起被馈入到 DNN 。我们对不同的模型使用相同的 DNN 结构，唯一的区别是模型如何利用用户行为数据。 结果如 Table 4 所示。从表中我们发现以下事实：

   • (i)：UBR（UBR-R/UBR-MR）取得了最佳性能。在三个数据集上，它的 AUC 比最佳基线模型分别高出 5.1％ 、2.1％ 和0.9％ 。在三个数据集上，Logloss 分别改善了 11.2％ 、0.2％ 和 3.8％ 。结果证明了 UBR 的有效性。

   • (ii)：通过比较 retrieved-based 的模型和传统模型（recent k behaviors），观察到显著的改进，这表明直接检索 user behaviors 的重要性。

     使用 recent k behaviors 的传统模型表现不佳。这表明最近的连续行为序列可能没有包含足够的时间模式。因此，模型无法有效地捕获 patterns 。虽然基线模型使用了复杂的网络结构，但由于输入数据的原因，它们无法获得良好的性能。

   • (iii) ：对于使用全长序列的传统基线，我们可以发现大多数基线模型的性能都有所提高，表明较长的序列携带着更丰富的信息和模式。

     然而，UBR 仍然优于传统基线。这表明较长的序列可能包含更多的噪音和不相关信息，因此有必要从整个序列中只获取最相关的信息。

   • (iv) ：UBR-R 和 UBR-MR 优于现有的 retrieval-based 的模型和 UBR-M 。这验证了我们新提出的参数化的 ranking 函数和相应的 LTR training 的优越性。

   

2. 为了增加测试难度并进一步验证 UBR 的有效性，我们通过按用户而不是时间来拆分 Tmall 数据集，并进行了额外的实验。我们从 non-retrieval models 中选择了 DIN 和 DIEN ，因为它们在 Tmall 数据集上表现良好，并列出了所有 retrieval-based 的基线。我们根据用户来拆分，训练集、验证集、测试集分别包含 80% 的用户及其对应的用户行为序列。结果如 Table 5 所示。

   

b. 消融研究

1. Retrieval 模块的重要性：为了验证 retrieval 模块的必要性，我们使用最近 k behaviors 而不是 retrieval 模块，然后使用不同的聚合函数。结果如 Table 6 所示。我们测试了两种不同的 behavior 聚合函数：sum pooling: SP 和 attention: ATT 。 从表中我们发现：

   • 配备 UBR 模块后，两种聚合函数的预测性能都得到了很大程度的提高。结果证明了 retrieval 模块的重要性。

   • 此外，我们可以发现，即使采用像 sum pooling 一样简单的聚合函数，SP w\ UBR-R 也可以实现与 ATT 相比具有竞争力的性能。这一事实证明了 retrieved behavior data 的有效性。

   • 此外，UBR-R 可以带来比 UBR-M 更多的性能提升，这验证了我们提出的 ranking 函数和 LTR training 的有效性。

   

2. 不同 UBR 变体之间的比较：为了弄清 retrieval 模块的不同子过程的影响，我们在 UBR-Fix （固定的 retrieval system）、UBR-M、UBR-R （使用两种不同的 ranking losses ：BPR loss （《BPR: Bayesian Personalized Ranking from Implicit Feedback》）、lambdaloss ）以及 UBR-MR 之间进行了另一次消融实验。 结果如 Table 7 所示。我们有以下观察和分析：

   • (i) ：UBR-Fix 在大多数情况下表现不如 UBR 的三个可学习的变体，这表明有必要使 retrieval system 可学习。

   • (ii)：在这三个数据集中，UBR-R (Lambda) 优于 UBR-R (BPR) 。这表明在 ${\mathcal{J}}_{\mathrm{\Phi }}^{\text{rank}}$$\mathcal J_\Phi^\text{rank}$ 中加入 $\mathrm{\Delta }{U}_{i,j}$$\Delta U_{i,j}$ 有利于提高 ranker 的性能。

   • (iii)：UBR-MR 在 Tmall 和 Alipay 数据集上优于 UBR-R 和 UBR-M ，但在 Taobao 数据集上表现较差。此外，在 Taobao 数据集上，UBR-Fix 优于 UBR-M 。

     • UBR-M 和 UBR-MR 的共同点在于它们都使用 selected features 作为 query 来进行 matching 过程。但是， Taobao 数据集只有两个 item features （item id, category id）。如果 selector 为某些样本删除一个特征（例如 category id ），则许多有用的 behaviors 将被删除，并且没有机会进行排名。相反，Tmall 和 Alipay 数据集有四个 item features （item id, category id, merchant id, and brand id ），这为 feature selector 提供了更大的操作空间。因此，matching 过程可以得到更充分的训练，并产生更好的性能。

     • 至于 UBR-Fix/UBR-R ，它们从更大 candidate set （从所有可能得特征中获取）中对 behaviors 进行排名，因此它们在 Taobao 数据集上取得了更好的性能。

   • (iv)：我们进一步介绍了每个 UBR 变体的训练时间。

     • UBR-Fix 无疑是最快的，因为它使用了不可训练的 retrieval 模块。

     • UBR-MR 的训练时间大约是 UBR-R 的 2-3 倍，因为两个子模块都经过了优化。因此，UBR-MR 的收敛速度要慢得多。

   在大多数情况下，考虑到 UBR-R 在训练效率和测试性能之间的良好平衡，它已经足够好了。特别是当数据集的特征很少时， learning to match 不是一个好主意（例如 Taobao 数据集）。总而言之，UBR-R 是一个足够好的做法；而 UBR-MR 是一个更难的版本，可以实现更好的性能，但它需要更多的成本训练并增加整个系统的复杂性。

   

c. 超参数研究

1. 本节我们研究了 retrieval size k 的影响。Figure 7 展示了 UBR-M、UBR-R 和 UBR-MR 在不同 retrieval size k 下的性能。从图中可以看出，AUC 和 logloss 的波动在绝对值上并不是很剧烈。然而，每个数据集都存在一个最优规模。这表明较小的 $k$$k$ 可能不包含足够的 behaviors 和信息；而太多的 retrieved behaviors 并不总是对性能有益，因为它们会包含更多的噪音。

   

d. 训练过程

1. 本节我们展示了 UBR 框架的训练过程。我们以 UBR-R 为例。prediction 模块的性能曲线如 Figure 8 所示。在曲线中，我们绘制了不同 test points 的 test AUC 值。图中，“P” 对应于 prediction 模块的训练过程（蓝色阴影区域），而 “R” 代表 retrieval 模块的训练（粉色阴影区域）。

   • 我们在训练数据集每间隔迭代 20% 后测试一次 CTR estimation 的性能。因此，对于 prediction module training 的一个 epoch ，我们可以有五个 test points 。

   • 当训练好 retrieval 模块时，我们每个 training epoch 测试一次 prediction 模块。

   从图中可以看出：

   • 在第一个粉色区域（ retrieval 模块正在训练）中， prediction 模块的测试性能显著提高。在粉色区域中，prediction 模块是固定的，因为两个模块是轮流训练的。

   • 在第一个粉色区域之后，prediction 模块接近收敛。接下来的训练逐渐提高性能，直到最终收敛。

   test AUC 曲线验证了 UBR 的训练策略，retrieval 模块实际上学习了有意义的模式，因为它可以在训练期间检索更多有用的 behaviors （test AUC 正在提高表明了这一点）。

   

e. 推理时间和内存开销

1. 为了解决效率问题，我们比较了UBR 和其他 user behavior-based 的CTR 模型的推理时间。Figure 9 显示了模型的平均推理时间。该时间是通过将测试数据集上的总时间除以 batches 数量来计算的。仅包括包含前向计算和 behavior retrieval 的时间。我们在具有 Intel(R) Core(TM) i7-6900K CPU 处理器、一块 NVIDIA GeForce GTX 1080Ti GPU 处理器和 128 GB 内存的机器上实现了两个版本的 index storage 。一种索引基于Elastic Search ，并持久保存在磁盘上；而另一个版本则将索引结构加载并存储在内存中。

   • UBR-M 、UBR-R 和 UBR-MR 具有相似的推理时间，因此我们使用 UBR 作为统一的名称。因为主要开销来自 retrieval 过程。 如图所示，UBR (in disk) 的推理时间最长。但是，在这三个数据集上，每个样本的推理时间不超过 1ms ，这表明合并 retrieval 模块不会严重损害效率。

   • 由于公共数据集的索引结构可以存储在内存中，我们实现了内存存储版本的 UBR 并测试了它的推理时间。我们发现更快的存储将显著提高 retrieval 模块的效率，并验证了 UBR 的主要开销来自访问磁盘。 倒排索引所消耗的内存存储如 Table 8 所示。

   总体而言，UBR 会带来一些效率问题和内存开销，但并非无法忍受。我们接下来的在线实验进一步验证了这一点。

   

   

f. UBR 与其他 Retrieval-based 的模型的详细比较

1. 在本节中，我们从有效性和复杂度方面比较了 UBR-MR 和 one-stage retrieval models 。我们在 Table 9 中列出了test AUC 、训练时间、以及推理时间。T-Inf 是模型完成一个 batch 测试样本的计算的 wall time。 从表中我们可以看出：

   • UBR 的性能最好，但其训练时间明显超过基线，这表明没有免费的午餐。

   • UBR 的推理复杂度为 $n\mathcal{C}+O(\mathcal{K})$$n\mathcal C+O(\mathcal K)$（$\mathcal{K}$$\mathcal K$ 是 matching 过程给出的 candidate behaviors 的数量）；而其他模型的复杂度为 $O(\mathcal{T})$$O(\mathcal T)$ ，其中 $\mathcal{T}$$\mathcal T$ 是整个用户序列长度。$\mathcal{T}$$\mathcal T$ 比 $\mathcal{K}$$\mathcal K$ 大得多，但 UBR 的 matching 操作需要额外的开销 $n\mathcal{C}$$n\mathcal C$ 来访问倒排索引。在实验中，我们观察到这些模型的推理时间没有显著差异。

   综上所述，结果表明，与其他 one-stage retrieval models 相比，UBR 具有更好的效果，以及具有竞争性的推理效率。

   

g. 非常长的用户行为序列

1. 我们在 Tmall 数据集中选取了 behaviors 超过 1,000 个的用户，从而对非常长的序列进行了广泛的实验。选定的用户数量为 2,900 。我们为每个用户使用一个 positive item 和九个随机采样的 negative items ，形成一个名为 Tmall-Long 的数据集。这个数据集用于推理过程。本次实验在具有 12 GB GPU 内存的 NVIDIA 1080 Ti 卡上进行。我们在这个数据集上测试了 UBR 与其他 attention-based models 的性能和开销。 结果如 Table 10 所示。从表中可以看出：

   • UBR-MR 明显优于 attention-based 的模型。这表明，对于非常长的序列，UBR 表现出比注意力机制更好的建模能力。因为在 1,000 behaviors 中，可能会有很多噪音，而 retrieval 模块可以直接关注最相关的行为。

   • 就开销而言，DIN 是最快的模型，但 UBR-MR 在速度上仍然优于 DIEN 。这种推理效率是可以接受的。

   • 至于 GPU 内存消耗，UBR-MR 是最好的，因为只有 matching 子模块给出的 candidate behaviors 才会放入 GPU 内存中，我们将 candidate behaviors size 设置为 100 。这意味着不会有超过 100 behaviors 被馈入到 ranking 子模块。

     SASRec 占用了太多内存，超过了 GPU 的内存大小。

   这个实验展示了从很长的序列中 retrieving behaviors （而不是直接将整个用户序列馈入到 attention model ）的优势。如果序列长度增长到 10,000 的级别（如 《Search-based user interest modeling with lifelong sequential behavior data for click-through rate prediction》 所示），由于计算和 GPU 内存的负担很重，attention 无法直接使用。但是 retrieval 模块可以处理它，因为我们总是可以获取一小部分 behaviors ，并仅将这一小部分 behaviors 提供给 prediction 模型。

   

1.5.2 真实世界的部署

1. UBR 已在真实世界部署中进行了测试，并取得了可喜的成果。在本节中，我们展示了在 Huawei App Store 付费广告场景中获得的离线和在线评估结果。app store 每天有数亿活跃用户，每天会产生数百亿个用户日志事件，这些事件包括浏览、点击和下载 apps 等隐式反馈。

a. 工业数据上的离线评估

1. 设置：离线评估是在工业数据集上进行的。工业数据集由 Huawei App Store 上主页广告场景的八天日志组成。前七天的日志用于训练，第八天的日志用于测试。对于工业数据集，positive ratio 约为 0.3% 。UBR 从用户过去一年的 behaviors 中检索数据，这意味着每个用户的 retrieval pool 都包含该用户去年的所有 behaviors 。

   我们通过将 retrieved behaviors （聚合后）作为新特征添加到 base model 来测试 UBR 性能。此 UBR 特征与其他常规特征拼接在一起，并馈入到 CTR 模型。base 模型是 DCN、DeepFM 和 PNN ，因为它们是广泛使用的工业级 CTR estimation 模型。

2. 结果：结果如 Table 11 所示。

   • 对于三个不同的 base models ，UBR-M 带来了 0.95%、0.93% 和 1.17% 的 AUC 改进。

   • 与 base model 相比，UBR-R 将 AUC 指标提高了 1.10%、1.09% 和 1.38% 。结果验证了 UBR 可以与其他模型一起使用，并实现显著的性能提升。

   • 从表中，我们还观察到 UBR-R 可以比 UBR-M 带来更多的性能提升，这表明 ranking function 是 UBR 系统的重要组成部分。

   • 至于 UBR 的开销，每个 batch 的推理时间增加了 31％ ，但仍少于 100 毫秒。由于倒排索引结构在内存中被存储，内存消耗增加了 56％ 。这个成本对于工业级应用来说是可以接受的。

   

b. 在线 A/B Test

1. 设置：我们在 Huawei App Store 的付费广告场景中进行 A/B test 。部署的场景位于 Huawei App Store 的主页上，它是 App Store 的主要广告服务。商业的 baseline 表示为 $\mathcal{M}$$\mathcal M$ ， UBR-enhanced model 表示为 ${\mathcal{M}}_{\text{UBR}}$$\mathcal M_\text{UBR}$。它们之间的唯一区别是：${\mathcal{M}}_{\text{UBR}}$$\mathcal M_\text{UBR}$ 配备了 UBR （具体而言是 UBR-R ）从过去一年检索到的 user behaviors 。在 A/B Test 实验持续 24 天，分为两个阶段：

   • 第一阶段随机选取总用户数的 20% ，其中一半作为实验组，另一半作为对照组。

   • 第二阶段随机选取 50% 的用户进行 A/B Test 。

   两个阶段都持续 12 天。每个阶段，我们进行 5 天的 A/A test ，然后进行 7 天的 A/B test 。在 A/A test 期间，所有用户都由base model $\mathcal{M}$$\mathcal M$ 提供服务。在 A/B test 期间，对照组用户使用base model $\mathcal{M}$$\mathcal M$ 提供的 apps ，而实验组用户使用 ${\mathcal{M}}_{\text{UBR}}$$\mathcal M_\text{UBR}$ 提供的 apps 。我们使用 Redis 存储 user behaviors 的倒排索引结构。 我们使用一台配备 48 core Intel Xeon CPU E5-2670 (2.30 GHz) 、400 GB RAM 、以及2张 NVIDIA TESLA V100 GPU 卡的机器来部署 UBR 。在压力测试中， ${\mathcal{M}}_{\text{UBR}}$$\mathcal M_\text{UBR}$ 的推理时间与 $\mathcal{M}$$\mathcal M$ 相比增加不到 30% 。

2. 指标：我们检查了 online evaluation 中广泛采用的两个指标：

   • 有效的每千次展示费用（effective Cost per Mille: eCPM）：

     $$\text{eCPM}=\frac{\text{total income}}{\text{num of impressions}}\times 1000$$

   • 点击率（Click-Through Rate: CTR）：

     $$\text{CTR}=\frac{\text{num of downloads}}{\text{num of impressions}}$$

   其中：num of downloads 和 num of impressions 分别是下载次数和展示次数。

3. 结果：eCPM 和 CTR 的改进分别如 Figure 10 和 Figure 11 所示。可以看到，系统非常稳定：

   • 在 A/A test 期间，eCPM 和 CTR 在 1.5% 以内波动。

   • 在第 6 天到第 12 天和第 18 天到第 24 天，A/B test 期间，当 ${\mathcal{M}}_{\text{UBR}}$$\mathcal M_\text{UBR}$ 投入使用时，可以观察到显著的改善。

     • 在 20% 流量 A/B test 中，eCPM和 CTR 的平均提升分别为 4.5% 和 6.6% 。

     • 对于 50%流量的 A/B test ，eCPM 和 CTR 平均分别提高了 6.6% 和 11.1% 。

   这些结果清楚地证明了UBR 的优越性，目前它已全面部署在 Huawei App Store 的付费广告场景中，并服务于所有流量。