腾讯技术 | 用万字长文聊一聊 Embedding 技术

作者：qfan，腾讯 WXG 应用研究员

随着深度学习在工业届不断火热，Embedding 技术便作为“基本操作”广泛应用于推荐、广告、搜索等互联网核心领域中。Embedding 作为深度学习的热门研究方向，经历了从序列样本、图样本、再到异构的多特征样本的发展过程。本文主要系统总结了现在主流的 Embedding 技术，简单介绍它们的基本原理，希望对大家快速整理相关知识有所帮助。

一、引言

在提到 Embedding 时，首先想到的是“向量化”，主要作用是将高维稀疏向量转化为稠密向量，从而方便下游模型处理。那什么是 embedding 呢？下面是大家对 embedding 的定义：

In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. -- Wikipedia

An embedding is a mapping from discrete objects, such as words, to vectors of real numbers. -- Tensorflow 社区

Embedding 是用一个低维稠密向量来表示一个对象，使得这个向量能够表达相应对象的某些特征，同时向量之间的距离能反应对象之间的相似性。 -- 王喆《深度学习推荐系统》

将一个实例（instance）从复杂的空间嵌入（投射）到相对简单的空间，以便对原始实例进行理解，或者在相对简单的空间中进行后续操作。 -- chrisyi《Network embedding 概述》

我个人比较倾向于 Tensorflow 社区给出的定义，即 Embedding是离散实例连续化的映射。如下图所示，可以将离散型词 embedding 成一个四维的连续稠密向量；也可以将图中的离散节点 embedding 成指定维度的连续稠密向量。

Embedding 作为深度学习的热门研究方向，经历了从序列样本、理图样本、再到异构的多特征样本的发展过程。此外，由于 embedding 技术本身具有较强的综合信息表示能力、较低的上线部署门槛，进一步加速了其在工业上的落地。

Embedding 对于推荐系统中深度学习方法的主要应用可以简单总结如下：

作为 Embedding 层嵌入到深度模型中，实现将高维稀疏特征到低维稠密特征的转换（如 Wide&Deep、DeepFM 等模型）；
作为预训练的 Embedding 特征向量，与其他特征向量拼接后，一同作为深度学习模型输入进行训练（如 FNN）；
在召回层中，通过计算用户和物品的 Embedding 向量相似度，作为召回策略（比 YouTube 推荐模型等）；
实时计算用户和物品的 Embedding 向量，并将其作为实时特征输入到深度学习模型中（比 Airbnb 的 embedding 应用）。

对于推荐场景中，什么数据可以采用 Embedding 来构造特征呢？下面简单列了下我在做微信游戏中心场景游戏和内容推荐时主要采用 embedding 技术来处理的数据（本文只简单列一下主要的点，后续会详细文章来具体讲如何处理以及其带来的效果）。

User 数据（用户的基础属性数据，如性别、年龄、关系链、兴趣偏好等）
- 对于用户兴趣偏好，一般简单地采用文本 embedding 方法来得到各标签的 embedding 向量，然后根据用户对个标签的偏好程度做向量加权；
- 对于关系链数据（如同玩好友、游戏中心相互关注等），构造用户关系图，然后采用基于图的 embedding 方法来得到用户的 embedding 向量；
Item 数据（Item 基本信息数据，如标题、作者、游戏简介、标签等）
对于文本、简介和标签等可以采用基于文本的 embedding 方法来在已有语料上预训练模型，然后得到对应的 embedding 向量（如 word2vec 或者 BERT）；
此外对于有明确关系的（如 item-> 文本-> 标签 or 关键词）可以采用对关键词/标签的向量均值来表示 item 的文本向量（这里安利一下 Facebook 开源的 StarSpace）；
User 行为数据（用户在场景中的行为数据，如点击、互动、下载等）
针对用户对 Item 的操作（如点击、互动、下载）构造用户->item+Item 标签体系，构造用户-item-tag 的异构网络，然后可以采用 Metapath2vec 来得到各节点的 embedding 向量；
通过记录用户在整个场景访问 item，构造 Item-Item 关系图，然后采用 DeepWalk 算法得到 item 的向量，用来挖掘 Item 间的关系特征；
额外数据（外部扩充数据，如用户游戏行为、用户微信其他场景活跃等）
标签型（主要是用户在各场景的兴趣偏好）：
关系链型（如游戏中心好友、游戏内好友、开黑好友）可以采用用户关系构造用户关系图，采用 Graph embedding 方法（如 GraphSAGE）来表示用户抽象特征

当然，这些处理方法只是我个人这一年多的经验，可能有些地方用的并不是很合理，欢迎大家一起交流。

下面开始本文正文“介绍现在主流的 Embedding 技术”，主要分三大块：

经典的矩阵分解方法：这里主要是介绍 SVD 方法
基于内容的 embedding 方法：这部分主要涉及到 NLP 相关的文本 embedidng 方法，包括静态向量 embedding（如 word2vec、GloVe 和 FastText）和动态向量 embedding（如 ELMo、GPT 和 BERT）
基于 Graph 的 embedding 方法：这部分主要是介绍图数据的 embedding 方法，包括浅层图模型（如 DeepWalk、Node2vec 和 Metapath2vec）和深度图模型（如基于谱的 GCN 和基于空间的 GraphSAGE）

二、经典矩阵分解法

1、奇异值分解

SVD（Singular value decomposition，奇异值分解）是一种矩阵分解的方法，任何矩阵，都可以通过 SVD 的方法分解成几个矩阵相乘的形式。

