meituan在《Enhancing Personalized Ranking With Differentiable Group AUC Optimization》中提出了PDAOM loss：

抽要

AUC是评估classifier效果的一个常用指标。然而，大多数分类器使用cross entropy训练，它不会直接最优化AUC metric，这在training和evaluation间会存在一个gap。这里提出的PDAOM loss：一个最大化violation的个性化可微AUC最优化方法（Personalized and Differentiable AUC Optimizationy method with Maximum violation）, 当训练一个二分类器时可以直接应用，并使用gradient-based方法进行最优化。特别的，我们会使用通过user ID group在一起的sub-batches内的不同的（neg, postive）pair样本，来构建了pairwise exponential loss，目标是指导分类器关注：在独立用户视角下，很难区分的正负样本对间的关系。对比起pairwise exponential loss的原始形式，提出的PDAOM loss不仅会提升在离线评估中的AUC和GAUC metrics，也会减少训练目标的计算复杂度。再者，在“猜你喜欢”的feed推荐上，PDAOM loss的在线评估可以获得在点击数上 1.4%的提升，在订单数上获得0.65%的提升，这在online life service推荐系统上是个显著的提升。

1.介绍

二分排序(Bipartite ranking)在过去受到了大量关注，在工业应用中被广泛使用。它的目标是：学习一个模型，使得正样本的排序高于负样本。不失一般性，我们以推荐系统为例，并详述二分排序。根据一个用户的历史行为统计，推荐系统会提供一个关于items的有序列表，其中，感兴趣的items会出现在不感兴趣的items之前。达到该目标的关键思想是：为每个item预估CTR。用户浏览过但没有点击的items会被标记为负样本，点击过的items会被标记为正样本。接着，CTR预估模型可以被训练成一个二分类器，并使用 cross entropy进行最优化。这种方式下，每个样本会被独立对待，并且在训练期间，正负样本间的限制关系不会被引入。另一个关注点是：对比起用户看过的items，clicked items只占一小部分。因而，模型的效果基本上使用AUC metric进行评估，其中数据分布是imbalanced的。AUC会measures：对于一个随机抽样的正例的score，它要比一个随机抽样的负例score具有更高分的概率。然而，在训练期间cross entropy目标，不会完全与evaluation期间的目标完全对齐。实际上，一个常见现象是，当训练loss减少时AUC metric不会增加，在工业界推荐数据集上训练的一个示例如图1所示。它会启发我们，在训练期间直接对AUC metric进行最优化。

图1 loss曲线和AUC metric随training steps的变化，其中AUC metric不总是随loss的减少而增加

另一个大问题是：推荐系统经常面对“长尾”现象，例如：一小部分商品会占据着大量的销售额。图2展示了来自Meituan电商的统计数据。我们根据它们的订单质量将商品分为100 bins，并绘制出top 30 bins。我们可以看到，top 1 bin的商品贡献了37%的订单，top 20 bins的商品贡献了80%的订单。如果我们使用这样不均衡的数据来训练一个CTR预估模型，该模型会趋向于分配更高得分给热门商品，即使一些用户可能不喜欢这些items，这在个性化预估上会降低模型效果。Group AUC【19】是一个合理的metric，用于评估一个ranking model的个性化推荐能力。它会通过user ID进行分组，计算各个sets中的AUC，并每个set的结果进行平均。经验上，对比起AUC metric，离线的GAUC metric会与在线效果更一致些，进一步启发我们在训练ranking model时将GAUC metric加入到objective中。

图2 在美团电商中的长尾现象。top bins中的商品贡献了大比例的订单

然而，有两个原因阻止我们直接最优化AUC metric。

• 一方面，AUC metric会通过一个binary indicator函数的总和来计算，它是不可微的。因而，gradient-based optimization方法不能应用于该问题中。
• 另一方面，AUC的公式会考虑上每个postive/negative样本对，会导致时间复杂度上升到\(O(N^+ N^-)\)，它在实际工业推荐场景中是不可接受的，通常会是数十亿阶。

该问题上做了大量研究：

• 对于前者：对于原始AUC公式，最近工作尝试替代可微替代目标函数（differentiable surrogate objective function）。【18】提出了使用它的convex surrogate（例如：hinge loss function）来替代indicator function。【2】设计了一个regression-based算法，它使用pairwise squared objective function，用于measure在不同分类的两个实例间的ranking errors。【3】研究了基于最优化pairwise surrogate objective functions的AUC一致性
• 对于后者：mini-batch 最优化策略可以使得处理大规模数据集。为了将AUC最大化方法应用于data-intensive场景，我们会研究以mini-batch方式最优化它。

特别的，我们提出了PDAOM loss，它关注于难区分的正负样本对，而非将所有组合考虑在内。该trick不仅会提升offline效果，也会减小最优化的复杂度。

2.相关工作

略

3.方法

A.前提

AUC的原始定义与ROC curve有关。假设分类器会生成一个连续值，用于表示输入样本是postive的概率，接着需要一个决策阈值来决定：样本是该标记成postive还是negative。对于每个阈值来说，我们可以获得一个true-postive rate和false-postive rate的pair。通过将该阈值从0到1进行遍历，我们绘制出获得的rates的pairs，就生成了ROC曲线。因而，通过对ROC曲线的下面面积计算均值的AUC metric是很复杂的。AUC的一个等价形式是：归一化的Wilcoxon-Mann-Whitney (WMW)统计：

\[AUC = \frac{\sum\limits_{i=0}^{m-1} \sum\limits_{j=0}^{n-1} \mathbb{1} (f(x_i^+) > f(x_j^-))}{mn}\]

…(1)

其中：

\(\lbrace x_i^+ \rbrace\)和\(\lbrace x_j^- \rbrace\)分别是postive和negative样本的集合。由于indicator function是不可微的，WMW统计不能使用gradient-based算法进行最优化。它启发我们寻找一种可微的surrogate objective function，用于替代WMW statistic。也就是说，获得surrogate function的最优解等价于最大化AUC metric。我们将使用将surrogate的objective function公式为：

\[\underset{x^+ \sim P^+, \\ x^- \sim P^-}{E} (\phi(f(x^+) - f(x^-)))\]

…(2)

其中：

• \(\phi\)是surrogate function，一些常用的示例如表1所示。
• \(P^+, P^-\)分别表示正负样本分布

表1 常用的surrogate function，当成AUC的indicator

在本paper中，我们出于两个原因会使用pairwise exponential loss 作为surrogate。

• 首先，【3】中已经证明，pairwise exponential loss与AUC一致。
• 第二，我们会对比在我们的先决实验列出的surrogates，并发现pairwise exponential loss要胜过离线评估（如表4所示）

表4

B. AUC Optimization with Maximum Violation

上述提到的surrogate objective function存在两个主要缺点：

• 一方面，这样的objective会等价地关注于每个pair，因而，分类器会花费大量精力在建模易区分的正负样本对关系上。
• 另一方面，对于一个batch数据，它包含了\(N^+\)的正样本和\(N^-\)的负样本，处理每个pair的复杂度是\(O(N^+ N^-)\)，它对于一个大batch-size来说是很耗时的。

聚焦于上面的问题，我们提出构建难样本对，并让模型关注于难样本对，而非所有样本对。一个难样本对指的是：模型很难区分正/负样本labels的实例。因而，对于这样的正负样本对，输出scores是很接近的，它使得决策边界不好判断。考虑：

\[\underset{x^+ \sim P^+ \\ x^- \sim P^-}{E} (\phi(f(x^+) - f(x^-))) \leq \underset{x^+ \sim P^+ \\ x^- \sim P^-}{max} ( \phi(f(x^+) - f(x^-)))\]

…(3)

