阿里在《Revisit Recommender System in the Permutation Prospective》中提出了PRS：

1.介绍

。。。

不同于在matching和ranking stages中采用的point-wise方法，通常在reranking阶段会采用许多list-wise的方法。广泛使用的listwise方法的pipeline通常具有三个关键组件：

• 1）Ranking：会根据基础的ranking model的scores生成initial list
• 2) Refining：initial list的list-wise feature分布通常会通过一个设计良好的模型（LSTM&self-attention等）来refine它的rating scores
• 3) Re-ranking：通过refined list-wise rating scores以贪婪方式对候选items进行rerank

总之，已经存在的list-wise方法在推荐中达到效果提升，主要是通过建模list-wise feature分布来聚焦对item rating scores进行refining。

然而，以排列（permutation）的视角看，流行的reranking pipeline不能帮助当前的RS来达到排列最优（permutation-optimal），因为会忽略推荐结果内的排列变化影响（permutation-variant influence）。如图1(1)所示，这里是从真实数据集中收集到的两个推荐结果。它们由相同的items组成并且展示给相同的用户，令人吃惊的是，用户会对排列2做出响应而非1。一个可能的原因是：将更昂贵的item B放置在前，可以促进用户希望去购买更便宜的item A。我们将这种由排列变化造成用户决策的影响称为：在推荐结果内的“排列变化影响（permutation-variant influence）”。通过解决这样的排列变化影响，理想的方法会推荐排列2给用户，它从排列角度上来说是更优的结果。而在排列2中的item A的监督训练，图1(2)所使用的list-wise模型只能获得当遇到共享initial list（比如：item B,A,C）时的item A的优先级。毕竟，list-wise模型会以贪婪的方式通过refined rating scores（例如：排列1）对items进行rerank，从而忽略掉更好的排列2。理想的，图1(3)中permutation-wise方法，通过将item B放置在A之前（从排列1变为排列2），item A的预测的交互概率会获得极大提升，这主要有助于更好地对排列2做出正确判断。相应的，这样包含在lists中的排列变化影响的完整考虑和使用，扮演着重要的角色来近似permutation-optimal推荐结果、以及更好的用户体验。

图1 (1）真实case (2) 和(3)表示在该case下list-wise和permutation-wise方法的对比

实验上，这样的排列会对当前RS潜在带来新挑战，它可以归纳为两个部分：

• 1) 指数级解。假设从size m=100的initial list中需要推荐n=10个items。当前RS会将它看成是一个检索任务，在re-ranking阶段部署list-wise模型会搜索在O(m)的解空间。然而，以排列的角度，解空间会从O(m)膨胀\(O(A_m^n)\)（接近\(O(100^{10})\)）。考虑到在最终item lists中的排列变化影响，用户会对每个list做出不同的响应。实际上，只有一个list会最终推荐给用户，因而如何有效且高效地达到permutation-optimal list会给当前RS带来新挑战。
• 2) permutation-wise evaluation。当前RS使用的大多数方法，会尝试point-wise的方式预测user-item交互概率（例如：CTR和转化率）。如上所述，它需要提供一个统一的permutation-wise ranking准则，来从大量合规的lists中选取permutation-optimal的list，在当前的许多工作中均没有涉及到。

图2

在本工作中，如图2所示，我们进一步将list-wise方法发展到一个新的permutation-wise框架，称为PRS（Permutation Retrieve System）。特别的，PRS会包含：PMatch（permutation-Matching）和PRank（Permutation-Ranking）：

• PMatch阶段会关注于以高效并行方式生成多个候选列表（candidate lists），目标是考虑上排列变化影响以及减轻指数解空间问题。这里我们提出了FPSA（Fast Permutation Searching Algrithm），一个permutation-wise和面向目标（goal-oriented）的beam search算法，来以一种高效方式生成candidate lists。
• PRank stage会提供一个统一的ranking criterion来解决permutation-wise evaluation的挑战。我们会在提出的模型DPWN（Deep Permutation-Wise Network）上使用Bi-LSTM，有了它，排列变化影响可以完全解决。另外，我们提出LR（List Reward）metric来对candidate lists进行排序，它可以通过添加在candidate list中每个item的DPWN的rating scores来进行计算。最后，具有最高LR score的list会被推荐给用户。

为了演示PRS的效果，我们在alimama数据集和taobao数据集上执行一系列实验。实验结果表明它可以胜过SOTA的方法。另外，PRS成功部署到taobao应用场景上，并获得了11%的PV（Page）效果提升、在IPV（Item Page View）获得8.7%的提升。

2.相关工作

。。。

3.准备工作

通常，一个web-scale推荐系统（例如：电商和新闻）由三个stages组成：matching、ranking、reranking。在本paper中，我们关注最终的re-ranking阶段，它的input为由前两stage生成的ranking list（例如：matching和ranking）。reranking的任务是：会精心选择来自input ranking list的候选，并将它们进行重新安排（rearrange）到final item list中，接着展示给用户。数学上，有了user set U和item set I后，我们将list交互记录（list interaction records）标记成：

\[R = \lbrace (u, C, V, y^{CTR}, y^{NEXT} | u \in U, V \subset C \subset I) \rbrace\]

这里：

• C：表示的是记录的具有m个items的input ranking list，用于reranking stage，
• V：表示的是具有n个items的final item list，它会最终展示给user u，通常：\(n <= m\)
• \(y_t^{CTR} \in y^{CTR}\)：是user u 对于第t个item \(v_t \in V\)的implicit feedback，其中：当交互（例如：click）被观察到后\(y_t^{CTR} = 1\)，否则：\(y_t^{CTR}=0\)。
• \(y_t^{NEXT}=1\)：表示用户在该item之后的持续浏览，否则\(y_t^{NEXT}=0\)。

在真实工业推荐系统中：

• 每个user u会与一个user profile \(x_u\)相关，它包含了sparse features \(x_s^u\)（例如：user id和gender）和dense features \(x_d^u\)（例如：age）
• 每个item i也会与一个item profile \(x_i\)相关，它包含了sparse features \(x_i^s\)（例如：item id和brand）和dense features \(x_i^d\)（例如：price）

给定上述定义，我们现在将reranking任务公式化为：

定义1: 任务描述

通常的，工业RS的目标是：使得用户消费更多浏览（PV: page view）和interactions（IPV: item page view），对于reranking任务也相同。给定一个特定用户u，以及他的input ranking list C，该任务是学习一个reranking strategy \(\pi: C \xrightarrow{\pi} P\)，它的目标是：从C中对items进行选择和重安排，接着推荐一个final item list P。

4.提出的框架

在本节中，我们介绍permutation-wise框架PRS，它的目标是有效和高效地利用排列变化影响（permutation-variant influence）以便更好地在RS的reranking环节进行item重安排（rearrangements）。为了解决指数解空间，以及permutation-wise evaluation挑战，我们将reranking任务转换成两个后继stages：Permutation-Matching（PMatch）和Permutation-Ranking（PRank）。在PMatch阶段，多个有效算法可以并行方式部署以便考虑上排列变化影响，并从指数解空间中有效搜索candidate item lists。接着，PRank阶段提出了LR metric作为一个统一的permutation-wise ranking规则来进行评估candidate item list set，其中具有最高的LR score的list会被最终推荐。关键概念会归纳在表1中。

表1

首先，我们从users和items的representations开始，它是我们提出的框架的基础inputs。从之前的工作中，我们会为users和items将可提供的profiles参数化成vector representations。给定一个user u，它相关的sparse features \(x_u^s\)和dense features \(x_u^d\)，我们将每个sparse feature value嵌入到d维空间中。接着，每个user可以表示成：

\[x_u \in R^{\mid x_u^s \mid \times d + \mid x_u^d \mid}\]

其中：

• \(\mid x_u^s \mid\)和\(\mid x_u^d \mid\)分别表示user u的sparse和dense feature space的size。

相似的，我们将每个item i表示成：

\[x_i \in R^{\mid x_i^s \mid \times d + \mid x_i^d \mid}\]

天然的，我们将input ranking list C记录成：

\[C = [x_c^1, \cdots, x_c^m]\]

以及将final item list V标记成：

\[V = [x_v^1, \cdots, x_v^n]\]

其中：

• m和n：分别是在input ranking list和final item list中的items数目。