X_{m\times n} \approx U_{m\times r} S_{r\times r} V^T_{r\times n}

其中U_{m\times n}和V_{n\times n}是正交矩阵，\sum_{m\times n}是特征值矩阵。

对于机器学习，SVD 一个主要优点是对矩阵降维，对于高维矩阵X可以通过 SVD 表示成三个维度相对较低的矩阵U、S和V。

在推荐系统中，可以将用户行为构造成 User-Item 的评分矩阵X_{m\times n} ，其中 m 和 n 分别表示平台的 User 数和 Item 数。 X(i,j)表示用户U_i对物品I_j的评分（也可以是点击、互动、播放、下载等行为），用于刻画 User 对 Item 的有效操作。采用 SVD 算法将M_{m \times n}分解成 $U_{m\times r} 、S_{r\times r}和V_{x\times n} ^ T$。

虽然，从形式上看 SVD 分解简单直接，但由于日常 User-Item 的评分矩阵事高度稀疏的，而 SVD 分解要求矩阵是稠密的，通常采用对评分矩阵中的缺失值进行补全（比如补 0、全局平均值、用户物品平均值补全等）得到稠密矩阵。再用 SVD 分解并降维。但实际过程中，元素缺失值是非常多的，导致了传统 SVD 不论通过以上哪种方法进行补全都是很难在实际应用中起效果。此外传统 SVD 在实际应用中还有一个严重的问题——计算复杂度（时间复杂度是O(n^3)，空间复杂度是O(nmp)）。当用户数和物品总量过大（如千上万级），对矩阵做 SVD 分解是非常耗时。这是得传统的 SVD 分解方法很难在实际业务中应用起来。

研究者们做了大量工作来解决传统 SVD 的稀疏数据不适用和高计算复杂度的问题，其中主要的有 FunkSVD、BiasSVD 和 SVD++ 算法。

2、隐语义模型（Latent Factor Model）

LFM 主要代表是 2006 年由 Simon Funk 在博客上公开的算法 FunkSVD，将评分矩阵分解成两个低维矩阵（P 和 Q）相乘，可直接通过训练集中的观察值利用最小化均方根学习 P，Q 矩阵。

X_{m\times n} \approx P_{k\times m}^T Q_{k\times n}

用户u对物品i的评分可以表示为p_u^Tq_i，其中p_u和q_i分别是矩阵P和Q对应第u和i的列向量，表示用户u和物品i的隐向量。FunkSVD 核心思想是将在原始 SVD 上加了线性回归，使得我们可以用均方差作为损失函数来寻找 P 和 Q 的最佳值：

L(X,P,Q) = \sum{(X_{u,i}-p_u^Tq_i)^2} = \sum{(X_{u,i} - \sum_{f=1}^kp_{uf}q_{if})^2}

上式可以通过梯度下降法来求解，损失函数求偏导为：

\frac{dL}{dp_{uf}} = -2q_{ik} + 2\lambda p_{uk} \\ \frac{dL}{dq_{if}} = -2p_{uk} + 2\lambda q_{ik}

参数更新如下：

p_{uf} = p_{uf} - \alpha \frac{dL}{dp_{uf}} = p_{uf} + \alpha (q_{ik}-\lambda p_{uk}) \\ q_{if} = q_{if} - \alpha \frac{dL}{dq_{if}} = q_{if} + \alpha (p_{uk}-\lambda q_{ik})

在 Funk-SVD 获得巨大成功之后，研究人对其进行进一步优化工作，提出了一系列优化算法。其中 BiasSVD 就是在原始 FunkSVD 模型中添加三项偏移项优化得到的：

物品偏移量 (b_i)：表示了物品接受的评分和用户没有多大关系，物品本身质量决定了的偏移；
用户偏移量 (b_u)：有些用户喜欢打高分，有些用户喜欢打低分，用户决定的偏移；
全局偏移量 (\mu)：根据全局打分设置的偏移，可能和整体用户群和物品质量有相对应的关系。

BiasSVD 的预测结果为：

\hat{X}_{u,v} = \mu + b_u + b_i + p_u^Tq_i

损失函数为：

L = \sum{(X_{u,i}-\hat{X}_{u,i})^2} + \lambda(b_u^2+b_i^2+||p_u||^2 + ||q_i||^2)

SVD++ 算法是在 BiasSVD 的基础上引入隐式反馈（如用户历史浏览、用户历史评分、电影历史浏览、电影历史评分等）作为新的参数，其预测结果为：

\hat{X}_{u,i} = \mu + b_u + b_i + q_i^T (p_u + \frac{1}{||X_u||\sum_{j\in X_u}y_j})

其优化如下：

e_{u,i} = X_{u,i} - \hat{X}_{u,i} \\ b_i \leftarrow b_i + \alpha (e_{u,i} - \lambda b_i) \\ b_u \leftarrow b_u + \alpha (e_{u,i} - \lambda b_u) \\ p_u \leftarrow p_u + \alpha (e_{u,i}q_i - \lambda p_u) \\ q_i \leftarrow q_i + \alpha (e_{u,i}(p_u + \frac{1}{||X_u||}\sum_{j\in X_u}{y_j}) - \lambda q_i) \\ y_j \leftarrow y_j + \alpha(e_{u,i}\frac{1}{||R_u||}q_i - \lambda q_i)

虽然矩基于矩阵分解的方法原理简单，容易编程实现，具有较好的扩展性，在小规模数据上也有不错的表现。但对于如今互联网推荐场景的数据量级，矩阵分解方法很难与深度学习算法一战。

