CIKM 2021 | BH：面向Web级应用的基于二进制码的Hash Embedding

▐ 摘要

现如今，深度学习模型被广泛的应用于 web 级应用中，比如推荐系统，广告系统等等。在这些应用中，ID类特征的表示学习(embedding learning)是这些模型成功的关键之一。其标准的模式是，为每一个特征值学习一个特征向量。尽管，这种方法能够刻画不同特征的特性，有效提升模型的精度。但是，存储这样的 embedding 将会消耗大量的空间，极大的约束了这类深度模型的应用和迭代。这样的问题，对于 web 级应用而言尤为严重。在本文中，我们提出了基于二进制码的 hash embedding 学习，能够任意比例的压缩存储空间的同时基本维持模型的精度。实验结果表明，模型存储大小缩减1000倍的时候，仍然能维持原有模型的99%精度。目前，该工作已被 CIKM 2021 接收。

论文下载：

https://arxiv.org/pdf/2109.02471.pdf

▐ 1. 背景

ID类特征的表示学习(embedding learning)在基于 embedding 的深度推荐模型(EDRMs)中起着至关重要的作用。一个经典的 embedding learning (称为 full embedding)的目标是为每一个特征值学习一个特征向量。具体来讲，设为一种ID特征(比如user ID 或者 item ID)，为该特征的词典大小(即特征值的 unique 数)，对于每一个特征值赋予一个 embedding 的索引(index) , 通过, 找到 embedding 矩阵()中的第行，将该行作为的特征向量 (其中，为 embedding 维度，在 full embedding 中 ，见图1(a))。

图1 不同方法之间的比较。Step 1,2,3 分别指特征hash、embedding索引生成、embedding向量生成。

然而，full embedding 方法面临着严重的存储问题。因为，存储 embedding 矩阵的开销是随着线性增长的。

对于一个web级应用而言，的大小可能是亿级别的，导致 embedding 矩阵需要巨大的存储空间。比如，假设为5百万，，那么对应的开销为475G。

在实际应用中，如此具大的存储开销将会极大的约束模型的部署和应用，尤其是对于一些存储敏感的场景(如部署在移动设备上)。

因此，减少 embedding 矩阵存储开销变得尤为重要，针对该问题，主要会面临两大挑战：

• 高灵活： 不同的场景对于存储的约束是不同的(比如分布式服务器和移动设备)。因此，减少 embedding 存储的方法需要足够的灵活，来满足不同场景的 embedding 需求。尤其是对于移动设备而言，一个轻量级的模型是迫切需要的。
• 效果不降： 一个大模型拥有更多的参数，更多的容量，往往能够取得更好的效果。然而，缩减模型存储势必会减少模型的参数，很有可能带来模型效果上的损失。因此，在模型存储减少的同时，如何保持模型的效果不降是一个极大的挑战，尤其是对于存储敏感的场景而言。

整体上讲，减少 embedding 存储可以从两个角度来考虑(1)减少每一个 embedding 向量的大小(即减小)。(2)减少 embedding 向量的个数(即减少)。然而前者虽然能减少存储，但其存储开销仍然随着线性增长，因此不是一个较优的选择。现有的大部分工作主要集中在如何减少。这类工作主要采用hash取模的方法(如图1(b)所示)，其核心思想是对每一个特征值的 Hash ID 进行取模(设模数为)，然后将取模后的余数作为 embedding 的索引（比如 Hash Embedding[1] 方法）。这样一来，embedding 的存储开销可以从减少到。但是这类方法的问题是会使得不同的特征值映射到相同的索引值，导致对应相同的 embedding 向量，这使得模型无法区分这些特征值，损失模型效果。该问题在构建轻量级模型的时候尤为严重。尽管，后续方法比如（Multi-hash[2],Q-R trick[3]）都尝试缓解取模操作带来的索引冲突问题，但都无法同时解决灵活性和效果问题。

在本工作中，不像现有的采用取模操作的工作，我们另辟蹊径，利用二进制码 binary code（比如13的二进制码为）来唯一对应每一个特征值的 Hash ID，并提出 Binary code based Hash embedding(BH) 来解决 embedding 存储大的问题。具体来讲，我们先将每一个特征值的 Hash ID 转换成二进制码。然后，设计 code block strategy 来灵活的调整 embedding 存储的大小(解决挑战1)。为了尽可能保留模型效果(挑战2)，不论 embedding 缩减成多大，我们都能够为不同的特征值赋予不同的索引值。这样以来，模型就很容易能够分辨不同的特征值，从而提升模型的表达能力和效果。此外，BH 的索引值是实时计算出来的，不需要提前存储索引值，这样一种模式有利于处理新 ID 的情况。

