facebook在2019的《Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems》，提出了一种compositional embedding，并且在dlrm中做了实现，我们来看下具体的概念。

DLRMs的设计是为了处理大量categorical (or sparse) features的情况。对于个性化或CTR预估任务，categorical features的示例可以包括：users、posts、pages、以及成百上千的这些features。在每个categorical feature中，categories的集合可能会有许多多样性的含义。例如，社交媒体主页（socal media pages）可能包含的主题范围是：从sports到movies。

为了利用这些categorical信息，DLRMs利用embeddings将每个category映射到在一个embedded空间中的一个唯一的dense representation；见[2,4,5等]。更精确的，给定一个关于categories的集合S以及它的基数 ∣S∣∣S∣，每个categorical实例会被映射到一个在一个embedding table W∈R∣S∣×DW∈R∣S∣×D的indexed row vector上，如图1所示。我们不用预先决定embedding的weights，对于生成准确的模型，在neural network的其余部分对embeddings进行jointly training更有效。

每个categorical feature，可有具有数千万可能不同的categories（比如：∣S∣≈107∣S∣≈107），采用的embedding vector的维度为D≈100D≈100。在DLRM的training和inference期，由于存在大量的categories，每个table可能需要多个GBs进行存储，因此embedding vectors的数目构成了主要的内存瓶颈。

一种减小内存需求的天然方法是，通过定义一个hash函数（通常是余项函数：remainder function）来减小embedding tables的size，它可以将每个category映射到一个embedding index上，其中embedding size会比categories的数目要更小。然而，该方法会将许多不同的categories映射到相同的embedding vector上，从而导致在信息的丢失以及在模型质量上变差。理想情况下，我们应减小embedding tables的size，并且仍为每个category生成唯一的representation，从而尊重数据的天然多样性。

在本paper中，我们提出了一种方法，它通过对caegory set使用complementary partitions来生成compositional embeddings，来为每个categorical feature生成唯一的embedding。这些compositional embeddings可以与多个更小的embeddings交互来生成一个final embedding。这些complementary partitions可以从categorical data的天然特性中获取，或者人工强制来减小模型复杂度。我们提出了具体的方法来人工定义这些complementary partitions，并演示了在一个modified DCN以及Facebook DLRM networks在Kaggle Criteo Ad Display Chaalenge dataset上是有用的。这些方法很容易实现，可以在training和inference上同时压缩模型，无需其它额外的pre-或post-training处理，比hashing trick能更好地保留模型质量。

1.1 主要贡献

• quotient-remainder：。。。
• complementary partitions：
• 更好的实验效果：

2.商&余数 trick（QUOTIENT-REMAINDER TRICK）

回顾DLRM setup中，每个category会被映射到embedding table中的一个唯一的embedding vector上。数学上，考虑单个categorical feature，假设：ϵ:S→{0,⋯,∣S∣−1}ϵ:S→{0,⋯,∣S∣−1}表示S的一个枚举(enumeration)（例如：一个categories集合S包括 S={dog, cat, mouse}, 接着S的一个潜在枚举enumeration： epsilon(dog)=0,ϵ(cat)=1, epsilon(mouse)=2epsilon(dog)=0,ϵ(cat)=1,epsilon(mouse)=2。假设W∈R∣S∣×DW∈R∣S∣×D是相应的embedding matrix或table，其中D是embeddings的维度。我们可以使用e_i \in R^{\mid S \mid}将每个category（或者说：category x∈Sx∈S具有index i=e(x)i=e(x)）编码成一个one-hot vector，接着将它映射到一个dense embedding vector xemb∈RDxemb∈RD上：

另外，该embedding可以被解释成embedding table上的一个单行lookup，例如：xemb=Wi,:xemb=Wi,:。注意，这会产生一个O(∣S∣D)O(∣S∣D)的内存复杂度来存储embeddings，当∣S∣∣S∣很大时这会变得非常受限。

减小embedding table的naive方法是，使用一个简单的hash function[17]，比如：remainder function，这称为hashing trick。特别的，给定一个size为m∈Nm∈N（其中, m≪∣S∣m≪∣S∣）的embedding table，也就是说，∼W∈Rm×D∼W∈Rm×D，你可以定义一个hash matrix R∈Rm×∣S∣R∈Rm×∣S∣：