（3）的一个可行解是：设置 \(\underset{x^+ \sim P^+, \\ x^- \sim P^-}{max}(\phi(f(x^+) - f(x^-)))\)作为objective function。计算该最大值只依赖于那些很可能有violate relation的正负样本对。在该方式下，来自easy negatives的loss累积不会影响模型的更新。尽管这样的转换会导致模型关注于确定决策边界，复杂度仍然是\(O(N^+ N^-)\)。由于\(f(x^+) - f(x^-) \in [-1, 1]\)，surrogate function \(\phi\)会在该区间内单调递减。相等的，\(\underset{x^+ \sim P^+ \\ x^- \sim P^-}{max} (\phi(f(x^+) - f(x^-)))\)可以简化为：

\[\phi (\underset{x^+ \sim P^+ \\ x^- \sim P^-}{min}(f(x^+) - f(x^-))) = \phi( \underset{x^+ \sim P^+}{min} f(x^+) - \underset{x^- \sim P^-}{max} f(x^-))\]

…(4)

理想的，一个正样本的最低分期望会高于在一个batch内负样本的最高分。我们将DAOM loss定义为：

\[L_{DAOM} = \phi( \underset{x^+ \sim P^+}{min} f(x^+) - \underset{x^- \sim P^-}{max} f(x^-))\]

…(5)

注意，我们只会选择具有最高score的正样本，以及具有最低score的负样本，构建pair的复杂度会减小到 \(O(N^+ + N^-)\)。

通过GAUC最优化来增强个性化排序

以上章节详述了如何构建在一个batch内的paired samples，但它满足不了个性化推荐的需求。实际上，我们会发现，GAUC[19] metric与在线效果更一致些。相应的，一个天然的想法是，当最优化模型时，将GAUC metric添加到objective中。考虑GAUC指标的原始计算，样本会首先被分成多个groups。在本context中，groups会被通过user ID进行划分。接着，AUC metric会分别在每个group中计算，GAUC metric会通过将所有groups的AUC metrics进行加权平均得到。weight与曝光或点击次数成比例，这里我们对所有用户将weight设置为1。我们会在训练阶段模拟GAUC的计算：

• 当准备训练数据时，我们会根据每个样本的user ID对样本进行排序，以便属于同一个用户的样本会出现在相同的batch中
• 一个batch的数据可能会包含许多不同的user IDs，我们将batch划分成sub-batches，在sub-batch中的user ID是相同的

接着我们应用DAOM loss到每个sub-batch中，并将个性化DAOM loss定义为：

\[L_{PDAOM} = \sum\limits_{u \in U} \phi( \underset{x^+ \sum P_u^+}{min} f(x^+) - \underset{x^- \sim P_u^-}{max} f(x^-))\]

…(6)

其中，U表示由user ID分组的sub batches。在训练一个二分类器的条件下，提出的PDAOM loss与cross entropy一起来形成最终的objective function：

\[L = -y log(f(x)) - (1-y) log(1 - f(x)) + \lambda \sum\limits_{u \in U} \phi( \underset{x^+ \sim P_u^+}{min} f(x^+) - \underset{x^- \sim P_u^-}{max} f(x^-))\]

…(7)

其中：y是label，\(\lambda\)会对cross entropy和PDAOM loss的weight进行balance。

实验

略

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

google在2021年的《Learning to Embed Categorical Features without Embedding Tables for Recommendation》中提出了一种Deep Hashing Embedding方法来编码categorical feature：

摘要

分类特征（例如user/item ID）的embedding learning是各种推荐模型的核心。标准方法是创建一个embedding表，其中每一行代表每个唯一特征值的专用嵌入向量（dedicated embedding vector）。然而，这种方法无法有效处理高基数特征（high-cardinality features）和在现实世界推荐系统中普遍存在的未见过的特征值（例如新的视频ID）。在本文中，我们提出了一种替代嵌入框架——深度哈希嵌入（DHE：Deep Hashing Embedding），通过深度嵌入网络动态计算嵌入，取代了embedding table。DHE首先使用多个哈希函数和转换将特征值编码为唯一标识符向量，然后应用深度神经网络（DNN）将标识符向量转换为embedding。编码模块是确定性的、不可学习的，并且无需存储，而嵌入网络在训练期间更新以学习生成嵌入。

实证结果表明，DHE在模型尺寸更小的情况下，与标准的独热满嵌入（one-hot full embedding）达到了可比的AUC。我们的工作为设计不使用嵌入表查找的基于DNN的分类特征替代嵌入方案提供了新的见解。

1. 引言

机器学习在建模各种数据类型方面具有高度的通用性，包括连续特征、稀疏特征和序列特征。在这些特征中，我们专注于改进大词汇量分类特征的嵌入学习。具体来说，我们假设：一个分类特征由词汇表𝑉定义，其中特征值是𝑉中的（确切的）一个元素。例如，ID特征通常是分类特征，其中每个特征值是一个唯一ID（例如视频ID）。另一个例子是“设备”特征，“iPhone 12”是一个可能的特征值。

嵌入学习已经成为建模分类特征的核心技术，并已被采用在各种模型中，如矩阵分解（MF）[28]和word2vec[24]。嵌入学习技术极大地帮助我们理解特征值（例如单词）的语义含义。embedding还已成为深度模型捕获特征值之间更复杂交互的基石（例如BERT[7]，DeepFM[10]）。

尽管嵌入学习在自然语言处理（NLP）[24]等多个领域取得了成功，但在推荐系统中应用嵌入学习时存在几个挑战：

• 巨大的词汇量size：推荐系统通常需要处理高基数的分类特征（例如，在线视频分享平台的视频ID可能达到数十亿）。此外，在自然语言处理（NLP）任务中，单词的词汇量通常较小（例如，高级模型BERT[7]只有30K个标记的词汇表），这是由于常用的子词分割[29]技术用于减少词汇量。但是，将这种方法应用于推荐系统中的分类特征通常是不可行的.
• 输入的动态性质：与相对静态的单词词汇表不同，推荐系统中的Vocabulary table可能高度动态。新user和新item每天都在进入系统，而过时的item逐渐消失.
• 高度偏斜的数据分布：推荐数据中的分类特征通常遵循高度偏斜的幂律分布。少量具有不频繁特征值的训练样本会显著影响长尾item的embedding质量。

独热编码（one-hot encoding）广泛用于嵌入学习，它将一个特征值映射到一个one-hot向量，然后查找嵌入表中的嵌入向量。然而，one-hot表示通常会导致巨大的嵌入表，特别是对于大词汇量特征，同时它也未能适应词汇表外的特征值。在大规模网络推荐系统中，大部分参数都在embedding table上，而神经网络本身只占很小一部分参数[5]。在实践中，为了更好地处理新的（即词汇表外/未见过的）特征值并降低存储成本，通常采用hashing trick[36]，它随机地将特征值映射到较少数量的哈希桶中，尽管不可避免的嵌入冲突通常会损害性能。本质上，这些嵌入方法可以被视为一个1层宽度的神经网络（即嵌入表）带有one-hot编码。

在本文中，我们寻求探索一种深度、狭窄且无冲突的嵌入方案，而不使用embedding table。我们提出了深度哈希嵌入（DHE）方法，使用密集编码(dense encodings)和一个深度嵌入网络来动态计算embedding。这完全取代了传统的embedding table。

具体来说，我们使用多重哈希和适当的转换来为给定特征值生成唯一的、确定的、dense real-valued的向量作为标识符编码（identifier encoding），然后深度嵌入网络将编码转换为最终的特征embedding。特征嵌入随后被送入推荐模型（例如MF或深度推荐模型）进行端到端训练。

图1展示了标准基于one-hot embedding与DHE之间的比较。

图1 一个基于one-hot的full embedding和深度哈希嵌入（DHE）的示意图，用于为200万个ID生成32维嵌入。维度数字来自我们的实验，以提供一个具体的例子。这两种模型达到了接近的AUC，而DHE的size仅为full模型的1/4。DHE使用密集哈希编码来为每个特征值获得一个唯一标识符，并应用深度嵌入网络来生成特征嵌入。DHE不执行任何嵌入查找

