三十九、AutoDis[2021]

1. 如下图所示，大多数现有的深度 CTR 模型遵循 Embedding & Feature Interaction (FI) 的范式。由于特征交互在 CTR 预测中的重要性，大多数工作集中在设计 FI 模块的网络架构从而更好地捕获显式特征交互或隐式特征交互。虽然在文献中没有很好的研究，但 embedding 模块也是深度 CTR 模型的一个关键因素，原因有二：

   • embedding 模块是后续 FI 模块的基石，直接影响 FI 模块的效果。
   • 深度 CTR 模型中的参数数量大量集中在 embedding 模块，自然地对预测性能有很高的影响。

   然而，embedding 模块被研究界所忽视，这促使 《An Embedding Learning Framework for Numerical Features in CTR Prediction》 进行深入研究。

   embedding 模块通常以 look-up table 的方式工作，将输入数据的每个 categorical field 特征映射到具有可学习参数的潜在 embedding 空间。不幸的是，这种 categorization 策略不能用于处理数值特征，因为在一个 numerical field （如身高）可能有无限多的特征取值。

   在实践中，现有的数值特征的 representation 方法可以归纳为三类（如下图的红色虚线框）：

   • No Embedding：直接使用原始特征取值或转换，而不学习 embedding 。
   • Field Embedding：为每个 numerical field 学习单个 field embedding 。
   • Discretization：通过各种启发式离散化策略将数值特征转换为 categorical feature ，并分配 embedding 。

   然而，前两类可能会由于 representation 的低容量而导致性能不佳。最后一类也是次优的，因为这种基于启发式的离散化规则不是以 CTR 模型的最终目标进行优化的。此外， hard discretization-based 的方法受到 Similar value But Dis-similar embedding: SBD 和 Dis-similar value But Same embedding: DBS 问题的影响，其细节将在后面讨论。

   

   为了解决现有方法的局限性，论文 《An Embedding Learning Framework for Numerical Features in CTR Prediction》 提出了一个基于 soft discretization 的数值特征的 automatic end-to-end embedding learning framework ，即 AutoDis 。AutoDis 由三个核心模块组成：meta-embedding 、automatic discretization 和aggregation ，从而实现高的模型容量、端到端的训练、以及 unique representation 等特性。具体而言：

   • 首先，论文为每个 numerical field 精心设计了一组 meta-embedding ，这些 meta-embedding 在该field 内的所有特征取值之间是共享的，并从 field 的角度学习全局知识，其中 embedding 参数的数量是可控的。
   • 然后，利用可微的 automatic discretization 模块进行 soft discretization ，并且捕获每个数值特征和 field-specific meta-embedding 之间的相关性。
   • 最后，利用一个 aggregation 函数从而学习 unique Continuous-But-Different representation 。

   据作者所知，AutoDis 是第一个用于 numerical feature embedding 的端到端 soft discretization 框架，可以与深度 CTR 模型的最终目标共同优化。

   论文主要贡献：

   • 论文提出了AutoDis ，一个可插拔的用于 numerical feature 的 embedding learning 框架，它具有很高的模型容量，能够以端到端的方式生成 unique representation 并且具有可管理的参数数量。
   • 在 AutoDis 中，论文为每个 numerical field 设计了 meta-embedding 从而学习全局的共享知识。此外，一个可微的 automatic discretization 被用来捕获数值特征和 meta-embedding 之间的相关性，而一个 aggregation 过程被用来为每个特征学习一个 unique Continuous-But-Different representation 。
   • 在两个公共数据集和一个工业数据集上进行了综合实验，证明了 AutoDis 比现有的数值特征的 representation 方法更有优势。此外，AutoDis 与各种流行的深度 CTR 模型兼容，大大改善了它们的推荐性能。在一个主流广告平台的 online A/B test 表明，AutoDis 在 CTR 和 eCPM 方面比商业 baseline 提高了 2.1% 和 2.7% 。

2. 相关工作：

   • Embedding：作为深度 CTR 模型的基石， embedding 模块对模型的性能有重大影响，因为它占用了大部分的模型参数。我们在此简单介绍推荐领域中基于 embedding look-up 的研究。

     现有的研究主要集中在设计 adaptable 的 embedding 算法，通过为不同的特征分配可变长度的 embedding 或 multi-embeddings ，如Mixed-dimension （《Mixed dimension embeddings with application to memory-efficient recommendation systems》），NIS （《Neural Input Search for Large Scale Recommendation Models》）和AutoEmb（《AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations》）。

     另一条研究方向深入研究了 embedding compression ，从而减少 web-scale 数据集的内存占用。

     然而，这些方法只能以 look-up table 的方式应用于 categorical feature 、或离散化后的数值特征。很少有研究关注数值特征的 embedding learning ，这在工业的深度 CTR 模型中是至关重要的。

   • Feature Interaction：根据显式特征交互和隐式特征交互的不同组合，现有的 CTR 模型可以分为两类：堆叠结构、并行结构。

     • 堆叠结构：首先对 embeddings 进行建模显示特征交互，然后堆叠 DNN 来抽取 high-level 的隐式特征交互。代表性的模型包括 FNN、IPNN、PIN、FiBiNET、FGCNN、AutoGroup、DIN 和 DIEN 。

     • 并行结构：利用两个并行网络分别捕捉显式特征交互信号和隐式特征交互信号，并在输出层融合信息。代表性的模型包括 Wide & Deep、DeepFM、AutoFIS、DCN、xDeepFM 和 AutoInt 。

       在这些模型中，隐式特征交互是通过 DNN 模型提取的。而对于显式特征交互，Wide & Deep 采用手工制作的交叉特征，DeepFM 和 AutoFIS 采用 FM 结构，DCN 采用 cross network ，xDeepFM 采用 Compressed Interaction Network: CIN ，AutoInt 利用多头自注意力网络。

39.1 模型

39.1.1 基础概念

1. 假设用于训练 CTR 模型的数据集由 $Q$$Q$ 个实例 $(\overrightarrow{\mathbf{x}},y)$$(\mathbf{\vec x}, y)$ 组成，其中 $y$$y$ 是标签，$\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 是包括 $M$$M$ 个 categorical fields 和 $N$$N$ 个 numerical fields 的 multi-field 数据记录：

   $$\begin{array}{}\text{(1)}& \overrightarrow{\mathbf{x}}=[\underset{\text{scalars}}{\underbrace{x_1,x_2,\cdots ,x_N}};\underset{\text{one-hot vectors}}{\underbrace{{\overrightarrow{\mathbf{x}}}_{N+1},{\overrightarrow{\mathbf{x}}}_{N+2},\cdots ,{\overrightarrow{\mathbf{x}}}_{N+M}}}]\end{array}$$

   其中： $x_j$$x_{j}$ 是第 $j$$j$ 个 numerical field 的标量值； ${\overrightarrow{\mathbf{x}}}_{N+i}$$\mathbf{\vec x}_{N+i}$ 是第 $i$$i$ 个 categorical field 的特征取值的 one-hot vector 。

   对于第 $i$$i$ 个 categorical field ，可以通过 embedding look-up 操作获得 feature embedding ：

   $$\begin{array}{}\text{(2)}& {\overrightarrow{\mathbf{e}}}_{N+i}={\mathbf{E}}_{N+i}{\overrightarrow{\mathbf{x}}}_{N+i}\end{array}$$

   其中：${\mathbf{E}}_{N+i}\in {\mathbb{R}}^{v_{N+i}\times d}$$\mathbf E_{N+i}\in \mathbb R^{v_{N+i}\times d}$ 为第 $i$$i$ 个 categorical field 的 embedding matrix ，$d$$d$ 为 embedding size，$v_{N+i}$$v_{N+i}$ 为第 $i$$i$ 个 categorical field 的词表规模。

   因此， categorical field 的 representation 为：$[{\overrightarrow{\mathbf{e}}}_{N+1},{\overrightarrow{\mathbf{e}}}_{N+2},\cdots ,{\overrightarrow{\mathbf{e}}}_{N+M}]\in {\mathbb{R}}^{M\times d}$$\left[\mathbf{\vec e}_{N+1},\mathbf{\vec e}_{N+2},\cdots,\mathbf{\vec e}_{N+M} \right]\in \mathbb R^{M\times d}$ 。

