作者 | 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^Ttextbf{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^Ttextbf{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，因为我们的问题是欠拟合而不是过拟合。
2.3 加入辅助信息以增强泛化性(解决OOV问题)
- 记忆性(memorization): 例如one-hot编码的每个id embedding都是独立的，因此只有记忆性没有泛化性
- 泛化性(generalization): 本文提出的DHE方法，embedding network中的参数变化会影响所有特征的embedding结果。
对于物品ID/用户ID的特征embedding，可以考虑「拼接」上它们属性（年龄、品牌等）的表示，然后输入到DHE「解码」阶段来生成最终的特征嵌入。这样能够增强泛化能力。
3. 实验对比
作者首先对比了one-hot的方式以及多种hash的方法：
- DHE取得了和one-hot相近的性能，但参数了极大的减小了。
- 其他方法虽然减小了参数量，但性能都下降了
本文参考资料
[1]Learning to Embed Categorical Features without Embedding Tables for Recommendation: https://arxiv.org/abs/2010.10784v2