我们的主要贡献如下所示：

• 我们分析了各种嵌入方法，包括针对categorical特征的hashing-based的方法。与严重依赖one-hot编码的现有方法不同，我们通过多重哈希将每个特征值编码为唯一的dense编码向量，这是完全去除大词汇量特征的巨大嵌入表的第一步
• 通过dense编码，我们用深度嵌入网络取代了常用的embedding loopup（本质上是一个浅层且宽的网络），这样做在参数上更高效
• 我们还解决了可训练性和表达能力问题，以提高embedding生成的能力
• 我们提出了基于上述编码和深度嵌入网络的深度哈希嵌入（DHE）。我们进一步改进DHE，通过在编码中整合侧特征，使其更好地泛化到特征值和新值

我们在两个具有大词汇量分类特征的推荐任务基准数据集上进行了广泛的实验。我们与最先进的模型进行了比较，并分析了DHE中各种关键组件的效果。结果表明，DHE是one-hot full embedding的一个有前景的替代方案。

我们首先从神经网络的角度讨论了各种现有的基于one-hot的嵌入方法。然后我们介绍了DHE的密集哈希编码（dense hash encodings）、深度嵌入网络（deep embedding network）、以及使用side features以获得更好编码的扩展方法，在我们呈现实验结果之前。最后，我们讨论相关工作，总结我们的论文，并指出未来工作的有前景的方向。

2.one-hot based embedding learning

嵌入学习的核心思想是将特征值映射到一个𝑑维连续空间中。这些可学习的嵌入可以被浅层模型如word2vec[24]或MF[28]直接使用，以衡量两个特征值之间的相似性（例如，相似单词的嵌入之间的大内积）。此外，像DeepFM[10]或BERT[7]这样的深度模型，可以通过考虑embedding之间的交叉来建模更复杂的结构。

我们定义了一个通用框架，用于描述各种现有的嵌入方法以及我们提出的方法。

• 嵌入函数：$T : 𝑉 → 𝑅^𝑑$：它将一个特征值（来自大小为$|𝑉| = 𝑛$的词汇表𝑉）映射到嵌入向量$e \in R^𝑑$。

一般来说，嵌入函数可以分解为两个组件：$T = F \circle E$，其中：

• E是一个编码函数，用于在某些空间中表示特征值
• F是一个解码函数，用于生成嵌入向量v

在本节中，我们介绍了基于one-hot编码的全嵌入（full embedding）和基于哈希的嵌入（hashing embedding）方案。相关符号总结在表9中。

2.1 One-hot Full Embedding

这是最直接且最常用的嵌入分类特征的方法，它为每个特征值分配了一个在嵌入表中唯一的𝑑维嵌入。具体来说，编码函数𝐸将一个特征值映射到一个独特的one-hot向量。在离线设置中，即使特征值是非数值类型（如字符串，例如分类特征“国家”的特征值“日本”或“印度”），这也很容易实现，因为我们可以从特征值到$\lbrace 1, 2, …, 𝑛 \rbrace$获得一对一的映射。

因此，我们假设特征值已经被映射到$\lbrace 1, 2, …, 𝑛 \rbrace$，然后嵌入方法创建了一个嵌入表$W \in R^{𝑛 \times 𝑑}$，并查找其第s行$W_𝑠$以获取特征值𝑠的嵌入。这相当于以下步骤：

• (i) 我们应用编码函数𝐸，使用one-hot编码向量对特征值𝑠进行编码：$𝐸(𝑠)=b \in \lbrace 0, 1 \rbrace^𝑛$，其中：$𝑏_𝑠=1$且$𝑏_𝑗=0(𝑗 \neq 𝑠)$
• (ii) 然后我们应用解码函数𝐹，一个可学习的线性变换$W ∈ R^{𝑛×𝑑}$来生成嵌入e，即$e = 𝐹(b) = W^T b$。

简而言之，embedding lookup过程可以被视为一个基于one-hot编码的1-layer神经网络（无bias项）。

2.2 One-hot Hash Embedding

尽管full embedding简单且有效，但在大规模或动态设置中存在两个主要问题：

• (i) 嵌入表的大小与词汇量大小线性增长，可能导致巨大的内存消耗。例如，仅用于10亿视频ID的100维嵌入就占用了接近400GB的内存；
• (ii) 在新值不断出现的在线学习环境中，full embedding方案无法处理未见过的（词汇表外的）特征值。为了解决上述问题，已经提出了各种基于哈希的方法（例如[30, 34, 36]），并在生产规模系统中广泛使用，用于处理大词汇量和词汇表外的分类特征（例如Youtube[37]和Twitter[38]）。

hasing trick[36]是一种代表性的哈希方法，用于减少大型词汇量的one-hot编码的维度。编码函数𝐸仍然将特征值映射到一个one-hot向量（但是使用通常更小的基数𝑚）:

\[𝐸(s) = b \in \lbrace 0, 1 \rbrace^𝑚\]

其中：

• $𝑠 \in 𝑉, 𝑏_{𝐻(𝑠)}=1$, 且$𝑏_𝑗=0 (𝑗 \neq 𝐻(𝑠))$
• 𝐻：为哈希函数，将特征值（包括未见过的值）映射到{1, 2, …, 𝑚}上，其中𝑚是哈希后词汇量的size

哈希函数𝐻试图尽可能均匀地分配哈希值以减少冲突，尽管当$𝑚 < 𝑛$时这是不可避免的。类似地，解码函数返回embedding table的第𝐻(𝑠)行。总之，hashing trick使用哈希将特征值映射到𝑚维one-hot向量，然后应用1层网络来生成嵌入。

3 深度哈希嵌入（DHE）

如前一节所介绍的，无论是full embedding还是hashing-based embedding方法，本质上都是基于one-hot编码和浅层网络。在本节中，我们提出了深度哈希嵌入（DHE），这是一种用于在大词汇量或动态设置中进行嵌入学习的替代方案。DHE使用real-valued dense编码和深度神经网络来生成embedding，无需任何embedding lookup。

遵循编码和解码的嵌入框架（T = F ◦ E），我们提出了几个设计良好编码的属性，然后介绍我们的编码函数E和DHE中的解码函数F，接着是增强side features的编码设计，以实现泛化。

3.1 编码设计

如果我们没有对特征值的任何先验知识，那么怎样才算是一个良好的编码？这是我们在本节中研究的核心问题，它也引出了我们的DHE的编码设计。我们得到了具备以下良好编码属性的设计：

• 唯一性：编码对于每个特征值应该是唯一的。这也是full embedding和多重哈希方法（multiple hashing）的目标。否则，就会有特征值不得不共享相同的编码。冲突的编码使得后续的解码函数无法区分不同的特征值，这通常会损害模型性能。
• 相等相似性(Equal Similarity)：我们认为只有唯一性是不够的。一个例子是二进制编码，它使用二进制表示作为整数（例如ID）的编码：例如，$𝐻(9)=[1, 0, 0, 1]$。我们可以看到，与$𝐻(7) = [0, 1, 1, 1]$相比，$𝐻(8)=[1, 0, 0, 0]$与𝐻(9)更为相似。我们认为：这引入了一个错误的归纳偏差（inductive bias：即ID 8和ID 9更相似），可能会误导后续的解码函数。双重哈希（double hashing）存在类似的问题：在某个哈希函数中发生冲突的两个特征值的编码，比在两个哈希函数中都没有冲突的两个值的编码更相似。由于我们不知道分类特征之间的语义相似性，我们应该使任意两个编码的相似性相等，不引入任何归纳偏差。
• 高维度（High dimensionality）：我们希望编码对于后续的解码函数来说易于区分不同的特征值。由于高维空间通常被认为更可分（例如，核方法），我们相信编码维度也应该相对较高。例如，one-hot编码具有极大的维度（full embedding的𝑛和hashing embedding的𝑚）。另一个例子是身份编码(identity encoding)，它直接返回ID号码：例如，$𝐸(7) = [7]$。尽管这为每个ID提供了一个唯一的编码，但对于后续的解码函数来说，基于1维编码生成嵌入将是极其困难的。
• 高香农熵：香农熵[31]（以“比特”为单位）衡量一个维度中携带的信息。高熵的要求是从信息理论的角度防止冗余维度。例如，一个编码方案可能满足上述三个属性，但在某些维度上，所有特征值的编码值都是相同的。因此，我们希望通过在每个维度上最大化熵来有效利用所有维度。例如，one-hot编码在每个维度上的熵非常低，因为对于大多数特征值来说，任何维度上的编码都是0。因此，one-hot编码需要极高的维度（即𝑛），并且效率极低。编码属性的正式定义和分析可以在附录中找到，我们总结的结果在表2中。