在下面章节中，我们会放大到PMatch。对于每个stage，我们将介绍划分成两部分：一个是offline training（preparation），另一个是online serving（inference）。这两部分的主要不同是：R中的\(V, y^{CTR}, y^{NEXT}\)是在offline training给出，而不是在online serving中。

4.1 PMatch阶段

PMatch stage提出是为了以一个更高效方式获得多个有效的candidate lists。如图3所示，有许多算法【1，25，26，35】可以并行部署来生成item lists，接着通过list merge操作合并成candidate list set。尽管有管，当前努力会忽略在最终item list中的排列变化影响，我们提出了一个permutation-wise和goal-oriented beam search算法，称为FPSA（Fast Permutation Searching Algorithm）。

图3 PRS框架的整体架构

4.1.1 offline training

为了使得用户进行更多的浏览和交互，除了常规使用的CTR score外，我们首先设计NEXT score，它会预测：用户在这个item之后是否持续浏览的概率。具有更高NEXT scores的items可以增加用户持续浏览的动力，它会提升后续items被浏览和点击的概率。

特别的，有了labeled interaction记录R，我们会详细说明两个point-wise models：

• CTR预估模型：\(M^{CTR}(v \mid u; \theta^{CTR})\)
• NEXT预估模型：\(M^{NEXT}(v \mid u; \theta^{NEXT})\)

它们的计算如下：

\[\begin{align} \hat{y}_t^{CTR} & = M^{CTR}(v | u; \theta^{CTR}) \\ & = \sigma(f(f(f(x_v \oplus x_u)))) \\ \hat{y}_t^{NEXT} & = M^{NEXT}(v | u; \theta^{NEXT}) \\ & = \sigma(f(f(f(x_v \oplus x_u)))) \end{align}\]

…(1)

其中：\(f(x) = ReLU(Wx+b)\)，\(\sigma(\dot)\)是logistic function。两个模型可以通过binary cross-entropy loss function进行优化，定义如下：

\[\begin{align} L^{CTR} & = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_0^t \in V} (y_t^{CTR} log \hat{y}_t^{CTR} + (1 - y_t^{CTR}) log(1 - \hat{y}_t^{CTR})) \\ L^{NEXT} & = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_0^t \in V} (y_t^{NEXT} log \hat{y}_t^{NEXT} + (1 - y_t^{NEXT}) log(1 - \hat{y}_t^{NEXT})) \end{align}\]

…(2)

我们会训练\(\theta^{CTR}\)和\(\theta^{NEXT}\)，直到根据等式(2)收敛。

4.1.2 Online serving

在本工作中，我们将reranking task看成是：从input ranking list中顺序的选择items，直接达到预定义长度。Beam search【21，30】是一种常用的技术，它通过在一个有限集合中探索和扩展最可能的candidates，来生成多个有效lists。在FPSA算法中，我们以一种goal-oriented方式实现了beam search算法，也就是说：我们会在每个step选择具有最高estimated reward的lists。

图4 FPSA算法说明

我们会在图4和算法1中清楚展示和说明提出的FPSA算法。

• 首先，我们会在input ranking list C中，通过收敛的CTR预估模型\(M^{CTR}(v \mid u; \theta^{CTR})\)和NEXT prediction 模型\(M^{NEXT}(v \mid u;\theta^{NEXT})\)分别得到：点击概率为\(P_{c_i}^{CTR}\)和持续浏览概率\(P_{c_i}^{NEXT}\)，并将两个predicted scores绑定到每个item \(c_i\)上。

• 接着，在每一步我们会为在set S中的每个list穷举扩展剩余candidates，并根据它们 calculated estimated reward（第1-17行）保留top k的candidate lists。

  在第18-28行，在每个step中，当迭代经过在list中的每个item时，我们会计算：transitive expose probability \(p^{Expose}\)乘以前面items的NEXT scores。受\(p^{Expose}\)的影响，我们会计算PV reward \(r^{PV}\)以及IPV reward \(r^{IPV}\)，并在迭代的终点将它们的求和表示为reward \(r^{sum}\)。这里：\(r^{PV}， r^{IPV}, r^{sum}\)分别表示estimated PV、IPV以及该list的混合收益。

算法1

在算法的结尾，我们会获得candidate list set \(S= \lbrace O_1, \cdots, O_t \rbrace_{size=k}\)，它可以根据reward \(r^{sum}\)来直接选择top list。另外，从其它方法生成（例如：DLCM和PRM）的final item lists也可以合并到S中，并进一步通过后续的PRank stage来进行排序。

4.1.3 有效性研究

我们尝试改善FPSA算法的效率。特别的，我们会在ranking stage以并行方式部署CTR和NEXT prediction模型来对每个item的 CTR和NEXT scores进行打分（rate），它的算法复杂度是O(1)。对于算法1中的算法，我们会以并行方式执行6-15行的循环，并采用最小最大堆（min-max heaps）的排序算法来选择第16行的top-k结果。总之，当是算法1时，我们会将算法复杂度减小为\(O(n(n+k logk))\)。

总之，FPSA的算法复杂度是\(a O(1) + b O(n(n+ k logk))\)。它要比已存在的list-wise方法（比如：DLCM【1】和PRM【26】）更高效，它们的复杂度为\(a O(n) + b O(n log n)\)。这里\(a >> b\)表示在深度模型中的矩阵计算开销要比数值型计算开销要多很多。(注：这里的n是final item list的size)

4.2 PRank stage

PRank stage为由PMatch stage生成的candidate list set提供了一个统一的permutation-wise ranking规则。当前RS的大多数方法，主要遵循基于rating scores的greedy strategy。尽管有效，但策略本身忽略了在final item list中的排列变化影响，因而不能评估排列。出于该目的，如图3的右边所示，我们提出了LR（List Reward）指标来从由PMatch stage中提供的candidate list set中选择permutation-optimal list，它通过对精心设计的permutation-wise模型DPWN（Deep Permutation-Wise Network）的rating scores计算得到。

4.2.1 Offline training

图5 DPWN模型的技术架构

DPWN的总架构如图5所示。DPWN是为了捕获和建模由final item list包含的排列变化影响。通过考虑这样的动机，DPWN \(M(x_v^t \mid u, V; \theta^D)\)，通过\(\theta^D\)进行参数化，来预测user u和第t个item \(x_v^t\)在final item list V中的permutation-wise交互概率。Bi_LSTM可以非常好地捕获这样的时间依赖（time-dependent）和在排列中的long-short term信息。数学上，对于第t个item \(x_v^t\)的forward output state可以如下进行计算：

\[i_t = \sigma(W_{xi} x_v^t + W_{hi} h_{t-1} + W_{ci}c_{t-1} + b_i) \\ f_t = \sigma(W_{xf} x_v^t + W_{hf} h_{t-1} + W_{cf}c_{t-1} + b_f) \\ c_t = f_t x_v^t + i_t tanh(W_{xc}x_v^t + W_{hc} h_{t-1} + b_c) \\ o_t = \sigma(W_{xo} x_v^t + W_{ho} h_{t-1} + W_{co} c_t + b_o) \\ \overrightarrow{h_t} = o_t tanh(c_t)\]

…(3)

其中：

• \(\sigma(\cdot)\)是logistic function
• i, f, o和c是input gate、forget gate、output gage以及cell vectors，它们具有相同的size为\(x_v^t\)。权重矩阵的shapes可以通过下标进行表示。相似的，我们可以得到backward output state \(\leftarrow{h_t}\)。接着，我们会将两个output states \(h_t = \rightarrow{h_t} \odot \leftarrow{h_t}\)进行拼接，并将\(h_t\)表示为序列表示\(x_v^t\)。

由于在CTR预估领域，建模复杂交互的强大能力，我们将MLP集成到DPWN中以获得更好的特征交叉。这里，我们将Bi-LSTM公式化为：

\[M(x_v^t | u, V; \theta^D) = \sigma(f(f(f(x_u \oplus x_v^t h_t))))\]

…(4)

其中：

• \[f(x) = ReLU(Wx+b)\]
• \(\sigma(\cdot)\)是logistic function

DPWN的参数集合是\(\theta^D = \lbrace W_*, b_* \rbrace\)，例如：是Bi-LSTM和MLP的参数的union。

很明显，DPWN可以通过binary cross-entropy loss function来进一步优化，它的定义如下：

\[L^D = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_v^t \in V} (y_{uv}^t log \hat{y}_{uv}^t + (1 - y_{uv}^t) log(1 - \hat{y}_{uv}^t))\]