▐ 2. 模型：Binary Code Based Hash Embedding

在这一章，我们将介绍所提的模型。如图2所示，Binary code based Hash embedding(BH)分为3步，即特征hash、embedding索引生成、embedding向量生成。

2.1 特征Hash

在实际过程中，ID类特征的原始类型可能是多种多样的，比如String或者Integer。为了统一不同类型的ID特征，在实际中，经常通过特征Hash[1,2,3]将ID的原始值映射成Integer,称为Hash ID(如图2所示)。特征Hash可以被形式化的表达为

其中为 Hash 函数(如Murmur Hash [4]),为特征值的 Hash ID。在实际中，的输出空间会被设为足够大 比如(为64-bit整数)来避免之间的Hash冲突。在这种情况下，不同的都有一个唯一的与之对应 [5,6]。

2.2 Embedding 索引生成

Embedding 索引生成主要分为3步：Binarization、Code Block Strategy和Decimalization。

2.2.1 Binarization

在特征 Hash 之后，每一个特征值都会都会有一个唯一的 Hash ID。我们首先将这样一个整数转化成二进制码的形式(表示二进制码的长度),比如13的二进制码是。需要注意的是二进制码仍然与特征值一一对应。

2.2.2 Code Block Strategy

为了能够灵活的缩减 embedding 的存储大小，我们提出了Code Block Strategy。

简单来讲，Code Block Strategy 会把中的每一个0-1值分到不同的 block。然后，每一个 block 的 0-1 值可以有序的组成一个 0-1 码来表示个整数(其中n是每个 block 中0-1的个数)。然后将每一个 block 的 0-1 码转换成一个十进制值，将该值作为 block embedding 矩阵的embedding索引。这样一来，一个特征值的所有block合在一起就唯一确定了该特征值，同时embedding存储的大小可以灵活的被参数所控制。比如当时，即每个 block 仅有 2 个 0-1 值，embedding 存储的开销是。当所有 0-1 值放在同一个 block 的时候，存储开销是(相当于Full embedding)。换而言之，通过调整,我们能够灵活的调整 embedding 大小来满足不同场景的存储限制。

形式化讲，我们定义为Code Block Strategy产出的的block序列，那么第个block 可以被表示为

其中 是一个分配函数，将每一个 0-1 值分配到不同的 block里。将每个 block 里的0-1值变成有序的 0-1 码。在这里，我们给出两个 code block strategies （即 Succession 和 Skip）的例子来展示其是如何起作用的，其他合适的 code block strategies 也都可以被应用。

• Succession： 如图3(a)所示，Succession 从左到右遍历，每个0-1值分到同一block。 为保持在中原有的顺序。注意的是，当最后剩余的 0-1 值不够时，将剩余的所有 0-1 值放到一个新的 block 中。

• Skip： 如图3(b)所示，Skip 将间隔为的 0-1 值放入同一个 block 中。与Succession一致。

图3. Code block strategies的例子。其中，,每一个例子中，相同颜色的0-1值被分到同一个block。

这样以来，通过 Code Block Strategy，对于每一个,我们可以得到唯一的。也就是说，Code Block Strategy 的过程是一个信息无损的过程。

2.2.3 Decimalization

每一个 block 的 embedding 索引可以通过将转成十进制值得到，即

比如。

2.3 Embedding向量生成

通过 Code Block Strategy，我们可以为每一个特征值得到多个 embedding 索引。然后，我们通过 embedding lookup 和 embedding fusion 得到对应的 embedding 向量。

2.3.1 Embedding lookup

如前文所介绍，每一个block可以得到一个索引。总共有个。我们可以将每一个 embedding 索引映射成一个 embedding 向量，

其中是第 m 个 block 的 embedding 矩阵，为的 embedding 向量。是 lookup 函数，其返回的第行。此外，为了经一步减少 embedding 存储开销，我们让不同的 block 共享同一个 embedding 矩阵。

2.3.2 Embedding Fusion

Embedding Fusion 函数将所有 block embedding 整合起来，得到特征值最后的 embedding 向量,

其中，Fusion 函数的设计多种多样，比如 pooling，LSTM，Concatenation 等等。在本工作中，我们采用了 sum pooling 作为默认的 Fusion 函数。

