推荐系统中 EMBEDDING 的应用实践

自 Embedding 的概念问世以来，Embedding 的探索和应用就没有停止过，Word2Vec、Sentence2Vec、Doc2Vec、Item2Vec，甚至 Everything2Vec。对，“万物皆可 Embedding”。几年来，Embedding 在推荐系统中的应用也越来越多，方式众多，技法新颖。

在之前的文章中，《文本内容分析算法》和 《基于矩阵分解的推荐算法》文中都稍有提及 Embedding 的概念，由于 Embedding 太过重要，本文我们将详细讲解 Embedding 的相关知识，以及在推荐系统中的一些应用，因篇幅限制，关于 Embedding 在推荐系统中的应用实践我分为了两篇文章来讲述，本篇主讲 Embedding 以及相关延伸方法，另外一篇是大厂的 Embedding 实践应用，是更加偏 tricks 的一些应用实践总结。

1.Embedding 的理解

Embedding，即嵌入，起先源自于 NLP 领域，称为词嵌入（word embedding），主要是利用背景信息构建词汇的分布式表示，最终可以可以得到一种词的向量化表达，即用一个抽象的稠密向量来表征一个词。

从数学角度看，Embedding 其实是一个映射（mapping），同时也是一个函数（function），即 $f: X \rightarrow Y$，该函数是 injective（就是我们所说的单射函数，每个 $Y$只有唯一的 $X$对应，反之亦然）和 structure-preserving（结构保存，比如在 X 所属的空间上 $X_1 < X_2$，那么映射后在 $Y$所属空间上同理 $Y_1 < Y_2$）的。那么对于 Word Embedding，就是将单词映射到另外一个空间，这个映射也具有 injective 和 structure-preserving 的特点。

“嵌入” 本身是一个数学概念。我们这里通俗理解，如果将词看作是文本的最小单元，词嵌入本身是一种特别的映射过程，即将文本空间中的某个词，通过一定的方法，映射或者说嵌入到另一个数值向量空间，原来的整数全部变为实数，是用连续向量表示离散变量的方法。之所以称之为 Embedding，是因为这种表示方法往往伴随着一种降维的意思，就像高维事物拍扁了嵌入到另一个低维空间中一样。

Embedding 这种向量化表达过程通常伴随以下变化：

• 高维——> 低维
• 稀疏——> 稠密
• 离散——> 连续
• 整数——> 实数

不难发现，经过 Embedding 向量化表达后的数据，其实变得更加适合深度神经网络的训练和学习，也有利于工业界数据的工程化处理。高维稀疏数据对于机器学习的参数学习和相关计算都不太友好（高维易引发 “维度之灾”，使空间距离很难有效衡量，另外高维经常使参数数量变得非常多，计算复杂度增加，也容易导致过拟合；稀疏容易造成梯度消失，导致无法有效完成参数学习），因此通常特别稀疏的高维离散数据更适合使用 Embedding 代替传统 One-Hot 编码方式。

此外，Embedding 虽然是一种降维表示，但是却携带了语义信息，而且这种表示方式并不局限于词，可以是句子、文档、物品、人等等，Embedding 能够很好地挖掘嵌入实体间的内部关联，即便降维也能保留这种潜在关系，这简直就是 “神来之笔”，怪不得说万物皆可 Embedding。

词嵌入的维度表示某个隐含语义，一个词可能隐藏很多语义信息，比如北京，可能包含 “首都、中国、北方、直辖市、大城市” 等等，这些语义在所有文本上是有限的，比如 128 个，于是每个词就用一个 128 维的向量表达，向量中各个维度上的值大小代表了词包含各个语义的多少。

本质上来说，经过 Word Embedding 之后，各个单词就组合成了一个相对低维空间上的一组向量，这些向量之间的远近关系则由他们之间的语义关系决定。

因为上面提到的特性，使用 Embedding 可带来诸多好处：

• 不丢失信息的情况下降低维度
• 矩阵及向量运行便于并行
• 向量空间具有物理意义，比如可以根据距离比较相似性
• 可以在多个不同的维度上具有相似性
• 线性规则：king – man = queen – woman

Embedding 的这种携带语义信息以及保留嵌入实体间的潜在关系的特性，使 Embedding 有了更多用武之地，例如：

• 计算相似度，比如 man 和 woman 的相似度比 man 和 apple 的相似度高
• 在一组单词中找出与众不同的一个，例如在如下词汇列表中：[dog, cat, chicken, boy]，利用词向量可以识别出 boy 和其他三个词不是一类。
• 直接进行词的运算，例如经典的：woman + king-man = queen
• 表征文本，如累加得到一个文本的稠密向量，或平均表征一个更大的主体；
• 方便聚类，会得到比使用词向量聚类更好的语义聚类效果。
• 由于携带了语义信息，还可以计算一段文字出现的可能性，也就是说，这段文字是否通顺。

上面的嵌入实体是单词，如果换成推荐物品（item），上面的一些用法，是不是让你眼前一亮呢？

2.Word2Vec

📚 Distributed Representations of Words and Phrases and their Compositionality

📚 word2vec Parameter Learning Explained

📚 word2vec Explained: deriving Mikolov et al.’s negative-sampling word-embedding method

词嵌入表示通常会用到谷歌提出的 Word2Vec 工具库，另外 fastText 和 TensorFlow 中也可以实现 Embedding 的功能。这个小节我们借助 Word2Vec 工具的模型实现来更加深入理解 Embedding。

2.1.Word2Vec 的原理

Word2Vec 是用浅层神经网络学习得到每个词的向量表达，而且在工程上进行了优化，使得百万词的规模在单机上可以几分钟轻松跑出来。它有两种网络结构，分别是 CBOW（Continues Bag of Words）和 Skip-gram，两种网络结构图见下图。

这两种结构都是假定每个词都跟其相邻的词的关系最密切，不同的是 CBOW 模型的动机是每个词都是由相邻的词决定的，所以 CBOW 的输入是 $w_t$ 周边的词，预测的输出是 $w_t $ ，而 Skip-gram 模型的动机则是每个词都决定了相邻的词，输入是 $w_t$ ，输出是 $w_t$ 周边的词。这里相邻的词通常由一个滑动窗口来获得，滑动窗口的长度为 2c+1（目标词前后各选 c 个词），从句子左边滑倒右边，每滑一次，窗口中的词就形成了我们的一个正样本。如上图，这里的 c 设为 2，其中 $w(t)$是当前所关注的词，$w(t−2)$、$w(t−1)$、$w(t+1)$、$w(t+2)$是上下文中出现的词。

经验上讲 Skip-gram 的效果要更好一点，我们以 Skip-gram 为例，理解一下原理。上面讲到通过滑动窗口可以获取到训练样本，有了训练样本之后我们就可以着手定义优化目标了，既然每个词 $p(w_{t+j}|w_t)$ 都决定了相邻词 $w_{t+j}$，基于极大似然，我们希望所有样本的条件概率 $p(w_{t+j}|w_t)$之积最大，于是有：

$$J^\prime (\theta) = \prod_{t=1}^T \prod_{-c\le j \le c,j \ne0} p(w_{t+j} \mid w_t ;\; \theta)$$

转为最大化对数似然：

$$J(\theta) = \sum_{t=1}^T \sum_{-c\le j \le c, j \ne0} \log p(w_{t+j} \mid w_t)$$

其中，T 是文本长度，即单词总数，c 是窗口大小，另外单词一般需要先用 One-Hot 编码。

其实从上面的图中可以看出，在实际训练学习过程中，训练样本是由中心词和其上下文词组成一个个 Pair 对，那我们可以将目标函数写成一个更容易理解的的式子：

$$\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log p(c|w)$$

其中，$(w, c)$表示中心词 $w$与其上下文词 $c$构成的样本对，$D$是语料中所有单词及其上下文词构成的样本对集合，这里的 $\theta$ 为待定参数集。

接下来的问题是怎么定义 $p(c|w)$ ，作为一个多分类问题，最简单最直接的方法当然是直接用 Softmax 函数，同时我们希望用隐向量来表示每个词。

于是设 $v_w$为中心词 w 的词向量，$v_c$为上下文词 c 向量，向量维度等于设置的隐藏层单元数量。整个语料共有 V 个单词，也就是词汇表单词数。

因此：

$$p(c \mid w; \theta) = \mathrm{Softmax} (v_w \cdot v_c) = \frac{\exp(v_w \cdot v_c)} {\sum_{i=1}^V \exp(v_w \cdot v_i)}$$

带入上面的目标函数，可以得到：

$$\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log p(c|w)=\sum_{(w, c) \in D}(\log e^{v_w \cdot v_c}-\log \sum_{i=1}^V e^{v_w \cdot v_i})$$

其中，参数 $\theta$是 $v_{w_i}$和 $v_{c_i}$，$i \in 1, \cdots, d$，$d$是向量维度。

这两个单词的隐向量的点积表示语义的接近程度，其实点积的物理意义就是词之间的距离，点积越大，表明两个单词的语义越接近，向量点积展开如下：

$$v_w \cdot v_c=v_w^Tv_c=v_w’v_c = \sum_{i=1}^d v_w^i \times v_c^i$$