3.2 稠密哈希编码（Dense Hash Encoding）

在分析了各种编码方案的属性之后，我们发现没有任何现有的方案能满足所有期望的属性。特别是我们发现，非独热编码（non-one-hot：如二进制和身份编码）虽然摆脱了embedding table，但未能满足相等相似性和高维度属性。受到这一点的启发，我们提出了稠密哈希编码（Dense Hash Encoding），旨在结合上述编码的优势并满足所有属性。

不失一般性，我们假设特征值是整数（integers），因为我们可以利用字符串哈希将字符串(strings)值映射为整数(integers)（由于输出空间很大（64位整数约有$2^64$个值），基本上不会发生冲突。一个例子是CityHash64：https://github.com/google/cityhash）。所提出的编码函数为：$𝐸 : N \rightarrow R^k$

它使用k个通用哈希函数将一个特征值映射到一个k维dense real-valued encodings上。具体来说，我们有：

\[𝐸′(𝑠) = [𝐻^{(1)}(𝑠), 𝐻^{(2)}(𝑠), \cdots, 𝐻^{(k)}(𝑠)]\]

其中：

• $𝐻(i) : N \rightarrow {1, 2, …, m}$

请注意，在这种情况下，m与embedding table无关，我们只需要将其设置为一个相对较大的数字（在我们的实验中是$10^6$）。通用哈希[4]（hashing）的一个优良属性是：哈希值在$\lbrace 1,2,\cdots,m \rbrace$上均匀分布（平均而言）。

通过适当的转换，我们可以获得实值编码，因为输入通常是实值的，为了数值稳定性进行归一化：$𝐸(𝑠) = transform(𝐸′(𝑠))$。我们考虑逼近以下几种常用的分布：

• 均匀分布。我们简单地将编码$𝐸‘$归一化到[-1, 1]的范围。由于哈希值在$\lbrace 1, 2, …, m \rbrace$中平均分布均匀，因此这在较大的m情况下可以合理地近似均匀分布𝑈(-1, 1)。
• 高斯分布。我们首先使用上述转换获得均匀分布的样本，然后应用Box-Muller变换[3]，将均匀分布的样本（即𝑈(-1, 1)）转换为标准正态分布N(0, 1)。具体实现请参见附录。

这两种分布的选择部分受到生成对抗网络（GANs）[9]的启发，GANs通常从均匀或高斯分布中抽取随机噪声，然后将其输入神经网络进行图像生成。请注意，转换（和哈希）是确定性的，这意味着编码（对于任何特征值）不会随时间变化。我们从经验上发现这两种分布在效果上类似，因此出于简单起见，默认选择均匀分布。

与现有仅限于几个哈希函数的hashing方法不同，我们选择了一个相对较大的k来满足高维度属性（在我们的实验中k=1024，尽管它比n显著小）。我们从经验上发现，与现有哈希方法相比，我们的方法从更大的k中显著受益。此外，所提出的密集哈希编码也满足其他三个属性。更多分析可以在附录中找到。

请注意，整个编码过程不需要任何存储，因为所有的计算都可以即时完成。这也是使用多重哈希的一个优良属性，因为我们获得了一个更易于区分的高维编码，而没有存储开销。从计算角度来看，时间复杂度是𝑂(𝑘)，每个哈希的计算是独立的，因此适合并行化和硬件如GPU和TPU。例如，我们使用整数的通用哈希[4]作为底层哈希，并在附录中的算法2中描述了编码过程。其他通用哈希（例如针对字符串的）也可以采用来处理不同的特征类型。

3.3 深度嵌入网络

在DHE中，解码函数$𝐹 : R^k \rightarrow R^d$需要将一个k维编码向量转换为一个d维嵌入。显然，实值编码不适用于embedding lookup。然而，映射过程非常类似于一个高度非线性的特征转换，其中输入特征是固定且不可学习的。因此，我们使用强大的深度神经网络（DNN）来模拟这样的复杂转换，因为DNN是表达能力强的通用函数逼近器[23]。此外，最近的一项研究表明，更深的网络比浅层网络更具参数效率[21]，因此DHE可以相比one-hot full embedding（一个1层浅层网络）减少模型大小。

然而，即使使用DNN，转换任务也极具挑战性。本质上，DNN需要在其权重中记忆信息（之前存储在巨大的嵌入表中）。我们希望层次结构和非线性激活可以使DNN比one-hot编码（即1层宽的NN）更有效地表达embedding函数。这是由最近的研究激发的，该研究表明深度网络可以比宽而浅的网络使用更少的参数来近似函数[21]。

具体来说，我们使用一个前馈网络作为DHE的解码函数。

• 我们通过h个隐藏层（每层有$𝑑_{NN}$个节点）转换k维编码。
• 然后，输出层（有𝑑个节点）将最后一层隐藏层转换为d维特征值嵌入。
• 在实践中，$𝑑_{NN}$由内存消耗费用决定。

我们可以看到DNN中的参数数量是：

\[𝑂(𝑘 * 𝑑_{NN} + (ℎ −1) * 𝑑_{NN}^2 + 𝑑_{NN} * 𝑑)\]

这与𝑛或𝑚无关。这也是DHE的时间复杂度。DHE的一个独特特点是：它不使用任何embedding lookup，而是完全依赖隐藏层来即时记忆和计算embedding。

然而，我们发现训练深度嵌入网络相当具有挑战性（相比之下，基于one-hot的浅层网络更容易训练）。我们观察到训练和测试性能较差，据推测是由于可训练性和表达能力问题。表达能力问题相对独特于我们的任务，因为NN通常被认为表达能力强且容易过拟合。然而，我们发现在我们的案例中，embedding网络是欠拟合而不是过拟合，因为从hash encoding到embedding的嵌入生成任务需要高度非线性的转换。我们怀疑默认的ReLU激活（$𝑓(𝑥)=max(0, 𝑥)$）表达能力不够，因为ReLU网络是分段线性函数[1]。我们尝试了各种激活函数2，并发现最近提出的Mish激活[25]（$𝑓(𝑥)=x \cdot tanh(ln(1 + e^x)))$）始终比ReLU和其他激活函数表现得更好。我们还发现batch normalization（BN）[16]可以稳定训练并取得更好的性能。然而，像dropout这样的正则化方法并没有帮助，这再次验证了我们的嵌入网络的瓶颈是欠拟合。

3.4 用于泛化的side features增强编码

DHE的一个有趣扩展是利用side features来学习更好的编码。这有助于将结构注入我们的编码中，并在特征值之间以及对新值实现更好的泛化。类别型特征的嵌入学习的一个重大挑战是：我们只能记忆每个特征值的信息，而无法在特征值之间泛化（例如，从ID 7泛化到ID 8）或泛化到新值。这是因为底层特征表示并没有暗示不同ID之间有任何内在的相似性。实现泛化的一个典型方法是使用side features，这些特征提供了泛化的固有相似性（例如，dense特征或bag-of-word特征）。然而，这些特征通常被用作推荐模型的附加特征，而不是用于改进分类特征的嵌入学习。

