KDD 2021 | 谷歌DHE：不使用embedding table的类别型特征embedding

NewBeeNLP

发布于 2021-12-16 15:51:30

9040

发布于 2021-12-16 15:51:30

文章被收录于专栏：NewBeeNLPNewBeeNLP

作者 | Chilia 哥伦比亚大学 NLP搜索推荐整理 | NewBeeNLP

类别型特征（用户ID/物品ID）的embedding在推荐系统中扮演着重要的作用，标准的方式是用一个(巨大的)embedding table为每个类别特征分配一个embedding。然而这种方式在推荐系统中存在以下几个挑战：

参数量巨大（Huge vocabulary size）：推荐系统通常包含几百万的用户ID/视频ID，如果每个特征都指定一个embedding会占据大量空间。
特征是动态的（Dynamic nature of input）：推荐系统中经常会出现全新的用户ID/视频ID，固定的embedding table不能解决OOV(out-of-vocabulary)问题.
特征分布高度倾斜（Highly-skewed data distribution）：推荐数据中低频特征的训练实例数量较少，因此该特征的embedding在训练阶段就很少更新，对训练的质量有显著影响。

这篇文章提出一个「Deep Hash Embeddings (DHE）」 的方式来缓解以上问题。

论文：Learning to Embed Categorical Features without Embedding Tables for Recommendation[1]

1. 已有的类别特征embedding方法

1.1 One-hot Full Embedding

这种方式就是最常见的方法，即把所有类别特征进行编号，假设共 n 个特征。特征 s 首先通过one-hot进行编码 E(s) = \textbf{b} = \{0,1\}^n , 其中只有第 !b_s 项为1，其他都为0。接着通过一个可学习的线性变换矩阵（说白了就是embedding table，可以看作一层神经网络，但没有bias项）得到对应的embedding表示：\textbf{e} = W^T\textbf{b}

优点：简单
缺点：embedding table随特征数量线性增长（即内存问题）；无法处理新出现的特征（OOV）。

1.2 One-hot Hash Embedding

为了解决One-hot Full Embedding中的内存消耗巨大的问题，可以使用「哈希函数」对类别特征进行「映射分桶」，将原始的维的 one-hot 特征编码映射为维的 one-hot 特征编码（即m个桶，m<<n相比One-hot Full Embedding，编码部分变为：E(s) = \textbf{b} = \{0,1\}^m , 其中只有 b_{H(s)} 项为1，其他为0。接着还是通过embedding table得到embedding表示：\textbf{e} = W^T\textbf{b} 。

优点：能有效缓解One-hot Full Embedding方式的内存问题。
缺点：只要是哈希，就会有「冲突」！哈希冲突导致多个ID共用一个embedding, 这会伤害模型性能。

为了解决哈希冲突的问题，可以做如下改进：

取k个不同的哈希函数 \{H^{(1)},H^{(2)},...H^{(k)}\} , 按照上述方法生成k个one-hot编码：\{\textbf{b}^{(1)},{\textbf{b}^{(2)}},...{\textbf{b}^{(k)}}\}

(分到了k个桶), 每个one-hot编码都去查一下embedding table，并且把最后的结果concat到一起/或者做avg-pooling。

2. Deep Hash Embeddings

DHE将整个特征嵌入分为「编码阶段(encoding)「和」解码阶段(decoding)」。下图是One-hot Embedding与DHE的整体区别：

可以看到：

One-hot Embedding的编码阶段将特征表示为one-hot的稀疏向量，解码阶段通过巨大的embedding look-up table（可看作一层神经网络）得到该特征的唯一表示。
DHE编码阶段通过多个(k=1024个)哈希函数将特征表示为稠密的Identifier vector, 解码阶段通过多层神经网络得到该特征的唯一表示。

2.1 Encoding阶段

2.1.1 一个好的encoding应该有哪些特性？

唯一性（Uniqueness）：每个不同特征值的编码应该是唯一的。
同等相似性（ Equal Similarity）：只有唯一表示是不够的。例如二进制编码中：9表示为1001，8表示为1000：，7表示为0111。我们发现8的表示和9的表示更相似，这会引入bias，让编码器以为id = 8 与 id = 9比起id = 7 与 id = 9更相似，然而id类特征是没有顺序的，因此它们应该是同等相似的。
高维（High dimensionality）：我们希望这些编码便于后续解码函数区分不同的特征值。由于高维空间通常被认为是「更可分的」 (回忆一下SVM中的kernel方法...)，我们认为编码维度也应该相对较高。
高香农熵（High Shannon Entropy）：香农熵(以bit为单位)测量一个维度中所携带的信息。从信息论的角度来看，高香农熵的要求是为了防止冗余维数。例如，一个编码方案可能满足上述三个属性，但在某些维度上，所有特征值的编码值是相同的。所以我们希望通过最大化每个维度的熵来有效地利用所有维度。例如，one-hot编码在每个维度上的熵都很低，因为对于大多数特征值来说，每个维度上的编码都是0。因此，one-hot编码需要非常高的维度(即)，而且效率非常低。高香农熵就是要让encoding更加高效。

2.1.2 DHE编码阶段(encoding)的设计

提出的DHE运用 k 个哈希函数把每个类别特征映射为一个 k 维的稠密向量。

具体的，每个哈希函数 H^{(i)} 都将一个正整数 \mathbb{N} 映射到{1,2,...m},本实验中取 m = 1e6 。因此，k个哈希函数就把一个正整数 \mathbb{N} 映射成了k维的向量 E'(s) = [H^{(1)}(s),H^{(2)}(s),...,H^{(k)}(s)] , 向量中的每个元素都取自{1,2,...m}。实验中取k=1024.然而，直接用上面得到的编码表示是不合适的，因此作者进行了两个变换操作来保证数值稳定性：

均匀分布（Uniform Distribution）：把 E'(s) 中的每个值映射到[-1,1]之间
高斯分布（Gaussian Distribution）：把经过均匀分布后的向量转化为高斯分布 N(0,1) 。(作者说，这里是受到GAN网络的启发，用服从高斯分布的随机变量做GAN网络的输入。)

作者在文章中验证了这样设计的encoding满足3.1.1的四个条件。

2.2 Decoding 阶段

Decoding阶段需要把Encoding阶段得到的 k 维向量映射为 d 维。如上面的图所示，作者用多层神经网络来实现。但是，由于参数量明显比embedding table降低很多，这种多层神经网络会导致「欠拟合」。因此，作者尝试了Mish激活函数 f(x) = x·tanh(ln(1+e^x)) 来代替ReLU激活函数，引入更多的非线性，从而提升表征能力。

作者还考虑了batch normalization (BN)等训练技巧。但是不能使用dropout，因为我们的问题是欠拟合而不是过拟合。