（注：向量点积在不同的论文有不同的表示形式，本文为了推导后面的负例采样优化，写法与第三篇论文的写法保持一致。）

而 Softmax 的作用就是将点积转换成概率，下图的例子可以辅助理解¹：

2.2.Word2Vec 的网络结构

CBOW 和 Skip-gram 都可以表示成由输入层（Input）、映射层（Projection）和输出层（Output）组成的神经网络。

输入层中的每个词通常由独热编码（One-Hot）方式表示，即所有词均表示成一个 $V$维向量，其中 $V$为词汇表中单词的总数。在向量中，每个词都将与之对应的维度置为 1，其余维度的值均设为 0。

在映射层（也就是隐含层）中，$N$个隐含单元（Hidden Units）的取值可以由 $V$维输入向量以及连接输入和隐含单元之间的 $V×N$维权重矩阵 $W$计算得到。在 CBOW 中，还需要将各个输入词所计算出的隐含单元求和。需注意的是，Word2Vec 网络中的隐含层没有使用任何非线性激活函数，或者可以勉强说用的是线性激活函数（Linear Activation Function）。因为 Word2Vec 不是为了做语言模型，它不需要预测的更准，加入非线性激活函数没有什么实际意义，反而会降低 Word2Vec 的性能。

同理，输出层向量的值可以通过隐含层向量，以及连接隐含层和输出层之间的 $N\times V$ 维权重矩阵 $W’$计算得到。输出层也是一个 $V$维向量，每维与词汇表中的一个单词相对应。最后，对输出层向量应用 Softmax 激活函数，可以计算出每个单词的生成概率。

再之后，利用反向传播来训练神经网络的权重即可。

不过上图的网络结构是单个上下文的一个示例，即当前词预测下一个词，对于真正的多词上下文的 CBOW 和 Skip-gram，通常是下面的结构：

以 Skip-gram 模型为例，其前向公式为：

$$\begin{eqnarray*} \textbf{h} = & W^T\textbf{x} \hspace{9.4cm} \\ \textbf{u}_c= & W’^T\textbf{h}=W’^TW^T\textbf{x} \hspace{4cm} c=1, \dots, C \hspace{0.7cm}\\ \textbf{y}_c = & \ \ \mathbb{S}\textrm{oftmax}(\textbf{u})= \mathbb{S}\textrm{oftmax}(W’^TW^T\textbf{x}) \hspace{2cm} c=1, \dots, C \end{eqnarray*}$$

因为输出层共享权重 $W’$，所以 $\textbf{u}_c(c=1, \cdots, C)$都是一样的，输出向量 $\mathbf{y}_c(c=1, \cdots, C)$也是都一样的，即 $\mathbf{y}_1=\mathbf{y}_2\dots= \mathbf{y}_C$。

如果想更详细地了解 CBOW 和 Skip-gram 的原理、后向传播、示例讲解等，推荐查看🔗《The backpropagation algorithm for Word2Vec》 这篇文章。

CBOW 和 Skip-gram 的性能对比

两种模型都有各自的优缺点，不过根据 Mikolov 的原论文，Skip-gram 在处理少量数据时效果很好，可以很好地表示低频单词。而 CBOW 的学习速度更快，对高频单词有更好的表示。实际应用中，Skip-gram 方式会更常见。

2.3.从权重矩阵到词向量

那么，到底什么才是我们想得到的 Embedding 向量化表示呢？

其实就是上面的权重矩阵$W_{V \times N}$和 $W^\prime_{N \times V}$(对 Skip-gram 来说，分别对应损失函数公式中的中心词词向量 $u$和上下文词向量 $v$)，这两个都可以作为最终的向量化表示矩阵，只是一个靠近输入空间，一个靠近输出空间，具体选择哪个，理论上没有什么区别。不过我个人更倾向于选择靠近中心词一端的权重矩阵，比如 CBOW 选择 $W’_{N \times V}$，而 Skip-gram 选择 $W_{V \times N}$，在 Word2Vec 使用的 Skip-gram 就是选的 $W_{V \times N}$，另外有些时候还可以尝试用两个矩阵的平均或者两个矩阵对应词向量的拼接作为最终 Embedding。

参考下图，训练完成的权重矩阵，一个维度是单词对应的维度，一个维度是隐含单元的维度，换个角度来看，它刚好就是每个词对应一个隐含特征向量，这不就是我们需要的词向量吗？因此由权重矩阵便可自然转化成 Word2Vec 的词向量查找表（Lookup Table）。

2.4.Word2Vec 的优化方法

Word2Vec 的最原本的算法在工程实现上会带来很多问题，以 Skip-gram 为例：

• Softmax 函数中存在归一化项，因此需要对词汇表中的所有单词进行遍历，这会使得每次迭代过程非常缓慢；
• 一般情况下词汇表维度 $V$远大于词向量维度 $N$，也就是无论是输入层与隐藏层之间的权重 $W_{V \times N}$还是隐藏层与输出层的权重 $W’_{N \times V}$，他们权重的数量都是由 $V$来决定的，而通常词表维度又是一个很大的值，也就是说，这个看似很简单的网络结构中却有大量的权重需要更新。举个例子，假设有 10000 个单词的词汇表，词向量维度是 300，那么这两个权重矩阵的权重数量都是 $10,000 \times 300 = 3000,000$个，这么多的权重用梯度下降更新是非常慢的。
• 即便退一步讲，不考虑时间问题，因为权重数量越多就越容易过拟合，这时就需要大量的训练数据去调整权重以避免过拟合的发生，然而数据资源往往并没有那么容易获得。

因此，Word2Vec 为了提高效率，提出了很多工程技巧对原始算法进行了优化，其中比较重要的有两个：

层次 Softmax（Hierarchical Softmax， H-Softmax）

为了避免 Softmax 公式中对词汇表中所有单词遍历，Hierarchical Softmax 的思想是将原来 Softmax 进行拆解分层，将原 Softmax 的 N 分类问题转化成 logN 个二分类问题。

这个分层转化的过程借助了霍夫曼树（Huffman Tree），在网络结构中的作用是代替从隐藏层到输出 Softmax 层的映射，优化后，隐藏层到输出层的 Softmax 映射不是一下子完成的，而是沿着霍夫曼树一步步完成的，因此这种 Softmax 取名为”Hierarchical Softmax”。

我们先来回顾一下霍夫曼树的知识点。

霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近，通常会作为一种高效的编码方式。

霍夫曼树的建立：

　　　　输入：权值为 $(w_1,w_2,…w_n)$的 n 个节点

　　　　输出：对应的霍夫曼树

　　　　1）将 $(w_1,w_2,…w_n)$看做是有 n 棵树的森林，每个树仅有一个节点。

　　　　2）在森林中选择根节点权值最小的两棵树进行合并，得到一个新的树，这两颗树分布作为新树的左右子树。新树的根节点权重为左右子树的根节点权重之和。

　　　　3）将之前的根节点权值最小的两棵树从森林删除，并把新树加入森林。

　　　　4）重复步骤 2）和 3）直到森林里只有一棵树为止。

下面我们用一个具体的例子来说明霍夫曼树建立的过程：

我们有（a、b、c、d、e、f）共 6 个节点，节点的权值分布是（20、4、8、6、16、3）。首先是最小的 b 和 f 合并，得到的新树根节点权重是 7，此时森林里 5 棵树，根节点权重分别是 20、8、6、16、7。此时根节点权重最小的 6、7 合并，得到新子树，依次类推，最终得到下面的霍夫曼树。

那么霍夫曼树有什么好处呢？一般得到霍夫曼树后我们会对叶子节点进行霍夫曼编码，霍夫曼树的构建方式决定了权重高的叶子节点越靠近根节点，而权重低的叶子节点会远离根节点，这样我们的高权重节点编码值较短，而低权重值编码值较长。这保证的树的带权路径最短，也符合我们的信息论，即我们希望越常用的词拥有更短的编码。如何编码呢？一般对于一个霍夫曼树的节点（根节点除外），可以约定左子树编码为 0，右子树编码为 1。如上图，则可以得到 c 的编码是 00。

而在 word2vec 中，约定编码方式和上面的例子相反，即约定左子树编码为 1，右子树编码为 0，同时约定左子树的权重不小于右子树的权重。

那霍夫曼树如何完成从隐藏层到输出 Softmax 层映射呢？

由于我们把之前所有都要计算的从输出 Softmax 层的概率计算变成了一颗二叉霍夫曼树，那么我们的 Softmax 概率计算只需要沿着树形结构进行就可以了。如下图所示，我们可以沿着霍夫曼树从根节点一直走到我们的叶子节点的词 $w_2$。

这里使用霍夫曼树来代替隐藏层和输出层的神经元，霍夫曼树的叶子节点起到输出层神经元的作用，叶子节点的个数即为词汇表的小大， 而内部节点则起到隐藏层神经元的作用。

• 叶子节点：树的每一个叶子节点都代表一个单词，所以通常词频越高离根节点越近；