2.4 讨论

2.4.1 优势

这里简单概括一下所提方法的优越性。

• 确定性： embedding 索引的产生是一个确定性的无参的实时计算过程，该特性对于新ID的索引计算是十分友好的。
• 灵活性： embedding 的大小能够灵活的被超参所调整。这样一种性质，使得模型能够被部署在存储敏感的场景中(如移动设备)。
• 唯一性： 不论 embedding 缩减到什么程度，始终与特征值一一对应，也就是说不同的有不同的，使得模型能够很容易的区别出不同的特征，提高模型的表达能力。

2.4.2 和现有方法的关系

• Full embedding： 本文所提方法和 Full embedding 都能够很好地区分不同的特征。而本文方法能够进一步的减少 embedding 存储大小。

• Hash embedding： 该方法可以看作是本文的一个简化版。其中，code block strategy 是 Succession 并且仅前个0-1值作为embedding索引。
• Multi-Hash Embedding： 本文方法和 Multi-Hash Embedding 都采用的多个 embedding 索引的模式，不同的是，本文对这些索引之间做了唯一性的约束。
• Q-R Trick： 该方法可以看作是本文的一个特殊的 case。其中 code block strategy 是 Succession，且 block 的个数为2。然后前个作为 Q-R Trick 的 quotient，剩下的做为 remainder。

▐ 3. 实验

3.1 实验设置

• 数据集
• Alibaba
• Amazon
• MovieLens
• Baselines
• Full Embedding(Full)
• Hash Embedding (Hash)
• Multi-Hash Embedding (MH)
• Q-R Trick (Q-R)

3.2 CTR 预估任务

我们分别在阿里内部数据和公开数据上做了 CTR 任务的评测。记录了不同存储缩减倍数下，模型的效果表现。

如表1所示，可以看到，相比于基于取模的方法和原始的 Full embedding。所提 BH 方法在不同缩减程度下，都取得了最好的效果。并且缩减倍数越多时，效果越好。

表1.CTR预估任务结果

3.3 存储开销比较

为了比较，缩减 embedding 存储的能力。我们分别比较在不同缩减方法下取得原模型(Full embedding)99% 效果的时候，能够缩减的程度。

如表2所示，当都取得原模型 99% 的效果的时候，BH 的模型大小是原先的1000分之一。远远小于其他模型大小。这样一个效果，能够为移动场景的应用提供良好的条件。

表2.模型缩减能力对比

3.4 不同 Code Block Strategy 比较

我们比较了 Succession 和 Skip 两种 Code Block Strategy 的效果，如表3所示，两种方式不相上下，且相比于最好的 baseline(Q-R) 均能够取得更有的效果。

表3.不同Code Block Strategy比较

3.5 收敛性比较

我们还比较不同模型的收敛快慢，如图4所示，相比于模型缩减的方法，所提 BH 方法在 test 的 auc 上收敛更快并更高，loss 上也更小。

图4. 收敛性比较

▐ 4. 结语

通过构建无损的 embedding 索引来获取不要特征值的 embedding，来使得模型在缩减大小时仍然能够拥有良好的效果。BH 是我们团队在模型瘦身(继FCN-GNN[7]之后)上在一次发力。希望后续能够在该方向上带来更多更好的作品。

Reference

[1] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning. 1113–1120.

[2] Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. 2017. Hash embeddings for efficient word representations. Advances in neural information processing systems 30 (2017), 4928–4936.

[3] Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang. 2020. Compositional embeddings using complementary partitions for memory-efficient recommendation systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 165–175.

[4] Fumito Yamaguchi and Hiroaki Nishi. 2013. Hardware-based hash functions for network applications. In 2013 19th IEEE International Conference on Networks (ICON). IEEE, 1–6.

[5] Wang-Cheng Kang, Derek Zhiyuan Cheng, Tiansheng Yao, Xinyang Yi, Ting Chen, Lichan Hong, and Ed H Chi. 2020. Deep Hash Embedding for Large-Vocab Categorical Feature Representations. arXiv preprint arXiv:2010.10784 (2020).

[6] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning. 1113–1120.

[7] Li F, Yan B, Long Q, et al. Explicit Semantic Cross Feature Learning via Pre-trained Graph Neural Networks for CTR Prediction[J]. SIGIR 2021.

END

欢迎关注「阿里妈妈技术」，了解更多~

疯狂暗示↓↓↓↓↓↓↓