2. 对于 numerical field ，现有的 representation 方法可以总结为三类：No Embedding、Field Embedding、Discretization 。

   • No Embedding：这种方式直接使用原始值或原始值的变换，而不学习 embedding 。例如，Google Play 的 Wide & Deep 和JD.com 的 DMT 分别使用原始数值特征和归一化的数值特征。此外，YouTube DNN 利用了归一化特征取值 ${\tilde{x}}_j$$\tilde x_{j}$ 的几种变换（即平方、平方根）：

     $$\begin{array}{}\text{(3)}& {\overrightarrow{\mathbf{e}}}_{\text{YouTube}}=[{\tilde{x}}_1^2,{\tilde{x}}_1,\sqrt{{\tilde{x}}_1},{\tilde{x}}_2^2,{\tilde{x}}_2,\sqrt{{\tilde{x}}_2},\cdots ,{\tilde{x}}_N^2,{\tilde{x}}_N,\sqrt{{\tilde{x}}_N}]\in {\mathbb{R}}^{3N}\end{array}$$

     在 Facebook 的 DLRM 中，他们使用了一个多层感知机来建模所有的数值特征：

     $$\begin{array}{}\text{(4)}& {\overrightarrow{\mathbf{e}}}_{\text{DLRM}}=\text{DNN}([x_1,x_2,\cdots ,x_N])\end{array}$$

     其中 DNN 的结构为 512-256-d ， ${\overrightarrow{\mathbf{e}}}_{\text{DLRM}}\in {\mathbb{R}}^d$$\mathbf{\vec e}_\text{DLRM}\in \mathbb R^d$ 。

     直观而言，这些 No Embedding 方法由于容量太小，很难捕获到 numerical field 的 informative 知识。

   • Field Embedding：学术界常用的方法是 Field Embedding，即同一个 field 内的的所有数值特征共享一个 uniform field embedding ，然后将这个 field embedding 与它们的特征取值相乘：

     $$\begin{array}{}\text{(5)}& {\overrightarrow{\mathbf{e}}}_{\text{FE}}=[x_1{\overrightarrow{\mathbf{e}}}_1,x_2{\overrightarrow{\mathbf{e}}}_2,\cdots ,x_N{\overrightarrow{\mathbf{e}}}_N]\in {\mathbb{R}}^{N\times d}\end{array}$$

     其中：${\overrightarrow{\mathbf{e}}}_j\in {\mathbb{R}}^d$$\mathbf{\vec e}_{j} \in \mathbb R^d$ 为第 $j$$j$ 个numerical field 的 uniform embedding vector 。

     然而，由于单个共享的 field-specific embedding 、以及field 内不同特征之间的线性缩放关系，Field Embedding 的 representation 容量是有限的。

     例如，收入 $x=1$$x=1$ 和收入 $x=10000$$x=10000$ ，根据 Field Embedding 的做法：

     $$\begin{array}{}\text{(6)}& (1\times \overrightarrow{\mathbf{e}})\cdot (1\times \overrightarrow{\mathbf{e}})<(1\times \overrightarrow{\mathbf{e}})\cdot (10000\times \overrightarrow{\mathbf{e}})\end{array}$$

     即，收入分别为1 和 10000 的两个用户，其相似度大于收入分别为 1 和 1 的两个用户。这在实际场景中是不恰当的。

   • Discretization：在工业推荐系统中，处理数值特征的一个流行方法是 Discretization ，即把数值特征转化为 categorical feature 。对于第 $j$$j$ 个 numerical field 的特征 $x_j$$x_{j}$ ，可以通过两阶段操作得到 feature embedding ${\overrightarrow{\mathbf{e}}}_j$$\mathbf{\vec e}_{j}$：离散化 discretization 和 embedding look-up：

     $$\begin{array}{}\text{(7)}& {\overrightarrow{\mathbf{e}}}_j={\mathbf{E}}_j{d}_j(x_j)\end{array}$$

     其中：${\mathbf{E}}_j\in {\mathbb{R}}^{H_j\times d}$$\mathbf E_{j}\in \mathbb R^{H_{j}\times d}$ 为第 $j$$j$ 个 numerical field 的 embedding matrix ；$H_j$$H_{j}$ 为离散化之后的桶数量；$d_j(\cdot )$$d_{j}(\cdot)$ 为针对第 $j$$j$ 个 numerical field 人工设计的离散化函数，它将该特征内的每个特征取值映射到 $H_j$$H_{j}$ 个桶中。

     具体来说，有三种广泛使用的离散化函数：

     • Equal Distance/Frequency Discretization: EDD/EFD：EDD 将特征取值划分到 $H_j$$H_{j}$ 个等宽的桶中。假设第 $j$$j$ 个 numerical field 的特征取值范围为 $[x_j^{min},x_j^{max}]$$\left[x^\min_{j}, x_{j}^\max\right]$，区间宽度 interval width 定义为 $w_j=(x_j^{max}-x_j^{min})/H_j$$w_{j} = \left(x_{j}^\max - x_{j}^\min\right)/H_{j}$ 。因此，通过 EDD 离散化函数 $d_j^{\text{EDD}}(\cdot )$$d_{j}^\text{EDD}(\cdot)$ 得到离散化结果 ${\hat{x}}_j$$\hat x_{j}$：

       $$\begin{array}{}\text{(8)}& {\hat{x}}_j=d_j^{\text{EDD}}(x_j)=\text{floor}\left(\frac{x_j-x_j^{min}}{w_j}\right)\end{array}$$

       类似地，EFD 将范围 $[x_j^{min},x_j^{max}]$$\left[x^\min_{j}, x_{j}^\max\right]$ 划分为若干个桶，使得每个桶包含相同数量的样本。

     • Logarithm Discretization: LD：Kaggle 比赛中 Criteo advertiser prediction 的冠军利用对数和 floor 操作将数值特征转化为 categorical 形式。离散化后的结果 ${\hat{x}}_j$$\hat x_{j}$ 通过LD 离散化函数 $d_j^{\text{LD}}(\cdot )$$d_{j}^\text{LD}(\cdot)$ 得到：

       $$\begin{array}{}\text{(9)}& {\hat{x}}_j=d_j^{\text{LD}}(x_j)=\text{floor}(\log (x_j{)}^2)\end{array}$$

     • Tree-based Discretization: TD：除了深度学习模型外，tree-based 模型（如 GBDT ）在推荐中被广泛使用，因为它们能够有效地处理数值特征。因此，许多 tree-based 方法被用来离散化数值特征。

     虽然 Discretization 在工业界被广泛使用，但它们仍然有三个限制（如下图所示）：

     • Two-Phase Problem: TPP：离散化过程是由启发式规则或其他模型决定的，因此它不能与 CTR 预测任务的最终目标一起优化，导致次优性能。

     • Similar value But Dis-similar embedding: SBD：这些离散化策略可能将类似的特征（边界值）分离到两个不同的桶中，因此它们之后的 embedding 明显不同。

       例如， Age field 常用的离散化是将 [18,40] 确定为青少年、[41,65] 确定为中年，这导致数值 40 和 41 的 embedding 明显不同。

     • Dis-similar value But Same embedding: DBS：现有的离散化策略可能将明显不同的元素分组同一个桶中，导致无法区分的 embedding。使用同一个例子（Age field ），18 和 40 之间的数值在同一个桶里，因此被分配了相同的 embedding 。然而，18 岁和 40 岁的人可能具有非常不同的特征。基于离散化的策略不能有效地描述数值特征变化的连续性。

     

3. 综上所述，下表中列出了 AutoDis 与现有 representation 方法的三方面比较。我们可以观察到，这些方法要么因为容量小而难以捕获 informative 知识、要么需要专业的特征工程，这些可能会降低整体性能。因此，我们提出了 AutoDis 框架。据我们所知，它是第一个具有高模型容量、端到端训练、以及保留 unique representation 特性的 numerical features embedding learning 框架。

   

39.1.2 AutoDis

1. AutoDis 框架如 Figure 3 所示，它可以作为针对数值特征的可插拔的 embedding framework ，与现有的深度 CTR 模型兼容。AutoDis 包含三个核心模块：meta-embedding、automatic discretization、aggregation 。

   代码实现比较简单直观： 数值特征 $x$$x$ （标量） -> 单层 DNN 网络（隐层维度为 $H$$H$ ，softmax 激活函数） -> 单层 DNN 网络（隐层维度为 $d$$d$ ，无激活函数）。

   

   对于第 $j$$j$ 个 numerical field，AutoDis 可以通过如下方式为每个数值特征 $x_j$$x_{j}$ 学习一个 unique representation （如 Figure 4 所示）：

   $$\begin{array}{}\text{(10)}& {\overrightarrow{\mathbf{e}}}_j=f(d_j^{\text{Auto}}(x_j),{\mathbf{ME}}_j)\end{array}$$

   其中：

   • ${\mathbf{ME}}_j$$\mathbf {ME}_{j}$ 是第 $j$$j$ 个 numerical field 的 meta-embedding matrix 。

   • $d_j^{\text{Auto}}(\cdot )$$d_{j}^\text{Auto}(\cdot)$ 是第 $j$$j$ 个 numerical field 的 automatic discretization 函数。

   • $f(\cdot )$$f(\cdot)$ 为聚合函数。

     所有 numerical field 都使用相同的聚合函数。

   最后，categorical 特征和数值特征的 embedding 被拼接起来，并馈入一个深度 CTR 模型进行预测：

   $$\begin{array}{}\text{(11)}& \hat{y}=\text{CTR}(\underset{\text{numerical embeddings}}{\underbrace{{\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,\cdots ,{\overrightarrow{\mathbf{e}}}_N}};\underset{\text{categorical embeddings}}{\underbrace{{\overrightarrow{\mathbf{e}}}_{N+1},{\overrightarrow{\mathbf{e}}}_{N+2},\cdots ,{\overrightarrow{\mathbf{e}}}_{N+M}}})\end{array}$$

   

2. Meta-Embeddings： 为了平衡模型的容量和复杂性，对于第 $j$$j$ 个 numerical field ，我们设计了一组 meta-embeddings ${\mathbf{ME}}_j\in {\mathbb{R}}^{H_j\times d}$$\mathbf {ME}_{j}\in \mathbb R^{H_{j}\times d}$ ，其中 ${\mathbf{ME}}_j$$\mathbf {ME}_{j}$ 由该 field 内的特征所共享，$H_j$$H_{j}$ 为 meta-embedding 的数量。 每个 meta-embedding 可以被看作是潜在空间中的一个子空间，用于提高表达能力和容量。通过结合这些 meta-embedding ，学习到的 embedding 比 Field Embedding 方法更 informative ，因此可以很好地保留高的模型容量。此外，所需参数的数量由 $H_j$$H_{j}$ 所决定，因此模型的复杂性是高度可控的，使我们的方法 scalable 。

   对于不同的 field $j$$j$ ，$H_j$$H_j$ 的数量可以不同。对于均匀分布的field ，$H_j$$H_j$ 可以取较大的值；对于取值聚焦于几个点的 field，$H_j$$H_j$ 可以取较小的值。

3. Automatic Discretization：为了捕获数值特征的值和所设计的 meta-embeddings 之间的复杂关联，我们提出了一个可微的 automatic discretization 模块 $d_j^{\text{Auto}}(\cdot )$$d_{j}^\text{Auto}(\cdot)$ 。由于有 $d_j^{\text{Auto}}(\cdot )$$d_{j}^\text{Auto}(\cdot)$ ，第 $j$$j$ 个 numerical field 的每个数值特征被离散化到 $H_j$$H_{j}$ 个桶，每个 bucket embedding 对应于上面提到的 meta-embedding 。

   具体而言，利用一个带有 skip-connection 的两层神经网络，将numerical field 特征取值 $x_j$$x_{j}$ 离散化到 $H_j$$H_{j}$ 个桶中：

   $$\begin{array}{}\text{(12)}& \begin{array}{c}{\overrightarrow{\mathbf{h}}}_j=\text{Leaky-ReLU}\left({\overrightarrow{\mathbf{w}}}_j{x}_j\right)\\ {\widetilde{\overrightarrow{\mathbf{x}}}}_j={\mathbf{W}}_j{\overrightarrow{\mathbf{h}}}_j+\alpha {\overrightarrow{\mathbf{h}}}_j\end{array}\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{w}}}_j\in {\mathbb{R}}^{H_j},{\mathbf{W}}_j\in {\mathbb{R}}^{H_j\times H_j}$$\mathbf{\vec w}_j\in \mathbb R^{H_j}, \mathbf W_j\in \mathbb R^{H_j\times H_j}$ 为 automatic discretization network 在第 $j$$j$ 个 numerical feature field 上的可学习参数。
   • Leaky-ReLU 为激活函数，$\alpha$$\alpha$ 为 skip-connection 的控制因子 control factor 。

   投影结果为：${\widetilde{\overrightarrow{\mathbf{x}}}}_j=[{\tilde{x}}_{j,1},{\tilde{x}}_{j,2},\cdots ,{\tilde{x}}_{j,H_j}]$$\tilde{\mathbf{\vec x}}_j = \left[\tilde x_{j,1},\tilde x_{j,2},\cdots,\tilde x_{j,H_j}\right]$ ，其中 ${\tilde{x}}_{j,h}$$\tilde x_{j,h}$ 为numerical field 特征取值 $x_j$$x_j$ 在第 $h$$h$ 个桶的投影输出。最后，通过 Softmax 函数将numerical field 特征取值 $x_j$$x_j$ 与每个 meta-embedding ${\mathbf{ME}}_j$$\mathbf {ME}_j$ 之间的相关性进行归一化：

   $$\begin{array}{}\text{(13)}& {\hat{x}}_{j,h}=\frac{\exp \left({\tilde{x}}_{j,h}/\tau \right)}{\sum _{k=1}^{H_j}{\tilde{x}}_{j,k}/\tau }\end{array}$$

   其中：$\tau$$\tau$ 为温度系数，用于控制 discretization 分布。因此，通过 automatic discretization 函数 $d_j^{\text{Auto}}(\cdot )$$d_{j}^\text{Auto}(\cdot)$ ，得到离散化的结果 ${\widehat{\overrightarrow{\mathbf{x}}}}_j\in {\mathbb{R}}^{H_j}$$\hat{\mathbf{\vec x}}_j\in \mathbb R^{H_j}$：

   $$\begin{array}{}\text{(14)}& {\widehat{\overrightarrow{\mathbf{x}}}}_j=d_j^{\text{Auto}}(x_j)=[{\hat{x}}_{j,1},{\hat{x}}_{j,2},\cdots ,{\hat{x}}_{j,H_j}]\end{array}$$

   ${\widehat{\overrightarrow{\mathbf{x}}}}_j$$\hat{\mathbf{\vec x}}_j$ 是一个向量，其中每个元素 ${\hat{x}}_{j,h}$$\hat x_{j,h}$ 表示 numerical field 特征取值 $x_j$$x_j$ 被离散化到第 $h$$h$ 个桶中的概率，它表示 numerical field 特征取值 $x_j$$x_j$ 与第 $h$$h$ 个 meta-embedding （即 bucket embedding ）之间的相关性。这种离散化方法可以理解为 soft discretization 。与前面提到的 hard discretization 相比， soft discretization 没有将特征取值离散化到一个确定的桶中，这样就可以很好地解决 SBD 和 DBS 问题。此外，可微的 soft discretization 使我们的 AutoDis 能够实现端到端的训练，并以最终目标进行优化。

   值得注意的是：当温度系数 $\tau \to \mathrm{\infty }$$\tau\rightarrow \infty$ 时，discretization 分布趋于均匀分布；当 $\tau \to 0$$\tau\rightarrow 0$ 时，discretization 分布趋于 one-hot 分布。因此，温度系数 $\tau$$\tau$ 在 automatic discretization distribution 中起着重要作用。此外，不同 field 的特征分布是不同的，因此对不同的 features 学习不同的 $\tau$$\tau$ 具有很大的必要性。具体而言，我们提出了一个温度系数自适应网络 temperature coefficient adaptive network （双层网络），它同时考虑了 global field statistics feature 和 local input feature ，公式如下：

   $$\begin{array}{}\text{(15)}& {\tau }_{x_j}=\text{Sigmoid}\left({\mathbf{W}}_j^{(2)}\text{Leaky-ReLU}\left({\mathbf{W}}_j^{(1)}[{\overline{\overrightarrow{\mathbf{n}}}}_j||x_j]\right)\right)\end{array}$$

   其中：

   • ${\overline{\overrightarrow{\mathbf{n}}}}_j$$\bar{\mathbf{\vec n}}_j$ 为第 $j$$j$ 个numerical field 特征的全局统计特征向量，包括：采样的累积分布函数 Cumulative Distribution Function: CDF 、均值。$x_j$$x_j$ 为 local input feature 。$(\cdot ||\cdot )$$(\cdot ||\cdot)$ 为拼接操作。
   • ${\mathbf{W}}_j^{(1)},{\mathbf{W}}_j^{(2)}$$\mathbf W_j^{(1)}, \mathbf W^{(2)}_j$ 为待学习的权重参数。

   为了指导模型训练， ${\tau }_{x_j}$$\tau_{x_j}$ 的输出范围从 $(0,1)$$(0,1)$ rescale 为 $(\tau -ϵ,\tau +ϵ)$$(\tau-\epsilon, \tau+\epsilon)$，其中 $\tau$$\tau$ 是一个全局的超参数。

   $ϵ$$\epsilon$ 是什么？作者没有说。读者认为这里是一个超参数。

   这个温度系数自适应网络的设计不太简洁，工程实现也更复杂。根据实验部分的结论，这里完全可以微调 global 温度来实现。