• 内部节点：每一个内部节点都代表一次逻辑回归的过程，可以规定沿着左子树走是负类（霍夫曼编码 1），沿着右子树走是正类（霍夫曼编码 0）。假设 $x_w$是当前内部节点的词向量，而 $\theta$ 则是需要学习的模型参数。对于 CBOW 模型，$x_w$ 初始化（根节点）为输入的词向量加和求平均后的向量，对于 Skip-gram 来说，就是 $x_w$ 的词向量。判别正类和负类的方法是使用 Sigmoid 函数：

  $$P(+)=\sigma(x_w^T \theta)=\frac{1}{1+e^{-x_w^T\theta}}$$

  $$P(-)=1-P(+)$$

最终输出哪个单词是由 logN 次逻辑回归过程决定的，回到基于 Hierarchical Softmax 的 word2vec 本身，我们的目标就是找到合适的所有节点的词向量和所有内部节点 $\theta$, 使训练样本达到最大似然。如此经过一系列推导便可得到目标函数：

$$L= \log \prod_{i=2}^{l_w}P(d_i^w|x_w, \theta_{i-1}^w) = \sum\limits_{i=2}^{l_w} ((1-d_i^w) \log [\sigma(x_w^T\theta_{i-1}^w)] + d_i^w \log[1-\sigma(x_w^T\theta_{i-1}^w)])$$

其中，从根节点到 $w$所在的叶子节点，包含的节点总数为 $l_w$, $w$在霍夫曼树中从根节点开始，经过的第 $i$个节点表示为 $p_i^w$，对应的霍夫曼编码为 $d_i^w \in \{0,1\}$，其中 $i =2,3,…,l_w$。而该节点对应的模型参数表示为 $\theta_i^w$, 其中 $i =1,2,…,l_w-1$，没有 $i =l_w$是因为模型参数仅仅针对于霍夫曼树的内部节点。

之后利用梯度下降来更新参数：每个单词 $x_w$ 的词向量和霍夫曼树每个内部结点的 $\theta$。

使用霍夫曼树有什么好处呢？首先，由于是二叉树，之前计算量为 $V$，现在变成了 $\log_2V$。第二，由于使用霍夫曼树是高频的词靠近树根，这样高频词需要更少的时间会被找到，这符合我们的贪心优化思想。可能存在的缺点是，如果训练样本里的中心词 $w$是一个很生僻的词，那么就得在霍夫曼树中辛苦的向下走很久了。²

负例采样（Negative Sampling，简称 NEG，也称负采样）

负例采样不再使用复杂的霍夫曼树，而是利用相对简单的随机负采样来大幅提高性能，并且在经过论证后发现，负例采样不但可以提高训练速度，还可以改善所得词向量的质量，因此，负例采样比层次 Softmax 使用率更高。

负例采样的思想其实和层次 Softmax 很类似，也是将 Softmax 多分类问题转化成多次二分类问题，使用二元逻辑回归可以让一个训练样本每次仅仅更新一小部分的权重，不同于原本每个训练样本更新所有的权重，这样大大减少了梯度下降过程中的计算量。

举例来讲，当我们用训练样本 (input word: "fox"，output word: "quick") 来训练我们的神经网络时，fox 和 quick 都是经过 One-Hot 编码的。如果我们的单词表（vocabulary）大小为 10000，在输出层，我们期望对应 quick 单词的那个神经元结点输出 1，其余 9999 个都应该输出 0。在这里，这 9999 个我们期望输出为 0 的神经元结点所对应的单词我们称为 “negative” word。当使用负例采样时，我们将随机选择一小部分的 negative words（比如选 5 个 negative words）来更新对应的权重。我们也会对我们的 “positive” word 进行权重更新（在我们上面的例子中，这个单词指的是 quick）。

对于 Skip-gram 的输入层与隐藏层之间 10000 x 300 的权重矩阵，使用负例采样仅需要更新 positive word 即 quick 的和其他 5 个 negative words 的结点对应的权重，共计 6 个神经元，相当于每次只更新 $6 \times 300 =1800$个权重，对于 3 百万的权重来说，相当于只计算了 0.06% 的权重，这样计算效率就大幅度提高。

当然，负例采样的具体过程和层次 Softmax 有很大区别。 它的技术点会涉及两个关键的地方，一个是如何进行负例采样，另外一个是如何进行二元逻辑回归。

先来看采样方法，其实采样方法并不是固定的，后来很多论文中虽然使用负例采样的优化方法类进行 Embedding，但是采样方法都是根据自己的业务来进行调整的，下面以原始论文中的采样方法作为参考。

Word2Vec 论文中给出的采样方式其实并不复杂，首先采样的数量根据数据集的大小而定，一个经验是对于小数据集，选择 5~20 个负例，而对于较大的数据集，则只需要 2~5 个负例就可以。另外，采样会遵循一定的分布，这里用的是一元模型分布 (unigram distribution)，它的特点是词频更高的词更有可能被选为负例，是一个加权采样。假设我们要将整个语料库的单词作为单词表，并且从单词表中进行随机负例采样，则选取某个词的概率等于该词出现在语料库次数（词频）除以语料库出现的单词总数，用公式表示为：

$$P(w_i) = \frac{ f(w_i) }{\sum_{j=0}^{n}\left( f(w_j) \right) }$$

其中，$f(\cdot)$可以理解为计数，即得到词频。

论文中指出，作者在这个公式上尝试了很多变化，最后表现比较好的是将单词词频提高到 3/4 次幂。如下：

$$P(w_i) = \frac{ {f(w_i)}^{3/4} }{\sum_{j=0}^{n}\left( {f(w_j)}^{3/4} \right) }$$

这个改变后的公式会产生一个效果，就是稍微增加低频词的采样概率，降低高频词的采样概率。可根据下图（google 的搜索栏中输入 “plot y = x^(3/4) and y = x” 可以快速画图）的对比看出来：

对高频词汇进行降采样避免对于这些低信息词汇的无谓计算，同时避免高频词汇对模型造成过大的影响，注意这是一个很重要的思想，很多时候对于推荐算法中样本，都是过滤掉高频用户，保证每个用户出现的样本数近似，防止高频用户的样本对模型的过大影响，这和 CF 里面的高频用户惩罚系数一样。

然后再来看二元逻辑回归的目标函数，论文中给出了 Skip-gram 模型负采样的优化目标函数为：

其中 $P_n(w)$就是采样用的概率分布。

原论文中并没有给出负例采样的推导过程，2014 年，Yoav Goldberg 在论文《word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method》里对上述目标函数给出了推导。

从本文前面的内容我们已知 Skip-gram 的最初的目标函数：

$$\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log p(c|w)=\sum_{(w, c) \in D}(\log e^{v_w \cdot v_c}-\log \sum_{i=1}^V e^{v_w \cdot v_i})$$

如果对上述目标函数进行优化，第二项需要对词典里的所有词进行优化，所以计算量比较大。如果换个角度考虑，如果我们将合理的上下文样本对看成是 1，不合理的上下文样本对看成是 0，那么问题转换为二分类问题，那么我们目标就是最大化下面的目标函数：

$$\begin{align} &\arg \underset{\theta}{\max} \prod_{(w, c) \in D} p(D=1 \mid w,c;\theta) \\ =&\arg \underset{\theta}{\max} \;\log \prod_{(w, c) \in D} p(D=1 \mid w,c;\theta) \\ =&\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log p(D=1 \mid w,c;\theta) \end {align}$$

使用 Softmax 来定义 $p(D=1 \mid w,c;\theta)$：

$$ p(D=1 \mid w,c;\theta)=\frac{1}{1+e^{-v_w \cdot v_c}}$$

带入目标函数：

$$\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log \frac{1}{1+e^{-v_w \cdot v_c}} $$

不过这个目标函数存在问题，如果 $v_w = v_c$ 且 $v_w \cdot v_c$足够大的话（论文中提到 $v_w \cdot v_c \approx 40$就能让概率接近 1），就能取到最大值，这时所有的词向量都是一样的，因此最终得到的 Embedding 向量也就没了意义。我们需要一种机制，通过不允许某些 $(w，c)$样本对的出现来防止所有向量具有相同的值。所以才考虑负例采样，加入负样本：

$$\begin{align} &\arg \underset{\theta}{\max} \prod_{(w, c) \in D} p(D=1 \mid w,c;\theta) \prod_{(w, c) \in D’} p(D=0 \mid w,c;\theta) \\ =&\arg \underset{\theta}{\max} \prod_{(w, c) \in D} p(D=1 \mid w,c;\theta) \prod_{(w, c) \in D’} (1-p(D=1 \mid w,c;\theta)) \\ =&\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log p(D=1 \mid w,c;\theta) \sum_{(w, c) \in D’} \log (1-p(D=1 \mid w,c;\theta)) \\ =&\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log \frac{1}{1+e^{-v_w \cdot v_c}} \sum_{(w, c) \in D’} \log (1-\frac{1}{1+e^{-v_w \cdot v_c}}) \\ =&\arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log \frac{1}{1+e^{-v_w \cdot v_c}} \sum_{(w, c) \in D’} \log \frac{1}{1+e^{v_w \cdot v_c}} \end {align}$$