三、基于内容的 Embedding 方法

对于基于内容的 embedding 方法，主要是针对文本类型数据（对图像、音视频等多媒体数据 embedding 方法，感兴趣的可以自行查阅相关技术）。下图是从 word2vec 到 BERT 的发展历史（最新已经发展到了 GPT3 了，模型更新太快，还没来得及用，就已经过时了），从图中可以看出自从 2013 年 word2vec 横空出世后，文本 embedding 方法不断被优化。从最开始的静态向量方法（如 word2vec、GloVe 和 FastText）发展为能根据上下文语义实现动态向量化的方法如（ELMo、GPT 和 BERT）。下面主要从分静态向量和动态向量两个方面来介绍相应的方法。

1、静态向量

所谓静态向量指的是一旦训练完成后，对应的向量便不再发生改变，比如一个词经过向量化之后，在后续的场景中该词对应的向量不会发生改变。这些方法主要包括 Word2Vec、GloVe 和 FastText。

A) Word2vec

Word2vec 是 2013 年 Google 发布的无监督词向 embedding 模型。该模型采用 CBOW 或 Skip-gram 模型来训练词向量，将词从 one-hot 编码的向量映射成 d 维稠密向量：

其中 CBOW 是采用词的上下文来预测该词，而 Skip-gram 则是采用词来预测其上下文。两者网络结构相似，通常所得到的词向量效果相差不大；但对于大型语料，Skip-gram 要优于 CBOW。

B) GloVe

GloVe（Global Vectors for Word Representation）是 2014 年由斯坦福大学提出的无监督词向量表示学习方法，是一个基于全局词频统计（count-based & overall statistics）的词表征工具。由它得到的词向量捕捉到单词之间一些语义特性，比如相似性、类比性等。GloVe 主要分为三步：

基于语料构建词的共现矩阵X

X_{i,j}表示词i和词j在特定大小的窗口内共同出现的次数。如对于语料：I play cricket, I love cricket and I love football，窗口为 2 的的共现矩阵可以表示为：

构造词向量和贡献矩阵之间的关系：

其中，v_i和v_j是要求解的词向量，b_i和b_j是两个词向量的偏差项。

最终 GloVe 的 loss function 如下：

J = \sum_{i,j}^N{f(X_{i,j})(v_i^Tv_j + b_i + b_j - log(X_{i,j}))^2}

其中，N表示语料库中词个数。在语料库中，多个单词会一起出现多次，f表示权重函数主要有以下原则：

非递减函数，用于确保多次一起出现的单词的权重要大于很少在一起出现的单词的权重
权重不能过大，达一定程度之后应该不再增加
f(0)=0，确保没有一起出现过的单词不参与 loss 的计算

在论文中，作者给出了如下分段函数：

f(x)= \begin{cases} (x/x_{max})^\alpha & if x < x_{max}\\ 1& if x >= x_{max} \end{cases}

通过实验，作者得到了效果相对较好的\alpha=3/4 ，x_{max}=100，此时对应曲线如下图：

CBOW 和 Skip-gram 是 local context window 的方法，缺乏了整体的词和词的关系，负样本采样会缺失词的关系信息。此外，直接训练 Skip-gram 类型的算法，很容造成高曝光词汇得到过多的权重。Global Vector 融合了矩阵分解 Latent Semantic Analysis (LSA)的全局统计信息和 local context window 优势。融入全局的先验统计信息，可以加快模型的训练速度，又可以控制词的相对权重。

C) FastText

FastText 是 Facebook 在 2017 年提出的文本分类模型（有监督学习）。词向量则是 FastText 的一个副产物。FastText 模型结果如下图所示：

其中x_1, x_2, ...,x_{N-1}, x_N表示一个文本中的 n-gram 向量，每个特征是词向量的平均值。从模型结构可以看出，FastText 与 CBOW 模型的结构相似，不同在于 FastText 预测的是全部的 n-gram 去预测指定类别，而 CBOW 预测的是中间词。

2、动态向量

由于静态向量表示中每个词被表示成一个固定的向量，无法有效解决一词多义的问题。在动态向量表示中，模型不再是向量对应关系，而是一个训练好的模型。在使用时，将文本输入模型中，模型根据上下文来推断每个词对应的意思，从而得到该文本的词向量。在对词进行向量表示时，能结合当前语境对多义词进行理解，实现不同上下文，其向量会有所改变。下面介绍三种主流的动态向量表示模型：ELMo、GPT 和 BERT。

A) ELMo

ELMo（Embeddings from Language Models）是 2018 年 3 月发表，获得了 NAACL18 的 Best Paper。ELMo 的模型结构如下图所示：

由于当时并没有提出现在火热的 Transformer 结构，ELMo 采用的是多层双向 LSTM 来搭建模型。在给定一个包含 N 个 token 的文本 (t1, t2, ..., tN)：

前向语言模型用于计算给定句子 t1,t2,...,tk-1，目标为 tk 的概率：

p(t_1, t_2, ..., t_N) = \prod_{k=1}^N{p(t_k|t_1,t_2,...,t_{k-1})}

后向语言模型与前向相反，对于给定 tk+1,tk+2,...,tN，目标为 tk 的概率：

p(t_1, t_2, ..., t_N) = \prod_{k=1}^N{p(t_k|t_{k+1},t_{k+2},...,t_N)}

最终目标函数为：

