QR embedding介绍

Reading time ~3 minutes

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

1.介绍

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以及它的基数 \(\mid S \mid\),每个categorical实例会被映射到一个在一个embedding table \(W \in R^{\mid S \mid \times D}\)的indexed row vector上,如图1所示。我们不用预先决定embedding的weights,对于生成准确的模型,在neural network的其余部分对embeddings进行jointly training更有效。

每个categorical feature,可有具有数千万可能不同的categories(比如:\(\mid S \mid \approx 10^7\)),采用的embedding vector的维度为\(D \approx 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,假设:\(\epsilon: S \rightarrow \lbrace 0, \cdots, \mid S \mid -1 \rbrace\)表示S的一个枚举(enumeration)(例如:一个categories集合S包括 S={dog, cat, mouse}, 接着S的一个潜在枚举enumeration:\(\ epsilon (dog)=0, \epsilon (cat)=1, \ epsilon (mouse)=2\)。假设\(W \in R^{\mid S \mid \times D}\)是相应的embedding matrix或table,其中D是embeddings的维度。我们可以使用\(\)e_i \in R^{\mid S \mid}\(\)将每个category(或者说:category \(x\in S\)具有index \(i=e(x)\))编码成一个one-hot vector,接着将它映射到一个dense embedding vector \(x_{emb} \in R^D\)上:

\[x_{emb} = W^T e_i\]

…(1)

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

减小embedding table的naive方法是,使用一个简单的hash function[17],比如:remainder function,这称为hashing trick。特别的,给定一个size为\(m \in N\)(其中, \(m \ll \mid S \mid\))的embedding table,也就是说,\(\sim{W} \in R^{m \times D}\),你可以定义一个hash matrix \(R \in R^{m \times \mid S \mid}\):

\[\]

…(2)

接着,该embedding通过下面执行:

\[x_{emb} = \sim{W}^T Re_i\]

…(3)

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

算法1

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

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

算法2

更严格的,我们定义了两个embedding矩阵:\(W_1 \in R^{m \times D}\)和\(W_2 \in R^{(\mid S \mid/m) \times D}\)。接着定义一个额外的hash矩阵\(Q \in R^{(\mid S \mid /m) \times \mid S \mid}\):

\[\]

…(4)

接着,我们可以通过以下方式获取我们的embedding:

\[x_{emb} = W_1^T R e_i \odot W_2^T Q e_i\]

…(5)

其中,\(\odot\)表示element-wise乘法。该trick会产生一个\(O(\frac{\mid S \mid}{m} D + 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\)表示通过partition P索引的\(x \in S\)的等价类。

定义1: 。。。

作为一个具体示例,考虑集合 \(S=\lbrace 0,1,2,3,4 \rbrace\)。接着,以下三个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 \in N\),我们定义了集合:\(\Epsiion(n) = \lbrace 0, 1, \cdots, n-1 \rbrace\)

(1) Naive Complementary Partition:

\[P = \lbrace \lbrace x \rbrace: x \in S \rbrace\]

如果P满足上式,那么P就是一个Complementary Partition。这对应于一个full embedding table,它的维度是:\(\mid S \mid \times D\)。

(2) Quotient-Remainder Complementary Partitions:

给定\(m \in N\),有:

\[P_1 = \lbrace \lbrace x \in S: \epsilon(x)\m=l \rbrace: l \in \epsilon(\lceil |S| /m \rceil) \rbrace && P_2 = \lbrace \lbrace x \in S: \epsilon(x) mod m = l \rbrace: l \in \epsilon(m) \rbrace\]

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

(3) Generalized Quotient-Remainder Complementary Partitions:

对于\(i=1, \cdots, k\),给定\(m_i \in N\),以便\(\mid S \mid \leq \prod\limits_{i=1}^{k} m_i\),我们可以递归定义complementary partitions:

\[P_1 = \lbrace \lbrace x \in S: \epsilon(x) mod m = l \rbrace: l \in \epsilon(m_1) \rbrace && P_j = \lbrace \lbrace x \in S: \epsilon(x)\M_j mod m_j = l \rbrace: l \in \epsilon(m_j) \rbrace\]

其中,对于\(j=2, \cdots, k\), 有\(M_j = \prod\limits_{i=1}^{j-1} m_i\)。这会泛化qutient-remainder trick。

(4) Chinese Remainder Partitions:

考虑一个pairwise 互质因子分解(coprime factorization),它大于或等于\(\mid S \mid\),也就是说,对于所有的\(i=1,\cdots,k\) 以及\(m_i \in N\), 有 \(\mid S \mid \leq \prod_{i=1}^{k} m_i\);以及对于所有的\(i \neq j\),有\(gcd(m_i, m_j)=1\)。接着,对于\(j=1,\cdots,k\),我们可以定义该complementary partitions:

\[P_j = \lbrace \lbrace x\inS: \epsilon(x) mod m_j = l \rbrace: l \in \Epsilon(m_j) \rbrace\]

具体取决于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的集合:\(P_1,P_2,\cdots,P_k\)。对于每个partition \(P_j\),我们可以创建一个embedding table \(W_j \in R^{\mid P_j \mid \times D_j}\),其中,由\(i_j\)索引的每个等价类\([x]_{P_j}\)被映射到一个embedding vector中,\(D_j \in N\)是embedding table j的embedding维度。假设:\(p_j: S \rightarrow \lbrace 0, \cdots, \mid P_j\mid -1\)函数可以将每个element \(x \in S\)映射到相应的等价类的embedding index上,比如:\(x \rightarrow i_j\)。

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

\[\]

…(6)

其中,\(w: R^{D_1} \times \cdots \times R^{D_k} \rightarrow R^D\)是一个operation function。operation function的示例包括:

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

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

定理1

该方法会将存取整个embedding table \(O(\mid S \mid D)\)的内存复杂度减小到\(O(\mid P_1 \mid D_1 + \mid P_2 \mid D_2 + \cdots + \mid P_k \mid D_k)\)。假设\(D_1 = D_2 = \cdots = D_k = D\)并且\(\mid P_j \mid\)可以被专门选中,该方法会生成一个最优的内存复杂度\(O(k \mid S \mid ^{1/k} D)\),这对于存储和使用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集合:\(P_1, P_2, \cdots, P_k\),我们可以定义一个embedding table \(W \in R^{\mid P_1 \mid} \times D_1\)来进行第一次划分(partition),接着为每一个其它partition定义函数集合\(M_j = \lbrace M_{j,i}: R^{D_{j-1}} \rightarrow R^{D_j}: i \in \lbrace 1, \cdots, \mid P_j \mid \rbrace \rbrace\)。在这之前,假设:\(p_j: S \rightarrow \lbrace 1, \cdots, \mid P_j \mid \rbrace\)是这样的函数:它将每个category映射到embedding index对应的等价类上。

为了为category \(x \in S\)获得embedding,我们可以执行以下transformation:

\[x_{emb} = (M_{k,p_k(x)} \degree \cdots \degree M_{2,p_2(x)}) (W e_{p_1(x)}\]

…(7)

我们

参考

DFN介绍

微信在《Deep Feedback Network for Recommendation》提出了DFN。# 摘要显式与隐式反馈可以影响用户关于items的opinions,这对于学习用户偏好来说是必要的。然而,大多数当前的推荐算法主要关注于隐式正反馈(implicit po...… Continue reading

CSCNN介绍

Published on December 11, 2020

AutoInt介绍

Published on October 10, 2020