其中，$D’$是所有随机采样的负样本对，我们令 $\sigma(x)=\frac{1}{1+e^{-x}}$，上式则可继续简化为：

$$ \arg \underset{\theta}{\max} \sum_{(w, c) \in D} \log \sigma (v_w \cdot v_c) \sum_{(w, c) \in D’} \log \sigma (-v_w \cdot v_c)$$

这个式子基本与 Mikolov 提出的一样。和 Hierarchical Softmax 类似，接下来采用随机梯度上升法，逐步完成参数更新。

2.5.Word2Vec 在推荐中的应用

Word2Vec 本身就是处理文本内容的一把 “利器”，因此它可以直接应用在基于内容的推荐算法中。内容推荐的一个常用方法是通过理解内容（挖掘内容属性）去挖掘用户的兴趣点来构建推荐模型，此时 Embedding 可以作为一个非常有效的方法来辅助理解内容，当然，这时的 Embedding 是依然是属于自然语言领域，也是它最本源的应用。

基于内容的推荐算法，从大多数业务的效果来看，这样的模型是有效的，也就是说用户行为与内容是相关的。不过有一点常被忽略的是：相关性是对称的！这意味着如果可以从内容属性去理解用户行为，预测用户行为，那么也可以通过理解用户行为去理解内容，预测内容属性。

3.Item2Vec

📚 Item2Vec: Neural Item Embedding for Collaborative Filtering

Embedding 是一种很好的思想或方法，不仅仅局限于自然语言处理领域，因为嵌入式表示有众多优势，因此很快有人就尝试把这种嵌入式表示的思想应用到推荐系统中。最常见的就是构建实体的嵌入式表示，使得多种实体的嵌入式表示存在于同一个隐含空间内， 进而可以计算两个实体之间的相似性。

与 Word2Vec 对应，这种方法被称为 Item2Vec，代表论文是微软研究人员在 2016 年发表《Item2Vec: Neural Item Embedding for Collaborative Filtering》。论文把 Word2vec 的 Skip-gram with Negative Sampling (SGNS)的算法思路迁移到基于物品的协同过滤 (Item-Based CF) 上，以物品的共现性作为自然语言中的上下文关系，构建神经网络学习出物品在隐空间的向量表示。

3.1.从 Word2Vec 到 Item2Vec

首先，我们知道 Word2Vec 在构建样本时，需要一个个句子构成的序列。那么在推荐场景的数据集中，如何构建这个序列，或者说如何生成训练样本？

在 Item2Vec 中，样本数据可以有两种看待方式：

1. 基于时序

   认为 item 之间存在强时序关系，即前面 item 对后面 item 的产生有很大的影响，那么可以把一段时间内连续发生的 item 序列看作是句子，序列中的 item 看作是句子中的词，这样与 Word2Vec 的训练数据的构造就没什么区别了，因此可以直接按照 Word2Vec 的方法进行 Embedding 训练。

   基于时序的示例比如视频网站的用户观看的视频序列，音乐网站用户听的歌曲序列。

2. 基于集合

   认为 item 之间存在非常弱的时序关系，或者因为某种原因，我们无法获得 item 的序列。那么这种情况只能放弃考虑 item 间的时空信息，转而使用 item 集合来取代序列。通常我们把用户的行为序列视为一个集合（当然还有其他集合构造方式），我们假定一个静态的环境，在这个环境中，共现在同一个集合的 item 就可以认为它们是相似的，然后视为正样本，不管它们是以什么样的顺序产生的，如果某两个 item 频繁共现，二者的 Embedding 则可能也很相似。很明显，这种利用集合共现性构建样本的方式与 Word2Vec 的输入样本还是不一样的，因此无法直接应用 Word2Vec 的算法，这就需要对 Word2Vec 的过程进行调整。另外还需要注意的是，上面的这种的假设是有局限性的，不一定适用于其它场景。

   基于集合的示例比如电商网站订单中的商品集合。

到这里，再回想一下 Embedding 的本质是什么？是不是觉得有了更深的理解，个人理解，Embedding 就是通过给定大量的关联信息，就比如上面的两种样本构建方式分别是给定上下文信息以及共现集合的关联信息， 然后通过最大似然估计的方式来计算这些关系发生概率最大时的参数，再借助于参数来赋予个体一种抽象的隐含属性并且对这些属性编码赋值的过程，到最后，这些编码过的隐含属性就能表征甚至替代这些个体，而且还保留了原始个体间的关联信息，其实这些关联信息就是通过给隐含属性编码的方式来体现的。

论文中讨论的样本构建方法是第二种，作者还提出了两种相应的调整方式：

1. 把 Word2Vec 的上下文窗口 (window size) 由定长的修改为变长的，窗口长度就是集合长度。其实也就是对整个 item 结合中的 item 进行两两组合构成正样本，此方法需要修改网络结构。
2. 不修改网络结构，而在训练神经网络时对物品集合做 shuffle 操作，变相地起到忽略序列带来对影响。

论文指出两种方法的实验效果基本一致。

Item2Vec 的论文使用的是第一种调整方法，即给定一个 iterm 集合，SGNS 的目标函数可以改为：

$$\frac{1}{K}\sum_{i=1}^{K}\sum_{j\neq i}^{K}\log p(w_j|w_i)$$

其中，K 是集合长度，因为摒弃了序列中 item 的时空关系，在原来的目标函数基础上，其实已经不存在时间窗口的概念了，或者说窗口长度就是集合长度，取而代之的是 item 集合中两两之间的条件概率。

在论文中，作者把中心词词向量$u_i$作为第 $i$个 item 的最终的向量表示，同时两个 item 的相似度是通过余弦相似度进行计算的。作者还指出，最终的词向量也可以选用上下文词向量 $v_i$，甚至可以是 $u_i$和 $v_i$的向量和 $u_i+v_i$或 $u_i$和 $v_i$的连接 $[u_i^Tv_i^T]^T$来表示，后两种表示方式有时候能够产生更好的向量化表示。

论文中将 Word2Vecs 模型从自然语言序列迁移到物品集合，丢失了时间和空间的序列信息，导致无法对用户行为程度建模（喜欢和购买是不同程度的行为，可以建模体现用户对不同 item 的喜欢程度高低）。好处是可以忽略用户－物品关系，即便获得的订单不包含用户信息，也可以生成物品集合。而论文的结论证明，在一些场景下序列信息的丢失是可忍受的。

最终论文的实验表明，使用 Item2Vec 对协同过滤中的 item 计算相应的向量化表示，在 item 的相似度计算上比起 SVD 方法要更加优越，也就是说 Item2Vec 方法得到的 item 的向量化表示能够很好地提取 item 间的相似度特征。从应用上说，Embedding 也非常便于用于相似 item 主动检索，Item2vec 甚至能够应用到错误标签的检测和纠正上，所以 Item2vec 具有很好的使用价值，这也使得 Embedding 在很多深度学习推荐系统模型中几乎成了 “标配”。

Item2Vec 与 MF 有什么区别？

首先，二者都应用了隐向量来表征实体特征，不同的是，传统的 MF 通常是 user-item 矩阵，而 Item2Vec 通过滑动窗口样本生成的方式构造出的则更像是 item-item 矩阵；另外，二者得到隐向量的方式也不同，MF 利用均方差损失，使预测得分与已有得分之间的误差尽可能地小，而 Item2Vec 则是利用空间信息并借助了最大似然估计的思想，使用对数损失，使上下文关系或者共现关系构造出的正样本的 item pair 出现的概率可能地大；此外训练 Item2Vec 的时候还要引入负样本，这也是与 MF 不同的地方。

对于二者在推荐效果上的差异，一个经验是传统 MF 推荐会让热门内容经常性排在前面，而 Item2vec 能更好的学到中频内容的相似性。Iterm2Vec 加上较短的时间窗口，相似推荐会比 MF 好很多。³

Embedding 的在推荐下局限性

在推荐算法中使用 Embedding 有个前提，item 数目必须很庞大，如果 item 很小，估计效果就很不理想。也就是说，如果推荐的候选集很小（比如是供应商，供应商一般不会很大），此方法可能会失效。⁴

3.2.端到端和非端到端的 Embedding

Embedding 的训练可以分为两种方法：端到端（End-to-End）和非端到端的训练。

端到端（嵌入层）

端到端的方法是将 Embedding 层作为神经网络的一部分，在进行 BP 更新每一层参数的时候同时更新 Embedding，这种方法的好处是让 Embedding 的训练成为一个有监督的方式，可以很好的与最终的目标产生联系，使得 Embedding 与最终目标处于同一意义空间。（端到端的方法可参考 TensorFlow 中的 tf.nn.embedding_lookup 方法。）

将 Embedding 层与整个深度学习网络整合后一同进行训练是理论上最优的选择，因为上层梯度可以直接反向传播到输入层，模型整体是自洽和统一的。但这样做的缺点同样显而易见的，由于 Embedding 层输入向量的维度甚大，Embedding 层的加入会拖慢整个神经网络的收敛速度。