…(5)

其中，D是训练dataset。出于便利性，我们将\(\hat{y}_{uv}^t\)看成是\(M(x_v^t \mid u, V; \theta^D)\)，\(y_{uv}^t \in \lbrace 0, 1 \rbrace\)是ground truth。我们可以通过最小化\(L^D\)来对参数\(\theta^D\)最优化。

注意，DPWN与当前list-wise方法的主要不同点是：DPWN会建模final item list，而非input ranking list。实际上，用户会更受展示的final item list的排列信息的影响。

4.2.2 Online serving

如上所述，我们基于DPWN模型提出了一个统一的permutation-wise LR metric，它被应用于：在PMatch stage生成的candidate list set达到最优的permutation-optimal list解。特别的，我们会计算：在candidate list set S中的每个list \(O_t\)的LR（list reward）score：

\[LR(O_t) = \sum\limits_{x_o^i \in O_t} M (x_o^i | u, O_t)\]

…(6)

之后，具有最高LR score的list P会被最终选中并推荐给该user，获得permutation-optimal list的希望，最可能满足用户的需求。

最终，我们将PRS framework中的PMatch和PRank的online serving部分称为学到的reranking startegy \(\pi\)，来从input ranking list C中生成permutation-optimal list P。

5.实验

在本节中，会开展许多在线和离线实验来验证PRS的有效性，目标是回答以下问题：

• RQ1: 在PRank stage中提出的LR metric是如何准备评估permutations的收益（profits）的？
• RQ2: 在PMatch stage中的FPSA算法，是如何以有效方式从指数级解空间中生成candidate list set的？
• RQ3: 在真实推荐系统中PRS的效果如何？

5.1 实验设置

5.1.1 Datasets

。。。

5.2 效果对比（RQ1）

5.3 FPSA算法研究（RQ2）

5.4 在线AB测试（RQ3）

6.结论

略

• 1.https://arxiv.org/pdf/2102.12057.pdf

huawei在2021《Cross-Batch Negative Sampling for Training Two-Tower Recommenders》中提出了一种cross-batch negative sampling的方法：

摘要

双塔结构被广泛用于学习item和user representations，它对于大规模推荐系统来说是很重要的。许多two-tower models会使用多样的in-batch negative sampling的策略，这些策略的效果天然依赖于mini-batch的size。然而，使用大batch size的双塔模型训练是低效的，它需要为item和user contents准备一个大内存容量，并且在feature encoding上消耗大量时间。有意思的是，我们发现，neural encoders在训练过程中在热启（warm up）之后对于相同的input可以输出相对稳定的features。基于该事实，我们提出了一个有效的sampling策略：称为“Cross-Batch Negative Sampling (CBNS)”，它可以利用来自最近mini-batches的encoded item embeddings来增强模型训练。理论分析和实际评估演示了CBNS的有效性。

3.模型框架

3.1 问题公式

我们考虑对于large-scale和content-aware推荐系统的公共设定。我们具有两个集合：

• \[U = \lbrace U_i \rbrace_i^{N_U}\]
• \[I = \lbrace I_j \rbrace_i^{N_I}\]

其中：

• \(U_i \in U\)和\(I_j \in I\)是features（例如：IDs, logs和types）的预处理vectors集合

在用户为中心的场景，给定一个带features的user，目标是：检索一个感兴趣items的子集。通常，我们通过设置两个encoders（例如：“tower”）：

\[f_u: U \rightarrow R^d, g_v: I \rightarrow R^d\]

之后我们会通过一个scoring function估计user-item pairs的相关度：

\[s(U,I) = f_u(U)^T g_v(I) \triangleq u^T v\]

其中：

• u,v分别表示来自\(f_u, g_v\)的user、item的encoded embeddings

3.2 基础方法

通常，大规模检索被看成是一个带一个（uniformly）sampled softmax的极端分类问题（extreme classification）：

\[p(I | U; \theta) = \frac{e^{u^T v}}{e^{U^T v} + \sum\limits_{I^- \in N} e^{U^T v^-}}\]

…(1)

其中：

• \(\theta\)表示模型参数
• N是sampled negative set
• 上标“-”表示负样本

该模型会使用cross-entropy loss（等价为log-likelihood）进行训练：

\[L_{CE} = - \frac{1}{|B|} \sum\limits_{i \in [|B|]} log p(I_i | U_i; \theta)\]

…(2)

图1 双塔模型的采样策略

为了提升双塔模型的训练效率，一个常用的抽样策略是in-batch negative sampling，如图1(a)所示。具体的，它会将相同batch中的其它items看成是负样本（negatives），负样本分布q遵循基于item frequency的unigram分布。根据sampled softmax机制，我们修改等式为：