L = \sum_{k=1}^N{log\ p(t_k|t_1,...,t_{k-1}; \Theta_x, \stackrel{\rightarrow}{\Theta}_{LSTM}, \Theta_s) + log \ p(t_k|t_{k+1},..., t_N; \Theta_x, \stackrel{\leftarrow}{\Theta}_{LSTM}, \Theta_s)}

其中，\Theta_x是输入 token 的 embedding，\Theta_s表示 softmax 层的参数，\stackrel{\rightarrow}{\Theta}_{LSTM}和\stackrel{\leftarrow}{\Theta}_{LSTM}分别是双向 LSTM 的参数。

对于每个输入的 token，一个 L 层的双向 LSTM 输出有 2L+1 个向量：

R_k = \{x_k^{LM}, h_{k,j}^{\stackrel{\rightarrow}{LM}}, h_{k,j}^{\stackrel{\leftarrow}{LM}} | j=1,...,L\} = \{h_{k,j}^{LM}| j=0,...,L\}

其中，h_{k,j}^{LM}表示第j层中底k个节点的输出（\stackrel{\rightarrow}{LM}和\stackrel{\leftarrow}{LM}分别表示前向和反向）,j=0表示 token layer，j>0表示双向 LSTM layer。

在下游的任务中， ELMo 把所有层的 R 压缩在一起形成一个向量：

ELMo_k^{task} =E(R_k; \Theta^{task}) = \gamma^{task}\sum_{j=0}^L{s_j^{task} h_{k,j}^{LM}}

具体步骤如下：

预训练 biLM 模型，通常由两层 bi-LSTM 组成，之间用 residual connection 连接起来。
在任务语料上 fine tuning 上一步得到的 biLM 模型，这里可以看做是 biLM 的 domain transfer。
利用 ELMo 提取 word embedding，将 word embedding 作为输入来对任务进行训练。

B) GPT

GPT-1（Generative Pre-Training）是 OpenAI 在 2018 年提出的，采用 pre-training 和 fine-tuning 的下游统一框架，将预训练和 finetune 的结构进行了统一，解决了之前两者分离的使用的不确定性（例如 ELMo）。此外，GPT 使用了 Transformer 结构克服了 LSTM 不能捕获远距离信息的缺点。GPT 主要分为两个阶段：pre-training 和 fine-tuning

Pre-training（无监督学习）

预训练模型采用前向 Transformer 结构如下图所示：

GPT 采用 auto regressive language model 对大量文本进行无监督学习，目标函数就是语言模型最大化语句序列出现的概率，其损失函数为：

L_1 = \sum_{i}{log \ P(x_i | x_{i-k},...,x_{i-1}; \Theta)}

其中，k 为上文的窗口，P表示参数为\Theta的神经网络模型。

h_0 = U W_e + W_p \\ h_l = transformer(h_{l-1}) \forall i in [1,n] \\ P(u) = softmax(h_nW_e^T)

U表示左侧窗口的上下文词向量，n表示 Transformer 的层数，W_e表示词向量矩阵，W_p表示 position embedding 矩阵（作者对 position embedding 矩阵进行随机初始化并训练学习）。

Fine-tuning（有监督学习）

采用无监督学习预训练好模型后后，可以把模型模型迁移到新的任务中，并根据新任务来调整模型的参数。

假设数据集的一个样本为(x_1, x_2, ..., x_m, y)，则将(x_1, x_2, ..., x_m)输入到预训练好的模型中，得到文本的 embedding 向量h_l^m，最后采用线性层和 softmax 来预测标签，输出和损失分别为：

P(y|x_1,x_2, ..., x_m) = softmax(h_l^m W_y) \\ L_2 = \sum_{(x,y)}{log \ P(y|x_1,x_2, ...,x_m)}

其中，W_y为下游任务的参数。

为避免在 Fine-Tuning 时，模型陷入过拟合和加速收敛，添加了辅助训练目标的方法，就是在使用最后一个词的预测结果进行监督学习的同时，前面的词继续上一步的无监督训练。最终的损失函数为：

L = L_2 + \lambda L_1

其中，\lambda用于控制无监督目标权重，一般取 $0.5$。

总体来说，Fine-tuning 阶段需要的额外参数是W_y和以隔符 token 的 embedding。其他任务迁移的输入格式可参考下张图：

C) BERT

BERT (Bidirectional Encoder Representations from Transformers)是 Goole 在 2018 年 10 月发表的，当时刷新了 11 项 NLP 任务，从此成为 NLP 领域“最靓的仔”。BERT、ELMo 和 GPT 模型结构对比图如下图所示：

相较于 ELMo，BERT 采用句子级负采样来得到句子表示/句对关系，使用 Transformer 模型代替 LSTM，提升模型表达能力，Masked LM 解决“自己看到自己”的问题。相较于 GPT，BERT 采用了双向的 Transformer，使得模型能够挖掘左右两侧的语境。此外，BERT 进一步增强了词向的型泛化能力，充分描述字符级、词级、句子级甚至句间的关系特征。

BERT 的输入的编码向量（长度为 512）是 3 种 Embedding 特征 element-wise 和，如下图所示：

这三种 Embedding 特征分别是：

Token Embedding (WordPiece)：将单词划分成一组有限的公共词单元，能在单词的有效性和字符的灵活性之间取得一个折中的平衡。如图中的“playing”被拆分成了“play”和“ing”；
Segment Embedding：用于区分两个句子，如 B 是否是 A 的下文（对话场景，问答场景等）。对于句子对，第一个句子的特征值是 0，第二个句子的特征值是 1；
Position Embedding：将单词的位置信息编码成特征向量，Position embedding 能有效将单词的位置关系引入到模型中，提升模型对句子理解能力；