这里可以做一个简单的计算。假设输入层维度是 $100,000$，Embedding 输出维度是 $32$，上层再加 5 层 32 维的全连接层，最后输出层维度是 $10$，那么输入层到 Embedding 层的参数数量是 $100,000 \times 32 = 3,200,000$，其余所有层的参数总数是 $(32 \times 32)\times 4+ 32 \times 10=4416$。那么 Embedding 层的权重总数占比是 $3,200,000 / (3,200,000 + 4416) = 99.86\%$。

也就是说 Embedding 层的权重占据了整个网络权重的绝大部分。那么训练过程可想而知，大部分的训练时间和计算开销都被 Embedding 层所占据。正因为这个原因，对于那些时间要求较为苛刻的场景，Embedding 最好采用非端到端，也就是预训练的方式完成。

当然，端到端的 Embedding 层在深度模型中还是非常常见的，由于高维稀疏特征向量天然不适合多层复杂神经网络的训练，因此如果使用深度学习模型处理高维稀疏特征向量，几乎都会在输入层到全连接层之间加入 Embedding 层完成高维稀疏特征向量到低维稠密特征向量的转换。

广义来说，Embedding 层的结构可以比较复杂，只要达到高维向量的降维目的就可以了，但一般为了节省训练时间，深度神经网络中的 Embedding 层往往是一个简单的高维向量向低维向量的直接映射，如下图：

用矩阵的形式表达 Embedding 层，本质上是求解一个 m（输入高维稀疏向量的维度）乘以 n（输出稠密向量的维度）维的权重矩阵的过程。如果输入向量是 One-Hot 特征向量的话，权重矩阵中的列向量即为相应维度 One-Hot 特征的 Embedding 向量。

推荐系统应用实践中，使用端到端训练 Embedding 典型的例子，一个是微软的 Deep Crossing 模型：

另外一个就是谷歌提出的著名的 Wide&Deep 模型（深度部分）：

非端到端（预训练）

也就是通过预训练获得 Embedding，上一小节讲到的 Word2Vec 方法，通过语料库切分后的一堆词构建样本进行训练，其目的很纯粹，就是为了得到词向量。在真正的任务中，训练词向量并不是最终目的，而是一个预处理过程，只是为了提高最终任务模型的性能且缩短训练时间。在做其他任务时，将训练集中的词替换成事先训练好的向量表示放到网络中，就是一个非端到端的过程。在推荐场景也是一样，由于 Embedding 层的训练开销巨大，因此在一些时间要求比较高的场景下，Embedding 的训练往往独立于深度学习网络进行，在得到稀疏特征的稠密表达之后，再与其他特征一起输入神经网络进行训练。

在自然语言中，非端到端很常见，因为学到一个好的的词向量表示，就能很好地挖掘出词之间的潜在关系，那么在其他语料训练集和自然语言任务中，也能很好地表征这些词的内在联系，预训练的方式得到的 Embedding 并不会对最终的任务和模型造成太大影响，但却能够提高效率节省时间，这也是预训练的一大好处。

但是在推荐场景下，根据不同目标构造出的序列不同，那么训练得到的 Embedding 挖掘出的关联信息也不同。所以，在推荐中要想用预训练的方式，必须保证 Embedding 的预训练和最终任务目标处于同一意义空间，否则就会造成预训练得到 Embedding 的意义和最终目标完全不一致。比如做召回阶段的深度模型的目标是衡量两个商品之间的相似性，但是 CTR 做的是预测用户点击商品的概率，初始化一个不相关的 Embedding 会给模型带来更大的负担，更慢地收敛。

因此在推荐场景下，如果对于训练时间要求并不高的场景下，用端到端的训练方式可以得到更理想的效果。

Word2Vec，Doc2Vec，Item2Vec 都是典型的非端到端的方法，另外需要注意一点，Embedding 的本质是建立高维向量到低维向量的映射，而 “映射” 的方法并不局限于神经网络，实质上可以是任何异构模型，这也是 Embedding 预训练的另一大优势，就是可以采用任何传统降维方法，机器学习模型，深度学习网络完成 Embedding 的生成。

比如主题模型 LDA 可以给出每一篇文章下主题的分布向量，也可以看作是学习出了文章的 Embedding：

在推荐系统应用实践中，FNN 也可以看做是一种采用 Embedding 预训练方法的模型：

FNN 利用了 FM 训练得到的物品向量，作为 Embedding 层的初始化权重，从而加快了整个网络的收敛速度。在实际工程中，直接采用 FM 的物品向量作为 Embedding 特征向量输入到后续深度学习网络也是可行的办法。

另外一种更加特别的例子，就是是 2013 年 Facebook 提出的著名的 GBDT+LR 的模型，其中 GBDT 的部分本质上也是完成了一次特征转换，可以看作是利用 GBDT 模型完成 Embedding 预训练之后，将 Embedding 输入单层神经网络进行 CTR 预估的过程。

2015 年以来，随着大量 Graph Embedding 技术的发展，Embedding 本身的表达能力进一步增强，而且能够将各类特征全部融合进 Embedding 之中，这使 Embedding 本身成为非常有价值的特征。这些特点都使 Embedding 预训练成为更被青睐的技术途径。

诚然，将 Embedding 过程与深度网络的训练过程割裂，必然会损失一定的信息，但训练过程的独立也带来了训练灵活性的提升。举例来说，由于物品或用户的 Embedding 天然是比较稳定的（因为用户的兴趣、物品的属性不可能在几天内发生巨大的变化），Embedding 的训练频率其实不需要很高，甚至可以降低到周的级别，但上层神经网络为了尽快抓住最新的正样本信息，往往需要高频训练甚至实时训练。使用不同的训练频率更新 Embedding 模型和神经网络模型，是训练开销和模型效果二者之间权衡后的最优方案。⁵

3.3.Embedding 质量的评估

虽然目前 Embedding 的应用已经十分火热，但对其评价问题，即衡量该 Embedding 训练得是好是坏，并没有非常完美的方案。实际上，评价其质量最好的方式就是以 Embedding 对于具体任务的实际收益（上线效果）为评价标准。但是若能找到一个合适的方案，可以在上线前对得到的 Embedding 进行评估，那将具有很大的意义。

我们这里分 Word Embedding 和 Item Embedding 来分别讨论二者的度量方案。

Word Embedding 有较多的比较成熟的度量方案，常用的有以下几种⁶：

1. Relatedness

   Relatedness:task(相似度评价指标，看看空间距离近的词，跟人的直觉是否一致) 目前大部分工作都是依赖 wordsim353 等词汇相似性数据集进行相关性度量，并以之作为评价 Word Embedding 质量的标准。这种评价方式对数据集的大小、领域等属性很敏感。Google 在 Word2Vec 中给出的评估方案就是这个。 示例如图：

   

2. Analogy

   Analogy:task 也就是著名 A – B = C – D 词汇类比任务（所谓的 analogy task，就是 Embedding 线性规则的体现，如 king – queen = man – woman）。

   示例如图：

   

3. Categorization Categorization 分类，看词在每个分类中的概率。

   示例如图：

   

4. 聚类算法 例如 kmeans 聚类，查看聚类分布效果 。若向量维度偏高，则对向量进行降维，并可视化。如使用 pca，t-sne 等降维可视化方法，包括 google 的 tensorboard 以及 Embedding Projector，python 的 matplotlib 等工具，从而得到词向量分布。

   示例如图：

   

Item Embedding 则基本上没有统一认可的方案，下面提供一些方案提供参考：

1. 一个常用的评估的办法就是采样看 Top N 的相似度，看是不是确实学习到了有意义的信息，下一节提到的阿里 EGES 论文中，用的就是这样的方法。
2. 从 item2vec 得到的词向量中随机抽出一部分进行人工判别可靠性。即人工判断各维度 item 与标签 item 的相关程度，判断是否合理，序列是否相关。
3. 也可以借鉴 Word Embedding 中聚类可视化的方法，抽样进行对比，查看效果如何。
4. 还有一种方案，就是用大量数据训练出一个相对新的类似于 wordsim353 标准的 item 类型的标准，之后进行相似度度量。但是实现难度主要在训练数据的质量和时效性方面，对于商品类还好，但对于新闻类这种更新率极快的 item 类型，时效性是很大问题。
5. 当然，也可通过观察实际效果来定，也可采用替换 Embedding 对应值为初始值来看预测效果是否有显著下降。

4.Graph Embedding

Word2Vec 通过序列（sequence）式的样本：句子，学习单词的真实含义。仿照 Word2Vec 思想而生的 Item2Vec 也通过商品的组合去生成商品的 Embedding，这里商品的组合也是序列式的，我们可以称他们为 “Sequence Embedding”。然而，在更多场景下，数据对象之间更多以图（网络）的结构呈现，这种结构生成 Embedding 的方法，我们称之为图嵌入（Graph Embedding）。例如下图，由淘宝用户行为数据生成的物品关系图（Item Graph）：

从上图的例子中，我们已经能触碰到一些 Graph Embedding 的本质。Graph Embedding 之所以能好于 “Sequence Embedding”，是因为 Graph Embedding 能够生成一些 “不存在” 的序列。例如，上图数据中没有这样的用户行为数据：B-E-F、D-E-C 等等。但是在物品关系图中，我们有机会生成这样的序列。