基于one-hot full embedding继承了类别型特征的属性，并独立生成嵌入（即，任何两个ID的嵌入都是独立的）。因此，基于one-hot的方案可以被视为去中心化的架构，它们擅长记忆但无法实现泛化。相比之下，DHE方案是一个集中式的解决方案：嵌入网络中的任何权重变化都会影响所有特征值的嵌入。我们相信集中式结构为泛化提供了潜在的机会。

由于DHE的解码函数是一个神经网络，我们可以灵活地修改输入，例如结合side feature。我们提出了针对DHE的side features增强编码，并希望这将改善特征值之间的泛化，以及对新值的泛化。增强编码的一个直接方法是直接连接可泛化的特征和哈希编码。如果特征向量的维度太高，我们可以使用局部敏感哈希[6]来显著减少基数，同时保留标签相似性。增强后的编码随后被输入到深度嵌入网络中以生成嵌入。

我们认为，哈希编码提供了一个用于记忆的唯一标识符，而其他特征则使泛化能力得以实现。

3.5 总结

总而言之，DHE有两个主要组成部分：1. 密集哈希编码；2. 深度嵌入网络。编码模块是完全确定性的且不可学习的，不需要任何存储参数。嵌入网络将标识符向量转换为所需的嵌入。DHE的一个显著区别是缺乏嵌入表，因为我们将所有嵌入信息存储在DNN的权重中。因此，所有特征值共享整个嵌入网络来生成嵌入，这与hashing trick不同，后者为不同的特征值共享相同的嵌入向量。这使得DHE免受嵌入冲突问题的影响。DHE的瓶颈在于嵌入网络的计算，尽管这可以通过更强大的硬件和神经网络加速方法（如剪枝[8]）来加速。

与现有明确为每个ID分配相同嵌入长度的嵌入方法不同，DHE的一个有趣事实是，每个特征值的嵌入容量是隐含的，并且可能是可变的。这对于在线学习环境（词汇量不断增长）和幂律分布（嵌入网络可能会花费更多的参数来记忆流行的ID）可能是一个期望的属性。

paper原文：

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

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

kuaishou在《PEPNet: Parameter and Embedding Personalized Network for Infusing with Personalized Prior Information》中提出了PEPNet：

1.抽要

随着在线服务（电商/在线视频）的内容页面和展示样式的增加，工业级推荐系统经常面临着multi-domain和multi-task的推荐挑战。multi-task和multi-domain推荐的核心是，在给定不同的用户行为时，能精准捕获在不同domains中的用户兴趣。在本paper中，我们在multi-domain环境下的multi-task推荐上提出了一种即插即用（plug-and-play）的 Parameter and Embedding Personalized Network (PEPNet) **。PEPNet会将具有强bias的features作为input，并动态地对模型中的bottom-layer embeddings和top-layer DNN hidden units通过一个gate机制进行缩放（scale）**。通过将个性化先验（personalized priors）映射，将weights归一化范围(0, 2)，PEPNet会同时引入参数个性化和embedding个性化。PPNet（Parameter Personalized Network ）会影响DNN参数，来对多个任务上的相互依赖目标进行权衡。我们会做出一系列特征的工程优化，将Kuaishou训练框架与在线部署环境相结合。我们已经成功在Kuaishou apps上进行部署，服务了3亿的日活用户。

1.介绍

略

2.方法

该部分会介绍详细设计，用来缓解“双跷跷板（double seesaw）”问题。我们会详述问题公式、以及PEPNet的网络结构。

2.1 问题公式

这里我们定义了我们研究的概念和问题settings。该模型会使用sparse/dense inputs，比如：用户历史行为、用户profile features、item features、context features等。预估目标\(\hat{y}_i\)是user u在domain d的第i个task上对item p的偏好，它的计算如下：

\[\hat{y}_i = f(\lbrace E(u_1), \cdots, E(u_t) \bigoplus E(p_1), \cdots, E(p_j) \bigoplus E(c_1), \cdots, E(c_k) \rbrace_d)\]

…(1)

其中：

• \(u_1, \cdots, u_t\)：表示user-side features，它包含了：用户的历史行为、user profile和user ID等。
• \(p_1, \cdots, p_j\)：表示target item features，它包含了：item ID(iid)、author ID(aid)等
• \(c_i, \cdots, c_k\)：表示其它features，它会包含context feature和combine feature
• \(\lbrace \rbrace_d\)表示来自domain d的样本
• \(E(*)\)：表示sparse/dense features，会通过在分桶算法之后的embedding layer被映射到可学习embedding中，
• \(\bigoplus\)：表示 concatenation

对于一个真实应用，item candidate pool和用户part会在多个场景共享。由于不同的消费目标，用户在不同场景对于相同item会改变他们的行为趋势。为了更好捕获对于不同行为的用户偏好，并增强在多个场景的联系，推荐系统需要同时为多个domains D做出多任务预估。注意，模型输入是\(\lbrace x, y_i, D \rbrace\)，

其中：

• x：是上述提到的feature
• \(y_i\)：是每个任务的label

• \(d \in D\)：是domain indicator，它表示样本收集来自哪个domain

• Input：表示sparse/dense inputs，比如：用户历史行为、用户profile features、item features和其它context features
• Output：一个推荐模型，它会估计用户在多个domains上的多个目标，例如：点赞（like）、关注（follow）、转发（forward）等

2.2 网络结构

图3展示了PEPNet的网络结构。该模型由三个部分组成，我们一一解释。

• GateNU（Gate Neural Unit）：Gate NU是EPNet和PPNet的基本单元，它是一个基于先验信息生成的门控结构。
• EPNet（Embedding个性化网络：Embedding Personalized Network）：EPNet会采用domain信息作为input，并使用Gate NU来进行domain-specific个性化，增强模型的bottom layer的能力来表示跨域的features。
• PPNet（参数个性化网络：Parameter Personalized Network）。 PPNet使用用户信息和item信息来生成gates，并调整在不同task towers上每个layer的参数，并对模型的top layer上相互依赖目标进行权衡。

图3 PEPNet包含了Gate NU, EPNet, PPNet。Gate NU是基础单元，它会使用先验信息来生成门控和增强的合法信号。EPNet会在Embedding layer上增加模型的domain-awareness，并将PPNet进行stacking到每个任务的DNN tower上来增强task personalization. 在多个domains上会估计相同集合的multi-targets。PEPNet可以被插入到任意网络中。颜色如上所示。

2.2.1 Gate Neural Unit(Gate NU)

受LHUC算法的启发，其关键思想是：为每个speaker学习一个特定的hidden unit贡献，PEPNet会引入一个门控机制，称为“Gate Neural Unit”，它对于不同用户来说，网络参数是个性化的。 Gate Neural Unit（简称为Gate NU），包含了两个nueral network layers。

• \(x^{(0)}\)：表示Gate NU的input
• \(W^{(0)}\)：表示第一层network layer的weight
• \(b^{(0)}\)：表示第一层network layer的bias

Relu被选择作为第一层该函数的activation function。第一层公式如下：

\[x_1 = Relu(x^{(0)} W^{(0)} + b^{(0)})\]

…(2)

接着， Gate NU会使用Sigmoid function来生成gate，它会将output限制为[0, 1]。

• \(\gamma\)是参超数，设置为2
• \(W^{(1)}\)和\(b^{(1)}\)是第二个layer的weight和bias

第二层的公式化如下：

\[x_2 = \gamma * Sigmoid(x^{(1)} W^{(1)} + b^{(1)}), x_2 \in [0, \gamma]\]

…(3)

根据等式1和等式2，Gate NU会使用先验信息\(x^{(0)}\)来生成gating vector，并使用超参数\(\gamma\)来进一步放大有效信号。接着，我们会详述如何使用该gating机制来组合EPNet和PPNet。

