应用在大规模推荐系统，Facebook提出组合embedding方法 | KDD 2020 来源|深度传送门（ID:deep_deli

文章插图
文章插图
来源 | 深度传送门（ID: deep_deliver）
Facebook团队考虑embedding的存储瓶颈，提出了一种新颖的方法，通过利用类别集合的互补分区为每个类别生成唯一的embedding向量，无需明确定义，从而以端到端的方式减小embedding大小。通过基于每个互补分区存储多个较小的embedding table并组合来自每个table的embedding，以较小的内存成本为每个类别定义了唯一的embedding。可以将这种方法解释为使用特定的固定密码本来确保每个类别表示的唯一性。
实验结果表明，该方法比hash技巧更有效，同时也能使参数量减小，可减少模型损失和准确性，减少embedding table的大小。
文章插图
问题
现有的推荐系统一般将类别特征用embedding表示，对于那种千万维度的特征，将其映射为100维的embedding 向量。这样需要大量的存储空间。
一种常见的方案就是hash ，将类别hash到一个embedding index上。这样做的方法会导致很多类别共用一个embedding ，这样会损失精度。因此提出一种方法，让特征的每个值都有一个独特的embedding于其对应，还可以减少整体embedding的存储大小。
文章插图
模型
2.1.QUOTIENT-REMAINDER TRICK（商余技巧）
先来回顾一下embedding的做法，定义对于某个特征的所有取值：
文章插图
有一个embedding矩阵如下，这里的D是embedding维度：
文章插图
将特征进行one hot 编码：
文章插图
然后映射到对应的低维embedding:
文章插图
这样的一般做法需要的空间复杂度为（一般工业场景下S都特别大，这导致整体的空间复杂度很高）：
文章插图
为了解决S太大带来的空间复杂度个过高的问题，一般可以用hashing trick 。就是先给定最大的embedding的行数m ，这里的m远小于S ，这样embedding矩阵为：
文章插图
那如何映射特征的某个值到一个embedding向量呢？先定义一个hash矩阵：
文章插图
取值为：
文章插图
这样映射过程为：
文章插图
具体的算法如下：
文章插图
实际上就是将特征取值 i 来对事先定义好的 m 取模（整除取余），然后用这个余数作为这个特征值的embedding索引。这样空间复杂度就变为了：
文章插图
这样很容易导致的不同的特征取值映射到相同的embedding ，然后就损失信息了。因此提出了quotient-remainder trick方法，使用两个互补函数（整数商和余数函数），可以生成两个单独的embedding table ，并以某种方式为每个类别生成唯一的嵌入的方式来组合embedding 。具体见下面算法2 ， /为整除。
文章插图
给定两个embedding tables ，一个为m*D维，一个是（S/m）*D维。对于特征x的取值i ，计算两个索引：一个是 i 对m取模，一个是整除（i/m）。然后emebdding look up出来两个embedding ，两个embedding逐个元素相乘，获得最后的embedding 。这样做，空间复杂度为：
文章插图
整体的空间复杂度要比常规的那种hash trick要大一些，但是可以获得独一无二的embedding 。
2.2.COMPLEMENTARY PARTITIONS（互补分区）
在商余技巧中，每个操作（商或余数）将类别集合划分为多个“存储桶” ，通过将商和余数的embedding组合在一起，可以为每个索引生成一个独一无二的向量，同样，可以划分多个embedding ，使用基本集理论集成多个embedding作为一个索引的表示，将此概念形式化为一个概念，称之为互补分区。