KDD 2020 | Facebook提出组合embedding方法在大规模推荐系统中的应用

作者 | Fahhh

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

编辑 | 海边的拾遗者公众号

本文仅作学术交流，如有侵权，请联系后台删除

0.摘要

Facebook团队考虑embedding的存储瓶颈，提出了一种新颖的方法，通过利用类别集合的互补分区为每个类别生成唯一的embedding向量，无需明确定义，从而以端到端的方式减小embedding大小。通过基于每个互补分区存储多个较小的embedding table并组合来自每个table的embedding ，以较小的内存成本为每个类别定义了唯一的embedding 。可以将这种方法解释为使用特定的固定密码本来确保每个类别表示的唯一性。实验结果表明，该方法比hash技巧更有效，同时也能使参数量减小，可减少模型损失和准确性，减少embedding table的大小。

1.问题

现有的推荐系统一般将类别特征用embedding表示，对于那种千万维度的特征，将其映射为100维的embedding 向量。这样需要大量的存储空间。

一种常见的方案就是hash，将类别hash到一个embedding index上。这样做的方法会导致很多类别共用一个embedding，这样会损失精度。因此提出一种方法，让特征的每个值都有一个独特的embedding于其对应，还可以减少整体embedding的存储大小。

2.模型

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

定义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.结果

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的方法，虽然效果不好，但是总感觉大有可为。