2.2.2 Embedding Personalized Network（EPNet）

出于计算和内存开销考虑，EPNet模型会共享相同的embedding layer，其中：

\[E(*) = E(SF) \oplus E(DF)\]

…(4)

• SF是sparse features，DF是dense features。
• \(E(*)\)是共享底层结构，它实际上会有许多缺点，关注共享却忽略了多个domains的不同

对于共享的EPNet，我们会使用domain-side features \(E(df) \in R^k\)作为input，比如：domain ID和统计特征。

对于在第i个domain的特定数据样本，我们将其余feature表示为\(E(*) \in R^d\)，其中：

• d是input维度
• \(V_{ep}\)是embedding layer的Gate NU

EPNet的输出\(\sigma_{domain} \in R^d\)给定如下：

\[\sigma_{domain} = V_{ep}(E(df))\]

…(5)

我们使用一个额外的Gate NU network来将embedding进行变换，并将多个domains的分布进行对齐（align），无需变更原始的embedding layers。转换后的embedding（transformed embedding）如下：

\[O_{ep} = \sigma_{domain} \otimes E(*)\]

…(6)

其中：

• \(O_{ep} \in R^d\): 输出
• \(\otimes\): 是element-wise乘法

2.2.3 Parameter Personalized Network(PPNet)

为了增强关于task-specific个性化的信息，我们使用user/item/author-side feature(uf/if/af)作为PPNet的输入，比如：user ID, item ID, author ID，以及side information features，比如：user age/gender, item tag/topic/popularity等。特别的，详细的PPNet结构如下：

\[O_{prior} = E(uf) \oplus E(if) \oplus E(af) \\ \sigma_{task} = V_{pp} (O_{prior} \oplus (\oslash(O_{ep})))\]

…(7)

其中:

• \[E(uf) \in R^u, E(if) \in R^i, E(af) \in R^a\]

PPNet会将EPNet的output拼接在一起，features \(O_{prior}\)具有很强的个性化先验，它会给出模型关于先验信息的更多感知。关于个性化的先验信息可以通过一个来自user ID、item ID以及author ID的扩展来获得，其中：author表示kuaishou短视频的创作者。为了不影响在EPNet中已经更新的embedding，我们会在EPNet的output上执行stop gradient \(\oslash\)操作。在传统模型中，所有hidden units会被相等对待，并传给下一layer中。我们使用element-wise乘法来选择和放大合法信号，如下：

\[O_{pp} = \sigma_{task} \otimes H\]

…(8)

其中：

• H是在task towers上每个DNN layer上的hidden unit。

在多任务学习中的参数共享可以极大减小DNN参数的size，但在多个共享targets间的一些信息会丢失，导致不均衡的效果。例如，预估Follow和Like的任务会共享DNN参数，但Follow任务具有更少的正样本。前两者的梯度会累计，Follow的一些信号会被Like所覆盖。因此对于每个任务，我们会在将PPNet \(O_{pp}^l\)插入到每个DNN task tower的第l个layer中，来增强任务个性化的先验信息，如下所示：

\[O_{pp}^{(l)} = \sigma_{task}^{(l)} \otimes H^{(l)} \\ O_{pp}^{(l+1)} = f(O_{pp}^{(l)} W^{(l)} + b^{(l)}), l \in \lbrace 1, \cdots, n \rbrace\]

…(9)

其中：

• n是每个task tower的DNN layers的数目
• f是activation function。

对于第n-1个layers，activation function f会使用Relu。最后一个layer是Sigmoid，它没有放大系数\(\gamma\)，这与Gate NU不同。在获得last layer上的多个domains上的多个targets的预估得分后，会使用binary cross-entropy进行最优化。

2.3 工程优化策略

为了部署PEPNet，我们做出以下的工程优化策略：

• Feature score消除策略：由于每个ID映射到一个embedding vector，可以快速填满服务的内存资源。为了确保系统进行长时间执行，我们设计了一个特殊参数服务器，来达到一个无冲突（conflict-free）、高效内存的全局共享embedding表（memory-efficient Global Shared Embedding Table） (GSET）。GSET使用feature score elimination策略来控制内存footprint，使得总是在一个预设的阈值之下。然而，传统的cache elimination策略使用LFU和LRU，只考虑了条目的频率信息，主要用于最大化cache命中率。

• DNN/Embedding layer Updating: 由于系统采用在线学习，它在训练时会长时间累积数据。我们将训练数据的最小单元称为一个pass，每个pass会更新online inference模型。由于存在大量users、authors以及items，这会导致user ID、item ID、author ID的features的快速膨胀。平台的一些ID features会超期或变得很冷门，因此将所有ID features进行存储是不高效的。它会盲目增大系统的冗余，带来额外的存储和计算开销。我们会增加两个特征选择策略（feature eviction）。一个是指定一个feature的特定数目，当超过时会抛弃。另一个是设置ID featrues的过期时间，保证ID features可以频繁更新，并删除那些没有达到所需更新数的ids。相似的，当模型被更新时，我们会检查相应的embedding，只更新变化的embedding。

• Training策略：由于在kuaishou的短视频场景的商业特性，ID features会快速变化。实际上，我们会发现：embedding的更新会比DNN模型参数更频繁。在线学习场景中，为了更好捕获在bottom-layer embeddings的变化，并稳定更新top-layer DNN参数，我们会分别更新embedding part和DNN参数部分，并使用不同的update策略。在bottom-layer embedding中，我们会使用AdaGrad optimizer，学习率会设置为0.05。而DNN参数会通过Adam optimizer进行更新，学习率为：5.0e-06.

3.离线实验

略

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

wechat在《Reweighting Clicks with Dwell Time in Recommendation》中提出了一种基于停留时长加权的建模：

2.模型设计与分析

图1

2.1 Dwell Time Modeling

用户真正需要什么样的推荐？最近研究表明：对于CTR，停留时长（dweill time）更会影响用户的真实满意度。然而，直接对原始的dwell time进行最优化会导致模型过度增强具有long total duration的items，使得重度用户和long items会主宰模型训练。

我们相信：用户使用推荐系统的中心诉求是获得信息。因此，我们会返回：在dwell time、信息增益、用户偏好间的关系本质，并做出以下猜想：

• (A1) 对于不同的items和users交互，具有相同dwell time，则正信号是相当的。因为他们通常表示会具有相同的time cost，对每个人公平
• (A2) 用户需要一个最小的dwell time，以便从items获得信息。太短的dwell time表示着非常少的收益
• (A3) 当前dwell time足够长时，信息增益（information gain）会逐渐随着dwell time的增加而递减。

基于这些，我们在click reweighting中使用一个normalized dwell time function作为一个更好的监督信号来定义有效阅读（valid read）.

2.2 有效阅读选择（valid read selection）

有效阅读是高质量点击行为，可以更好反映用户的真实偏好，它可以通过dwell time来天然选择。对于dwell time的一个更深理解，我们会绘制点击数随不同log dwell time的趋势。图2左可以看到：

• 1) 总体上，我们可以假设：log dwell time具有一个近似高斯分布，例如： \(lnT=\mu + \sigma \epsilon\)，其中：T是一个random dwell time，\(\epsilon \sim N(0,1)\)。
• 2) 我们会将\([\mu-\sigma, \mu + \sigma]\)看成是主要的dwell time区间
• 3) 接近19%的点击行为要短于15s dwell time，并且接近15%的点击行为要长于200s dwell time

根据上述假设A2和A3，具有过短和过长的dwell time的点击行为在click reweighting上会被降级。

图2 log dwell time在我们系统中的趋势（左）以及normalized dwell time的趋势（右）

简单做法是：直接设置一个共享的dwell time阈值来收集有效阅读。然而，简单依赖阈值来定义有效阅读，会不可避免地忽略掉关于轻度用户与short items的大量行为信息。因此，我们定义了三种类型的user-item clicks作为我们的合法阅读行为：