图结构比 Item2Vec 更能反映一些实际场景下的复杂关系网络，更能捕获 Items 间的高维相似性。如今 Graph Embedding 已经是推荐系统、计算广告领域非常流行的做法，并且在工业实践中也取得了非常不错的线上效果。

Graph Embedding 有很多类似的称呼，图（Graph）有时会称为网络（Network），因此，有些地方还会称把 Graph Embedding 称为网络表示学习（Network Representation Learning）。类似的，我们还会经常看到 Network Embedding、Node Embedding、Graph Representation 等等 ，这些名词可能在定义上会有差异，大部分时间，我们可以在特定场合将他们视为同义词。

Graph Embedding 的相关算法有很多，我们这里介绍几个关键的算法。

4.1.DeepWalk

📚 DeepWalk: Online Learning of Social Representations

训练 Embedding 的一个重要过程是构建含有关系的样本（我这里姑且称这种样本为关系样本），然后作为 Skip-gram 模型的输入，虽然从 “一维” 序列（sequence）变成了 “二维” 的图（graph），但训练 Embedding 的核心算法基本是没有变的，关于 Graph Embedding 的相关研究，很大一部分其实是研究如何更好地构建这种关系样本，其中包括如何更合理地构造图，如何更合理地从图中采样得到关系样本，从而能够在 Embedding 中更好地保留这些关系。DeepWalk 其实就是这样，它并没有在训练 Embedding 的模型上动手，因此只有输入更合理的关系样本数据，才能得到更好的 Embedding 向量化结果，这也是图结构存在的意义之一。既然模型没有变，那么模型要求的输入也和原来一样，我们自然也需要提供和序列采样出的类似的关系样本数据，只不过现在高了一个维度，于是整个样本构建的流程就变成了先按照业务关系构造图，然后从图采样到序列，再从序列采样到样本，才能作为 Embedding 训练模型的输入，如下图：

其中各个环节的采样和转化都关系到最终效果的好坏，这也是大家研究和优化的重点内容。

DeepWalk 是 2014 年提出的影响力较大的 Graph Embedding 方法，也是最基础的 Graph Embedding 方法，它重点解决的就是如何从图采样到序列，其主要思想是在由物品组成的图结构上进行随机游走（Random Walk），产生大量物品序列，然后将这些物品序列作为训练样本输入 word2vec 进行训练，得到物品的 Embedding。

上图中展示的是阿里在淘宝上的 DeepWalk 的过程，在传统 DeepWalk 的基础上，阿里的还应用了会话切分和加权边，具体过程如下⁷：

1. 图 a 展示了原始的用户行为序列，这里设置了一个时间窗口，只选择用户在该窗口内的行为，这样处理不但可以节省计算和存储开销，也符合一个用户的兴趣趋向于随时间迁移的实情。这种处理方法被称为是基于 session 的用户行为（session-based）。经验上，该时间窗口的区间是一个小时；
2. 图 b 基于这些用户行为序列构建了物品相关图，可以看出，物品 A，B 之间的边产生的原因就是因为用户 U1 先后购买了物品 A 和物品 B，所以产生了一条由 A 到 B 的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了；
3. 图 c 采用随机游走的方式随机选择起始点，重新产生物品序列；
4. 图 d 最终将这些物品序列输入 word2vec 模型，生成最终的物品 Embedding 向量。

随机游走是一种路径搜索算法，用来从图上获得一条随机的路径。从一个节点开始，随机沿着一条边正向或者反向寻找到它的邻居，以此类推，直到达到设置的路径长度。不难发现随机游走有两个关键步骤，第一，起始节点的选择；第二，下一跳节点的选择。

其中，起始节点的选择有两种常见做法：

1. 按照一定的规则（比如均匀抽样）随机从图中抽取一定数量的节点；
2. 以图中所有节点作为起始节点。

一般来说我们选择第 2 种方法，以使所有节点都被选取到。⁸

下一跳节点的选择，有很多方案，包括后面介绍的几种 Graph Embedding 算法，很多也是在下一跳的选择上进行优化研究，我们这里先列举几个简单的基础方法：

1. 对于无权图，无差别的从当前节点的邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。DeepWalk 论文中的就是用的这种纯粹的随机游走方法；

2. 对于有权图，下一跳节点的选择最简单的方法是按照边的权重随机选择，阿里的论文在讲述 DeepWalk 的时候，给出了一个非常简单的随机游走转移概率的公式，也就是到达节点 $v_i$后，下一步遍历 $v_i$的临接点 $v_j$的概率。

   如果物品的相关图是有向有权图，那么从节点 $v_i$跳转到节点 $v_j$的概率定义如下：

   $$P(v_j|v_i)=\begin{cases} \frac{M_{ij}}{\sum_{j^* \in N_{+}(v_i)}M_{ij^*}}, & v_j \in N_+(v_i)\\ 0, &e_{ij} \notin \varepsilon \end{cases}$$

   其中 $N_+(v_i)$是节点 $v_i$所有的出边集合，$M_{ij}$是节点 $v_i$到节点 $v_j$边的权重，$e_{ij} \notin \varepsilon$表示节点 $v_i$ 到 $v_j$没有边的情况。

   如果物品相关图是无向无权重图，那么跳转概率将是上面公式的一个特例，即权重 $M_{ij}$将为常数 1，且 $N_+(v_i)$应是节点 $v_i$所有 “边” 的集合，而不是所有 “出边” 的集合。

使用随机游走带来的好处：

• 并行化，随机游走是局部的，图的规模比较大的时候，可以同时在不同的顶点开始进行一定长度的随机游走，多个随机游走同时进行，可以减少采样的时间。

• 适应性，可以适应图的局部的变化。图的的演化通常是局部的点和边的变化，这样的变化只会对部分随机游走路径产生影响，因此在图演化的过程中不需要每一次都重新计算整个图的随机游走。

• 解释性，论文中提到，在图中通过随机游走得到序列的节点分布规律与 NLP 中句子序列在语料库中出现的词频规律有着类似的幂律分布特征，见下图。在自然语言里面，幂律分布特征可以理解为只有少量的单词出现频率非常高，而绝大部分的单词出现的频率较低，还可以理解为，在日常交流中，常用的词汇很少，而绝大部分的词汇并不常用，可以看出随机游走路径显然符合自然语言的特点，从某个角度说明随机游走采样生成序列的合理性。

  

DeepWalk 的算法流程：

参数更新过程：

4.2.LINE

📚 LINE: Large-scale Information Network Embedding

DeepWalk 之后，比较重要的工作是微软亚洲研究院在 2015 年发布的 LINE（Large-scale Information Network Embedding）。LINE 中定义了两种相似度来进一步深化 “节点关系”，使训练出的 Embedding 既保留局部网络结构信息又保留了一定的全局网络结构信息。

First-order proximity（一阶相似度）：用于描述图中成对顶点之间的局部相似度，形式化描述为若节点之间存在直连边，则边的权重即为两个顶点的相似度（权重可以是 0-1 这样的二进制表示，也可以是任意的非负数），若不存在直连边，则一阶相似度为 0。 如下图，节点 6 和 7 之间存在直连边，且边权较大，则认为两者相似且一阶相似度较高，而 5 和 6 之间不存在直连边，则两者间一阶相似度为 0。

Second-order proximity（二阶相似度）：网络中的很多相互关系其实不一定能够直接观察到，仅有一阶相似度并不能保留全局网络结构，因此作为补充，加入了二阶相似度。二阶相似度并不是通过直接观察到的连接来确定的，而是通过顶点的共享邻域结构来确定的。如下图，虽然节点 5 和 6 之间不存在直连边，但是他们有很多相同的相邻节点（1,2,3,4），这其实也可以表明 5 和 6 是相似的，二阶相似度就是用来描述这种关系的，拥有相似邻居的顶点往往彼此相似。其实二阶相似度也是符合自然的直觉的，例如，在社交网络中，拥有相同朋友的人往往有相似的兴趣，从而成为朋友；在单词共现网络中，总是与同一组词同时出现的词往往具有相似的含义。二阶相似度形式化定义为，令 $p_u =(w_{u,1},\cdots, w_{u,|V|})$表示顶点 $u$ 与所有其他顶点间的一阶相似度，则 $u$ 与 $v$ 的二阶相似度可以通过 $p_u$ 和 $p_v$ 的相似度表示。若 $u$与 $v$之间不存在相同的邻居顶点，则 2 阶相似度为 0。

相比 DeepWalk 纯粹随机游走的序列生成方式，LINE 可以应用于有向图、无向图以及边有权重的网络，并通过将一阶、二阶的邻近关系引入目标函数，能够使最终学出的 node embedding 的分布更为均衡平滑，避免 DeepWalk 容易使 node embedding 聚集的情况发生。下图是论文中的结果对比：