4. Aggregation Function：在得到 feature value 和 meta-embeddings 之间的相关性后，可以通过对 meta-embeddings 进行聚合操作 $f(\cdot )$$f(\cdot)$，将相关性作为选择概率来生成 embedding 。我们考虑了以下聚合函数 $f(\cdot )$$f(\cdot)$：

   • Max-Pooling：选择最相关的 meta-embedding （具有最高概率 ${\hat{x}}_{j,h}$$\hat x_{j,h}$ ）：

     $$\begin{array}{}\text{(16)}& {\overrightarrow{\mathbf{e}}}_j={\mathbf{ME}}_{j,k},k=\arg \underset{1\le h\le H_j}{max}{\hat{x}}_{j,h}\end{array}$$

     其中：$k$$k$ 是具有最高概率${\hat{x}}_{j,h}$$\hat x_{j,h}$ 的最相关 meta-embedding 的索引， ${\mathbf{ME}}_{j,k}$$\mathbf {ME}_{j,k}$ 是 ${\mathbf{ME}}_j$$\mathbf {ME}_j$ 中的第 $k$$k$ 个 meta-embedding 。

     然而，这种 hard selection 策略使 AutoDis 退化为一种 hard discretization 方法，从而导致上述的 SBD 问题和 DBS 问题。

   • Top-K-Sum：将具有最高相关性 ${\hat{x}}_{j,h}$$\hat x_{j,h}$ 的 top-K 个 meta-embedding 相加：

     $$\begin{array}{}\text{(17)}& {\overrightarrow{\mathbf{e}}}_j=\sum _{l=1}^K{\mathbf{ME}}_{j,k_l},k_l=\arg \underset{1\le h\le H_j,l-th}{max}{\hat{x}}_{j,h}\end{array}$$

     其中 $k_l$$k_l$ 是第 $l$$l$ （$1\le l\le K$$1\le l\le K$ ）大的 ${\hat{x}}_{j,h}$$\hat x_{j,h}$ 的 meta-embedding 的索引， ${\mathbf{ME}}_{j,k}$$\mathbf {ME}_{j,k}$ 是 ${\mathbf{ME}}_j$$\mathbf {ME}_j$ 中的第 $k$$k$ 个 meta-embedding 。

     然而，Top-K-Sum方法 有两个局限性：

     • 尽管与 Max-Pooling 相比，可能生成的 embedding 数量从 $H_j$$H_j$ 增加到 $C_{H_j}^K$$C_{H_j}^K$，但它不能从根本上解决 DBS 问题。
     • 学习到的 embedding ${\overrightarrow{\mathbf{e}}}_j$$\mathbf{\vec e}_j$ 未考虑相关性的取值。

   • Weighted- Average：充分地利用整个 meta-embeddings 集合、以及 meta-embedding 与特征取值的相关性：

     $$\begin{array}{}\text{(18)}& {\overrightarrow{\mathbf{e}}}_j=\sum _{h=1}^{H_j}{\hat{x}}_{j,h}{\mathbf{ME}}_{j,h}\end{array}$$

     通过这种加权聚合策略，相关的元嵌入对提供一个信息丰富的嵌入有更大的贡献，而不相关的元嵌入则在很大程度上被忽略了。此外，这种策略保证了每个特征都能学到 unique representation ，同时，学到的 embedding 是 Continuous-But-Different ，即，特征取值越接近则 embedding 就越相似。

5. 训练：AutoDis 是以端到端的方式与具体的深度 CTR 模型的最终目标共同训练的。损失函数是广泛使用的带有正则化项的LogLoss：

   $$\begin{array}{}\text{(19)}& \mathcal{L}=-[\frac{1}{Q}\sum _{i=1}^Q{y}_i\log {\hat{y}}_i+(1-y_i)\log (1-{\hat{y}}_i)+\lambda ||\mathrm{\Theta }|{|}_2]\end{array}$$

   其中：$y_i$$y_i$ 和 ${\hat{y}}_i$$\hat y_i$ 为第 $i$$i$ 个样本的 ground truth label 和预测结果；$Q$$Q$ 为总的训练样本数；$\lambda$$\lambda$ 为 L2 正则化系数；$\mathrm{\Theta }=\{{\mathrm{\Theta }}_{\text{Cat-Emb}},{\mathrm{\Theta }}_{\text{AutoDis}},{\mathrm{\Theta }}_{\text{CTR}}\}$$\Theta=\{\Theta_\text{Cat-Emb},\Theta_\text{AutoDis},\Theta_\text{CTR}\}$ 为 categorical field 的 feature embedding 参数、meta-embedding 和 automatic discretization 参数、以及深度 CTR 模型的参数。

   为了稳定训练过程，我们在数据预处理阶段采用了特征归一化技术，将数值特征取值缩放到 [0, 1] 。第 $j$$j$ 个 numerical field 的取值 $x_j$$x_j$ 被归一化为：

   $$\begin{array}{}\text{(20)}& x_j\leftarrow \frac{x_j-x_j^{min}}{x_j^{max}-x_j^{min}}\end{array}$$

39.2 实验

1. 数据集：

   • Criteo：Criteo Display Advertising Challenge 2013 发布的，包含 13 个 numerical feature field 。
   • AutoML：AutoML for Lifelong Machine Learning Challenge in NeurIPS 2018 发布的，包含 23 个numerical feature field 。
   • 工业数据集：从一个主流的在线广告平台上采样收集的，有 41 个 numerical feature field 。

   数据集的统计数据如下表所示。

   

2. 评估指标：AUC, LogLoss。

   所有的实验都通过改变随机数种子重复 5 次。采用 two-tailed unpaired t-test 来检测 AutoDis 和最佳 baseline 之间的显著差异。

3. baseline 方法：为了证明所提出的 AutoDis 的有效性，我们将 AutoDis 与数值特征的三类 representation learning 方法进行了比较：No Embedding（YouTube, DLRM）、Field Embedding: FE（DeepFM ）、Discretization （EDD ，如 IPNN；LD 以及 TD，如 DeepGBM）。

   此外，为了验证 AutoDis 框架与 embedding-based 的深度 CTR 模型的兼容性，我们将 AutoDis 应用于六个代表性模型：FNN、Wide & Deep、DeepFM、DCN、IPNN、xDeepFM 。

4. 实现：

   • 我们用 mini-batch Adam 优化所有的模型，其中学习率的搜索空间为 {10e-6, 5e-5, ... , 10e-2} 。
   • 此外，在 Criteo 和 AutoML 数据集中， embedding size 分别被设置为 80 和 70 。
   • 深度 CTR 模型中的隐层默认固定为1024-512-256-128 ，DCN 和 xDeepFM 中的显式特征交互（即 CrossNet 和 CIN ）被设置为 3 层。
   • L2 正则化系数的搜索空间为 {10e-6, 5e-5, ... , 10e-3} 。
   • 对于 AutoDis ，每个 numerical field 的 meta-embedding 数量为：Criteo 数据集为 20 个，AutoML 数据集为 40 个。
   • skip-connection 控制因子的搜索空间为 {0, 0.1, ... , 1} ，temperature coefficient adaptive network 的神经元数量设置为 64

5. 和其它 Representation Learning 方法的比较：我们在三个数据集上执行不同的 numerical feature representation learning 方法，并选择 DeepFM 作为深度 CTR 模型。结果如下表所示。可以看到：

   • AutoDis 在所有数据集上的表现都远远超过了所有的 baseline ，显示了其对不同数值特征的优越性和鲁棒性。

   • No Embedding 和 Field Embedding 方法的表现比 Discretization 和 AutoDis 更差。No Embedding 和 Field Embedding 这两类方法存在容量低和表达能力有限的问题。

     No Embedding, Field Embedding 二者之间的差距不大，基本上在 0.1% 以内。

   • 与现有的三种将数值特征转化为 categorical 形式的 Discretization 方法相比，AutoDis 的 AUC 比最佳 baseline 分别提高了 0.17% 、0.23% 、以及 0.22% 。

   

6. 不用 CTR 模型的比较：AutoDis 是一个通用框架，可以被视为改善各种深度 CTR 模型性能的插件。为了证明其兼容性，这里我们通过在一系列流行的模型上应用 AutoDis 进行了广泛的实验，结果如下表所示。可以看到：与 Field Embedding representation 方法相比，AutoDis 框架显著提高了这些模型的预测性能。numerical feature discretization 和 embedding learning 过程的优化是以这些 CTR 模型为最终目标的，因此可以得到 informative representation ，性能也可以得到提高。

   