• T1: dwell time要比长于\(x_l\)秒
• T2: 该用户在最近一周近至少点击7个items
• T3: dwell time会长于该item的历史dwell time记录的10%（例如：长于分位数P10）

(1) 第一种类型：根据common-sense阈值\(x_l\)构建了有效阅读的基础规则。我们将\(lnT\)的\(x_l = exp(\mu - \sigma)\)看成是有效阅读的共享dwell time阈值，它可以适配于不同的推荐系统。在我们的系统中，\(exp(\mu - \sigma)\)接近15s。19%的点击行为会被T1过滤掉。出于简单性，对于所有的users和items，我们根据time costs的绝对值直接采用一个共享的DT阈值，对于不同的user或item groups设置定制的dwell time阈值也很方便。

（2）第二种类型：会在轻度用户上打个补丁，将所有轻度用户的点击行为看成是在训练中的监督信号，因为他们的行为很稀少。我们希望避免长尾轻度用户（偏向于扫描浏览而非深度阅读）的重要信息丢失。

(3) 第三种类型：会在一个指定item上考虑相对dwell time，在相同item上所有历史点击间，取回的click具有一个相对符合条件的dwell time（top 90%）。通过该方法，我们的有效阅读会考虑上具有天然短长度、少dwell time的items（例如：news或short videos）. 为了避免噪声，我们进一步将清除所有具有5s dwell time的点击，以确保有效阅读的最低能力。在我们的实践中，T1、T2、T3类型分别具有89.9%、2.9%、7.2%的总有效阅读。只有有效阅读会被用于训练中的监督信号。

2.3 归一化dwell time函数

有效阅读选择会作为一个pre-filter使用。然而，我们仍然面临着在click reweighting中如何精准定义不同dwell time值的挑战。直觉上，相同的dwell time提升，当current dwell time更短时对于一个click的quality会具有更大的贡献（例如：[1s -> 15s]要比[601s->615s]更大）。太长的dwell time会带来疲乏，对用户体验有害。因而，大量工作采用log dwell time的MSE作为训练loss作为dwell time的预估【2，16，27】。

不同于常规模型，我们会将有效阅读定义成高质量的supervised label，并且希望提升有效阅读的数目的比例。因此，我们的dwell time function会拥有以下两种特性C1和C2，分别对应于以上的A2和A3:

• C1: 设计好的dwell time function曲线在early stage应该很陡，此时具有大梯度（特别是接近有效阅读阈值 \(exp(\mu - \sigma)\)的地方），这会指导模型很好区分有效阅读 vs. 无效点击
• C2: dwell time funciton曲线在dwell time过长时会比较平，避免过长的items得到太多rewards，导致伤害轻度用户对短items的交叉。

根据以下规则，我们基于原始的dwell time T，使用一个sigmoid function，设计了normalized dwell time \(T_N\)：

\[T_N = \frac{A}{1 + exp(- \frac{T-offset}{\tau})} - B\]

…(1)

图2（右）展示了\(T_N\)的趋势。对比起log dwell time，\(T_N\)会使用设置好的rates单调增加，其中：offset和\(\tau\)本质上是满足C1和C2的参数。

• offset：决定了具有最大梯度的dwell time point。对于C1，我们会设置：\(offset = exp(\mu - \sigma)\)来使得normalized dwell time在有效阅读/无效阅读边界上具有最大的梯度，它会基于supervised training与有效阅读很好的一起协作。
• \(\tau\)：定义了dwell time曲线的sharpness。对于C2，我们定义了一个upper阈值 \(x_h\)作为\(exp(\mu + \sigma)\)，假设：比\(x_h\)更大的dwell time T对\(T_N\)没啥贡献（例如：\(T_N\)提升\(x_h \rightarrow T\)要小于最小精度，例如：在系统中为1e-5）。\(\tau\)被设置成满合\(x_h\)的上述假设。
• A和B：是超参数，可以将\(T_N\)归一化成\([0, T_{max}]\)，其中：\(T_{max}\)是当前在线dwell time模型的最大dwell time值。我们将normalized dwell time范围保持不变，减少可能的不匹配问题。

最终，基于上述讨论，我们设置：\(offset=15, \tau = 20, A = 2.319, B = 0.744\)来满足C1和C2 。 我们也对这些参数做了grid search，发现当前setting可以达到最好的在线效果。

2.4 Click Reweighting

有效阅读和normalized dwell time被设置成过滤噪声，选出符合点击的分位数，以便更好的进行学习。在click reweighting中，我们采用一个multi-task learning框架来进行有效阅读预估（valid read prediction）以及加权有效阅读预估（weighted valid read prediction）。特别的，我们会进行一个共享bottom来跨任务共享原始的user/item features。

对于valid read tower，我们会采用一个3- layer MLP，它会采用原始user/item features \(f_u, f_{d_i}\)作为inputs，并输出用户u在item \(d_i\)上的预估点击概率\(P_{u, d_i}\)。接着，有效阅读loss \(L_v\)定义如下：

\[L_v = - \sum\limits_{(u,d_i) \in S_p} log P_{u,d_i} + \sum\limits_{(u,d_j) \in S_n} log (1 - P_{u,d_j})\]

…(2)

其中：

• \(S_p\)和\(S_n\)表示正样本集（有效阅读）和负样本集（无效点击和未点击）。