从图中可以看出，LINE 的效果最好，DeepWalk 对不同颜色的点分得也不错，但是图形中部很多点都挤在一块，而这些点都是出度很大的点，文章提了一句说对于这种点的处理 DeepWalk 会产生很大噪音，但没有详细对此分析。论文还指出，DeepWalk 利用随机游走去捕获邻近关系，更像是深度优先搜索 DFS；而 LINE 的方式更像是广度优先搜索 BFS，相对而言更合理。上图中的 GF 代表 graph factorization，这里不作介绍。⁹

4.3.Node2Vec

📚 node2vec: Scalable Feature Learning for Networks

在 DeepWalk 和 LINE 的基础之上，斯坦福大学在 2016 年发布了 Node2Vec。Node2Vec 是一种综合考虑 DFS 邻域和 BFS 邻域的 Graph Embedding 方法。简单来说，Node2Vec 可以看作是 DeepWalk 的一种扩展，是可以控制随机游走呈现 DFS 还是 BFS 的 DeepWalk，进而实现不同关系序列的均衡。

Node2Vec 把领域的采样看作是局部搜索的一种形式，通常分为两种极端采样策略：广度优先采样（Breadth-first Sampling，BFS）和深度优先采样（Depth-first Sampling，DFS），下图能够明显看出这两种采样方式的不同。

广度优先抽样 (BFS)：邻域被限制在起始节点的近邻节点上，与初始节点在同一社区内的节点更容易出现在一个路径里。在上图中，对于大小为 k=3 的领域采样，BFS 采样节点 s1、s2、s3。

深度优先抽样 (DFS)：邻域由在距离起始点越来越远的连续采样的节点组成，发现能力更强。在上图中，对于大小为 k=3 的邻域采样，DFS 采样节点 s4、s5、s6。

论文指出，通常在网络中存在着两种相似性，即同质性（homophily）和结构性（structural equivalence）。

同质性通常是那些高度互联且属于类似网络集群或社区的节点，同质性表示内容相似，它们 Embedding 应该也尽量近似。如上图中，节点 u 与其相连的节点 s1、s2、s3、s4 的 embedding 表达应该是接近的，这就是 “同质性“的体现。

结构性指的是在网络中具有类似结构作用的节点，结构性表示结构相似，它们的 Embedding 也应该尽量接近，需注意的是，结构相似并不强调连接性，即使节点在网络中可能相距很远，仍然可以具有相似的结构。如上图中节点 u 和节点 s6 都是各自局域网络的中心节点，结构上相似，其 Embedding 的表达也应该近似，这是 “结构性” 的体现。

论文发现，BFS 和 DFS 采样策略在产生反映上述两种对应关系的向量表示方面发挥着关键作用。DFS 擅长学习网络的同质性，BFS 擅长学习网络的结构性。

这个结论特别容易理解反了，具体该怎样理解呢？¹⁰

知乎网友：（個人理解）如果把上面的 Graph 的某一个作为 Root，然后画一个树状结构去搜索，BFS 和 DFS 就好理解了。

对于广度优先搜索（BFS）来说，其搜索往往是在当前节点（这里以节点 u 为例）的邻域进行的，特别是在 node2vec 中，由于存在所谓的 “返回概率”，所以即使从 u 搜索到了 s1，也有很大概率从 s1 再返回 u，所以 BFS 产生的序列往往是在 u 附近的节点间进行来回的震荡，这就相当于对 u 周围的网络结构进行了一次微观扫描（microscope view）。

那么这个微观扫描当然更容易得到微观结构的观察，所以 BFS 就更容易使 Embedding 结果更多反应网络的 “结构性”。这里我需要纠正一下大家对 “结构性” 的理解，正如上面所说的一样，这里的 “结构” 更多的指的是微观结构，而不是大范围内，甚至整个网络范围内的宏观结构，而是一阶、二阶范围内的微观结构。

再举个例子理解一下，比如对于节点 u 和节点 s9 这两个节点来说，节点 u 是局部网络的中心节点，节点 s9 是一个十分边缘的节点。那么在对这个网络进行多次 BFS 随机游走的过程中，节点 u 肯定会被多次遍历到，而且会与 s1-s4 等更多节点发生联系，而边缘节点 s9 无论从遍历次数，还是从邻接点的丰富程度来说都远不及节点 u，因此两者的 Embedding 自然区别很大。

如果用 DFS 进行遍历，由于遍历存在更大的不确定性，因此 s9 有更大的可能被包含在更多的序列中，并跟更多的节点发生联系，这就减弱了局部结构性的信息。类似于平滑了结构性的信息，自然是不如 BFS 更能反应 “微观结构” 了。

另一方面，为什么说 DFS 更能反应 “同质性” 呢？

这里还要对 “同质性” 也进行一个纠正，这里的 “同质性” 不是指一阶、二阶这类非常局限的同质性，而是在相对较广范围内的，能够发现一个社区、一个群、一个聚集类别的 “同质性”。要发现这类同质性，当然需要使用 DFS 进行更广范围内的探索。如果仅用 BFS 在微观范围内探索，如何发现一个社区的边界在哪里呢？

所以，DFS 相当于对网络结构进行了一次宏观扫描（macroscope view），只有在宏观的视角，才能发现大的集团、社区的聚集性，和集团内部节点的 “同质性”。

论文中最后通过实验的方式验证了 DFS 和 BFS 对于 “同质性” 和 “结构性” 的挖掘结果。颜色接近的节点代表其 Embedding 的相似性更强，节点也比较相似。

其中，上部分的参数 p = 1，q = 0.5，表现为更倾向于 DFS 的结果（详细控制公式和参数见下面内容），可以看到各聚类的内部节点相似，这是网络 “同质性” 的体现；而下部分参数 p = 1，q = 2，表现为更倾向于 BFS 的结果，结构类似节点的 Embedding 更为相似，这是 “结构性” 的体现。

同时，论文给出了一个可以控制广度优先或者深度优先的方法，进而进一步权衡控制同质性和结构性相似的 Embedding 关系的学习。

其实 DFS 还是 BFS，主要还是通过节点间的跳转概率来控制的，以下图为例，我们假设第一步是从 t 随机游走到 v 后，这时候我们要确定下一步的邻接节点。

形式化来讲，从节点 $v$跳转到下一个节点 $x$的概率为：

$$\pi_{vx}=\alpha_{pq}(t, x) \cdot \omega_{vx}$$

其中，$w_{vx}$是边 $vx$的权重，$\alpha_{pq}(t, x)$的定义如下：

$$\alpha_{pq}(t,x)=\begin{cases}\frac{1}{p} &{\rm if}\; d_{tx}=0 \\1 &{\rm if}\; d_{tx}=1 \\\frac{1}{q} &{\rm if}\; d_{tx}=2\end{cases}$$

其中，$d_{tx}$指的是节点 $t$到节点 $x$的距离，只有 0，1，2 三种取值。当 $d_{tx}=0$时，表示 $x$就是 $t$本身，相当于下一节点选择的是 $t$，即往回走的情况；当 $d_{tx}=1$，则表示 $x$和 $t$直接相连，比如下一节点选图中的 $x_1$，这种情况通常会将连接的三个结点构成一个三角形，如 $t、v、x_1$三个结点；当 $d_{tx}=2$时，则下一节点 $x$和 $t$不直接相连，比如当 $x$为图中的 $x_2$或者 $x_3$时。

上式利用参数 $p$和 $q$共同控制着随机游走的倾向性，来选择 BFS 还是 DFS，从而控制对结构性或同质性网络关系的学习。

参数 $p$被称为返回参数（return parameter），控制跳回到前序节点 $t$的概率，$p$越小，随机游走回退到节点 $t$的可能性越大，如果 $p< \min(q, 1)$，则更倾向于搜索局部周边的节点，则产生的序列与宽度优先搜索（BFS）类似，更加擅长学习到网络的结构性；相反，$p$越大，游走越不会访问到之前的节点，如果 $p>\max(q, 1)$，刚刚访问过的节点不太可能被重复访问，则更倾向于搜索更大范围，产生的序列与深度优先搜索（DFS）类似，更加擅长学习到网络的同质性。

参数 $q$被称为进出参数（in-out parameter），控制下一跳节点选择与 $t$不直接相连节点的概率，当 $q > 1$ 时，节点 $v$ 之后更倾向于访问前序节点 $t$ 的共同邻居，当前节点更可能在附近节点游走，产生的序列与宽度优先搜索（BFS）类似，更加擅长学习到网络的结构性；q < 1 时，节点 $v$ 之后，更不倾向访问前序节点 t 的邻居，则随机游走到远方节点的可能性越大，产生的序列与深度优先搜索 (DFS) 类似，更加擅长学习到网络的同质性。

上面这种随机游走策略和当前节点 $v$，前序节点 $t$相关，其实是二阶马尔科夫。

一般来说，我们会从每个点开始游走 5~10 次，步长则根据点的数量 N 游走 $\sqrt{N}$步。⁸

Node2Vec 的算法流程：

Node2Vec 所体现的网络的同质性和结构性在推荐系统中也是可以被很直观的解释的。同质性相同的物品很可能是同品类、同属性、或者经常被一同购买的物品，而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的物品。毫无疑问，二者在推荐系统中都是非常重要的特征表达。由于 Node2Vec 的这种灵活性，以及发掘不同特征的能力，甚至可以把不同 Node2Vec 生成的 Embedding 融合共同输入后续深度学习网络，以保留物品的不同特征信息。