最后，[CLS] 表示该特征用于分类模型，对非分类模型，该符合可以省去。[SEP] 表示分句符号，用于断开输入语料中的两个句子。

在模型预训练阶段，BERT 采用两个自监督任务采用来实现模型的多任务训练：1）Masked Language Model；2）Next Sentence Prediction

Masked Language Model (MLM)

MLM 的核心思想早在 1953 年就被 Wilson Taylor[Wilson]提出，是指在训练时随机从输入语料中 mask 掉一些单，然后通过该词上下文来预测它（非常像让模型来做完形填空），如下图所以：

本文地址：腾讯技术 | 用万字长文聊一聊 Embedding 技术
本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

在论文实验中，只有 15% 的 Token 会被随机 Mask 掉。在训练模型时，一个句子会被多次输入模型中用于参数调优，对于某个要被 Mask 的 Token 并不是每次都一定会被 Mask 掉：

80% 概率直接替换为 [MASK]，如 my dog is hairy -> my dog is [mask]
10% 概率替换为其他任意 Token，如 my dog is hairy -> my dog is appl
10% 概率保留为原始 Token，如 my dog is hairy -> my dog is hairy

这样做的好处主要有：

如果某个 Token100% 被 mask 掉，在 fine-tuning 的时候会这些被 mask 掉的 Token 就成为 OOV，反而影响模型的泛化性;
加入随机 Token 是因为 Transformer 要保持对每个输入 Token 的分布式表征，否则模型就会记住这个[MASK]=“hairy”
虽然加入随机单词带来的负面影响，但由于单词被随机替换掉的概率只有 15%*10% =1.5%，负面影响可以忽略不计

Next Sentence Prediction (NSP)

许多重要的下游任务譬如 QA、NLI 需要语言模型理解两个句子之间的关系，而传统的语言模型在训练的过程没有考虑句对关系的学习。BERT 采用 NSP 任务来增强模型对句子关系的理解，即给出两个句子 A、B，模型预测 B 是否是 A 的下一句，如下图所示：

训练数据集构造上，从平行语料中随机抽取连续的两句话：50% 保留抽取的两句话（label=IsNext）；50% 的第二句话随机从语料中抽取（label=NotNext）

Fine-tuning

在 https://github.com/google-research/bert.git 中有 N 多种预训练模型，大家可以根据需要下载对应的模型，下面主要给出两个常用的模型：

BERT-Base_L-12_H-768_A-12，总参数为 110M
BERT-Large_L-24_H-1024_A-16，总参数为 340M

其中，L 表示网络层数（Transformer blocks 数量），A 表示 Multi-Head Attention 中 self-Attention 数，filter 的尺寸是 4H

BERT 提供了 4 中不同的下游任务的微调方案，大家根据自己的语料在预训练好的模型上采用这些任务来微调模型：

句对关系判断：第一个起始符号[CLS]经过编码后，增加 Softmax 层，即可用于分类；
单句分类任务：实现同“句对关系判断”；
问答类任务：问答系统输入文本序列的 question 和包含 answer 的段落，并在序列中标记 answer，让 BERT 模型学习标记 answer 开始和结束的向量来训练模型；
序列标准任务：识别系统输入标记好实体类别（人、组织、位置、其他无名实体）文本序列进行微调训练，识别实体类别时，将序列的每个 Token 向量送到预测 NER 标签的分类层进行识别。

BERT 是截止至 2018 年 10 月的最新的的 SOTA 模型，通过预训练和精调可以解决 11 项 NLP 的任务。采用 Transformer 作为算法的主框架，能更好地捕捉更长距离的依赖和语句中的双向关系。与之前的预训练模型相比，BERT 能捕捉到正意义上的 bidirectional context 信息。采用 MLP+NSP 多任务方法使模型具有更强的泛化能力。最后，强大的计算资源 + 更大的数据造就了更强更复杂的模型。

四、基于 Graph 的 Embedding 方法

基于内容的 Embedding 方法（如 word2vec、BERT 等）都是针对“序列”样本（如句子、用户行为序列）设计的，但在互联网场景下，数据对象之间更多呈现出图结构，如 1）有用户行为数据生成的物品关系图；2）有属性和实体组成的只是图谱。

对于图结构数据，基于内容的 embedding 方法不太好直接处理了。因此，为了解决土结构数据的问题，Graph Embedding 开始得到大家的重视，并在推荐系统领域流行起来。

Graph Embedding 是一种将图结构数据映射为低微稠密向量的过程，从而捕捉到图的拓扑结构、顶点与顶点的关系、以及其他的信息。目前，Graph Embedding 方法大致可以分为两大类：1）浅层图模型；2）深度图模型。

1、浅层图模型

浅层图模型主要是采用 random-walk + skip-gram 模式的 embedding 方法。主要是通过在图中采用随机游走策略来生成多条节点列表，然后将每个列表相当于含有多个单词（图中的节点）的句子，再用 skip-gram 模型来训练每个节点的向量。这些方法主要包括 DeepWalk、Node2vec、Metapath2vec 等。

A) DeepWalk

DeepWalk 是第一个将 NLP 中的思想用在 Graph Embedding 上的算法，输入是一张图，输出是网络中节点的向量表示，使得图中两个点共有的邻居节点（或者高阶邻近点）越多，则对应的两个向量之间的距离就越近。

