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）可能是一个期望的属性。