\[P_{In-batch} (I | U; \theta) = \frac{e^{s'(U,I;q)}}{e^{s'(U,I;q)} + \sum_{I^- \in B \ \lbrace I \rbrace} e^{s'(U, I^-;q)}} \\ s'(U, I;q) = s(U,I) - log q(I) = u^T v - log q(I)\]

…(3)(4)

其中：

• logq(I) 是对sampling bias的一个correction。

In-batch negative sampling会避免额外additional negative samples到item tower中，从而节约计算开销。不幸的是，in-batch items的数目batch size线性有界的，因而，在GPU上的受限batch size会限制模型表现。

3.3 Cross Batch Negative Sampling

3.3.1 Nueral model的embedding稳定性（embedding stability of neural model）

由于encoder会在训练中持续更新，来自过往mini-batches的item embeddings通常会被认为是过期并且丢弃。然而，因为embedding stability of neural model，我们会识别这样的信息，并且被复用成一个在当前mini-batch的valid negatives。我们会通过估计item encoder \(g_v\)的feature drift【26】来研究该现象，feature drift定义如下：

\[D(I, t; \Delta t) \triangleq \sum\limits_{I \in I} \| g_v(I; \theta_g^t) - g_v(I; \theta_g^{t - \Delta t}) \|_2\]

…(5)

其中：

• \(\theta_g\)是\(g_v\)的参数
• \(t, \Delta_t\)分别表示训练迭代数和训练迭代间隔（例如：mini-batch）

我们会从头到尾使用in-batch negative softmax loss来训练一个Youtube DNN，并计算具有不同间隔\(\lbrace 1,5,10 \rbrace\)的feature drift。

图2 YoutubeDNN的Feature drift w.r.t. Δts, 数据集：Amazon-Books dataset

如图2所示，features会在早期激烈变化。随着learning rate的减小，在\(4 \times 10^4\)次迭代时features会变得相对稳定，使得它可以合理复用它们作为合法负样本（valid negatives）。我们将这样的现象称为“embedding stability”。我们进一步以公理3.1方式展示：embedding stability会提供一个关于scoring function的gradients error上界，因此， stable embeddings可以提供合法信息进行训练。

引理3.1 假设：\(\| \hat{v}_j - v_j \|_2^2 < \epsilon\)，scoring function的output logit是\(\hat{o}_{ij} \triangleq u_i^T \hat{v}_j\)并且user encoder \(f_u\)满足Lipschitz continuous condition，接着：gradient w.r.t user \(u_i\)的偏差为：

\[|| \frac{\partial \hat{o}_{ij}}{\partial \theta} - \frac{\partial o_{ij}}{\partial \theta} ||_2^2 < C \epsilon\]

…(6)

其中：C是Lipschitz常数。

证明：近似梯度error可以被计算为：

\[\| \frac{\partial \hat{o}_{ij}}{\partial \theta} - \frac{\partial o_{ij}}{\partial \theta} \|_2^2 = \| \frac{\partial \hat{o}_{ij}}{\partial \theta} - \frac{\partial o_{ij}}{\partial \theta} ) \frac{\partial u_i}{\partial \theta} \|_2^2 = \| (\hat{v}_j - v_j) \frac{\partial u_i}{\partial \theta} \|_2^2 \\ \leq \| \hat{v}_j - v_j \|_2^2 \|\frac{\partial u_i}{\partial \theta} \|_2^2 \leq \| \frac{\partial f_u(U_i;\theta^t)}{\partial \theta} \|_2^2 \epsilon \leq C \epsilon\]

…(7)(8)

经验上，线上的模型会保持\(C \leq 1\)。因而，gradient error可以通过embedding stability被控制。

3.3.2 对于Cross Batch Features使用FIFO Memory Bank

首先，由于embeddings在早期变化相对剧烈，我们会使用naive in-batch negative sampling对item encoder进行warm up到\(4 \times 10^4\)次迭代，它会帮助模型逼近一个局部最优解，并生成stable embeddings。

接着，我们开始使用一个FIFO memory bank \(M = \lbrace (v_i, q(I_i)) \rbrace_{i=1}^M\)训练推荐系统，其中：

• \(q(I_i)\)：表示在unigram分布q下item \(I_i\)的抽样概率，其中M是memory size。

cross-batch negative sampling（CBNS）配合FIFO memory bank如图1(b)所示，CBNS的softmax的output被公式化为：

\[p_{CBNS}(I | U; \Theta) = \frac{e^{s'(U,I;q)}}{e^{s'(U,I;q)} + \sum\limits_{I^- \in M U B \backslash \lbrace I \rbrace} e^{s'(U,I^-;q)}}\]

…(9)

在每次迭代的结尾，我们会enqueue该embeddings 以及 对应当前mini-batch的抽样概率，并将早期的数据进行dequeue。注意，我们的memory bank会随embeddings更新，无需任何额外计算。另外，memory bank的size相对较大，因为它对于这些embeddings不需要更多memory开销。

4.实验与结果

https://dl.acm.org/doi/pdf/10.1145/3404835.3463032

google在2021《Self-supervised Learning for Large-scale Item Recommendations》中在双塔模型中使用了SSL：

介绍

在本paper中关注的推荐任务是：给定一个query，从一个很大的item catalog中找出与该query最相关的items。large-scale item推荐的问题已经被多个应用广泛使用。一个推荐任务可以根据query类型划分为：

• i) 个性化推荐： 此时query是一个用户
• ii) item to item推荐：此时query是一个item
• iii) 搜索（search）：此时query是一个自由文本片段

为了建模一个query和一个item间的交叉，广告使用的方法是：embedding-based neural networks。推荐任务通常被公式化为一个极端分类问题（extreme classification problem）：其中每个item被表示成在output space中的一个dense vector。

图1 模型结构：使用 query和 item representations的Two-tower DNN

该paper主要关注于two-tower DNNs（见图1），它在许多真实推荐系统中很常见。在该结构中，一个neural network会将一个item features的集合编码成一个embedding，使得它甚至适用于检索cold-start items。另外，two-tower DNN结构使得可以实时serving大量的items，将一个top-k NN搜索问题转成一个NIPS（Maximum-Inner-Product Search），可以在sublinear的复杂度中求解。

Embedding-based deep models通常具有大量参数，因为他们会使用高维embeddings进行构建，可以表示高维稀疏features，比如：topics或item IDs。在许多已经存在的文献中，训练这些模型的loss functions会被公式化为一个监督学习问题。监督学习需求收集labels（比如：clicks）。现代推荐系统会从用户侧收集数十亿的footprints，并提供大量的训练数据来构建deep models。然而，当它建模一个大量items问题时，数据仍会非常稀疏，因为：

• 高度倾斜的数据分布：queries和items通常会以一个二八分布（power-law）方式高度倾斜。因此，只有一小部分流行的items会获得大量的交互。这使得长尾items的训练数据非常稀疏。
• 缺乏显式用户反馈：用户经常提供许多隐式正向反馈，比如：点击或点赞。然而，像显式反馈（item评分、用户喜好度反馈、相关得分）等非常少。

自监督学习（SSL：Self-supervised learning）会提供一个不同的视角来通过unlabeled data来提升deep表征学习。基本思想是：使用不同的数据增强（data augmentations）来增强训练数据，监督任务会预测或重新设置原始样本作为辅助任务（auxiliary tasks）。自监督学习（SSL）已经被广泛用在视觉、NLP领域。

• CV中的一个示例是：图片随机旋转，训练一个模型来预估每个增强的输入图片是如何被旋转的。
• 在NLU中，masked language任务会在BERT模型中被引入，来帮助提升语言模型的预训练。
• 相似的，其它预训练任务（比如：预估周围句子、将wikipedia文章中的句子进行链接）已经被用于提升dual-encoder type models.

对比起常规则的监督学习，SSL提供互补目标（complementary objectives），来消除人工收集labels的前提。另外，SSL可以利用input features的内部关系来自主发现好的语义表示。

SSL在CV和NLP中的广泛使用，但在推荐系统领域还没有被研究过。最近的研究[17,23,41]，会研究一些正则技术，它用来设计强制学到的表示（例如：一个multi-layer perception的output layer），不同样本会相互远离，在整个latent embedding space中分散开来。尽管SSL中共享相似的精神，这些技术不会显式构建SSL任务。对比起CV和NLU应用中的建模，推荐模型会使用极度稀疏的input，其中高维categorical featurers是one-hot（）编码的，比如：item IDs或item categories。这些features通常被表示为在深度模型中的可学习embedding vectors。由于在CV和NLU中大多数模型会处理dense input，创建SSL任务的已存在方法不会直接应用于在推荐系统中的稀疏模型。最近，一些研究研究SSL来改进在推荐系统中的sequential user modeling。。。。

2.相关工作

。。。

3.方法

我们使用自监督学习框架来进行DNN建模，它会使用大词汇表的categorical features。特别的，一个常见的SSL框架会在第3.1中引入。在第3.2节中，我们提出一个数据增强方式，用来构建SSL任务，并详述 spread-out regularization的connections。最后，在第3.3节中，我们通过一个multitask learning框架，描述了如何使用SSL来改进factorized models（图1中的 two-tower DNNs）。

3.1 框架

受SimCLR框架的启发，对于visual representation learning，我们采用相似的对比学习算法来学习categorical features的表示。基本思想是两部分：

• 首先，对于相似的训练样本，我们使用不同的数据增强来进行学习表示；
• 接着使用contrastive loss函数来鼓励从相同训练样本中学习的representations是相似的。contrastive loss会被用于训练two-tower DNNs（见：[23, 39]），尽管这里的目标是：使得正样本（postive item）会与它相应的queries一致。

我们会考虑关于N个item样本的一个batch：\(x_1, \cdots, x_N\)，

• 其中：\(x_i \in X\)表示了样本i的一个特征集合，

在推荐系统场景中，一个样本由一个query、一个item或一个query-item pair构成。假设：存在一个关于转换函数对（transform function pair）：\(h, g: X \rightarrow X\)，它会将\(x_i\)分别增强为\(y_i, y_i'\)：

\[y_i \leftarrow h(x_i), y_i' \leftarrow g(x_i)\]

…(1)

给定关于样本i的相同输入，我们希望学习在增强后（augmentation）不同的表示\(y_i, y_i'\)，确认模型仍能识别\(y_i\)和\(y_i'\)代表相同的input i。

• 换句话说，contrastive loss会学习最小化在\(y_i, y_i'\)间的不同之处
• 同时，对于不同的样本i和j，contrastive loss会最大化在数据进行不同增强后在学到的\(y_i, y_i'\)间的representations的不同之处

假设：\(z_i, z_i'\)表示通过两个nueral networks \(H, G: \rightarrow R^d\)对\(y_i, y_i'\)进行编码后的embeddings，也就是说：

\[z_i \rightarrow H(y_i), z_i' \leftarrow G(y_i')\]

…(2)

我们将：

• \(z_i, z_i'\)看成是postive pairs
• \((z_i, z_j')\)看成是negative pairs，其中：\(i \neq j\)

假设：\(s(z_i, z_j') = \frac{<z_i,z_j'>}{\| z_i \| \cdot \|z_j'\|}\)（即余弦相似度）。为了鼓励上述的属性，我们将一个关于N个样本\(\lbrace x_i \rbrace\)的batch的SSL loss定义为：

\[L_{self} ( \lbrace x_i \rbrace; H, G) := -\frac{1}{N} \sum\limits_{i \in [N]} log \frac{exp(s(z_i, z_i')) / \tau}{\sum\limits_{i \in [N]} exp(s(z_i, z_j'))/ \tau}\]

…(3)

其中：

• \(\tau\)是一个对于softmax temperature可调的超参数。

上述的loss function学习了一个健壮的embedding space，使得：在数据增强后相似items会相互更近些，随机样本则会被push更远。整个框架如图2所示：

图2 self-suprevised learning框架说明。两个数据增强h和g会被应用到input上；encoders H和G会被应用到增强样本\(y_i\)和\(y_i'\)来生成embeddings \(z_i\)和\(z_i'\)。SSL loss \(L_{self} w.r.t. z_i\)会朝着最大化与\(z_i'\)的相似度、以及最小化\(z_j\)和\(z_j'\)的相似度的方式进行

Encoder结构

对于categorical features的输入样本，通常在其上使用一个input layer和一个multi-layer perceptron（MLP）来构建H, G。

• input layer：通常是一个关于normalized dense features和多个sparse feature embeddings的concatenation，其中，sparse feature embeddings是学到的representations，会存储在embedding tables中（作为对比，CV和语言模型的input layers，会直接作用于raw inputs中）。

为了使用SSL对监督学习更容易，对于network H和G，我们会共享sparse features的embedding table。这取决于数据增强(h, g)的技术，H和G的MLPs可以被完全或部分共享。

Connection with Spread-out Regularization

如果是这样的特征：(h,g)是相同的map, H,G是相同的neural network，在等式(3)中的loss function退化为：

\[-\frac{1}{N} \sum_i log \frac{exp(1/\tau)}{ exp(1 / \tau) + \sum_{j \neq i} exp(s(z_i, z_j) / \tau)}\]

它会鼓励不同样本的representations具有很小的cosine相似度。该loss与[41]中引入的e spread-out regularization相近，除了：原文建议使用square loss，例如：\(\frac{1}{N} \sum\limits_i \sum\limits_{j \neq i} \langle z_i, z_j \rangle^2\)，而非softmax。spread-out regularization已经被证明是会改进大规模检索模型的泛化性。在第4节中，我们展示了，引入特定的数据增强，使用SSL-based regularization可以进一步提升模型效果。

3.2 two-stage data augmentation

我们引入了数据增强，例如：在图2中的h和g。给定一个item features的集合，关键思想是：通过将部分信息进行masking，创建两个augmented examples。一个好的transformation和data augmentation应在该数据上做出最少的假设，以便它可以被应用于大量任务和模型上。masking的思想受BERT中的Masked Language Modeling的启发。不同于sequential tokens，features的集合不会有顺序，使得masking方式是一个开放问题， 我们会通过探索特征相关性（feature corelation）来找到masking模式。我们提出了相关特征masking（Correlated Feature Masking (CFM)），通过知道feature correlations，对于categorical features进行裁剪。

在详究masking细节前，我们首先提出一种two-stage augmentation算法。注意，无需augmentation，input layer会通过将所有categorical features embeddings进行concatenating的方式来创建。该two-stage augmentation包含：

• Masking：通过在item features集合上使用一个masking pattern。我们会在input layer上使用一个缺省embedding来表示被masked的features。
• Dropout：对于multi-value的categorical features，我们会：对于每个值都一定概率来丢弃掉。它会进一步减少input信息，并增加SSL任务的hardness

masking step可以被解释成一个关于dropout 100%的特例，我们的策略是互补masking模式（complementary masking pattern），我们会将feature set分割成两个互斥的feature sets到两个增强样本上。特别的，我们可以随机将feature set进行split到两个不相交的subsets上。我们将这样的方法为Random Feature Masking（RFM），它会使用作为我们的baselines。我们接着介绍Correlated Feature Masking(CFM) ，其中，当创建masking patterns时，我们会进一步探索feature相关性。

Categorical Feature的互信息

如果整个feature set具有k个feature， 一旦masked features集合以随机方式选择，(h, g)必须从\(2^k\)个不同的masking patterns上抽样得到，这对于SSL任务会天然地导致不同效果。例如，SSL contrastive learning任务必须利用在两个增强样本间高度相关features的shortcut，这样可以使SSL任务太easy。

为了解决该问题，我们提出将features根据feature相关性进行分割，通过互信息进行measure。两个类别型features的互信息如下：

\[MI(V_i, V_j) = \sum\limits_{v_i \in V_i, v_j \in V_j} P(v_i, v_j) log \frac{P(v_i, v_j)}{P(v_i)p(v_j)}\]

…(4)

其中：

\(V_i, V_j\)表示它们的vocab sets。所有features的pairs的互信息可以被预计算好。

相关特征掩码（Correlated Feature Masking）

有了预计算好的互信息，我们提出Correlated Feature Masking (CFM)，对于更有意义的SSL任务，它会利用feature-dependency patterns。对于masked features的集合\(F_m\)，我们会寻找将高度相关的features一起进行mask。我们会：

• 首先从所有可能的features \(F=\lbrace f_1, \cdots, f_k \rbrace\)中，均匀抽样一个seed feature \(f_{feed}\)；
• 接着根据与\(f_{seed}\)的互信息，选择top-n个最相关的features \(F_c = \lbrace f_{c,1}, \cdots, f_{c,n} \rbrace\)。我们会选择\(n = \lfloor k / 2 \rfloor\)，以便关于features的masked set和retained set，会具有完全相同的size。我们会变更每个batch的seed feature，以便SSL任务可以学习多种masking patterns。

3.3 Multi-task训练

为了确保SSL学到的representations可以帮助提升主要监督任务（比如：回归或分类）的学习，我们会利用一个 multi-task training策略，其中：主要(main)监督任务和辅助(auxiliary) SSL任务会进行联合优化（jointly optimized）。准确的，

• \(\lbrace (q_i, x_i)\rbrace\)是一个关于query-item pairs的batch，它从训练数据分布\(D_{train}\)抽样得到；
• \(\lbrace x_i \rbrace\)是一个从item分布\(D_{item}\)抽样得到的items的batch；

那么，joint loss为：

\[L = L_{main} (\lbrace q_i, x_i) \rbrace) + \alpha \cdot L_{self} (\lbrace x_i \rbrace)\]

…(5)

其中：

• \(L_{main}\)：是main task的loss function，它可以捕获在query和item间的交叉
• \(\alpha\)：是regularization strength

不同样本分布（Heterogeneous Sample Distribution）

来自\(D_{train}\)的边缘item分布（The marginal item distribution）通常会遵循二八定律（power-law）。因此，对于\(L_{self}\)使用training item分布会造成学到的feature关系会偏向于head items。作为替代，对于\(L_{self}\)我们会从corpus中均匀抽样items。换句话说，\(D_{item}\)是均匀item分布。实际上，我们发现：对于main task和ssl tasks使用不同分布（Heterogeneous Distribution）对于SSL能达到更优效果来说非常重要。

图3 模型结构：带SSL的two-tower model。在SSL任务中，我们会在item features上使用feature masking和dropout来学习item embeddings。整个item tower（红色）会与supervised task共享

Main task的loss

对于依赖objectives的main loss来说有多个选择。在本paper中，对于优化top-k accuracy，我们考虑batch softmax loss。详细的，如果：

• \(q_i, x_i\)是关于query和item样本\((q_i, x_i)\)的embeddings（它会通过两个neural networks编码得到），

那么对于一个关于pairs \(\lbrace (q_i, x_i) \rbrace_{i=1}^N\)的batch和temperature \(\tau\)，batch softmax cross entropy loss为：

\[L_{main} = - \frac{1}{N} \sum\limits_{i \in [N]} log \frac{exp(s(q_i, x_i)/\tau)}{\sum\limits_{j \in [N]} exp(s(q_i, x_j) / \tau)}\]

…(6)

其它Baselines。如第2节所示，对于main task，我们使用two-tower DNNs作为baseline模型。对比起经典的MF和分类模型，two-tower模型对于编码item features具有独特性。前两种方法可以被用于大规模item检索，但他们只基于IDs学到item embeddings，不符合使用SSL来利用item feature relations。

4.离线实验

4.1

表1展示了wikipedia和AAI datasets的一些基础状态。图4展示了两个datasets的最高频items的CDF，它表示了一个高度倾斜的数据分布。例如，在AAI dataset中top 50 items会在训练数据中占据10%。

评估

https://dl.acm.org/doi/pdf/10.1145/3459637.3481952

阿里在《CAN: Feature Co-Action for Click-Through Rate Prediction》中提出了CAN模型：

3.CTR预估中的特征交叉

在广告系统中，一个user u在一个ad m上的点击的predicted CTR \(\hat{y}\)计算如下：

\[\hat{y} = DNN(E(u_1), \cdots, E(u_I), E(m_1), \cdots, E(m_J))\]

…(1)

其中：

• \(U= \lbrace u_1, \cdots, u_I\rbrace\)是包含了user features的集合，包含了：浏览历史、点击历史、user profile feature等。
• \(M=\lbrace m_1, \cdots, m_J \rbrace\)是：items features的集合
• User和Item features通常是unique IDs
• \(E(\cdot) \in R^d\)表示size d的embedding，它会将sparse IDs映射到可学习的dense vectors上作为inputs DNNs。

除了这些一元项（unary terms）外，之前的工作会将feture interaction建模成二元项（binary terms）：

\[\hat{y} = DNN(E(u_1), \cdots, E(u_I), E(m_1), \cdots, E(m_J), \lbrace F(u_i, m_j)\rbrace_{i \in [1,\cdots, I], j \in [1, \cdots, J]})\]

…(2)

其中：

• \(F(u_i, m_j) \in R^d\)表示了user feature \(u_i\)和item feature \(m_j\)之前的交叉。

模型可以从feature interaction受益，因为会存在feature共现性，如之前的示例：“啤酒与尿布”。因此，如何有效建模feature interaction对提升效性非常重要。

在仔细回顾之前方法，可以发现：不管是将feature interaction可以作为weights，还是同时学习隐式相关性和其它目标(满意度等)，都会产生不满意的结果。学习feature interaction的最直接方式是：将特征组合（feature combinations）作为新特征，并为每个特征组合直接学习一个embedding，例如：笛卡尔积（catesian product）。笛卡尔积可以提供独立的参数空间，因此对于学习co-action信息来提升预估能力来说足够灵活。

然而，存在一些严重缺点。

• 首先：存在参数爆炸问题。笛卡尔积的参数空间会产生size N的两个features，可以从\(O(N \times D)\)展开成\(O(N^2 \times D)\)，其中：D是embeddings的维度，它会对在线系统带来主要开销。
• 另外，由于笛卡尔积会将<A,B>和<A,C>看成是完全不同的features，在两个组合间没有信息共享，这也会限制representation的能力。

考虑到笛卡尔积和计算的服务有效性，我们会引入一种新方式来建模feature interaction。如图2(a)所示，对于每个feature pair，它的笛卡尔积会产生一个新的feature和相应的embedding。由于不同的feature pairs会共享相同的feature，在两个feature pairs间存在一个隐式相似度，这在笛卡尔积下会被忽略。如果隐式相似度可以被有效处理，在这些pairs间的feature interaction可以使用更小的参数规模进行有效和高效建模。受笛卡尔积的独立编码的启发，我们首先会将embedding的参数和feature interaction进行区分，以便避免相互干扰。考虑DNNs具有强大的拟合能力，我们会设计一个co-action unit，它可以以一个micro-network的形式对feature embeddings进行参数化。由于不同的feature pairs会共享相同的micro-network，相似度信息会被学到，并自然地存储到micro-network中，如图2(b)所示。

图2 从cartesian product到co-action network的演进，其中，A,B,C与D表示4种feature。\(N_A, N_B, N_C, N_D\)分别表示A,B,C,D的特征数目。h是feature embedding的维度，d是从co-action unit的output的维度。在图中，我们使用A与其它3个features进行交叉

4.Co-Action Network

在本节中，我们提出了CAN来有效捕获feature interaction，它会首先引入一个可插入的模块，co-action unit。该unit对于embedding和feature interaction learning的参数会进行区别。特别的，它会由来自raw features的两个side info组成，例如：induction side和feed side。induction side被用于构建一个micro-MLP，而feed side为它提供input。另外，为了提升更多非线性，以及深度挖掘特征交叉，多阶增强和multi-level独立性会被引入。

4.1 结构总览

CAN的整个结构如图3所示。

图3 Co-Action Network的整体框架。给定target item和user features，embedding layer会将sparse features编码成dense embeddings。一些选中的features会被划分成两部分：\(P_{induction}, P_{feed}\)，它它是co-action unit的组成部分。\(P_{induction}\)会将micro MLP进行参数化，\(P_{feed}\)则作为input使用。co-action unit的output，会与公共feature embeddings一起，被用来做出最终的CTR预估

一个user和target item的features U和M被会以两种方式feed到CAN中。

• 第一种方式下，他们会使用embedding layer被编码成dense vectors \(\lbrace E(u_1), \cdots, E(u_I)\rbrace\) 和 \(\lbrace E(m_1), \cdots, E(m_J) \rbrace\)，并分别进一步cancatenated成\(e_{item}\)和\(e_{user}\)。
• 第二种方式下，我们会从U和M中选择一个subset \(U_{feed}\)和\(M_{induction}\)，使用co-action unit来建模特征交叉：\(\lbrace F(u_i, m_j) \rbrace_{u_i \in U_{feed}, \ m_j \in M_{induction} \ }\)。

co-action unit的详细解释会在下一节详细介绍，CAN的公式如下：

\[\hat{y} = DNN(e_{item}, e_{user}, \lbrace F(u_i, m_j)\rbrace_{u_i \in U_{feed}, \ m_j \in M_{induction} \ }| \theta)\]

…(3)

其中：

• \(\theta\)表示在模型中的参数，
• \(\hat{y} \in [0, 1]\)是点击行为的预估概率

click信息的ground truth被表示为\(y \in \lbrace 0, 1 \rbrace\)。我们最终对prediction\(\hat{y}\)和label \(y\)间的cross-entropy loss function进行最小化：

\[\underset{\theta}{min} -y log(\hat{y}) - (1-y) log(1-\hat{y})\]

…(4)

4.2 Co-Action Unit

总的来说，co-action unit为每个feature pair提供一个独立MLP，称为micro-MLP，它的输入有：由feature pair提供的带weight、bias、MLP的input。

• 对于一个指定的user feature ID \(u_{o'} \in U_{feed}\)，我们使用参数查询（parameter lookup）来获得可学习参数 \(P_{induction} \in R^{D'}\)，
• 而对于item feature ID \(m_o \in M_{induction}\)对应获取的是\(P_{feed} \in R^D (D < D')\)

接着，\(P_{indction}\)会被reshape，为micro-MLP划分成weight matrix和bias vector。该process可以公式化成：

\[||_{i=0}^{L-1} (w_i \| b_i) = P_{induction} \\ \sum\limits_{i=0}^{L-1} (|w_i| + |b_i| = |P_{induction}| = D')\]

…(5)(6)

其中：

• \(w_i\)和\(b_i\)表示micro-MLP的第i个layer的weight和bias
• \(\|\)表示concatenation操作
• L决定了micro-MLP的深度
• \(\mid \cdot \mid\)则可以获得变量的size

该过程的可视化如图3左侧所示。

图3左

\(P_{feed}\)接着被feed到micro-MLP，特征交叉可以通过每个layer的output的concatentation来实现：

\[h_0 = P_{feed} \\ h_i = \sigma(w_{i-1} \bigotimes h_{i-1} + b_{i-1}), i=1,2,\cdots, L \\ F(u_{o'}, m_o) = H(P_{induction}, P_{feed}) = ||_{i=1}^L h_i\]

…(7)(8)(9)

其中：

• \(\bigotimes\)表示了矩阵乘法
• \(\sigma\)表示activation function
• H表示co-cation unit，它具有vector input \(P_{induction}\)和\(P_{feed}\)，而非使用原始符法F，它的inputs是features \(u_{o'}\)和\(m_o\)。

对于序列features，比如：用户行为历史 \(P_{seq} = \lbrace P_{b(t)} \rbrace_{t=1}^T\)，co-action unit会被应用到每个点击行为上，在序列后跟着一个sum-pooling：

\[H(P_{induction}, P_{seq}) = H(P_{induction}, \sum\limits_{t=1}^T P_{b(t)})\]

…(10)

在我们的实现中，\(P_{induction}\)会获得来自item features的信息，而\(P_{feed}\)则来自user features。然而，\(P_{feed}\)可以充当micro-MLP的参数，\(P_{induction}\)也一样。经验上，在广告系统中，candidate items是所有items的很小一部分，他们的数目要小于在用户点击历史中的items。这里，我们选择\(P_{induction}\)作为micro-MLP参数来减小总参数量，它使得学习过程更容易且稳定。

注意：micro-MLP layers的数目依赖于学习的难度。经验上，一个更大的feature size通常需要更深的MLP。实际上，FM可以被看成是CAN的一个特殊case，其中：micro-MLP是一层的1xD matrix，没有bias和activation function。

对比其它方法，提出的co-action unit具有至少三个优点：

• 首先，之前的工作使用的都是关于inter-field交叉的相同的latent vectors，而co-action unit则使用micro-MLP的计算能力，将两个组成特征\(P_{induction}\)和\(P_{feed}\)进行动态解耦，而非使用一个固定的模型，这提供了更多的能力来保证：两个field features的分开更新。
• 第二，可以学习一个更小规模的参数。例如：考虑上具有N个IDs的两个features，笛卡尔积的参数规模可以是：\(O(N^2 \times D)\)，其中，D是embeddings的维度。然而，通过使用co-action unit，该scale会递减到\(O(N \times (D' + D))\)上，而\(D'\)是在co-aciton unit中的\(P_{induction}\)的维度。更少参数不仅有助于学习，也可以有效减小在线系统的开销。
• 第三，对比起笛卡尔积，co-action unit对于新的特征组合具有一个更好的泛化。对比起笛卡尔积，给定一个新的特征组合（feature combination），只有在这之前，只要两侧embeddings在这之前被训练，co-action unit仍能工作。

4.3 多阶增强

之前的feature基于1阶features形成。然而，特征交叉可以通过高阶进行估计。考虑到micro-MLP的非线性，尽管co-action unit可以隐式学习高阶特征交叉，因为特征交叉的稀疏性导致学习过程很难。结尾处，我们会显式引入高阶信息来获得一个多项式输入。可以通过使用micro-MLP到\(P_{feed}\)的 不同阶上来实现：

\[H_{Multi-order}(P_{induction}, P_{feed}) = \sum\limits_{c=1}^C H(P_{induction}, (P_{feed})^C)\]

…(11)

其中：

• C是orders的数目

我们使用tanh来避免由高阶项带来的数目问题。多阶增强可以有效提升模型的非线性拟合能力，没需带来额外的计算和存储开销。

4.4 Multi-Level独立性

学习独立性是特征交叉建模的一个主要关注点。为了确保学习的独立性，我们提出了一种基于不同角度的3-level策略。

第一层，参数独立性，它是必需的。如4.2节所示，我们的方法会解决representation learning的更新和特征交叉建模。参数独立性是CAN的基础。

第二层，组合独立性，推荐使用。特征交叉会随着特征组合数目的增加而线性增长。经验上，target item features，如：“item_id”和”category_id”会被选中作为induction side，而user features则作为feed side。由于一个induction side micro-MLP可以使用多个feed sides进行组合，并且反之亦然，我们的方法可以轻易扩大模型指数的表达能力。

图4 组合独立性的演示

如图4所示，正式的，如果induction和feed sides具有Q和S个分组，特征交叉组合应满足：

\[|P_{induction}| = \sum\limits_{s=1}^S \sum\limits_{i=0}^{L_s - 1} (| w_i(s) | + | b_i(s) | ) \\ |P_{feed}| = \sum\limits_{q=1}^Q | x(q) |\]

…(12)(13)

其中，\(\mid x(q) \mid\)是第q个micro-MLP的input维度。在forward pass中，特征交叉被划分成几个部分来满足每个micro-MLP。

第3个level，阶数独立性，它是可选的。为了进一步提升特征交叉建模在多阶输入的灵活性，我们的方法会为不同orders做出不同的induction side embedding。然而，与等式（12）相似这些embedding的维度对于增加C倍。

multi-level独立性帮助特征交叉建模，同时，会带来额外的内存访问和开销。这需要在independence level和部署开销间进行tradeoff。经验上，模型使用越高的independence level，需要训练更多训练数据。在我们的实际系统中，independence的3个levels会被使用；而在公共数据集中，由于缺少训练样本，只有参数独立性会使用。

5. 实验

略

• 1.https://arxiv.org/pdf/2011.05625.pdf
• 2.https://github.com/CAN-Paper/Co-Action-Network

美团在《AutoFAS: Automatic Feature and Architecture Selection for Pre-Ranking System》中提出了AutoFAS的做法：

1.摘要

工业界搜索和推荐系统大多数遵循经典的multi-stage IR范式：matching、preranking、ranking和reranking stages。为了对系统效率负责，简单的vector-product based模型常被部署到preranking stage中。大多数工作会考虑将大的ranking模型的知识蒸馏到小的preranking模型中以便得到更好的效果。然而，在preranking系统中存在两个主要挑战：

• i) 无法显式建模效果增益 vs. 计算开销，预定义的延迟限制会导致次优解
• ii) ，将ranking teacher的知识转移一个预先手工制作的结构到的preranking student中，仍会有模型效果的损失

在本工作中，提出了一个新的框架AutoFAS，它会联合优化preranking模型的效率和效果：

• i) AutoFAS首先同步选择大多数有价值的features，网络结构使用NAS技术（Neural Architecture Search）
• ii) 在NAS过程中使用ranking model进行指导收益，对于一个给定的ranking teacher，AutoFAS可以选择最好的preranking架构，无需任何计算开销

在真实世界搜索系统中的实验结果，展示了AutoFAS的效果要比SOTA的方法更好，并且开销更低。注意，我们的模型已经在美团的搜索系统的preranking模块上使用，取得了巨大提升。

1.介绍

略

2.相关工作

略

3.方法

我们的工作构建在NAS（neural architecture search）之上，因而我们首先介绍下该主题。接着给出preranking的介绍以及详细介绍我们的方法。

3.1 Neural Architecure Search

Neural network设计通常需要人工专家们的大量经验。在最近几年，在研究算法NAS解决方案来将结构设计过程由人工转向自动化上取得了大量关注【1，15，37】。一些工作【1，22】尝试通过共享跨模型权重来提升搜索空间，它会进一步划分成两类：

• continuous relaxation方法【3，17】
• One-Shot方法 【2,8】

基本上，我们遵循weight sharing方法，它包含了三个steps：

• (1) 设计一个过参数化网络（overparameterized network），因为搜索空间包含了每个候选结构
• (2) 在training set或held-out validation set上直接作出结构决策
• (3) 对大多数有希望的结构从头到尾进行retrain，并在test set上验证它们的效果；

注意，在我们的场景和之前的结果间有一个大的不同之处是：我们需要同时联合搜索特征和结构。

3.2 搜索和推荐系统介绍

搜索和推荐系统的整体结构如图1所示。基本上，matching stage会从用户的动作历史、以及当前query中取出事件（如果存在）作为input，并从一个大的corpus（上百万）检索出一个小的items子集（上千）。这些与用户相关的候选通常具有适度准确性。接着，preranking stage会提供更大的个性化，过滤出具有高precision和高recall的近千个top items。一些公司会选择组合matching和preranking stages，比如Youtube【6】。接着，复杂的ranking network会根据期望的objective function，使用丰富的特征，为每个item分配一个score。在没有reranking的情况下，具有最高得分的items会根据得分排序展示给用户。通常，preranking会共享相似的ranking功能。最大不同点依赖于问题的scale。直接在preranking系统中使用ranking模型会面临计算开销问题。如何对模型效果和计算开销进行权衡是设计preranking的核心问题。

图1

3.3 美团Preranking的历史

之前提到，preranking模块可以被看成是一个在matching和ranking间的transition stage。在Meituan的主搜索上，它会接受来自matching阶段的上万个候选，并过滤出数百个结果给到ranking阶段。我们的底层preranking架构的演进：双塔模型、GBDT、当前的DNN模型。随着效果提升，大量的计算复杂度和大量存储使得它面临着更大的挑战。我们的online inference engine的瓶颈主要面临两部分：

• 从database的特征检索（feature retrieve）
• DNN inference

特征选择和神经网络结构选择对于成功部署高效且有效的preranking模型来说非常重要。

3.4 在Preranking中的特征选择和结构选择

我们的方法背后的一个关键动机是：我们应该联合构建preranking model以及ranking model，以便ranking model的知识可以自动指导我们为preranking model去发现最有价值的features和architechtures。因而，我们不会采用独立训练preranking models，而是会联合构建preranking model和常规的ranking model。我们首先描述了search space的构建，接着介绍：如何利用feature和architecture参数来搜索最有价值的features和architectures。

最终，我们会展示我们的技术来处理延迟以及KD-guided reward。

搜索空间

如图2所示，图的左半边是我们的ranking网络，而右半边是过参数化网络，它包含了所有的候选preranking models。这两部分会共享相同的input features \(F = \lbrace f_1, f_2, \cdots, f_M \rbrace\)。在我们的setup中，F主要包含了user features、item features以及interactive features。我们会使用所有的M个feature inputs来训练ranking model，接着将ranking model的大部分features进行归零（zero out）来评估它们的重要性，从而选出最好的特征组合。

图2 AutoFAS框架的网络结构。AutoFAS由两部分组成。左边子网络是：我们的具有feature mask module的常规ranking network。由于Meituan的搜索引擎会服务多个业务，它们具有重合的user groups和items，我们的ranking model具有multi-partition结构。右边子网络包含了L个Mixops，它包含了所有候选preranking结构。在每个Mixop中的最强operator会以黑色标注，构成了preranking model的最终结构。

与feature selection并行的是，我们需要搜索最优结构。假设O是一个building block，它包含了N个不同的候选操作符：\(O= \lbrace O_1, O_2, \cdots, O_N \rbrace\)。在所有case中，\(O\)包含了零操作符（zero operator）或具有多个hidden units的MLP。零操作符（zero operator）会保持input与output相同。一些参考里也将它称为等同操作符（identity operator）。注意，零操作符允许layers数目的减少。其它操作符比如外积、点乘可以被相似抽象并集成到框架中，这留给后续探讨。为了构建over-parameterzied network（它包含了每个候选结构），而非设置每个edge（网络连接）是一个明确的原始操作（definite primitive operation），我们设置每个edge（网络连接）是一个具有N个并行路径（paralled paths）的mixed operation（Mixop），表示为\(m_O\)。接着，我们的over-parameterzied network可以被表示为\(N(e_1 = m_O^1, \cdots, e_L = m_O^L)\)，其中L是Mixops的总数。

Feature和Architecture参数

为了选择大部分有效的features，我们会引入M个real-valued mask参数\(\lbrace \theta_i \rbrace_{i=1}^M\)，其中M是涉及的features数目。不像[5]中会对每个weights进行二值化（binairzes），我们会将整个feature embedding进行二值化。这里，每个feature \(f_i\)的独立的mask \(g_i\)会被定义成以下的Bernoulli分布：

\[g_i = \begin{cases} [1, \cdots, 1], & \text{with probability $\theta_i$} \\ [0, \cdots, 0], & \text{with probability $1-\theta_i$} \end{cases}\]

…(1)

其中：1s和0s的维度通过\(f_i\)的embedding维度来决定。会为样本的每个batch抽样M个独立Bernoulli分布结果。由于binary masks \(\lbrace g_i \rbrace_{i=1}^M\)会涉及计算图，feature参数\(\lbrace \theta_i \rbrace_{i=1}^M\)可以通过BP进行更新。

根据结构参数，我们会展示：在给定Mixop i的N个路径的outputs下，如何获得Mixop \(i+1\)的N个outputs？

图3 一个示例：通过递归方式计算每个Mixop的期望延迟。以上式中的\(T_{1024 \times 1024}\)为例。它意味着，一个multi-layer perceptron的延迟，具有输入维度1024和输出维度1024。它通过对我们的搜索引擎的真实请求进行回放（replay）到该特定网络结构中进行统计。图中的每个p是由等式(2)的operator strength。

如图3所示，Mixop i的路径表示为\(m_O^i = \lbrace O_1^i, O_2^i, \cdots, O_N^i\rbrace\)，我们会介绍N个real-valued结构参数\(\lbrace \alpha_j^{i+1} \rbrace_{j=1}^N\)。接着，Mixop \(i+1\)的第k个output计算如下：

\[O_k^{i+1} = \sum_{j=1}^N p_j^{i+1} MLP_j^k(O_j^i) \\ = \sum\limits_{j=1}^N \frac{exp(\alpha_j^{i+1})}{\sum_{m=1}^N exp(\alpha_m^{i+1})} MLP_j^k(O_j^i)\]

…(2)

其中:

• multi-layer perceptron \(MLP^k\)具有相同的units数目\(O_k^{i+1}\)
• \(p_j^{i+1} := \frac{exp(\alpha_j^{k+1})}{\sum_{m=1}^N exp(\alpha_m^{i+1})}\)可以被看成是在Mixop i+1中的第j个operator

在这种continuous relaxation后，我们的目标是：在所有mixed op中联合学习结构参数以及weight参数。

Latencey Constraint

除accuracy外，当设计preranking系统时，latency（not FLOPs或embedding维度）是另一个非常重要的目标。为了让latency不同，我们会将一个网络的latency建模为一个关于neural network结构的continous function。在我们的场景中，存在两个因子：feature相关的latency和结构相关的latency。features可以被进一步从latency的角度划分成两个类别：从matching stage传来过的、以及从in-memory dataset中检索过来的，分别表示成 \(F_1\)和\(F_2\)。如上，我们有关于一个指定特征\(f_i\)的期望latency：

\[E[latency_i] = \theta_i \times L_i\]

…(3)

其中：

• \(L_i\)是返回时间（return time），它可以被服务器记录。

接着，\(E[latency_i]\)的随结构参数的梯度可以给定：\(\frac{\partial E[latency_i]}{ \partial \theta_i} = L_i\)。接着，期望的feature相关latencey可以以如下方式计算：

\[E[latency] = max_{f_i \in F_1, f_j \in F_2} (E[latency_i] + \beta \cdot |F_1|, E[latency_j] + \gamma \cdot |F_2|)\]

…(4)

其中：

• \(F_k\)表示了在\(F_k, k=1, 2\)的features数目
• \(\beta, \gamma\)影响着底层系统的不同并发数，可以由经验决定

我们将这种expected feature latency包含到常规loss function中，乘以一个scaling因子\(\lambda\)，它会控制着在accuracy和latency间的tradeoff。对于feature selection的最终的loss function为：

\[Loss_1 = Loss_{Ranking} (y, f(X; \theta, W_{Ranking})) + \lambda E[latency]\]

…(5)

其中，f表示ranking network。

相似的，对于Mixop i+1的结构latency，我们可以通过递归来计算它的expected latency \(E[latency^{'i+1}]\)，如图3的右图所示。由于这些ops可以在inference期间按顺序执行，preranking network的expected latency可以被表示为last Mixop的expected latency：

\[E[latency'] = E[latency'^{L}]\]

Ranking系统的监督

知识蒸馏（KD），会将teacher model的泛化能力转移给student model，受广泛关注。而在监督学习中的常规的one-hot label被限定在0/1 label内，从teacher model的soft probability output会对student model的知识有贡献。记住，在preranking系统中当前KD方法的一个缺点是：如果它只能将teacher的知识转移给具有确定网络结构的student。受AKD的启发，我们提出添加一个distillation loss给结构搜索过程（architecture search）。特别的，我们会采用由ranking models产生的soft targets作为监督信号来指导每个Mixop的选择。因此对结构选择的final loss function：

\[Loss2 = (1-\lambda_1) Loss_{pre-Ranking}(y, g(X; \theta, \alpha, W_{pre\-Ranking})) + \lambda_1 || r(x) - p(x)||_2^2 + \lambda_2 E[latency']\]

…(7)

其中，g是preranking network，\(Loss_{pre\-Ranking}\)表示使用已知hard labels y的pre-ranking pure loss。r(x)和p(x)分别是关于ranking和preranking network的final softmax activation outputs。

我们会进一步讨论\(\lambda_1\)的效果和第4.5节中的distilation loss。\(\lambda_2\)是scaling factor，它控制着在accuracy和latency间的tradeoff。Loss1和Loss2会一起优化，产生最终的multi-task loss function：

\[Loss = Loss1 + Loss2\]

…(8)

在Loss1和Loss2间的超参数的权衡的缺失来自于：Loss1只会最优化feature mask参数，而Loss2会最优化preranking model中的结构参数和weights。我们选择该策略是因为，它在经验上要好于没有gradient block的模型，如表5所示。Loss1和Loss2相互相关，Loss2的输入是masked embedding，其中：mask参数会通过Loss1在训练期间持续优化。为了获得最终的preranking结构，我们会保留在每个Mixop中的最强的features和operators，从头到尾都保留它。AutoFAS的整个训练过程如算法1所示。

算法1

4.实验

略

• 1.https://dl.acm.org/doi/pdf/10.1145/3534678.3539083