DeepWalk 得本质可以认为是：random walk + skip-gram。在 DeepWalk 算法中，需要形式化定义的是 random walk 的跳转概率，即到达节点v_i后，下一步遍历其邻居节点v_j的概率：

P(v_j|v_i) = \begin{cases} \frac{M_{ij}}{\sum_{k\in N{+}(v_i)}{M_{ik}}} & ,v_j \in N_{+}(v_i) \\ 0 & ,v_j \notin N_{+}(v_i) \end{cases}

其中，N_{+}(v_i)表示及节点v_i的所有出边连接的节点集合，M_{ij}表示由节点v_i连接至节点v_j的边的权重。由此可见，原始 DeepWalk 算法的跳转概率是跳转边的权重占所有相关出边权重之和的比例。算法具体步骤如下图所示：

DeepWalk 算法原理简单，在网络标注顶点很少的情况也能得到比较好的效果，且具有较好的可扩展性，能够适应网络的变化。但由于 DeepWalk 采用的游走策略过于简单（BFS），无法有效表征图的节点的结构信息。

B) Node2vec

为了克服 DeepWalk 模型的 random walk 策略相对简单的问题，斯坦福大学的研究人员在 2016 年提出了 Node2vec 模型。该模型通过调整 random walk 权重的方法使得节点的 embedding 向量更倾向于体现网络的同质性或结构性。

同质性：指得是距离相近的节点的 embedding 向量应近似，如下图中，与节点u相连的节点s_1、s_2、s_3 和 s_4的 embedding 向量应相似。为了使 embedding 向量能够表达网络的同质性，需要让随机游走更倾向于 DFS，因为 DFS 更有可能通过多次跳转，到达远方的节点上，使游走序列集中在一个较大的集合内部，使得在一个集合内部的节点具有更高的相似性，从而表达图的同质性。
结构性：结构相似的节点的 embedding 向量应近似，如下图中，与节点u结构相似的节点s_6的 embedding 向量应相似。为了表达结构性，需要随机游走更倾向于 BFS，因为 BFS 会更多的在当前节点的邻域中游走，相当于对当前节点的网络结构进行扫描，从而使得 embedding 向量能刻画节点邻域的结构信息。

在 Node2vec 中，同样是通过控制节点间的跳转概率来控制 BFS 和 DFS 倾向性的。如下图所示，当算法先由节点t跳转到节点v，准备从节点v跳转至下一个节点时（即t-> v -> x? ），各节点概率定义如下：

\pi_{vx} = \alpha_{p,q}(t,x) \cdot w_{vx}

其中，w_{vx}是节点v和x边的权重，\alpha_{p,q}(t,x)定义如下：

\\ \alpha(t, x) = \begin{cases} \frac{1}{p} & if \ d_{tx} = 0 \\ 1 & if \ d_{tx} = 1 \\ \frac{1}{q} & if \ d_{tx} = 2 \end{cases}

这里d_{tx}表示节点t与x的最短路径，如t与x_1的最短路径为 1（即d_{tx_1} = 1），则\alpha_{p,q}(t, x_1)=1。作者引入了两个参数p和q来控制游走算法的 BFS 和 DFS 倾向性：

return parameter p：值越小，随机游走回到节点的概率越大，最终算法更注重表达网络的结构性
In-out parameter q：值越小，随机游走到远方节点的概率越大，算法更注重表达网络的同质性

当p=q=1时，Node2vec 退化成了 DeepWalk 算法。

下图是作者通过调整 p 和 q，使 embedding 向量更倾向于表达同质性和结构性的可视化结果：

从图中可以看出，同质性倾向使相邻的节点相似性更高，而结构性相似使得结构相似的节点具有更高的相似性。Node2vec 的算法步骤如下：

相较于 DeepWalk，Node2vec 通过设计 biased-random walk 策略，能对图中节点的结构相似性和同质性进行权衡，使模型更加灵活。但与 DeepWalk 一样，Node2vec 无法指定游走路径，且仅适用于解决只包含一种类型节点的同构网络，无法有效表示包含多种类型节点和边类型的复杂网络。

C) Metapath2vec

为了解决 Node2vec 和 DeepWalk 无法指定游走路径、处理异构网络的问题，Yuxiao Dong 等人在 2017 年提出了 Metapath2vec 方法，用于对异构信息网络（Heterogeneous Information Network, HIN）的节点进行 embedding。

Metapath2vec 总体思想跟 Node2vec 和 DeepWalk 相似，主要是在随机游走上使用基于 meta-path 的 random walk 来构建节点序列，然后用 Skip-gram 模型来完成顶点的 Embedding。

作者首先给出了异构网络（Heterogeneous Network）的定义：

异构网络G=(V,E,T)，其中节点和边的映射函数分别为\phi(v): v \rightarrow T_v 和 \varphi(e): \\E\rightarrow T_E，满足|T_V|+|T_E|>2，其中V_E和T_E分别是节点和边的类型

即，存在多种类型节点或边的网络为异构网络。
虽然节点类型不同，但是不同类型的节点会映射到同一个特征空间。由于异构性的存在，传统的基于同构网络的节点向量化方法很难有效地直接应用在异构网络上。

为了解决这个问题，作者提出了 meta-path-based random walk：通过不同 meta-path scheme 来捕获不同类型节点之间语义和结构关系。meta-path scheme 定义如下：

V_1 \stackrel{R_1}{\rightarrow} V_2 \stackrel{R_2}{\rightarrow} ... V_t \stackrel{R_t}{\rightarrow}V_{t+1}...V_{l-1} \stackrel{R_{l-1}}{\rightarrow}V_l