7. Online A/B Testing：我们在一个主流广告平台上进行在线实验从而验证 AutoDis 的优越性能，该平台每天有数百万活跃用户与广告互动，并产生数千万的用户日志事件。对于控制组，数值特征通过 hybrid manually-designed rules （如 EDD、TD 等）进行离散化。实验组则选择 AutoDis 对所有数值特征进行离散化和自动学习 embedding 。将 AutoDis 部署到现有的 CTR 模型中很方便，几乎不需要 online serving 系统的工程工作。

   AutoDis 实现了 0.2% 的离线 AUC 的提升。此外，相对于对照组，实验组在线 CTR 和 eCPM 分别提升了 2.1% 和 2.7% （统计学意义），这带来了巨大的商业利润。

   此外，随着 AutoDis 的融合，现有的数值特征不再需要任何离散化规则。此外，在未来引入更多的数值特征将更加有效，而不需要探索任何人工制作的规则。

8. Embedding Analysis：为了更深入地理解通过 AutoDis 学到的 Continuous-But-Different embedding ，我们分别在 embeddings 的宏观分析、以及 soft discretization 的微观分析中做了进一步的调研。

   • Embeddings 的宏观分析：下图提供了 DeepFM-AutoDis 和 DeepFM-EDD 在 Criteo 数据集的第 3 个 numerical field 中得出的 embedding 的可视化。我们随机选择 250 个 embedding ，并使用 t-SNE 将它们投影到一个二维空间。具有相似颜色的节点具有相似的值。可以看到：

     • AutoDis 为每个特征学习了一个 unique embedding 。此外，相似的数值特征（具有相似的颜色）由密切相关的 embeddings （在二维空间中具有相似的位置）来表示，这阐述了 embedding 的 Continuous-But-Different 的特性。
     • 然而，EDD 为一个桶中的所有特征学习相同的 embedding 、而在不同的桶中学习完全不同的 embedding ，这导致了 to step-wise "unsmooth" embedding ，从而导致了较差的任务表现。

     

   • Soft Discretization 的微观分析：我们通过调查 DeepFM-AutoDis 的 soft discretization 过程中的 Softmax 分布进行一些微观分析。我们从 Criteo 数据集的第 8 个 numerical field 中选择一个相邻的 feature-pair （特征取值为 1 和 2 ）、以及一个相距较远的feature-pair （特征取值为 1 和 10 ），然后在下图中可视化它们的 discretization distribution 。可以看到：相邻的feature-pair 具有相似的 Softmax 分布，而相距较远的feature-pair 具有不同的分布。

     这一特点有利于保证相似的特征取值能够通过 AutoDis 学习相似的 embedding ，从而保持 embedding 的连续性。

     

9. Numerical Fields Analysis：为了评估 DeepFM-AutoDis 对每个 numerical field 的影响，在 Criteo 数据集中，我们选择了所有26 个 categorical fields 作为基础特征，并每次累积添加 13 个 numerical fields 中的一个。下图展示了根据数据集的原始顺序和随机顺序添加 numerical fields 的预测性能。可以看到：

   • 即使只有一个 numerical field ，AutoDis 也能提高性能。
   • AutoDis 对多个 numerical fields 具有 cumulative improvement 。
   • 与现有方法相比，AutoDis 取得的性能改善更加显著和稳定。

   

10. Model Complexity：为了定量分析我们提出的 AutoDis 的空间复杂度和时间复杂度，我们比较了 DeepFM 上的 EDD 离散化方法的模型参数、以及 batch inference time ，结果如下表所示。可以看到：

    • 与 EDD 相比，AutoDis增加的模型参数量可以忽略不计。
    • 此外，AutoDis 的计算效率也是可比的。

    

11. 消融研究和超参数敏感性：

    • 聚合策略：下图总结了 DeepFM-AutoDis 采用 Max-Pooling 、Top-K-Sum 、Weighted-Average 等聚合策略的预测性能。可以看到：Weighted-Average 策略实现了最好的性能。原因是：与其他策略相比，Weighted-Average 策略充分利用了 meta-embeddings 及其相应的关联性，完全克服了 DBS 和 SBD 问题。

      

    • 温度系数：为了证明 temperature coefficient adaptive network 在生成 feature-specific ${\tau }_{x_j}$$\tau_{x_j}$ 的有效性，我们将 ${\tau }_{x_j}$$\tau_{x_j}$ 与不同全局温度 $\tau$$\tau$ 进行比较。如下图所示：

      • 在 Criteo 和AutoML 数据集上，最佳全局温度分别为 1e-5 和 4e-3 左右。
      • 然而，我们的 temperature coefficient adaptive network 取得了最好的结果（红色虚线），因为它可以根据 global field statistics feature 和 local input feature ，针对不同的特征自适应地调整温度系数，获得更合适的 discretization distribution 。

      

    • Meta-Embeddings 的数量：实验结果如下图所示。可以看到：

      • Meta-Embeddings 数量的增加有助于在开始时大幅提高性能，因为 meta-embeddings 中涉及更丰富的信息。
      • 然而，使用过多的 meta-embeddings 不仅会增加计算负担，而且会使性能受挫。

      考虑到预测效果和训练效率，我们将 Criteo和 AutoML 数据集的数量分别设定为 20 和 40 。

      

四十、MDE[2020]

1. 标准的 embedding 做法是：将 objects 以固定的统一纬度 uniform dimension: UD $d$$d$ 嵌入到 ${\mathbb{R}}^d$$\mathbb R^d$ 中。

   • 当 embedding 维度 $d$$d$ 太小时，下游任务的预测性能会受到影响。

   • 当 embedding 维度 $d$$d$ 太大、并且需要表示的 objects 数量很大时，内存消耗就成为一个问题。例如，在推荐模型中， embedding layer 可以占到存储模型所需内存的 99.9% 以上，而在 large-scale setting 中，它可能会消耗数百 GB 甚至数百TB 。

     不仅内存消耗是一个瓶颈，模型太大也容易过拟合。

   因此，寻找新颖embedding representation 是一个重要的挑战，其中该embedding representation 使用更少的参数，同时保留下游模型的预测性能。

   在现实世界的applications 中，object 的频率往往是严重倾斜的。例如：

   • 对于 full MovieLens 数据集，top 10% 的用户收到的 query 数量和剩余 90% 的用户一样多、top 1% 的 item 收到的 query 数量和剩余 99% 的 item 一样多。
   • 此外，在 Criteo Kaggle 数据集上， top 0:0003% 的 indices 收到的 query 数量与剩余 3200 万个 indices 一样多。

   为了在推荐中利用 heterogeneous object popularity ，论文 《Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems》提出了 mixed dimension(MD) embedding layer ，其中一个 specific-object 的 embedding 维度随着该object 的 popularity 而变化，而不是保持全局统一。论文的案例研究和理论分析表明：MD embedding 的效果很好，因为它们不会在rare embedding 上浪费参数，同时也不会欠拟合 popular embedding 。此外，在测试期间，MD embedding 通过有效地分配参数从而最小化 popularity-weighted loss 。

   论文贡献：

   • 论文提出了一种用于推荐系统的 mixed dimension embedding layer ，并提供了一种新颖的数学方法来确定具有可变 popularity 的特征的尺寸。这种方法训练速度快、易于调优、并且在实验中表现良好。
   • 通过矩阵补全 matrix completion 和 factorization model ，论文证明了在有足够的 popularity 倾斜的情况下， mixed dimension embedding 在内存有限的情况下会产生较低的失真，在数据有限的情况下会有更好的泛化效果。
   • 对于内存有限的领域，论文推导出最佳特征维度。这个维度只取决于特征的popularity、参数预算、以及pairwise 交互的奇异值谱。

40.1 背景