相似的对于weighted valid read tower，我们直接使用normalized dwell time \(T_N^{u, d_i}\)作为每个\((u, d_i)\)的weight。另一个3-layer MLP会被用来输出预估点击概率\(P_{u,d_i}'\)。加权有效阅读tower接着会在loss \(L_w\)下被训练：

\[L_w = \sum\limits_{(u,d_j) \in S_n} T_N^{(u,d_j)} log(1 - P_{u,d_j}') - \sum\limits_{(u,d_i) \in S_p} T_N^{(u,d_i)} log P_{u,d_i}'\]

…(3)

\(L_v\)和\(L_w\)是线性组合成最终loss：\(L = L_v + L_w\)。在线部署中，两个towers的求和的预估得分会被用于在线排序。终合考虑original和DT weighted有效阅读预估任务是有益的。再者，我们进一步探索了MTL框架（MMoE和PLE），在线提升并不大。可能是因为dwell time与点击高度相关。出于简单，我们直接使用MLP作为shard bottom。

• 1.https://arxiv.53yu.com/pdf/2209.09000.pdf

Clara Meister等在《Determinantal Beam Search》中提出了Determinantal Beam Search：

2.Neural Sequence Models

神经网络序列模型（Neural sequence models）是：给定一个input x，在一个output space Y上的序列y的概率分布\(p(y \mid x)\)。这里我们将Y定义成来自词汇表中的所有合法句子序列，以BOS开头，以EOS结尾。通常，序列长度由值\(n_{max} \in Z_+\)给定，它会依赖于x。在本文，我们会考虑局部归一化模型（locally normalized models），例如：给定之前已生成的tokens序列 \(y_{<t}\) ，这里的p表示：是一个在\(\bar{V} = V \cup \lbrace EOS \rbrace\)的概率分布。完整序列\(y = <y_1, y_2, \cdots>\)的概率接着通过概率的chain rule进行计算：

\[p(y | x) = \prod\limits_{t=1}^{|y|} p(y_t | y_{<t}, x)\]

…(1)

其中，\(y_{<1}= y_0 = BOS\)。

我们的模型p通常通过一个具有weights \(\theta\)的neural network进行参数化。由于我们不关注底层模型本身，我们忽略掉p在参数\(\theta\)的依赖。

我们将decoding problem定义为：在空间Y上的所有序列间，根据模型\(y(y \mid x)\)搜索具有最高scoring的y，它也被称为最大后验概率估计（maximum-a-posteriori（MAP）inference）：

\[y^{*} = \underset{y \in Y}{argmax} \ log p(y | x)\]

…(2)

其中：惯例上，会使用p的log变换。

我们进一步将set decoding problem定义为：对于一个指定的基数k，在所有合法的subsets \(\lbrace Y' \subseteq Y \mid \mid Y'\mid=k \rbrace\)上，搜索一个具有最高分的set \(Y^*\)，定义为：

\[p(Y | x) = \prod\limits_{y \in Y} p(y | x)\]

…(3)

类似于等式(2)，set-decoding问题接着被定义为：

\[Y^* = \underset{Y' \subseteq Y, |Y'|=k}{argmax} \ log p(Y' | x)\]

…(4)

然而，由于需要注意的是，等式（2）和（4）有许多问题：

• 首先，因为Y是一个指数大的空间，并且p通常是非马尔可夫（non-Markovian）性的，我们不能进行有效搜索，更不用说\(Y^k\)。
• 第二，特别是对于语言生成任务，这些可能不是有用的目标

目标降级

需要重点注意的是：在 neural sequence models下具有最高概率解，并不总是高质量的（high-quality）；特别是涉及到语言生成的任务，比如：机器翻译等。相应的，启发式搜索方法或者一些替代目标通常会被用于decoding language generators.

2.1 Beam Search

用于逼近等式(2)的decoding problem的一种常见启发法是：在每一timestep t上，以最大化 \(p(y_t \mid y_{<t}, x)\)的方法，顺序选择token \(y_t\)，直到EOS token被生成，或者达到最大序列长度\(n_{max}\)。该过程被称为greedy search。Beam search是一种经常使用（oft-employed）的greedy search的生成方法，它会返回k个candidates，并探索更多search space。在本工作中，我们关注于迭代式子集选择(iterative subset selection)的beam search，它有一个很简洁的算法公式。给定一个初始集合\(Y_0\)，它只包含了BOS token，对于\(t \in \lbrace 1,\cdots,n_{max} \rbrace\)，我们会根据以下递归来选择子序列\(Y_t\)：

图1

其中，我们会限制，只扩展在beam set中的candidates，它被定义为：

\[B_t = \lbrace y_{<t} \circ y | y_{<t} \in Y_{t-1} \ and \ y \in \bar{V} \rbrace\]

…(6)

其中：

• \(\circ\)会被用于表示string concatenations。

注意：在\(Y_{t-1}\)中的candidates已经以EOS结尾，会直接添加到\(B_t\)上，例如：\(EOS \circ EOS = EOS\)。在该定义下，我们有基数k的constraint：\(\mid B_t \mid \leq \mid \bar{V} \mid \cdot k\).

2.2 Determinanta新公式

对于公式（5），我们接着引入另一种的等价概念，它使用matrics和determinants，它会阐明beam search的直接泛化（generation）。我们定义了一种timestep-dependent diagonal matrix \(D \in R^{\mid B_t \mid \times \mid B_t \mid}\)，其中：我们会采用diagonal entry:

\[D_{ii} \overset{=}{def} p(Y_{\leq t}^{(i)} | x)\]

…(7)

这里：

• \(y_{\leq t}^{(i)}\)：表示在\(B_t\)中的第i个candidate，它根据一个unique mapping：对于每个element \(y_{\leq t} \in B_t\)会唯一映射到一个介于1和\(\mid B_t \mid\)间的integer

接着，我们会使用概念\(D_{Y_t}\)：它表示只包含了对应于\(Y_t\)的elements的相应行和列的submatrix，其中：\(Y_t \subseteq B_t\)我们将等式(5)重写成：

图2

这里的等式遵循对角阵行列式的定义。正式的，等式（8）被称为“子行列式最大化问题（subdeterminant maximization problem）”，该问题是发现这样一个行列式：它能最大化一个矩阵子集。而等式(8)引入的概念可能是人为的，它允许我们执行后续泛化。

3. Determinantal Beam Search

现在，我们会问该工作的基础问题：如果我们使用一个non-diagonal matrix来替换 diagonal matrix D，会发生什么？这种替换会允许我们对在beam中的elements间的interactions做出解释。正式的，我们会考虑一个时间独立半正定矩阵（ timestep-dependent positive semi-definite (PSD) matrix）：

\[D+w \cdot K\]

其中：

• K：对角矩阵（off-diagonal matrix），表示在candidates间interactions的strength。
• \(w \geq 0\)：非负权重，控制着在decoding过程中interactions的重要性

在本case中，beam search递归变为：

图3

很明显，当w=0时我们会恢复成图2的beam search。然而，我们现在会基于在candidate interactions之上来选择子集。也就是说，等式（9）现在具有一个作为“diversity objective function”解释，当K被合适选择时。由于log的存在，当矩阵\(D_Y + w \cdot K_Y\)是PSD时，等式(9)会被良好定义。

3.1 K的构建

构建K的最简单方法是：Gram matrix，其中：每个i, j element会通过一个kernel function: \(K: S \times S \rightarrow R\)来计算，它会将空间中的两个items映射到一个实数上。特别的，我们会定义：\(K_{ij}=K(s_i, s_j)\)，其中\(s_i, s_j \in S\)是S的第i和第j个elements。概念上有些混洧，我们会该该kernel function K overload，它会采用一个set S，以便\(K = K(S)\)是在S的elements之上由pairwise计算的kernel matrix。根据Mercer理论，矩阵K=K(S)必须是PSD的，因为矩阵\(D_Y + w \cdot K_Y\)对于任意\(Y \subseteq S\)是PSD的。

3.2 与DPP关系

等式(9)是一个DPP。特别的，它是一个在L-ensemble parameterization上的k-DPP，其中：我们有\(L = D + w \cdot K\)。k-DPP的解释，对于为什么等式（8）是一个diverse beam search，给出了一个非常清晰的理解。对角的entries会编码quality，它会告诉我们：在beam上的每个candidate是多么“好”，而非对角entries（off-diagonal entries）则编码了两个elements有多么相似。

3.3 计算log-determinants

不幸的是，等式（9）中的argmax计算是一个NP-hard问题。然而，由于子行列式最大化问题（ subdeterminant maximization problem）具有许多应用，业界研究了许多高效算法来近似计算DPP中的log-determinants。Han et.2017使用一个关于log-determinant function的一阶近似。Chen et.2018使用一个贪婪迭代法；通过增量式更新matrix kernel的Cholesky factorization，该算法可以将infernence time减小到\(O(k^2 \mid S \mid)\)，并返回来自set S中的k个candidates。伪代码可以在Chen et.2018中找到，log-space算法的伪代码，可以在App.A中找到。

3.4 运行时(runtime)分析

我们会考虑：在给定任意时间，在等式（9）的递归上选择k个candidates的运行时。在每个timestep上，我们会首先构建一个matrix K。该计算高度依赖于被建模的interactions的集合；这样，当我们使用beam size为k时，\(O(c(k))\)是对于K计算的一个runtime上限。一旦我们构建矩阵\(D + w\cdot K\)，我们必须接着选择k个items。在任意timestep上的hypotheses集合至多是\(k \mid \bar{V} \mid\)。如3.3中讨论，我们假设采用近似算法，以最大化等式（9）的方式精准发现size-k的子集具有指数的runtime。使用Chen et.2018的方法，近似MAP inference会具有\(k^3\mid \bar{V} \mid\)的时间，从一个size为\(k \mid \bar{V} \mid\)的集合返回k个items。这样，在该条件下，determinantal beam search的每轮迭代的runtime会是：\(O(c(k) + k^3 \mid \bar{V} \mid)\)。注意， standard beam search在每轮迭代会运行\(O(k \mid \bar{V} \mid log(k \mid \bar{V} \mid))\)。由于k通常很小（\(leq 20\)），c(k)的影响可以合理做出，在runtime上的实际增加通常是适中的。

4.Case Study: Diverse Beam Search

略略

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