4.4.EGES

📚 Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

Graph Embedding 能够保留一些 CF 忽略了的复杂的高阶相似网络关系，但是它有一个致命的弱点，就是 “冷启动” 问题。如果单纯使用用户行为生成的物品相关图，固然可以生成物品的 Embedding，但是如果遇到新加入的物品，或者没有过多互动信息的长尾物品，推荐系统将出现严重的冷启动问题。为了使 “冷启动” 的商品获得 “合理” 的初始 Embedding，阿里团队通过引入了更多补充信息来丰富 Embedding 信息的来源，从而使没有历史行为记录的商品获得 Embedding。

这便是 2018 年阿里公布的其在淘宝应用的 Embedding 方法 EGES（Enhanced Graph Embedding with Side Information），其基本思想是在 DeepWalk 生成的 Graph Embedding 基础上引入 Side Information。

Side Information，可以简单理解为用户或物品的相关属性信息，我们通常会称之为用户侧信息、物品侧信息。

在推荐系统中常用的特征源有：用户对物品的历史行为交互信息、发生交互的上下文环境信息、用户侧或者物品侧的属性信息、通过属性信息连接的拓扑结构延伸出的知识图谱信息。

接下来我们简单分析一下这种方法背后的思想是什么。

生成 Graph Embedding 的第一步是生成物品关系图，我们通常只是通过用户行为序列来生成物品关系图。其实我们也可以通过物品侧信息（Side Information）的相似性来建立物品之间的边，比如利用相同品牌、相同类别等信息，这样就可以生成基于内容物品关系图，有了这个物品关系图，自然可以在没有用户行为的情况下也能够学习到 Embedding，也一定程度上缓解了冷启动问题。

基于这种物品侧属性信息生成的物品 Embedding 向量可以被称为 Side Information Embedding 向量，当然，根据使用的物品侧信息类别的不同，可以有多个 Side Information Embedding 向量⁷。比如对于淘宝的商品，这些 Side Information 可以是类目、店铺、价格、品牌等等，其实就是物品在某一个方面的属性内容信息，叫 Side Information 确实也形象，Side Information 通常在排序阶段被广泛用作关键特征，但在召回阶段应用较少。

GES 和 EGES 模型

通过随机游走，我们可以得到 item 的游走序列，包括了之前有行为的 item 以及新加入的 item，每个 item 都对应一组 Side Information，也就意味着我们同时得到了 Side Information 序列，此时需要将 item 和 Side Information 一起加入 Skip-gram 模型进行训练学习，否则不在一个向量空间，做运算无意义。

因此，对于每个 item，最后除了会得到它对应的 item Embedding，还有有各个 Side Information 产生的 Embedding，那么如何融合一个物品的多个 Embedding 向量，使之形成物品最后的 Embedding 呢？最简单的方法是在深度神经网络中加入 average pooling 层将不同 Embedding 平均起来，用公式表示为：

$$H_v = \frac{1}{n+1} \sum_{s=0}^nW_v^s$$

其中，$H_v$是 item v 的聚合 Embedding，我们使用 $W$来表示 items 或者 Side Information 的 Embedding Matrix。特别的，$W_v^0$ 表示 item v 的 Embedding，$W_v^S$表示绑定到 item v 上的第 s 个类型的 Side Information 的 Embedding。因此，对于 item v，使用 n 种类型的 Side Information，我们将有 n+1 个向量 $w_v^0, …, W_v^n \in R^d$，d 是 Embedding 的维度。注意，item Embeddings 和 Side Information Embeddings 的维度，经验上设置为相同的值。

在论文中上述方法称为 GES（Graph Embedding With Side Information），通过这种简单的方法将 Side Information 加了进来，从而使具有相近 Side Information 的 item 可以在 Embedding 空间内更接近。这会使冷启动 item 的 Embedding 表征更加精准，同时因为内容属性的加入，丰富了向量表达，进一步提升了在线和离线的效果。

阿里团队在上述方法的基础上，将平均进一步改为加权平均的方式，也就是最终的 EGES（增强型的 EGS，Enhance Graph Embedding With Side Information）方法，这样的改动也更加符合实际情况，因为不同类型的 Side Information 对最终的 Embedding 的贡献是不可能相等的。例如，一个购买了 IPhone 的用户，趋向于会浏览 Macbook 或者 Ipad，因为品牌都是”Apple”；而一个购买了多个不同品牌衣服的用户，出于便利和更低价格，还会在相同的淘宝店上继续购买。因此，不同类型的 Side Information 对于在用户行为中的共现 item 的贡献各不相同。

EGES 使用了一个加权平均层（weighted average layer）来结合不同的 Side Information，定义如下：

$$H_v = \frac{\sum_{j=0}^{n} e^{a_v^j} W_v^j} {\sum_{j=0}^n e^{a_v^j}}$$

其中，设 v 是给定的一个 item，$A \in R^{\mid V \mid \times (n+1)}$是权重矩阵（weight matrix），$A_{ij}$是第 $i$个 item、第 $j$个类型 Side Information 的权重。注意，$A_{*0}$，即 A 的首列，表示 item v 的自身权限。出于简洁性，我们使用 $a_v^s$来表示关于第 v 个 item 的第 s 个类型的 Side Information 的权重，$a_v^0$表示 item v 自身的权重。另外我们使用 $e^{a_v^j}$来替代 $a_v^j$，一是为了确保每个 Side Information 的贡献（权重）都大于 0，二是因为 $e^{a^j}$在梯度下降过程中有良好的数学性质。分母 $\sum_{j=0}^n e^{a_v^j}$被用于归一化不同类型 Side Information 的 Embeddings 的相关权重。

EGES 的流程如下图：

该模型将传统 Skip-gram 模型进行了改进，加入 Side Information 以及加权平均层，成为 Weighted Skip-gram 模型，其中：

1. SI 表示 Side Information，SI 0 表示 item 本身，剩下的 SI 1 ~ SI n 表示 item 对应的几种 Side Information；
2. Sparse Features 代表 item 和 Side Information 的 ID 信息，通常用 One-Hot 编码表示；
3. Dense Embeddings 表示 item 和 Side Information 的 Embedding 信息，并在 Hidden Representation 处进行加权平均聚合；
4. Sampled Softmax Classifier 表示使用负例采样的优化方式，N 代表采样的负样本，P 代表正样本（某个 item 周边上下 n 个 item 均为正样本，在模型中表示时不区分远近）。

EGES 的算法流程：

Side Information 带来的好处

1. 提升 Embedding 的表征力度

   Side Information 加入 Embedding 的训练，除了用到原本用户的行为信息，又加入了物品的内容属性信息，这样可以极大丰富 item Embedding 的表征力度，因为用户的偏好跟这些物品内容属性也可能有很大的关联。

2. 为解决 item 冷启动提供了便利

   新的 item 是没有用户交互信息的，因此也就无法训练 Embedding，没有 Embedding 也就无法有效推荐新物品，这是一个很棘手的问题。不过这个新 item 会有品牌、店铺、价格、类目等一系列内容属性信息，即 Side Information，Side information 都是有现成的训练好的 Embedding。因此，可以借用 Side Information 训练好的 Embedding 来解决 item 的冷启动问题，通常的做法是，根据 item 内容属性所关联的 Side Information，将这些 Side Information 对应的 Embedding 计算向量平均值，作为冷启动 item 的 Embedding 向量。

   下图是论文在获取到冷启动 item 的 Embedding 后，比较了与冷启动 item 的 Embedding 最相似的 Top 4 个物品，用来评估 Embedding 的质量。从结论来看，相似的 Embedding 确实有很多相似的 Side Information，这种冷启动方法效果还不错。

5.总结

文本首先深入介绍 Embedding 的相关内容，然后介绍了 Embedding 在推荐系统中几种常见的应用方法，其中，Word2Vec 可以直接作为文本解析工具来辅助完成一些基于内容的推荐，而 Item2Vec 则是 Word2Vec 在推荐系统领域的一个转化，也是最基本最常见的 Embedding 应用，Item2Vec 借助基于物品的协同过滤，得到 item 的向量化表征，从而使 item 方便获得更深层次的关联信息。最后，我们介绍了当下流行的 Graph Embedding，Graph Embedding 比 Item2Vec 能够获得更加高阶的相似和关联信息，其中 DeepWalk 使用随机游走的方式从 Graph 中获取到序列，LINE 方法则提出两种不同的相似度概念，并提出 BFS 和 DFS 的一些区别，Node2Vec 则进一步提出一种控制方案，可以通过控制游走方式呈现 BFS 还是 DFS 来平衡学习 “同质性” 和 “结构性” 的相似关系，最后我们介绍了阿里的 EGES，该方法引入了 Side Information 来缓解物品的冷启动，也通过加权平均将多种 Side Information Embedding 聚合成最终的 Embedding，使得最后的 Embedding 除了保留了用户行为序列中物品的共现性，还加入了 Side Information 中的内容关联信息，使得 item 的 Embedding 表征更加丰富。

6.参考资料