当前位置：首页 > 编程日记 > 正文

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

编程日记 2024-11-21 03:20:00

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

定义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.朴素互补分区