其中R_i表示不同类型节点V_i和V_{i+1}之间的关系。节点的跳转概率为：

p(v^{i+1}|v_t^i,P)=\left\{ \begin{array}{rcl} \frac{1}{|N_{t+1}(v_t^i)|} & if \ (v^{i+1}, v^i_t) \in E \ \& \ \phi(v^{i+1})=t+1\\ 0 & if \ (v^{i+1}, v^i_t) \in E \ \& \ \phi(v^{i+1}) \neq t+1\\ 0 & if \ (v^{i+1}, v^i_t) \notin E \end{array} \right.

其中，v_t^i \in V_t，N_{t+1}(v_t^i)表示节点的类型的邻居节点集合。me ta-path 的定义一般是对称的，比如 user-item-tag-item-user。最后采用 skip-gram 来训练节点的 embedding 向量：

O = \mathop{\arg \max}_{\theta} \sum_{v\in V}{\sum_{t \in T_v}{\sum_{{c_t}\in N_t(v)}{log \ p(c_t | v; \theta)}}}

其中：N_t(v)表示节点v的上下文中，类型为t的节点，

p_{metapath2vec}(c_t|v; \theta)=\frac{e^{X_{c_t}\cdot X_v}}{\sum_{u\in V}{e^{X_u \cdot X_v}}}

通过分析 metapath2vec 目标函数可以发现，该算法仅在游走是考虑了节点的异构行，但在 skip-gram 训练时却忽略了节点的类型。为此，作者进一步提出了 metapath2vec++ 算法，在 skip-gram 模型训练时将同类型的节点进行 softmax 归一化：

p_{metapath2vec++}(c_t|v;\theta)=\frac{e^{X_{c_t}\cdot X_v}}{\sum_{u_t\in V_t}{e^{X_{u_t}\cdot X_v}}}

metaptah2vec 和 metapath2vec++ 的 skip-gram 模型结构如下图所示：

metapath2vec++ 具体步骤如下图所示：

2、深度图模型

上一节讲的浅层图模型方法在世纪应用中是先根据图的结构学习每个节点的 embedding 向量，然后再讲得到的 embedding 向量应用于下游任务重。然而，embedding 向量和下游任务是分开学习的，也就是说学得的 embedding 向量针对下游任务来说不一定是最优的。为了解决这个 embedding 向量与下游任务的 gap，研究人员尝试讲深度图模型是指将图与深度模型结合，实现 end-to-end 训练模型，从而在图中提取拓扑图的空间特征。主要分为四大类：Graph Convolution Networks (GCN)，Graph Attention Networks (GAT)，Graph AutoEncoder (GAE)和 Graph Generative Networks (GGN)。

本节主要简单介绍 GCN 中的两个经典算法：1）基于谱的 GCN (GCN)；2）基于空间的 GCN (GraphSAGE)。

其他方法有兴趣的同学可以参考。。。

提取拓扑图的空间特征的方法主要分为两大类：1）基于空间域或顶点域 spatial domain(vertex domain)的；2）基于频域或谱域 spectral domain 的。通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。

基于 spatial domain：基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上，跟传统的卷积神经网络中的卷积更相似一些。主要有两个问题：1）按照什么条件去找中心节点的邻居，也就是如何确定 receptive field；2）按照什么方式处理包含不同数目邻居的特征。
基于 spectral domain：借助卷积定理可以通过定义频谱域上的内积操作来得到空间域图上的卷积操作。

A) GCN

图神经网络的核心工作是对空间域(Spatial Domain)中节点的 Embedding 进行卷积操作（即聚合邻居 Embedding 信息），然而 Graph 和 Image 数据的差别在于节点邻居个数、次序都是不定的，使得传统用于图像上的 CNN 模型中的卷积操作不能直接用在图上，因此需要从频谱域(Spectral Domain)上重新定义卷积操作再通过卷积定理转换回空间域上。

Thomas 等人在 2017 年对上式做了进一步简化：限制每个卷积层仅处理一阶邻居特征，通过采用分层传播规则叠加多层卷机，从而实现对多阶邻居特征的传播。通过限制卷机核的一阶近似能缓解节点度分布非常宽的图对局部邻域结构的过度拟合问题。如下图所示，通过集联多个卷积层，节点x_3能聚合多个邻居节点特征。

使用切比雪夫一阶展开（K=1）的核卷积 + 非线性单元如下：

H^{l+1} = \sigma(\widetilde{D}^{-1/2} \widetilde{A} \widetilde{D}^{-1/2} H^{l}W^{l+1})

其中，H^l表示第l层卷积核的输出，作为H^{l+1}的数据，H^0为各节点的特征X。\widetilde{D}^{-1/2} \widetilde{A} \widetilde{D}^{-1/2} 是卷积核的一阶近似，可以简单理解成邻接节点特征的加权平均。\sigma为非线性激活函数，W^l为第l层的卷积核参数（每个节点共享）。

Thomas 等人在设计卷积核时做了两个 trick：

每个节点增加了 selp-loop，使在卷积计算时能考虑当前节点自身特征：\widetilde{A}=A + I
对\widetilde{A}进行对称归一化：\widetilde{A}=\widetilde{D}^{-1/2} \widetilde{A} \widetilde{D}^{-1/2}。避免了邻接节点数越多，卷积后结果越大的情况。此外这个操作还能考虑邻接节点度大小对卷积核的影响。

B) GraphSAGE

