来源|深度门户(ID: deep_deliver) 　　

　　

　　脸书团队考虑到嵌入的存储瓶颈，提出了一种新的方法，通过使用类别集的互补划分为每个类别生成唯一的嵌入向量，以端到端的方式减少嵌入的大小，而无需显式定义。通过基于每个互补分区存储多个较小的嵌入表并组合来自每个表的嵌入，以较小的存储成本为每个类别定义唯一的嵌入。这种方法可以解释为使用特定的固定码本来确保每个类别表示的唯一性。 　　

　　

　　实验结果表明，该方法比hash技术更有效，并且可以减少参数、模型损失和精度，减小嵌入表的大小。 　　

　　

　　问题 　　

　　

　　现有的推荐系统一般将类别特征表示为嵌入，对于那些几千万维的特征，映射成100维的嵌入向量。这需要大量的存储空间。 　　

　　

　　一个常见的方案是hash，它将类别散列到一个嵌入索引中。这种方法会造成很多类别共用一个嵌入，会失去准确性。因此，提出了一种方法，使得特征值的每一个值都有一个唯一的嵌入与之对应，这样也可以减少整个嵌入的存储大小。 　　

　　

　　型号 　　

　　

　　2.1 .商余数技巧(商余数技巧) 　　

　　

　　让我们回顾一下嵌入和定义特性的所有值的实践： 　　

　　

　　具有如下嵌入矩阵，其中D是嵌入维数： 　　

　　

　　一个热编码功能： 　　

　　

　　然后映射到对应的低维嵌入： 　　

　　

　　这种通用做法所需的空间复杂度为(在一般工业场景中s特别大，导致整体空间复杂度很高): 　　

　　

　　为了解决S过大导致的空间复杂度过高的问题，一般可以使用哈希技巧。首先给出最大嵌入行数m，其中m远小于s，因此嵌入矩阵为： 　　

　　

　　那你怎么把某个特征值映射到嵌入向量呢？首先定义一个散列矩阵： 　　

　　

　　的值为： 　　

　　

　　此映射过程是： 　　

　　

　　具体算法如下： 　　

　　

　　实际上是取特征的值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作为一个索引的表示，将此概念形式化为一个概念，称之为互补分区。

　　

定义1：

　　

给定集合S的k个分区 P1,P2….PK，这些分区是互补的。即对于集合S中任意两个元素a和b，总是存在一个分区，在这个分区关系下的a和b的等价类集合不同。关于等价类可以参考知乎：离散数学中的等价类是什么意思？- laogan的回答 - 知乎

　　

举个例子：

　　

（我理解就是对于每两个不同元素比如1和4，总有一种分区关系，让1和4存在两个子集中，像1和4在第二种分区关系下，它们就在两个分区子集里）

　　

给定分区的每个等价类都指定一个映射到embedding向量的“bucket”。因此，每个分区P对应于一个embedding table。在互补分区下，在每个分区产生的每个嵌入通过某种操作组合之后，每个索引被映射到一个不同的embedding向量。（上面那个例子就是三个embedding table，第一个embedding table 有三行，后两个embedding table是两行）

　　

2.3.互补分区的例子

　　

a.朴素互补分区

　　

b.商余互补分区

　　

c.一般商余互补分区

　　

d.中国的余数分区

　　

考虑一个大于或等于S的两两互质因式分解

　　

（我理解就是任意两个不同分区size的最大公约数等于 1 ）

　　

这种分区可以根据需要自由定义，可以根据年份、品牌、类型等定义不同的分区。假设这些属性的唯一规范生成一辆独特的汽车，这些分区确实是互补的

　　

2.4.COMPOSITIONAL EMBEDDINGS USING COMPLEMENTARY PARTITIONS

　　

为每个分区创建一个embedding table:

　　

分区中每个等价类中的元素映射到同一个embedding 向量上。

　　

对于某个特征取值x，它的embedding为：

　　

可以有很多整合方法：

　　

拼接

　　

相加

　　

追元素相乘（hadamard积）

　　

下面证明一下，这样做对于每个特征取值都可以获得一个独一无二的embedding：

　　

这很简单了，（只要创建互补分区的时候，别让任意两个不同的特征取值在所有分区中的索引都相同就好了）

　　

空间复杂度：

　　

就是：

　　

这里有个图很形象了：

　　

2.5.Path-Based Compositional Embeddings

　　

生成embedding的另一种方法是为每个分区定义一组不同的转换（第一个embedding table除外）。特别是，可以使用一个单独的分区来定义一个初始嵌入表，然后通过其他分区确定的函数组合来传递初始嵌入向量。

　　

W是embedding table ， M是传递函数。这里的传递函数，也一起训练。

　　

这样的M可以是：

　　

a.线性的

　　

b.MLP

　　

与基于操作的组合embedding不同，基于路径的组合embedding需要学习函数中的非embedding参数，这可能会使训练复杂化。内存复杂性的降低还取决于如何定义这些函数以及它们添加了多少附加参数。较小的参数情况下可以与基于操作的组合的空间复杂度相同。

　　

结果

　　

3.1.实验设置：

　　

选择两个模型，DCN和Facebook内部的推荐模型。

　　

3.2.数据集：

　　

Kaggle 的 Criteo Ad Kaggle Competition，前6天训练，第7天预测。

　　

优化器adagrad和amsgrad，batch128，无正则，embedding size 16，损失交叉熵。实施了4个哈希冲突，使模型大小减少了约4倍。每条曲线显示了5次试验中验证损失的平均值和标准差。

　　

3.3.基本效果：

　　

可以看到Q-R方法的loss比hash方法小很多，比FULL table的大一些，hash方法和Q-R方法的模型比FULL TABLE小了4倍。

　　

3.4.不同组合embedding的效果：

　　

为了更全面的比较，在每个特征中强制加入了很多hash冲突，得到的结果是5次试验的平均值。总体来说乘法运算的效果最好。

　　

3.5.不同组合embedding的效果2：

　　

因为不同特征，取值数量差别大，所以hash方法的阈值（hash的最大维度）对于效果也有影响，这里分不同阈值测试了效果：

　　

3.6.Path-Based Compositional Embeddings效果

　　

（效果好像一般哈。看来学习的方法不是万能的。）作者最后也提到了这个path based的方法，这种方法是计算密集型模型，模型复杂度低，但效果不太能取代操作base的方法，还需要深入的研究。

　　

读后感：

　　

方法还是很惊艳的，但是没有讨论时间复杂度，只讨论了模型的大小，我感觉时间复杂度还是要高了一些。但是整个思路还是非常好的，特别是最后的path based的方法，虽然效果不好，但是总感觉大有可为。

　　

来源：https://zhuanlan.zhihu.com/p/267375732

　　

论文地址：https://arxiv.org/abs/1909.02107