本文分享一篇谷歌团队发表在KDD’21的推荐系统文章：不使用嵌入表的方式获得类别特征的表征用于推荐系统[1]。
本文结构组织如下：
- 背景
- 已有的类别特征嵌入方法
- One-hot Full Embedding方法
- One-hot Hash Embedding方法
- 其他Emb方法
- 提出的Deep Hash Embeddings (DHE）方法
- Deep Hash Embeddings (DHE）结构
- 实验对比
背景
类别特征（用户ID/物品ID）的学习在推荐系统中扮演着重要的作用，标准的方式是为每个类别特征分配一个嵌入向量（embedding vector）。然而这种方式在推荐系统中存在以下几个挑战：
- 嵌入特征数量大（Huge vocabulary size）：推荐系统通常包含几百万的用户ID/视频ID。
- 特征的动态的（ Dynamic nature of input）：推荐系统中经常会出现全新的用户ID/视频ID。
- 特征分布高度倾斜（Highly-skewed data distribution）：推荐数据中低频特征的训练实例数量较少，因此对特征嵌入质量有显著影响。
这篇文章提出一个Deep Hash Embeddings (DHE）的方式来缓解以上问题。
已有的类别特征嵌入方法
One-hot Full Embedding方法
做法：这种方式把所有类别特征进行编号，假设共
个特征。每个特征
首先通过one-hot进行编码：
，其中
并且
；接着通过一个可学习的线性变换矩阵（可以看作一层神经网络，但没有bias项）得到对应的嵌入表示：
。
优点：简单
缺点：embedding table随特征数量线性增长（即内存问题）；无法处理新出现的特征
One-hot Hash Embedding方法
做法：为了解决One-hot Full Embedding中的内存问题，不少方法使用Hash函数的方式对类别特征进行映射，将原始的
维的one-hot特征编码映射为
纬的one-hot特征编码（
）。即相比One-hot Hash Embedding中编码部分变为：
其中
并且
。
是哈希函数。编码部分不变：
。
优点：能有效缓解One-hot Full Embedding方式的内存问题
缺点：由于地址冲突导致多个ID共用一个嵌入表示的方式可能会伤害性能（因此有Double hash, frequecy Hash等方式进行缓解）；
One-hot Double Hash Embedding方法
对One-hot Hash Embedding的改进
做法：使用两个哈希函数分别进行编码后得到两个特征嵌入（
；
。其中
,
由不同的编码函数得到。），再把得到的特征嵌入进行聚合（sum(
,
)或concat(
,
)等）。
One-hot Frequecy Hash Embedding方法
对One-hot Hash Embedding的改进
做法：对于高频的特征不适用哈希函数，仅对于低频特征使用哈希函数进行映射。
其他Emb方法
还有一些其他的embedding的方法可参考下列论文：
- Bloom Emb：Bloom Embeddings for Sparse Binary Input/Output Networks. In RecSys. ACM. 2017.
- Compositional Emb：Compositional Embeddings Using Complementary Partitions for Memory Efficient Recommendation Systems. In SIGKDD. 2020.
- Hash Emb：Hash Embeddings for Efficient Word Representations. In NIPS. 2017
提出的Deep Hash Embeddings (DHE）方法
Deep Hash Embeddings (DHE）结构
DHE并不像其他方式一样显式的维护embedding table，而是每次由DHE模型为特征
输出一个特征嵌入
.
DHE将整个特征嵌入分为编码阶段(encoding)和解码阶段(decoding)。下图是One-hot Emb与DHE的整体区别，可以看到：
- One-hot Emb编码阶段将特征表示为one-hot的稀疏向量，解码阶段通过线性变换矩阵（可看作一层神经网络）得到该特征的唯一表示。
- DHE编码阶段通过多个哈希函数将特征表示real-value的稠密向量, 解码阶段通过多层神经网络得到该特征的唯一表示。
DHE编码阶段(encoding)的设计
一个好的encoding应该有哪些特性呢？
- 唯一性（Uniqueness）：每个特征值的编码应该是唯一的。
- 等价相似性（ Equal Similarity）：只有唯一表示是不够的。例如二进制编码中：9表示为
，8表示为：
，7表示为
。我们发现8的表示和9的表示更相似（和7的表示相比）。这可能会引入归纳偏差，让编码器以为 < 8和9 > 比 < 8 和7 >更相似，然而它们应该是等价相似的。
- 高维（High dimensionality）：我们希望这些编码便于后续解码函数区分不同的特征值。由于高维空间通常被认为是更可分离的(例如内核方法)，我们认为编码维度也应该相对较高。
- 高香农熵（High Shannon Entropy）：香农熵(以bit为单位)测量一个维度中所携带的信息。从信息论的角度来看，高香农熵的要求是为了防止冗余维数。例如，一个编码方案可能满足上述三个属性，但在某些维度上，所有特征值的编码值是相同的。所以我们希望通过最大化每个维度的熵来有效地利用所有维度。例如，one-hot编码在每个维度上的熵都很低，因为对于大多数特征值来说，每个维度上的编码都是0。因此，one-hot编码需要非常高的维度(即
)，而且效率非常低。
提出的DHE运用k个哈希函数把每个类别特征映射为一个k纬的real-value稠密向量。具体的，我们有
where
。也就是每个哈希函数会得到一个
之间的哈希下标值，所以特征
得到的
纬度和哈希函数数量一致（在上面图中是1024个哈希函数），且其中的每个元素都在
之间。
然而，直接用上面得到的编码表示是不合适的，因此作者进行了两个变换操作来保证数值稳定性：
。
- 均匀分布（Uniform Distribution）：把
中的每个值映射到[-1,1]之间
- 高斯分布（Gaussian Distribution）：把经过均匀分布后的向量转化为高斯分布
。
这里是受到GAN网络的启发，用服从高斯分布的随机变量做GAN网络的输入。
作者在文章中验证了这样设计的enconding满足上面的四个期望条件。
DHE解码阶段(decoding)的设计
decoding阶段把enconding阶段得到的
维向量映射为
维：
。如上面的图所示，作者用多层神经网络来实现，并尝试了各种激活函数以及考虑了batch normalization (BN)等训练技巧。
DHE中考虑辅助信息
对于物品ID/用户ID的特征嵌入，可以考虑拼接上它们属性（年龄、品牌等）的表示，然后输入到DHE解码阶段来生成最终的特征嵌入。
实验对比
作者首先对比了one-hot的方式以及多种hash的方法：
(OOV表示新特征，即out-of-vocab values for online learning)
- DHE取得了和one-hot相近的性能，但参数了极大的减小了。
- 其他方法虽然减小了参数量，但性能都下降了。
参考资料
[1]
Learning to Embed Categorical Features without Embedding Tables for Recommendation. KDD, 2021.: https://arxiv.org/abs/2010.10784v2