接着，该embedding通过下面执行：

该过程可以通过算法1进行归纳：

尽管该方法可以极大减小embedding matrix的size，由于m≪∣S∣m≪∣S∣, 从O(∣S∣D)O(∣S∣D)减小到O(mD)O(mD)，它可以天然地将多个categories映射到相同的embedding vector，从而产生信息丢失以及模型质量上的下降。一个重要的observation是，该方法不会为每个unique category生成一个unique embedding，从而不会遵循categorical data的天然多样性。

为了克服这一点，我们提出了quotient-remainder trick。出于简洁性，m除以∣S∣∣S∣。假以”"表示整除或商（quotient）操作。使用两个complementary functions（integer quotient function和remainder function），我们可以生成两个独立的embedding tables，对于每个category，两个embeddings组合起来可以生成unique embedding。如算法2所示。

更严格的，我们定义了两个embedding矩阵：W1∈Rm×DW1∈Rm×D和W2∈R(∣S∣/m)×DW2∈R(∣S∣/m)×D。接着定义一个额外的hash矩阵Q∈R(∣S∣/m)×∣S∣Q∈R(∣S∣/m)×∣S∣：

接着，我们可以通过以下方式获取我们的embedding：

其中，⊙⊙表示element-wise乘法。该trick会产生一个O(∣S∣mD+mD)O(∣S∣mD+mD)的内存复杂度，它对比起hashing trick在内存上会有微小的增加，但可以生成unique representation。我们在第5节展示了该方法的好处。

3.COMPLEMENTARY PARTITIONS

quotient-remainder trick只是decomposing embeddings的一个更通用框架下的一个示例。注意，在 quotient-remainder trick中，每个操作（quotient或remainder）会将categories集合划分成多个”buckets”，以便在相同”bucket”中的每个index可以被映射到相同的vector上。然而，通过将来自quotient和remainder的两个embeddings组合到一起，可以为每个index生成一个distinct vector。

相似的，我们希望确保在category set中的每个element可以生成它自己的unique representation，即使跨多个partitions。使用基础的set theory，我们可以将该概念公式化成一个称为“complementary partitions”的概念。假设[x]p[x]p表示通过partition P索引的x∈Sx∈S的等价类。

定义1: 。。。

作为一个具体示例，考虑集合 S={0,1,2,3,4}S={0,1,2,3,4}。接着，以下三个set partitions是complementary：

{ {0}, {1,3,4}, {2} }, { {0,1,3}, {2,4} }, { {0,3}, {1,2,4} }

特别的，根据这些partitions中至少一个，你可以确认每个element与其它element是不同的。

注意，一个给定partition的每个等价类指定了一个“bucket”，它可以映射到一个embedding vector上。因而，每个partition对应到单个embedding table上。在complementary partitions下，在对来自每个partitions的每个embedding会通过一些操作进行组合之后，每个index会被映射到不同的embedding vector上，如第4节所示。

## 3.1 Complementary Partitions示例

使用complementary partitions的定义，我们可以抽象quotient-remainder trick，并考虑其它更通用的complementary partitions。这些示例会在附录中提供。出于简化概念，对于一个给定的n∈Nn∈N，我们定义了集合：\Epsiion(n)={0,1,⋯,n−1}\Epsiion(n)={0,1,⋯,n−1}

(1) Naive Complementary Partition：

如果P满足上式，那么P就是一个Complementary Partition。这对应于一个full embedding table，它的维度是：∣S∣×D∣S∣×D。

(2) Quotient-Remainder Complementary Partitions:

给定m∈Nm∈N，有：

这些partitions是complementary的。这对应于第2节中的quotient-remainder trick。

(3) Generalized Quotient-Remainder Complementary Partitions:

对于i=1,⋯,ki=1,⋯,k，给定mi∈Nmi∈N，以便∣S∣≤∏i=1kmi∣S∣≤∏i=1kmi，我们可以递归定义complementary partitions：

其中，对于j=2,⋯,kj=2,⋯,k, 有Mj=∏i=1j−1miMj=∏i=1j−1mi。这会泛化qutient-remainder trick。

(4) Chinese Remainder Partitions:

考虑一个pairwise 互质因子分解（coprime factorization），它大于或等于∣S∣∣S∣，也就是说，对于所有的i=1,⋯,ki=1,⋯,k 以及mi∈Nmi∈N, 有 ∣S∣≤∏ki=1mi∣S∣≤∏i=1kmi；以及对于所有的i≠ji≠j，有gcd(mi,mj)=1gcd(mi,mj)=1。接着，对于j=1,⋯,kj=1,⋯,k，我们可以定义该complementary partitions：

具体取决于application，我们可以定义更专门的 complementary partitions。回到我们的car示例，你可以基于year、make、type等来定义不同的partitions。假设这些属性的unique specificiation会生成一个unique car，这些partitions确实是complementary的。在以下章节，我们会演示如何来利用这些结构减小内存复杂度。

4.使用complementary partitions的compositional embeddings

在第2节对我们的方法进行泛化，我们可以为每个partitions创建一个embedding table，以便每个等价类可以被映射到一个embedding vector上。这些embeddings可以使用一些operation进行组合来生成一个compositional embedding或直接使用一些独立的sparse features（我们称它为feature generation方法）。feature generation方法尽管有效，但可以极大增加参数数目，需要增加额外features，并没有利用其内在结构，即：complementary partitions可以从相同的initial categorical feature中形成。

更严格的，考虑一个关于category set S的complementary partitions的集合：P1,P2,⋯,PkP1,P2,⋯,Pk。对于每个partition PjPj，我们可以创建一个embedding table Wj∈R∣Pj∣×DjWj∈R∣Pj∣×Dj，其中，由ijij索引的每个等价类[x]Pj[x]Pj被映射到一个embedding vector中，Dj∈NDj∈N是embedding table j的embedding维度。假设：pj:S→{0,⋯,∣Pj∣−1pj:S→{0,⋯,∣Pj∣−1函数可以将每个element x∈Sx∈S映射到相应的等价类的embedding index上，比如：x→ijx→ij。

为了泛化我们（operation-based）的compositional embedding，对于给定的category，我们会将来自每个embedding table与对应的所有embeddings交叉，来获得final embedding vector：

其中，w:RD1×⋯×RDk→RDw:RD1×⋯×RDk→RD是一个operation function。operation function的示例包括：

• 1) Concatenation:
• 2) Addition:
• 3) Element-wise Multiplication:

你可以看到，这些方法会为在简单假设下的每个category生成一个unique embedding。我们可以看到，在以下理论中。出于简洁性，下文的讨论仅限concatenation操作。

定理1

该方法会将存取整个embedding table O(∣S∣D)O(∣S∣D)的内存复杂度减小到O(∣P1∣D1+∣P2∣D2+⋯+∣Pk∣Dk)O(∣P1∣D1+∣P2∣D2+⋯+∣Pk∣Dk)。假设D1=D2=⋯=Dk=DD1=D2=⋯=Dk=D并且∣Pj∣∣Pj∣可以被专门选中，该方法会生成一个最优的内存复杂度O(k∣S∣1/kD)O(k∣S∣1/kD)，这对于存储和使用full embedding table是一个明显提升。该方法在图2中可视化。

4.1 Path-Based Compositional Embeddings

生成embeddings的另一个可选方法是，为每个partition定义一个不同的transformations集合（除了第一个embedding table外）。特别的，我们可以使用单个partition来定义一个initial embedding table，接着，将initial embedding通过一个函数组合来传递来获取final embedding vector。

更正式的，给定一个category set S的complementary partitions集合：P1,P2,⋯,PkP1,P2,⋯,Pk，我们可以定义一个embedding table W∈R∣P1∣×D1W∈R∣P1∣×D1来进行第一次划分（partition），接着为每一个其它partition定义函数集合Mj={Mj,i:RDj−1→RDj:i∈{1,⋯,∣Pj∣}}Mj={Mj,i:RDj−1→RDj:i∈{1,⋯,∣Pj∣}}。在这之前，假设：pj:S→{1,⋯,∣Pj∣}pj:S→{1,⋯,∣Pj∣}是这样的函数：它将每个category映射到embedding index对应的等价类上。

为了为category x∈Sx∈S获得embedding，我们可以执行以下transformation：

• 1.https://arxiv.org/pdf/1909.02107.pdf

Updated on July 01, 2020 d0evi1