1. 与典型的协同过滤 collaborative filtering: CF 相比，CTR 预测任务包括额外的上下文。这些上下文特征通过索引集合（categorical ）和浮点数（continuous ）来表达。这些特征可以代表关于点击事件或个性化事件的上下文的任意细节。第 $i$$i$ 个 categorical 特征可以用一个索引 $x_i\in \{1,2,\cdots ,n_i\}$$x_i\in \{1,2,\cdots,n_i\}$ 来表达，$i=1,\cdots ,\kappa$$i=1,\cdots,\kappa$ 。 除了 categorical 特征，我们还有 $s$$s$ 个标量特征，这些标量一起产生一个稠密的特征向量 ${\overrightarrow{\mathbf{x}}}^{\prime }\in {\mathbb{R}}^s$$\mathbf{\vec x}^\prime\in \mathbb R^s$ 。因此，给定 $({\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_{\kappa },{\overrightarrow{\mathbf{x}}}^{\prime })\in {\mathbb{R}}^{n_1+n_2+\cdots +n_{\kappa }+s}$$\left(\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_{\kappa},\mathbf{\vec x}^\prime\right) \in \mathbb R^{n_1+n_2+\cdots+n_\kappa+s}$ ，我们想预测点击事件$y\in \{0,1\}$$y\in \{0,1\}$ ，其中 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为 $x_i$$x_i$ 的 one-hot 向量。

   我们使用 SOTA 的 deep learning recommendation model: DLRM 作为一个现成的深度模型。各种深度 CTR 预测模型都是由内存密集型的 embedding layer 驱动的。 embedding layer 的大小和预测性能之间的权衡似乎是一个不可避免的权衡。对于一个给定的模型 $f_{\theta }$$f_\theta$ （$\theta$$\theta$ 为参数），标准的做法是用 embedding layer $\mathbf{E}$$\mathbf E$ 来表示 categorical 特征。通常，每个 categorical 特征都有自己的独立的 embedding matrix：$E[(x_1,\cdots ,x_{\kappa })]=({\mathbf{E}}^{(1)}{\overrightarrow{\mathbf{x}}}_1,\cdots ,{\mathbf{E}}^{(\kappa )}{\overrightarrow{\mathbf{x}}}_{\kappa })$$E[(x_1,\cdots,x_\kappa)] = \left(\mathbf E^{(1)}\mathbf{\vec x}_1,\cdots,\mathbf E^{(\kappa)}\mathbf{\vec x}_\kappa\right)$ ，其中 $E[\cdot ]$$E[\cdot]$ 为 embedding layer，${\mathbf{E}}^{(i)}$$\mathbf E^{(i)}$ 为第 $i$$i$ 个 categorical 的 embedding matrix 。

2. 相关工作：最近的工作提出了类似、但实质上不同的 non-uniform embedding 架构的技术，尤其是针对自然语言处理领域（《Groupreduce: Block-wise low-rank approximation for neural language model shrinking》、《Adaptive input representations for neural language modeling》）。这些方法都不适合用于 CTR 预测，因为它们忽略了 CTR 中固有的 feature-level 结构。

   还有一些方法是为 RecSys embedding layer 提出神经架构搜索neural architecture search : NAS （《Neural input search for large scale recommendation models》），其中使用强化学习算法来构建 embedding layer 。与计算昂贵的 NAS 相比，我们表明 non-uniform embedding layer 的架构搜索可以简化为调优一个超参数，而不需要 NAS 。由于我们的理论框架，模型搜索的这种简化是可能的。此外，与以前所有的 non-uniform embedding 的工作相比，我们从理论上分析了我们的方法。此外，过去的工作并没有从经验上验证他们的方法所推测的工作机制。

3. 从 popularity 倾斜的角度来看， embedding normalization 实际上隐含了对 rare embeddings 的惩罚，而不是对 popular embeddings 的惩罚。这是因为更大一部分的 training updates 仅包含 rare embeddings 的 norm penalty signal (而很少包含 rare 出现的事件）。

4. 如下图所示，图 (a) 表示 Criteo Kaggle 数据集中所有特征的 access 的直方图；图 (b), (c) 分别为 MovieLens 数据集的 user feature, item feature 的 access 的直方图。

   这些图都是典型的长尾分布。

   

40.2 模型

1. MD embedding layer 架构 $\overline{\mathbf{E}}$$\bar{\mathbf E}$ 由 $\kappa$$\kappa$ 个 block 组成，每个 block 对应一个 categorical field 。这些 block 定义为 $2\kappa$$2\kappa$ 个矩阵：$\overline{\mathbf{E}}=({\overline{\mathbf{E}}}^{(1)},\cdots ,{\overline{\mathbf{E}}}^{(\kappa )},{\overline{\mathbf{P}}}^{(1)},\cdots ,{\overline{\mathbf{P}}}^{(\kappa )})$$\bar{\mathbf E} = \left(\bar{\mathbf E}^{(1)},\cdots,\bar{\mathbf E}^{(\kappa)},\bar{\mathbf P}^{(1)},\cdots,\bar{\mathbf P}^{(\kappa)}\right)$，其中：

   • ${\overline{\mathbf{E}}}^{(i)}\in {\mathbb{R}}^{n_i\times d_i},{\overline{\mathbf{P}}}^{(i)}\in {\mathbb{R}}^{d_i\times \overline{d}}$$\bar{\mathbf E}^{(i)}\in \mathbb R^{n_i\times d_i}, \bar{\mathbf P}^{(i)}\in \mathbb R^{d_i\times \bar d}$ 为第 $i$$i$ 个 block 的矩阵；$d_i$$d_i$ 为第 $i$$i$ 个 categorical 特征的 embeding size ；$n_i$$n_i$ 为第 $i$$i$ 个 categorical 特征的词表大小；$\overline{d}$$\bar d$ 为所有 categorical 特征共享的 base dimension ，且满足 $\overline{d}\ge d_i$$\bar d \ge d_i$ ；$i=1,\cdots ,\kappa$$i=1,\cdots,\kappa$ 。
   • ${\overline{\mathbf{E}}}^{(i)}$$\bar{\mathbf E}^{(i)}$ 作为 MD embedding，然后 ${\overline{\mathbf{P}}}^{(i)}$$\bar{\mathbf P}^{(i)}$ 作为投影矩阵从投影到维度 $\overline{d}$$\bar d$ 的公共空间。

2. 一个关键问题是如何确定 embedding size $\overrightarrow{\mathbf{d}}=(d_1,d_2,\cdots ,d_{\kappa })$$\mathbf{\vec d} = (d_1,d_2,\cdots,d_\kappa)$ 。

   Power-law Sizing Scheme：我们定义 block-level 概率 $\overrightarrow{\mathbf{p}}\in {\mathbb{R}}^{\kappa }$$\mathbf{\vec p}\in \mathbb R^\kappa$ ，其中 $p_i$$p_i$ 为第 $i$$i$ 个 block 中的 embedding 的平均查询概率。当 block 与特征一一对应（我们这里的情况），那么 $p_i=\frac{1}{n_i}$$p_i = \frac{1}{n_i}$ 。

   假设 categorical feature 都是单值（而不是多值的），那么对于词表大小为 $n_i$$n_i$ 的 categorical feature，每个取值出现的平均概率为 $1/n_i$$1/n_i$ 。

   更一般的情况下，${\overrightarrow{\mathbf{p}}}_i=\sum _j\prod _{i,j}$$\mathbf{\vec p}_i = \sum_j \prod_{i,j}$ ，其中 $\prod$$\prod$ 为 block-wise 伯努利采样矩阵。那么 Popularity-Based Dimension Sizing 为：

   $$\begin{array}{}\text{(21)}& \overrightarrow{\mathbf{d}}\leftarrow \overline{d}\times \frac{{\overrightarrow{\mathbf{p}}}^{\alpha }}{{\Vert \overrightarrow{\mathbf{p}}\Vert }_{\mathrm{\infty }}^{-\alpha }}\end{array}$$

   其中：无穷范数是元素绝对值中的最大值；$0\le \alpha \le 1$$0\le \alpha\le 1$ 为温度系数，当 $\alpha =0$$\alpha = 0$ 时 embedding size 都等于 $\overline{d}$$\bar d$ ，当 $\alpha =1$$\alpha = 1$ 时 embedding size 与它们的 popularity 成正比。

   理论分析见原始论文。

   注意：这里仅考虑 field-level 的 popularity，而没有考虑 value-level 的 popularity 。例如，“学历” 这个 field 中，低学历的 value 占比更大，需要更高的维度。

   论文中的这种维度分配方式，使得词表越大的 field，其维度越小；词表越小的 field，其维度越大。例如，“性别” 只有两个取值，该 field 被分配的 embedding 维度最大。

   论文中的这种维度分配是启发式的规则，并不是从数据中学到的。

40.3 实验

1. baseline 方法：统一的 $d=32$$d=32$ 的 DLRM 。

2. 实验结果：

   • $\alpha =0.3$$\alpha = 0.3$ 的 MD embedding 产生的 learning curve 与 $d=32$$d=32$ 的 UD embedding 相当（下图 (a)），但是参数规模减少了 16 倍。
   • MD embedding layer 改善了每种 parameter budget 下的 memory-performance （下图 (b)）。
   • 最佳温度 $\alpha$$\alpha$ 取决于 parameter budget ，对于较小的预算，较高的温度会导致更低的 loss 。
   • $\alpha =0.2$$\alpha = 0.2$ 的 embedding 获得的性能以 0.1% 的准确性优势略微优于 UD embedding，但是参数规模约为 UD embedding 的一半。
   • MD embedding 的训练速度比 UD embedding 快两倍（下图 (c)）。

   

四十一、NIS[2020]

1. 大多数现代神经网络模型可以被认为是由两个组件组成的：

   • 一个是将原始（可能是 categorical 的）输入数据转换为浮点值的输入组件。
   • 另一个是将输入组件的输出结合起来并计算出模型的最终输出的 representation learning 组件。

   自 《Neural Architecture Search with Reinforcement Learning》 发表以来，以自动化的、数据驱动的方式设计神经网络架构（AutoML ）最近吸引了很多研究兴趣。然而，该领域以前的研究主要集中在 representation learning 组件的自动化设计上，而对输入组件的关注很少。这是因为大多数研究都是在图像理解问题上进行的，其中 representation learning 组件对模型性能非常重要，而输入组件是微不足道的，因为图像像素已经是浮点形式。

   对于工业界经常遇到的大规模推荐问题，情况则完全不同。虽然 representation learning 组件很重要，但输入组件在模型中起着更关键的作用。这是因为许多推荐问题涉及到具有大 cardinality 的 categorical 特征，而输入组件为这些离散特征的每一项分配 embedding 向量。这就导致了输入组件中有大量的 embedding 参数，这些参数在模型大小和模型归纳偏置 inductive bias 上都占主导地位。

   例如，YouTube 视频推荐模型使用了一个规模为 1M 的 video ID vocabulary ，每个 video ID 有 256 维的 embedding 向量。这意味着仅 video ID 特征就使用了 256M 个参数，而且随着更多离散特征的加入，这个数字还会迅速增长。 相比之下， representation learning 组件只包括三个全连接层。因此，模型参数的数量主要集中在输入组件，这自然对模型性能有很高的影响。在实践中，尽管 categorical 特征的 vocabulary size 和 embedding size 很重要，但它们往往是通过尝试一些具有不同手工制作的配置的模型从而以启发式的方式选择的。由于这些模型通常体积大，训练成本高，这种方法计算量大，可能会导致次优的结果。

   在论文 《Neural Input Search for Large Scale Recommendation Models》 中，作者提出了 Neural Input Search: NIS ，这是一种新颖的方法，为模型输入组件的每个离散特征自动寻找 embedding size 和 vocabulary size 。NIS 创建了一个由 Embedding Blocks 集合组成的搜索空间，其中 blocks 的每个组合代表不同的 vocabulary and embedding 配置。最佳配置是通过像 ENAS 这样的强化学习算法在单个 training run 中搜索而来。

   此外，作者提出一种新的 embedding 类型，称之为 Multi-size Embedding : ME 。 ME 允许将较大尺寸（即，维度）的 embedding 向量分配给更常见的、或更 predictive 的 feature item ，而将较小尺寸的 embedding 向量分配给不常见的、或没有predictive 的 feature item 。这与通常采用的方法相反，即在词表的所有 item 中使用同样维度的 embedding ，这称之为 Single-size Embedding: SE 。作者认为，SE 是对模型容量和训练数据的低效利用。这是因为：

   • 对于频繁出现的、或高 predictive 的 item ，我们需要一个大的 embedding 维度来编码它们与其他 item 的细微关系 nuanced relation 。
   • 但对于长尾item ，由于它们在训练集中的稀有性 rarity ，训练相同维度的 good embedding 可能需要太多的 epoch 。并且当训练数据有限时，对于 rare item 采用大维度的 embedding 可能会过拟合。

   有了 ME ，在相同的模型容量下，我们可以覆盖词表中更多的 item ，同时减少所需的训练数据规模和计算成本从而为长尾item 训练良好的 embedding 。

   下图概览了基于 Embedding Blocks 的搜索空间、以及强化学习控制器如何对候选 SE 和 ME 进行采样。

   图 (a)：Single-size Embedding，其中仅保留 top 2M 个 item，embedding 维度 192 。

   图 (b)：Multi-size Embedding，其中 top 2M 个 item 的 embedding 维度为 192 、剩余 7M 个 item 的 embedding 维度为 64 。

   注意：这要求词表中的 id 是根据频次来降序排列。这对于频次分布的波动较大的 field 而言，需要经常重新编码 id 和重新训练。

   embedding table 包含两个超参数：emebdding size 、以及词表大小（即，保留高频的多少个 item）。这篇论文保留了所有的 item，并针对性地优化 embedding size 。

   

   作者通过在两个广泛研究的推荐问题的公共数据集上的实验，证明了 NIS 在为 SE 和 ME 寻找良好的 vocabulary size 和 embedding size 配置方面的有效性。给定 baseline 推荐模型，NIS 能够显著提高它们的性能，同时在所有实验中显著减少 embedding 参数的数量（从而减少模型的规模）。此外，作者将 NIS 应用于 Google App store 中的一个真实世界的大规模 App ranking 模型，并进行了离线实验和在线 A/B test ，结果是 +1.02% 的 App Install ，而模型大小减少了 30% 。这个新的 NIS App ranking 模型已经部署在生产中。

2. 相关工作：几乎所有以前的 NAS 研究工作都集中在为图像/视频理解问题寻找最佳的 representation learning 组件。对于大规模的推荐问题，通过利用先进的representation learning 组件（如 CNN, RNN 等）也取得了很大的成果。然而，尽管输入组件由于 embedding 从而包含了很大一部分模型参数，但它在整个工业界中经常被启发式地设计，如 YouTube, Google Play, Netflix 等。据我们所知，我们的工作首次将自动化的神经网络设计引入输入组件从而用于大规模推荐问题。

41.1 模型

1. 假设模型的输入由一组 categorical 特征 $\mathcal{F}$$\mathcal F$ 组成。对于每个特征 $F\in \mathcal{F}$$F\in \mathcal F$，我们有一个其可能取值的列表，这个列表中的元素按照在数据集中出现的频率递减的顺序排序。这个列表将每个特征取值隐式地映射为一个整数，我们把这个列表称为词表 vocabulary 。
2. 一个 embedding 变量 $\mathbf{E}\in {\mathbb{R}}^{v\times d}$$\mathbf E\in \mathbb R^{v\times d}$ 是一个可训练的矩阵，其中 $v$$v$ 为 vocabulary size ，$d$$d$ 为 embedding 维度。对于任何 $0\le i<v$$0\le i\lt v$ 的情况，${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec e}_i \in \mathbb R^d$ 表示 $\mathbf{E}$$\mathbf E$ 的第 $i$$i$ 行，即词表内第 $i$$i$ 个 item 的 embedding 向量。
3. 令 $\mathcal{B}$$\mathcal B$ 为我们的 "memory budget" ，它指的是模型的 embedding 矩阵使用的浮点数的总数。对于一个 ${\mathbb{R}}^{v\times d}$$\mathbb R^{v\times d}$ 的 embedding 矩阵，它的浮点数总数为 $v\times d$$v\times d$ 。

41.1.1 Neural Input Search Problems

1. Single-size Embedding: SE：single-size embedding 是一个形状为 $v\times d$$v\times d$ 的规则的 embedding 矩阵，其中词表中的每一个 item （共计 $v$$v$ 个 item）都表示为一个 $d$$d$ 维的 embedding 向量。以前的工作大多使用 SE 来表示离散的特征，每个特征的 $v$$v$ 和 $d$$d$ 的值是以启发式方式选择的，这可能是次优的。

   下面我们提出一个 Neural Input Search 问题从而自动寻找每个特征的最佳 SE ，即 NIS-SE。解决这个问题的方法将在后面介绍。

2. Problem NIS-SE：为每个 $F\in \mathcal{F}$$F\in \mathcal F$ 找到 vocabulary size $v_F$$v_F$ 和 embedding dimension $d_F$$d_F$ 从而最大化结果模型的目标函数值，使得：

   $$\begin{array}{}\text{(22)}& \sum _{F\in \mathcal{F}}{v}_F\times d_F\le \mathcal{B}\end{array}$$

   该问题涉及两个 trade-off：

   • 特征之间的 memory budget：更有用的特征应该得到更多的预算。

   • 每个特征内部的 vocabulary size 和 embedding dimension 之间的 memory budget。

     • 大的 vocabulary size 给了我们更高的覆盖率，让我们包括尾部 item 作为输入信号。
     • 大的 embedding dimension 可以提高我们对头部 item 的预测，因为头部 item 有更多的训练数据。此外，大的embedding dimension 可以编码更细微的信息。

   在 memory budget 内，SE 使得我们很难同时获得高覆盖率和高质量 embedding 。为了克服这一困难，我们引入了一种新的 embedding 类型，即 Multi-size Embedding 。

3. Multi-size Embedding: ME：Multi-size Embedding 允许词表中的不同 item 有不同维度的 embedding 。它让我们对头部 item 使用大维度的 embedding 、对尾部 item 使用小维度的 embedding 。对尾部 item 使用较少的参数是有意义的，因为它们的训练数据较少。

   现在，一个 embedding 变量（对应于一个特征）的 vocabulary size 和 embedding size 是由 Multisize Embedding Spec: MES 给出的。MES 是 pair 的列表：$[(v_1,d_1),(v_2,d_2),\cdots ,(v_M,d_M)]$$[(v_1,d_1),(v_2,d_2),\cdots,(v_M,d_M)]$ ，其中：

   • $v_m$$v_m$ 是第 $m$$m$ 个 pair 的 vocabulary size，满足 $1\le v_m\le v$$1\le v_m\le v$，其中 $v=\sum _{m=1}^M{v}_m$$v=\sum_{m=1}^M v_m$ 为这个 categorical feature 的总的 vocabulary size 。

     这相当于将单个词表划分为 $M$$M$ 块。

   • $d_m$$d_m$ 是第 $m$$m$ 个 pair 的 embedding size，满足 $d_1>d_2>\cdots >d_M\ge 1$$d_1\gt d_2\gt\cdots\gt d_M \ge 1$ 。

   这可以解释为：最开始的 $v_1$$v_1$ 个最高频的 item 有 embedding 维度 $d_1$$d_1$，接下来的 $v_2$$v_2$ 个频繁的 item 有 embedding 维度 $d_2$$d_2$ ，等等。当 $M=1$$M=1$ 时，ME 就等价于 SE 。

   我们对于每个 $1\le m\le M$$1\le m \le M$ ，创建了一个形状为 $v_m\times d_m$$v_m\times d_m$ 的 embedding 矩阵 ${\mathbf{E}}^m$$\mathbf E^m$，而不是像 SE中那样只有一个 embedding 矩阵 $\mathbf{E}$$\mathbf E$ 。此外，还为每个 $1\le m\le M$$1\le m\le M$ 创建了一个可训练的投影矩阵 ${\mathbf{P}}^m$$\mathbf P^m$，它将一个 $d_m$$d_m$ 维的 embedding 投影到 $d_1$$d_1$ 维的空间。这有利于下游的 reduction 操作在同一个 $d_1$$d_1$ 维空间进行。定义 $V_0=0$$V_0 = 0$ ，以及 $V_m=\sum _{i=1}^m{v}_i$$V_m = \sum_{i=1}^m v_i$ 为前 $m$$m$ 个 embedding 矩阵的累计 vocabulary size ，则词表中第 $k$$k$ 个 item 的 ME 定义为：

   $$\begin{array}{}\text{(23)}& {\overrightarrow{\mathbf{e}}}_k={\mathbf{P}}^{m_k}{\overrightarrow{\mathbf{e}}}_{k-V_{m_k-1}}^{m_k}\end{array}$$

   其中：$m_k\in \{1,\cdots ,M\}$$m_k\in \{1,\cdots,M\}$ ，并且 $k\in [V_{m_k-1},V_{m_k}]$$k\in [V_{m_k-1},V_{m_k}]$ ；${\overrightarrow{\mathbf{e}}}_{k-V_{m_k-1}}^{m_k}$$\mathbf {\vec e}^{m_k}_{k-V_{m_k-1} }$ 为矩阵 ${\mathbf{E}}^m$$\mathbf E^m$ 的第 $k-V_{m_k-1}$$k-V_{m_k-1}$ 行。

   $k-V_{m_k}-1$$k-V_{m_k}-1$ 是第 $k$$k$ 个 item 在第 $m_k$$m_k$ 个 block 内的相对编号。

   通过对每个特征的适当的 MES ，ME 能够同时实现对尾部 item 的高覆盖率、以及头部 item 的高质量 representation 。然而，为所有特征手动寻找最佳 MSE 是非常困难的，因此需要一个自动方法来搜索合适的 MES 。下面我们介绍 Multi-size Embedding 的Neural Input Search 问题，即 NIS-ME 。解决这个问题的方法将在后面介绍。

4. NIS-ME：为每个 $F\in \mathcal{F}$$F\in \mathcal F$ 找到一个 MES $[(v_1,d_1),(v_2,d_2),\cdots ,(v_M,d_M)]$$[(v_1,d_1),(v_2,d_2),\cdots,(v_M,d_M)]$ 从而最大化结果模型的目标函数值，使得：

   $$\begin{array}{}\text{(24)}& \sum _{F\in \mathcal{F}}\sum _{i=1}^{M_F}{v}_{F_i}\times d_{F_i}\le \mathcal{B}\end{array}$$

5. 在任何使用 embedding 的模型中，ME 都可以用来直接替代 SE 。通常，给定一组 vocabulary ID $\mathcal{K}$$\mathcal K$ ，$\mathcal{K}$$\mathcal K$ 中的每个元素被映射到其相应的 SE ，然后对这些 SE 进行一个或多个 reduce 操作。例如，一个常用的 reduce 操作是 bag-of-words: BOW ，即对 embedding 进行求和或求平均。为了了解在这种情况下 ME 是如何直接替代 SE 的，即 BOW 的 ME 版本（我们称之为 MBOW ），由以下公式给出：

   $$\begin{array}{}\text{(25)}& \sum _{k\in \mathcal{K}}{\overrightarrow{\mathbf{e}}}_k=\sum _{k\in \mathcal{K}}{\mathbf{P}}^{m_k}{\overrightarrow{\mathbf{e}}}_{k-V_{m_k-1}}^{m_k}\end{array}$$

   其中 ME 是相加的。这在下图中得到了说明。请注意，对于那些 $m_k$$m_k$ 相等的 $k$$k$ ，在应用投影矩阵之前，对 embedding 进行求和是更高效的。

   

41.1.2 Neural Input Search Approach

1. 我们在模型的输入组件开发了一个新的搜索空间，它包含了我们想要搜索的 SE 或 ME 。我们使用一个独立的 controller ，从而在每一个 step 中为每个离散特征挑选一个 SE 或 ME 。这些选中的 SE 或 ME 与主模型的其他部分（不包括控制器）一起被训练。此外，我们使用主模型的前向传播来计算控制器的选择的奖励（是准确率和内存成本的组合），并使用 A3C 策略梯度方法将奖励用于训练控制器变量。

   正如论文在实验部分所述，NIS 方法对具有大 vocabulary size 的 categorical 特征的影响更大。至于像性别、学历这种词典规模较小的 categorical 特征，则 NIS 方法的价值不大。

2. 搜索空间：

   • Embedding Blocks：对于 vocabulary size 为 $v$$v$ 的给定特征 $F\in \mathcal{F}$$F\in \mathcal F$ ，我们创建一组 $S\times T$$S\times T$ 个矩阵，其中 $S>1,T>1$$S\gt 1, T\gt 1$ 。第 $(s,t)$$(s,t)$ 个矩阵 ${\mathbf{E}}^{s,t}$$\mathbf E^{s,t}$ 的尺寸为 ${\overline{v}}_s\times {\overline{d}}_t$$\bar v_s\times \bar d_t$ ，其中 $v=\sum _{s=1}^S{\overline{v}}_s,d=\sum _{t=1}^T{\overline{d}}_t$$v=\sum_{s=1}^S \bar v_s, d = \sum_{t=1}^T \bar d_t$ ，$d$$d$ 为 vocabulary 中的 item 允许的最大 embedding size 。 我们称这些矩阵为 Embedding Blocks 。这可以看作是将一个大小为 $v\times d$$v\times d$ 的 embedding 矩阵离散化为 $S\times T$$S\times T$ 个子矩阵。

     例如，假设 v=10M （M 代表一百万），$d=256$$d=256$ ，我们可以把行离散成五块：[1M, 2M, 2M, 2M, 3M] ；可以把列离散成四块：[64, 64, 64, 64] 。这样就有 20 个 Embedding Blocks ，如 Figure 1所示。

     此外，对于每个 $1\le t\le T$$1\le t\le T$ ，我们创建一个尺寸为 ${\overline{d}}_t\times d$$\bar d_t\times d$ 的投影矩阵 ${\overline{\mathbf{P}}}^t$$\bar {\mathbf P}^t$ ，以便将每个 ${\overline{d}}_t$$\bar d_t$ 维的 embedding 映射到一个共同的 $d$$d$ 维空间，从而方便下游的 reduction 操作。 显然，对于所有的 $s$$s$ ，我们应该有 ${\overline{v}}_s\gg d$$\bar v_s \gg d$，所以与 embedding 中的参数数量相比，投影矩阵中的参数数量是可以忽略的。

     Embedding Blocks 是搜索空间的构建块，允许控制器在每个 training step 中采样不同的 SE 或 ME 。

   • Controller Choices：controller 是一个神经网络，从 softmax 概率中采样不同的 SE 或 ME 。它的确切行为取决于我们是对 SE 还是 ME 进行优化。下面我们将描述控制器在一个特征 $F\in \mathcal{F}$$F\in \mathcal F$ 上的行为，为方便描述，删除 $F$$F$ 下标。

     • SE：为了对 SE 进行优化，在每个 training step 中，控制器集合 $\{(s,t)\mid 1\le s\le S,1\le t\le T\}\cup \{(0,0)\}$$\{(s,t)\mid 1\le s\le S, 1\le t\le T\} \cup \{(0,0)\}$ 中采样一个 pair $(\overline{s},\overline{t})$$(\bar s, \bar t)$ 。对于选中的 $(\overline{s},\overline{t})$$(\bar s, \bar t)$ ，只有 Embedding Blocks $\{{\mathbf{E}}^{s,t}\mid 1\le s\le \overline{s},1\le t\le \overline{t}\}$$\left\{\mathbf E^{s,t}\mid 1\le s\le \bar s, 1\le t\le \bar t \right\}$ 参与到该特定的 training step 。因此，控制器有效地挑选了一个 SE ，如 Figure 1(a) 中的红色矩形内的 SE ，它代表了一个大小为 $5M\times 192$$5M\times 192$ 的SE 。在这一步中，词表中第 $k$$k$ 个 item 中的 embedding 为：

       $$\begin{array}{}\text{(26)}& {\overrightarrow{\mathbf{e}}}_k=\sum _{t=1}^{\overline{t}}{\overline{\mathbf{P}}}^t{\overrightarrow{\mathbf{e}}}_{k-{\overline{V}}_{s_k-1}}^{s_k,t}\end{array}$$

       其中：

       • $V_0=0,{\overline{V}}_s=\sum _{i=1}^s{\overline{v}}_i$$V_0 = 0, \bar V_s = \sum_{i=1}^s \bar v_i$ 为累计的 vocabulary size 。$s_k\in \{1,s,\cdots ,S\}$$s_k\in \{1,s,\cdots,S\}$ ，且使得 ${\overline{V}}_{s_k-1}\le k<{\overline{V}}_{s_k}$$\bar V_{s_k-1}\le k \lt \bar V_{s_k}$ 。
       • ${\overrightarrow{\mathbf{e}}}_{k-{\overline{V}}_{s_k-1}}^{s_k,t}$$\mathbf{\vec e}^{s_k,t}_{k - \bar V_{s_k-1}}$ 为 ${\mathbf{E}}^{s_k,t}$$\mathbf E^{s_k,t}$ 的第 $k-{\overline{V}}_{s_k-1}$$k-\bar V_{s_k-1}$ 行。

       定义 ${\overline{D}}_t=\sum _{i=1}^t{d}_t$$\bar D_t = \sum_{i=1}^t d_t$ 为累计的 embedding size ，显然，${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$ 相当于用一个 ${\overline{D}}_t$$\bar D_t$ 维的 embedding 表示第 $k$$k$ 个 item ，然后将其投影到一个 $d$$d$ 维空间。这个投影矩阵 $\mathbf{P}$$\mathbf P$ 是 $\{{\overline{\mathbf{P}}}^1,\cdots ,{\overline{\mathbf{P}}}^t\}$$\{\bar{\mathbf P}^1,\cdots,\bar{\mathbf P}^t\}$ 沿列的拼接。任何一个 vocabulary ID 为 $k\ge {\overline{V}}_{\overline{s}}$$k\ge \bar V_{\bar s}$ 的 item 都被认为是 out-of-vocabulary ，要特别处理，通常采用的方法是使用零向量作为它们的 embedding 。因此，这种 SE 的选择带来的内存成本（参数数量）为：$\mathcal{C}={\overline{V}}_{\overline{s}}\times {\overline{D}}_{\overline{t}}$$\mathcal C = \bar V_{\bar s}\times \bar D_{\bar t}$ ，其中投影矩阵的成本被忽略，因为 ${\overline{v}}_s\gg d$$\bar v_s\gg d$ 。

       如果在 training step 中选择了(0, 0) ，就相当于从模型中去除该特征。因此，在这个 training step 中， zero embedding 被用于这个特征的所有 item ，相应的存储成本为 0 。随着控制器探索不同的 SE ，它根据每个 choice 引起的奖励进行训练，并最终收敛到最佳选择。如果它收敛到(0, 0) ，意味着这个特征应该被删除。显然，对于一个给定的特征，搜索空间的大小是$(S\times T+1)$$(S\times T + 1)$。

     • ME：当对 ME 进行优化时，控制器不是做出单个选择，而是做出一连串的 $T$$T$ 个选择，每个 $1\le t\le T$$1\le t\le T$ 都有一个选择。每个选择为 ${\overline{s}}_t\in \{1,\cdots ,S\}\cup \{0\}$$\bar s_t\in \{1,\cdots,S\}\cup \{0\}$ 。

       • 如果 ${\overline{s}}_t>0$$\bar s_t \gt 0$，则只有 Embedding Blocks $\{{\mathbb{E}}^{s,t}\mid 1\le s\le {\overline{s}}_t\}$$\left\{\mathbb E^{s,t}\mid 1\le s \le \bar s_t\right\}$ 参与到该特定的 training step 。
       • 如果 ${\overline{s}}_t=0$$\bar s_t = 0$，则对于词表内的所有item，整个 ${\overline{d}}_t$$\bar d_t$ 维的 embedding 都将被移除。

       因此，控制器选择了一个自定义的 Embedding Blocks 子集（而不仅仅是一个网格），它组成了一个 MES 。如 Figure 1(b) 所示：

       • 第一个 64-D embedding 被开头的 3M 个 item 所使用。
       • 第二个 64-D embedding 被所有 10M 个 item 所利用。
       • 第三个 64-D embedding 不被任何 item 所使用。
       • 最后一个 64-D embedding 被开头的 3M 个 item 所使用。

       因此，词表中开头的 3M 个 item 被分配了 192 维的embedding ，而最后 7M 个 item 只被分配了 64 维的 embedding 。换句话说，在这个 training step 中实现了 MES [(3M, 192), (7M, 64)] 。

       数学上，令 ${\mathcal{T}}_s=\{t\mid {\mathbf{E}}^{s,t}\text{ is selected}\}$$\mathcal T_s = \{t\mid \mathbf E^{s,t} \text{ is selected}\}$ ，那么词表中第 $k$$k$ 个 item 在当前 training step 的 embedding 为：

       $$\begin{array}{}\text{(27)}& {\overrightarrow{\mathbf{e}}}_k=\sum _{t\in {\mathcal{T}}_{s_k}}{\overline{\mathbf{P}}}^t{\overrightarrow{\mathbf{e}}}_{k-{\overline{V}}_{s_k-1}}^{s_k,t},k<v\text{ and }{\mathcal{T}}_{s_k}\ne \text{empty}\end{array}$$

       如果 ${\mathcal{T}}_{s_k}$$\mathcal T_{s_k}$ 为空，那么 ${\overrightarrow{\mathbf{e}}}_k=\overrightarrow{\mathbf{0}}$$\mathbf{\vec e}_k = \mathbf{\vec 0}$ 。

       SE 的 emebdding 公式为：${\overrightarrow{\mathbf{e}}}_k=\sum _{t=1}^{\overline{t}}{\overline{\mathbf{P}}}^t{\overrightarrow{\mathbf{e}}}_{k-{\overline{V}}_{s_k-1}}^{s_k,t}$$\mathbf{\vec e}_k = \sum_{t=1}^{\bar t} \bar {\mathbf P}^t \mathbf{\vec e}^{s_k,t}_{k - \bar V_{s_k-1}}$ 。可以看到，与 SE 相比，ME 公式中的 sum 不是从 $1$$1$ 到 $\overline{t}$$\bar t$ ，而是被选中的那些维度。

       ME 的内存成本为：$\mathcal{C}=\sum _{t=1}^T{\overline{d}}_t\times {\overline{V}}_{{\overline{s}}_t}$$\mathcal C = \sum_{t=1}^T \bar d_t\times \bar V_{\bar s_t}$ 。对于一个给定的特征，搜索空间大小为 $(S+1{)}^T$$(S+1)^T$。

3. 奖励：由于主模型是通过控制器对 SE 或 ME 的选择来训练的，控制器是通过主模型对验证集样本的前向传播计算出来的奖励来训练的。我们将奖励定义为：

   $$\begin{array}{}\text{(28)}& R=R_Q-\lambda \times C_M\end{array}$$

   其中：$R_Q$$R_Q$ 代表我们想要最大化的（潜在的不可微的）质量奖励，$C_M$$C_M$ 为内存成本用于惩罚控制器选择了超过预算的embedding配置，$\lambda$$\lambda$ 为一个系数用于平衡质量奖励和内存成本。

   • 质量奖励：一类常见的推荐问题是检索问题，其目的是给定模型的输入从而在一个可能非常大的 vocabulary $v$$v$ 中找到 $M$$M$ 个最相关的item 。这类问题的 objective 通常是实现 high recall ，因此我们可以直接让 Recall@N （$N\le M$$N\le M$）指标作为质量奖励。当 $v$$v$ 太大时，计算 Recall@N 变得太昂贵，我们可以通过采样一个小的 negative set（即，负采样），使用 Sampled Recall@N 作为代理。

     另一类常见的问题是排序 ranking 问题。ranking 模型的质量通常由 ROC-AUC 来衡量，他可以作为质量奖励。

     同样，对于回归问题，质量奖励可以设置为 prediction 和 label 之间的 L2-loss 的负值。

   • 内存成本：我们定义内存成本为：

     $$\begin{array}{}\text{(29)}& C_M=max(\frac{\sum _{F\in \mathcal{F}}{C}_F}{\mathcal{B}}-1,0)\end{array}$$

     注意：$C_F$$C_F$ 是基于控制器选择的内存用量，$\mathcal{B}$$\mathcal B$ 为预先定义的内存预算。

   • $\lambda$$\lambda$：显然，$\lambda$$\lambda$ 代表值得付出 $\mathcal{B}$$\mathcal B$ 的额外超预算的 embedding 参数的代价所对应的质量奖励的增量。例如，如果质量奖励是 ROC-AUC，$\lambda =0.1$$\lambda = 0.1$ ，这意味着我们愿意承担额外的 $\mathcal{B}$$\mathcal B$ 超预算的 embedding 参数，如果它能使 ROC-AUC 增加 0.1 。这是因为额外的 $\mathcal{B}$$\mathcal B$ 超预算参数会使奖励减少 $\lambda$$\lambda$ ，所以只有当它能使质量奖励至少增加 $\lambda$$\lambda$ 时才值得。

41.1.3 Training the Neural Input Search Model

1. Warm up 阶段：如前所述，训练 NIS 模型涉及到主模型和控制器之间 consecutive steps 的交替训练。如果我们从第 0 步开始训练控制器，我们会得到一个恶性循环：没有被控制器选中的 Embedding Blocks 没有得到充分的训练，因此给出了不好的奖励，导致它们在未来被选中的机会更少。

   为了防止这种情况，前几个 training steps 包括一个 warm up 阶段，我们训练所有的 Embedding Blocks ，并固定控制器参数。 warm up 阶段确保所有 Embedding Blocks 得到一些训练。在warm up 阶段之后，我们转向使用 A3C 交替训练主模型和控制器。

   在预热阶段，控制器被固定为选择所有的 Embedding Blocks 。

2. Baseline Network：作为 A3C 算法的一部分，我们使用一个 baseline 网络来预测每个控制器（使用已经做出的选择）的期望奖励。baseline 网络的结构与控制器网络相同，但有自己的变量，这些变量与控制器变量一起使用验证集进行训练。然后，我们从每个 step 的奖励中减去 baseline ，计算出 advantage 从而用于训练控制器。

   baseline 网络是主模型的拷贝，但是采用了不同的变量。每次更新主模型之后，就将主模型的参数拷贝给 baseline 。

   总体训练流程为：

   • warm up：通过训练集来更新主模型，此时选择所有的 Embedding Blocks 。

   • 迭代：

     • 在验证集上评估主模型的奖励，并通过奖励最大化来更新控制器参数。
     • 通过新的控制器参数，在训练集上更新主模型。

41.2 实验

41.2.1 公共数据集

1. 数据集：

   • MovieLens-1M：包含了由 6 千多个用户创建的 1M 条电影评分记录。我们通过遵循一个广泛采用的实验设置来制定一个电影推荐问题。用户的评分被视为隐性反馈，也就是说，只要用户给电影打了分，就被认为是对该电影感兴趣。此外，对于每个用户，从电影词表中均匀地采样 4 部随机电影作为用户的负样本（负采样策略，而不是在训练之前提前准备并固定了负样本）。意外的命中会被删除，即：负样本集合中包含了正样本，则把正样本从负样本集合中剔除。

     由于每条评分记录都有一个时间戳，我们把每个用户的最近一个评分记录拿出来进行测试。在测试阶段，对于每个正样本，我们随机采样 99 部电影作为负样本来计算评价指标。测试期间的采样策略与训练期间相同。

   • KKBox：来自 WSDM KKBox 音乐推荐挑战赛，任务是预测用户在一个时间窗口内第一次可观察到的听歌事件后是否会重复听歌。数据集同时包含了正样本和负样本：正样本表示用户重复听了这首歌，负样本表示用户没有再听这首歌。因此，与 MovieLens-1M 数据集不同的是，我们没有通过随机采样来手动构造负样本，而是使用数据集提供的负样本。

     由于该数据集没有与每条记录相关的时间戳，我们随机采样 80% 的记录用于训练、20% 的记录用于测试。

   对于这两个数据集，我们进一步从训练集中随机采样 10% 的样本用于训练控制器的验证集。

   下表给出了我们应用 NIS 的特征的 vocabulary size（即，feature 的 unique item 数量）。注意，原始的 KKBox 数据集有更多的特征，这些特征要么是浮点特征（如 "歌曲长度"）、要么是小 vocabulary size 的 categorical 特征（如 "流派"）。由于 NIS 对具有大 vocabulary size 的 categorical 特征的影响更大，在我们的实验中，为了简单起见，我们只使用下表中列出的特征。

   

2. vocabulary 构建细节：以 MovieLens-1M 为例，遍历每个 user-movie 评分记录，并计算每个用户在整个数据集中出现的记录数量，根据计数结果给每个用户分配 vocabulary ID：最高频的用户分配 ID 0、最低频的用户分配最大的 ID 。其它特征、其它数据集也以类似的方式构建 vocabulary 。

   在生产环境中，特征的频次分布有变化，如何处理？如何处理新出现的 ID ，如新广告的 ID ？这些论文都没有提到。读者猜测，NIS 仅适用于 ID 分布变化不大的场景。对于新闻、广告等等 ID 不断生成、消亡的领域，NIS 可能需要进行适配。

3. 实验配置：NIS 方法实际上是模型结构无关的，可以应用于各种类型的模型。这里我们采用 Neural Collaborative Filtering: NCF 模型。NCF 模型包括两个组件：Matrix Factorization: MF 组件、多层感知器 MLP 组件，如下图所示。

   • MF 组件中的 user embedding 和 item embedding 是 $d$$d$ 维的，其逐元素相乘产生了 $d$$d$ 维的 MF embedding 。

   • MLP 组件中的 user embedding 和 item embedding 是 $4d$$4d$ 维的，它们被拼接起来并馈入 $3$$3$ 个 MLP layer （ReLU 激活函数），其大小分别为$4d,2d,d$$4d, 2d, d$ 。top MLP layer 的输出被称作 MLP embedding 。

     我们没有使用任何规范化技术，如 BatchNorm 、LayerNorm 等。

     这意味着 MLP 组件和 MF 组件并没有共享 embedding，因此每个 id 都有两套 embedding。

   $d$$d$ 维的 MF embedding 和 $d$$d$ 维的 MLP embedding 拼接起来，然后被用于计算 logit （通过一个 $2d$$2d$ 的可学习的权重向量进行点乘）。模型使用交叉熵损失。

   所有权重（包括隐层权重和 embedding 矩阵）使用高斯分布随机初始化，高斯分布的均值为零、标准差为 $1/\sqrt{n}$$1/\sqrt n$，其中 $n$$n$ 为隐层或 embedding 的维度。任何权重都没有使用正则化或 dropout 。当一个特征有多个取值时（如，一首歌有多个作曲家），这些特征的取值的embedding 是均值池化。当某些训练样本中存在缺失的特征值时，使用全零的 embedding 。

   对于 MovieLens-1M 数据集， item embedding 是简单的 movie embedding 。于 KKBox 数据集，由于每个 item （即歌曲）有多个特征，即 song ID 、艺术家姓名、作曲家、作词人， item embedding 的计算方法如下：

   • 对于 MF 组件，四个特征中的每一个都表示为一个 $d$$d$ 维的 embedding ，然后将它们拼接起来并通过一个 $4d\times d$$4d\times d$ 的投影矩阵从而投影到一个 $d$$d$ 维向量。投影后的 $d$$d$ 维向量表示 MF 组件中的 item embedding 。
   • 对于 MLP 组件，四个特征中的每一个都表示为一个 $4d$$4d$ 维的 embedding ，然后将它们拼接起来并通过一个 $16d\times 4d$$16d\times 4d$ 的投影矩阵从而投影到一个 $4d$$4d$ 维向量。投影后的 $4d$$4d$ 维向量表示 MLP 组件中的 item embedding 。

   给出一个预先选择的 $d$$d$ ，从而形成一个具有 $m_d$$m_d$ 个 embedding 参数的模型，我们首先将其作为 baseline，不应用 NIS 。然后，我们将每个特征的 embedding size 增加一倍，从而产生 $2m_d$$2m_d$ 个 embedding 参数，并应用 NIS 的内存预算 $\mathcal{B}=m_d$$\mathcal B=m_d$ （即与 baseline 模型相同）。我们预期 NIS 通过更好地分配 $m_d$$m_d$ 个参数而表现得比 baseline 更好。我们进一步用 $\mathcal{B}=0.5m_d$$\mathcal B = 0.5 m_d$ 推动 NIS 的极限，看看它是否还能比 baseline 模型表现更好。

   我们为 baseline 模型实验了 $d=8$$d=8$ 和 $d=16$$d=16$ ，因此相应的 NIS 模型将有 $d=16$$d=16$ 和 $d=32$$d=32$ 。

   

4. 控制器：控制器用于在所有候选的 choice 上产生一个概率分布。我们在所有的实验中使用了一个简单的控制器：

   • 对于 SE settting，控制器为每个特征分配一个 $(S\times T+1)$$(S\times T+1)$ 维的向量，向量中的每个元素代表了多项式分布的 logit 。该向量被初始化为零向量。

     控制器从这个多样式分布中采样不同的 SE 。注意：每个特征的搜索空间大小为 $(S\times T+1)$$(S\times T+1)$ 。对一个具有 $|\mathcal{F}|$$|\mathcal F|$ 个特征的模型，控制器只是由 $|\mathcal{F}|$$|\mathcal F|$ 个独立的向量组成，因此不同特征的 SE 是独立采样的。

     我们没有使用更复杂的控制器结构，如 RNN ，因为不清楚对一个特征做出的决策是否会影响其他特征，以及应该按照何种顺序做出决策。

     对于 SE setting，控制器为每个特征从 ${\mathbb{R}}^{(S\times T+1)}$$\mathbb R^{(S\times T+1)}$ 向量中选择一个元素。

   • 对于 ME setting ，控制器为每个特征分配 $T$$T$ 个独立的 $(S+1)$$(S+1)$ 维的向量，因为需要做出 $T$$T$ 个独立的选择。对一个具有 $|\mathcal{F}|$$|\mathcal F|$ 个特征的模型，控制器是由 $T\times |\mathcal{F}|$$T\times |\mathcal F|$ 个独立的向量组成。

     对于 ME setting，控制器为每个特征从 $T$$T$ 个 ${\mathbb{R}}^{(S+1)}$$\mathbb R^{(S+1)}$ 个向量中，分别在每个向量中选择一个元素。

   每个特征构建了 20 个 Embedding Blocks ，其中：${\overline{d}}_t$$\bar d_t$ 为 $[0.25d,0.25d,0.25d,0.25d]$$[0.25d, 0.25d, 0.25d, 0.25d]$ ，${\overline{v}}_s$$\bar v_s$ 为 $[0.2v,0.2v,0.2v,0.2v,0.2v]$$[0.2v,0.2v,0.2v,0.2v,0.2v ]$ ，其中 $v$$v$ 为该特征的 total vocabulary size 。在实践中，我们发现这种配置在细粒度和搜索空间大小之间取得了良好的平衡。

   如前所述，控制器使用验证集进行训练。对于 MovieLens-1M 数据集，我们使用 Recall@1 （也称作 HitRate@1）作为质量奖励 $R_Q$$R_Q$ ，然后我们报告测试集上的多个指标：Recall, MRR, NDCG 。对于 KKBox 数据集，我们使用 ROC-AUC 作为质量奖励 ，并报告测试集上的 ROC-AUC 。在所有的实验中，我们设定 $\lambda =0.01$$\lambda=0.01$ 。

5. 训练细节：

   • 主模型：batch size = 256，应用梯度裁剪（梯度范数阈值为 1.0 ），学习率为 0.1，使用 Adagrad 优化器。在开始 A3C 算法之前，进行了 100K 步的预热阶段。
   • 控制器：使用 Adagrad 优化器，学习率为 0.1 ，不使用梯度裁剪（因为一个低概率但高回报的行动应该得到一个非常高的梯度，以显著提高其概率）。每个控制器的决策都由验证集的 64 个样本所共享，从中计算出一个奖励值。

   在预热阶段结束后，控制器和主模型每隔一个 mini-batch step 进行交替训练。在所有的实验中，我们在主模型和控制器都收敛后停止训练（而不是仅有一个收敛）。

   我们使用了分布式训练，其中 5 个 worker 独立地进行并行训练。

6. Table 2 和 Table 3 分别报告了 MovieLens-1M 数据集和 KKBox 数据集的实验结果。注意，$\mathcal{B}$$\mathcal B$ 代表 NIS 模型的内存预算。可以看到：

   • NIS 能够持续取得比 baseline 模型更好的性能，很多时候参数明显减少，证明了我们方法的有效性。
   • 在相同的条件下，NIS-ME 模型总是优于 NIS-SE ，而且通常参数比 NIS-SE 更少。
   • 即使 $\mathcal{B}$$\mathcal B$ 是 baseline 模型大小的一半，NIS 模型也几乎总是优于 baseline 。这不仅证明了我们方法的有效性，而且还表明在重度约束条件下有可能实现卓越的性能。
   • 一些 NIS 模型通过超出内存预算获得了卓越的性能。这种模型质量和模型规模之间的 tradeoff 反映在奖励函数的设计中。当内存预算只是一个指导方针而不严格时，这一点特别有用。