GraphSAGE（Graph SAmple and aggreGatE）是基于空间域方法，其思想与基于频谱域方法相反，是直接在图上定义卷积操作，对空间上相邻的节点上进行运算。其计算流程主要分为三部：

对图中每个节点领据节点进行采样
根据聚合函数聚合邻居节点信息（特征）
得到图中各节点的 embedding 向量，供下游任务使用

GraphSAGE 生成 Embedding 向量过程如下：

其中 K 表示每个节点能够聚合的邻居节点的跳数（例如 K=2 时，每个顶点可以最多根据其 2 跳邻居节点的信息来表示自身的 embedding 向量）。算法直观上是在每次迭代中，节点聚合邻居信息。随着不断迭代，节点得到图中来自越来越远的节点信息。

邻居节点采样：在每个 epoch 中，均匀地选取固定大小的邻居数目，每次迭代选取不同的均匀样本。

GraphSAGE 的损失函数如下：

J_g(z_u) = log(\sigma(z^T_u z_v)) - Q\cdot E_{v_n \sim P_n(v)} log(\sigma(-z_u^Tz_{v_n}))

其中，z_u和z_v表示节点u和v的 embedding 向量，v是u固定长度的邻居觉点，\sigma是 sigmoid 函数，P_n和Q分别表示负样本分布和数目。

对于聚合函数的，由于在图中节点的邻居是无序的，聚合函数应是对称的（改变输入节点的顺序，函数的输出结果不变），同时又具有较强的表示能力。主要有如下三大类的聚合函数：

Mean aggretator：将目标节点和其邻居节点的第 k-1 层向量拼接起来，然后对计算向量的 element-wis 均值，最后通过对均值向量做非线性变换得到目标节点邻居信息表示：

h_v^k \leftarrow \sigma(W \cdot MEAN(\{h_v^{k-1}\} \cup \{h_u^{k-1}, \forall u \in N(v)\}))

Pooling aggregator：先对目标节点的邻居节点向量做非线性变换并采用 pooling 操作（maxpooling 或 meanpooling）得到目标节点的邻居信息表示：

AGGREGATE_k^{pool} = max({\{ \sigma(W_{pool} h_{u_i}^k + b), \forall u_i \in N(v)\}})

LSTM aggretator：使用 LSTM 来 encode 邻居的特征，为了忽略邻居之间的顺序，需要将邻居节点顺序打乱之后输入到 LSTM 中。LSTM 相比简单的求平均和 Pooling 操作具有更强的表达能力。

五、总结

针对当前热门的 embedding 技术，本文系统的总结了能处理各类型数据的 embedding 方法，如传统基于矩阵分解的方法（如 SVD 分解）、处理文本的 embedding 方法（如 Word2vec、FastText 等）以及处理图数据的 embedding 方法（如 DeepWalk、GraphSAGE 等）。在推荐系统中，针对于不同数据类型，可以灵活采用上述方法来实现对数据的抽象表示。如可以基于用户行为，构造 item 列表，采用基于文本的方法对 item 进行向量化；也可以通过构建 user 和 item 关系图，采用基于图的方法来对 user 和 item 进行向量化。在实际过程中，不同的向量化方法得到的 embedding 结果也会有较大差异，需要根据具体业务需求来选择相应的算法。如要挖掘用户与用户的同质性，可以尝试采用 Node2vec；此外，如果需要结合物品或 Item 的 side-info，可以考虑 GraphSAGE 算法来对图中节点进行 embedding。跟深度学习炼丹术一样，要熟练掌握各类 embedding 技术，需要根据具体应用场景不断试错积累经验。最后，要司庆了，祝我们“炼丹人”能快乐搬砖！

参考文献

Simon Funk. Netflix Update: Try This at Home. http://www.sifter.org/~simon/journal/20061211.html. 2006

Koren, Yehuda. "Factorization meets the neighborhood: a multifaceted collaborative filtering model." Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 2008

Mikolov, Tomas, et al. "Distributed representations of words and phrases and their compositionality." Advances in neural information processing systems. 2013.

Pennington, Jeffrey, et al. "Glove: Global vectors for word representation." Conference on empirical methods in natural language processin. 2014.

Bojanowski, Piotr, et al. "Enriching word vectors with subword information." Transactions of the Association for Computational Linguistics 5 (2017): 135-146.

Peters, Matthew E., et al. "Deep contextualized word representations." arXiv preprint arXiv:1802.05365 (2018). Radford, Alec, et al. "Improving language understanding by generative pre-training." (2018): 12.

Devlin, Jacob, et al. "Bert: Pre-training of deep bidirectional transformers for language understanding." arXiv preprint arXiv:1810.04805 (2018).

Perozzi, Bryan, et al. "Deepwalk: Online learning of social representations." ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.

Grover, Aditya, et al. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.

Dong, Yuxiao, et al. "metapath2vec: Scalable representation learning for heterogeneous networks." Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017.

Wilson L Taylor. 1953. cloze procedure: A new tool for measuring readability. Journalism Bulletin, 30(4):415–433.

Hammond, David K., Pierre Vandergheynst, and R émi Gribonval. "Wavelets on graphs via spectral graph theory." Applied and Computational Harmonic Analysis 30.2 (2011): 129-150.

Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).

Hamilton, Will, et al. "Inductive representation learning on large graphs." Advances in neural information processing systems. 2017.

本文地址：https://www.6aiq.com/article/1605749293254
本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

更多内容请访问：IT源点

注意：本文归作者所有，未经作者允许，不得转载