【Embedding】Word2Vec：词嵌入的一枚银弹

1.Introduction

Word2Vec 是 Google 在 2013 年开源的一个词向量（Word Embedding）计算工具，其用来解决单词的分布编码问题，因其简单高效引起了工业界和学术界极大的关注。

我们先尝试着回答几个问题，以检测下自己对 Word2Vec 的理解。

Word2Vec 两个算法模型的原理是什么，网络结构怎么画？
网络输入输出是什么？隐藏层的激活函数是什么？输出层的激活函数是什么？
目标函数/损失函数是什么？
Word2Vec 如何获取词向量？
Word2Vec 的两个模型哪个效果好哪个速度快？为什么？
推导一下参数如何更新？
Word2Vec 加速训练的方法有哪些？
介绍下 Hierarchical Softmax 的计算过程，怎么把 Huffman 放到网络中的？参数是如何更新的？对词频低的和词频高的单词有什么影响？为什么？
介绍下 Negative Sampling，对词频低的和词频高的单词有什么影响？为什么？
Word2Vec 有哪些参数，有没有什么调参的建议？
Word2Vec 有哪些局限性？

注：由于本文公式比较多不适合 Wrod2Vec 入门。

2.Word Embedding

在聊 Word2Vec 之前，我们先来了解一下词向量，我们都知道字符变量在送到神经网络训练之前需要将其编码成数值变量，常见的编码方式有两种：

One-Hot 编码：以字符变量的种类为向量长度，向量中仅一个元素为 1 其它均为 0，这种编码方式的缺点是数据稀疏，不适合作为神经网络的输入（参数更新慢，收敛速度慢，计算量大），且无法捕捉到词与词之间的关系（相互正交）；
分布编码：将字符变量映射到固定长度的向量中，向量空间中的点可以表示某个字符变量，且字符间的距离有意义。理想状况下，两个对象越相似其在空间中的距离就越近。

举个简单的例子，使用 One-Hot 编码时男=[1, 0]，女=[0,1]，而使用分布编码时，男=1, 女=0。我们可以看到分布编码占用的空间比 One-Hot 要小。

今天要聊的 Word2Vec 是一种典型的分布编码方式，通过训练浅层神经网络获得词向量。

3.Structure

Word2Vec 有两种网络结构：CBOW 和 Skip-Gram，其结构如下图所示：

model architectures

CBOW 是用上下文预测当前单词，Skip-gram 是用当前词预测上下文，两种网络都可以概括为如下网络：

simple model architectures

其中，网络的输入是 One-Hot 向量

w_k=(x_1,x_2...x_k...x_V)

，隐藏层无激活函数，输出层有 Softmax 函数，输出的是概率分布，预测目标也为 One-Hot 向量

w_j=(x_1,x_2...x_j...x_V)

。层与层之间采用全连接方式，并用反向传播训练网络。

输入层到隐藏层的映射矩阵为

W_{V times N}

，隐藏层到输出层的映射矩阵为

W_{N times V}^{'}

，也就是说对于任意的单词

w_k

我们都可以有两种表示向量：

v_{w_j} = X_k W^T quad v_{w_j}^{'} = X_k W^{'}

其中，

X_k

为单词 k 的 One-Hot 编码，大小为 (1, N)。这个操作的本质是把 W 的第 k 行复制给 v。举个例子：

matrix multiplicate

为方便起见，我们将

v_{w_j}

成为输入向量，将

v_{w_j}^{'}

成为输出向量。

输出层的计算方式采用 Softmax：

p(w_j|w_k) = frac{exp({v_{w_j}^{'}}^Tv_{w_k})}{sum_{i=1}^V exp({v_{w_i}^{'}}^Tv_{w_k})}

我们目的是想让

y_j

的第 j 个位置的值越大越好，其他位置的值越小越好。

max ; p(w_j|w_k) = max ; log(p(w_j|w_k)) \ ={v_{w_j}^{'}}^Tv_{w_k} - log(sum_{i=1}^V exp({v_{w_i}^{'}}^Tv_{w_k})) := -E

所以损失函数为：

E=-log(p(w_j|w_k))

。

我们利用反向传播来更新参数，首先输出向量求偏导：

frac{partial E}{partial w_{i,j}^{'}} = frac{partial E}{partial u_{j}^{'}} frac{partial u_{j}^{'}}{partial w_{i,j}^{'}} =(y_j-p_j) cdot h_i \

其中：

u_{j}^{'} = {v_{w_j}^{'}}^Tv_{w_j}

，

y_j

为 One-Hot 向量第 j 个位置的值，

p_j

为预测的向量中第 j 个位置的值。

输出向量的参数更新为：

{w_{ij}^{'}}^{(new)} = {w_{ij}^{'}}^{(old)} - eta cdot (y_j-p_j) cdot h_i \

值得注意的是，这个更新方程意味着我们需要遍历所有的单词（计算损失函数）。

输入向量的参数更新为：

frac{partial E}{partial w_{ki}} = frac{partial E}{partial h_i} frac{partial h_i}{partial w_{ki}} = sum_{j=1}^{V}(y_j-p_j) cdot w_{ij}^{'} cdot x_k

其中，

h_i = sum_{k=1}^{V} x_k cdot w_{ki}

，

x_k

为输入的词向量中第 k 维的数值。

则输入向量的参数更新为：

{w_{ki}}^{(new)} = {w_{ki}}^{(old)} - eta cdot sum_{j=1}^{V}(y_j-p_j) cdot w_{ij}^{'} cdot x_k \

了解到网络的基本结构和训练方法后，我们一起来看下 Word2vec 两种特殊的网络结构。

3.1 CBOW

CBOW 的全称为 Continuous Bag-of-Word Model，通过单词的上下文来预测当前当前单词。在计算隐藏层的输出时，CBOW 并没有直接使用上下文单词的输入向量，而是将其相加并取其均值（质心），即：

h_i = frac{1}{C}(v_{w_1} v_{w_2} ... v_{w_C}) \

多个词预测一个词，所以损失函数为：

E=-log(p(w_j|w_{k,1},w_{k,2},...,w_{k,C})) \= -{v_{w_j}^{'}}^T h_i log(sum_{i=1}^V exp({v_{w_i}^{'}}^Tv_{w_k})) \

下图为 CBOW 的网络结构，

CBOW

3.2 Skip-Gram

Skip-Gram 的结构如下图所示，正好与 CBOW 结构相反。与上面的模型相比，其输出的不再是一个多项式分布，而是 C 个多项式分布（要预测 C 个单词），所以：

u_{c,j} = u_j = {v_{w_j}^{'}}^Tv_{w_j} quad c=1,2,...,C

因为预测数量增多，所以损失函数改为：

E=-log(p(w_{1,j},w_{2,j},...,w_{C,j}|w_k)) \ = -log prod_{c=i}^C frac{exp({v_{w_c}^{'}}^Tv_{w_k})}{sum_{i=1}^V exp({v_{w_i}^{'}}^Tv_{w_k})}

Skip-Gram

到目前为止，我们便介绍完了基本 Word2Vec 模型，但这种最原始的模型没法应用于大规模训练，所以我们还需要对模型进行改进。

4.Optimization

为了更新输出向量的参数，我们需要先计算误差，然后通过反向传播更新参数。在计算误差是我们需要遍历词向量的所有维度，这相当于遍历了一遍单词表，碰到大型语料库时计算代价非常昂贵。要解决这个问题，有三种方式：

Hierarchical Softmax：通过 Hierarchical Softmax 将复杂度从 O(n) 降为 O(log n)；
Sub-Sampling Frequent Words：通过采样函数一定概率过滤高频单词；
Negative Sampling：直接通过采样的方式减少负样本。

4.1 Hierarchical Softmax

Hierarchical Softmax 是一种非常高效的训练方法，模型使用 Huffman 二叉树的叶节点来表示语料库的所有单词。以下图为例，黑色为内部节点，白色的为叶子节点表示一个单词

w_i

，每一个叶子节点都存在唯一的路径通往根节点，高亮部分为节点

w_2

通向根节点的路径，

L(w_2) = 4

，我们可以用这条路径来评估单词出现的概率。

Hierarchical Softmax

在 Hierarchical Softmax 模型中，叶子结点（单词）没有输出向量，但每一个内部节点都有一个输出向量

v_{n_{w,i}}^{'}

，单词作为输出的概率可以表示为：

p(w | w_k) = prod_{i=1}^{L_(w)-1} sigma big[ rho[n(w,i 1) =ch(n(w,j)] cdot {v_{n(w,i)}^{'}}^T v_{w_k}) big] \

其中

ch(n)

为节点 n 的左子式（Work2Vec 使用的是 Huffman 树，必有左子式），

n(w,i)

表示根节点到单词 w 的第 i 个单元，

v_{n(w,i)}^{'}

是内部节点

n(w,i)

的向量表示，h 是隐藏层的输出值，

sigma(cdot)

为 Sigmoid 函数，

rho[cdot]

有如下定义：

rho[x] = left{ begin{aligned} 1 quad if x is true \ -1 quad if x is false end{aligned} right. \

以上图为例，假设我们需要计算

w_2

的输出概率，等同于从根节点到叶节点做随机游走的概率。我们定义内部节点 n 左移和右移的概率：

p(n,left) = sigma({v_n^{'}}^T cdot v_k) \ p(n,right) = 1 - sigma({v_n^{'}}^T cdot v_k) = sigma(-{v_n^{'}}^T cdot v_k)\

根据

w_2

的路径我们有：

begin{aligned} p(w_2 | w_k) &= p(n(w_2, 1), left) cdot p(n(w_2, 2), left) cdot p(n(w_2, 3), right) \ &= sigma({v_{n(w_2,1)}^{'}}^T cdot v_k) cdot sigma({v_{n_(w_2,2)}^{'}}^T cdot v_k)cdot sigma(-{v_{n_(w_2,3)}^{'}}^T cdot v_k) end{aligned} \

不难得到：

sum_{i=1}^V p(w_i | w_k) = 1 \

现在我们来看一下内部节点的参数

v_{n(w_j,i)}

是如何更新的。我们以单个输入输出的简单模型为例：

E = -log(p(w | w_k)) = - sum_{i=1}^{L(w)-1} logbig[ sigma(rho cdot {v_{n(w,i)}^{'}}^T v_{w_k}) big ]

对

{v_{n(w,i)}^{'}}^T v_{w_k}

求偏导：

begin{aligned} frac{partial E}{partial{{v_{n(w,i)}^{'}}^T v_{w_k}}} &= big [ sigma( rho cdot {v_{n(w,i)}^{'}}^T v_{w_k}) big]rho \ &= left{ begin{aligned} sigma({v_{n(w,i)}^{'}}^T v_{w_k}) -1quad if rho =1 \ sigma({v_{n(w,i)}^{'}}^T v_{w_k}) quad if rho = -1 end{aligned} right. \ &= sigma({v_{n(w,i)}^{'}}^T v_{w_k}) - t_{n(w,i)} end{aligned}

其中，当

rho= 1

时

t_{n(w,i)}=1

，当

rho= 0

时

t_{n(w,i)}=0

。

我们再对内部节点向量

v_{n(w,i)}^{'}

求偏导：

frac{partial E}{partial v_{n(w,i)}^{'}} = frac{partial E}{partial{{v_{n(w,i)}^{'}}^T v_{w_k}}} cdot frac{ partial{{v_{n(w,i)}^{'}}^T v_{w_k}}}{partial {v_{n(w,i)}^{'}}} =big( sigma({v_{n(w,i)}^{'}}^T v_{w_k}) - t_{n(w,i)} big) v_{w_k} \

所以内部节点向量的更新公式为：

{v_{n(w,i)}^{'}}^{(new)} = {v_{n(w,i)}^{'}}^{(old)} - eta big( sigma({v_{n(w,i)}^{'}}^T v_{w_k}) - t_{n(w,i)} big) v_{w_k}

我们可以把

sigma({v_{n(w,i)}^{'}}^T v_{w_k}) - t_{n(w,i)}

理解为内部节点路径的预测误差，在实际的训练过程中，这个误差会非常小。

在实际的应用中， Huffman 树将代替原本的隐藏层到输出层的结构。

4.2 Sub-Sampling

在训练样本中，类似 “the”、“a”、“an” 之类的停用词非常多，重复训练这些停用词没有多大意义，Word2Vec 通过实现 Sub-sampling 以一定概率舍弃单词。

我们先感受一下使用 Sub-Sampling 能够减少多少计算量：设窗口大小为 10，如果舍去停用词 “the” 可以减少 10 个训练样本，且这个 “the” 也不会出现在其他词的上下文中。通常来说，Sub-sampling 能够带来 2～10 倍的性能提升。

我们来看一下 Word2Vec 使用的概率函数：

P(w_i) = (sqrt{frac{f(w_i)}{Sample}} 1) frac{Sample}{f(w_i)} \

其中，

z(w_i)

表示

w_i

在语料库中出现的频率，Sample 可以用来控制采样，默认为 0.001，值越小保留的概率越低。下图为采样函数：

Subsample Function

横坐标表示单词的频率，因为语料库比较大，频率一般会很低，所以我们关注 x 轴的前半部分。可以看到单词的保留概率与单词的频率成反比，正好可以过滤掉那些停用词。

4.3 Negative Sampling

Negative Sampling 的思想是以一定概率的选取负样本，使得每次迭代时只需修改一小部分参数，这是典型 Categorical Distribution Sampling 分布问题——给定一些变量及其概率，随机采样使得其满足变量出现的概率。

先来定量的感受下负采样节省的计算量：假设有 1W 个单词，300 个隐藏单元，则输出向量的大小为 (300, 10000)，现在我们通过负采样选取了 5 个负例，加上原本的 1 个正例共 6 个输出神经元，此时只需要更新 300 * 6 个参数，相当于原来的 0.06%。另外，对于输入向量来说，无论是否使用负采样，其更新权重数量都不会改变。

^{[2]}

再来看一下 Word2Vec 使用的负采样函数：

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

其中，

f(w_i)

表示

w_i

在语料库中出现的频率； 3/4 是经验所得。

我们知道了负采样函数，那么采样过程具体是怎么实现的呢？是类似于 Sub-Sampling Frequent Words，对每一个单词都进行一个判断吗？那样时间复杂度又回到了原来的 O(n)。

Word2Vec 实现方法如下：

先将概率以累积概率分布的形式分布到一条线段上，以

a=0.2, b=0.3, c=0.5

为例，

所处线段为

[0, 0.2]

，

所处线段为

[0.2, 0.5]

，

所处线段为

[0.5, 1]

，然后定义一个大小为

的数组，并与上面的线段做一次映射，这样我们便知道了数组内的每个单元所对应的字符了，这种情况下算法的时间复杂度为

O(1)

，空间复杂度为

O(m)

，

越小精度越大，但空间复杂度也会变得更大。

5.Parameter

Skip-Gram 的速度比 CBOW 慢一点，小数据集中对低频次的效果更好；
Sub-Sampling Frequent Words 可以同时提高算法的速度和精度，Sample 建议取值为

[10^{-5} ,10^{-3}]

；

Hierarchical Softmax 对低词频的更友好；
Negative Sampling 对高词频更友好；
向量维度一般越高越好，但也不绝对；
Window Size，Skip-Gram 一般 10 左右，CBOW 一般为 5 左右。

6.Application

Word2vec 主要原理是根据上下文来预测单词，一个词的意义往往可以从其前后的句子中抽取出来。

而用户的行为也是一种相似的时间序列，可以通过上下文进行推断。当用户浏览并与内容进行交互时，我们可以从用户前后的交互过程中判断行为的抽象特征，这就使得我们可以用词向量模型应用到推荐、广告领域当中。

Word2vec 已经应用于多个领域，并取得了巨大成功：

Airbnb 将用户的浏览行为组成 List，通过 Word2Vec 方法学习 item 的向量，其点击率提升了 21%，且带动了 99% 的预定转化率；

^{[5]}

Yahoo 邮箱从发送到用户的购物凭证中抽取商品并组成 List，通过 Word2Vec 学习并为用户推荐潜在的商品；

^{[6]}

Google 将用户的搜索查询和广告组成 List，并为其学习特征向量，以便对于给定的搜索查询可以匹配适合的广告。

^{[7]}

7.Conclusion

简单总结一下： Word2Vec 是一个词向量开源工具，包括 Skip-Gram 和 CBOW 的两种算法，加速训练的方法有：Hierarchical Softmax、Sub-Sampling 和 Negative Sampling。

Skip-Gram：利用中心词预测上下文；
CBOW：利用上下文预测中心词，速度比 Skip-Gram 快；
Hierarchical Softmax：引入 Hierarchical 加速 Softmax 的计算过程，对词频低的友好；
Sub-Sampling：依据词频进行采样，对词频低的友好；
Negative Sampling：通过负采样避免更新全部参数，对词频高的友好；

最后我们来看一下文章开始时提出的一部分不太好回答的问题：

Word2Vec 的两个模型哪个效果好哪个速度快？为什么？
- 效果：CBOW 像是小学时做的填空题：I come ___ China，而 Skip-Gram 像是给你一个 from 让你预测上下文，理论上来说应该是 CBOW 的效果更好，但实际情况却恰恰相反。我觉得可能是因为 CBOW 是取上下文的输入向量的质心从而导致一部分有效信息损失，而 Skip-Gram 虽然看起来荒唐，但每个单词都会得到单独的训练不会损失有效信息，其实 Skip-Gram 比 CBOW 的效果好，主要是针对低频词而言，举个例子，让你补全 It is a ___ day，是不是突然有很多可能的答案，你大概率会填写一个高频词汇，如：nice、sun 等，而不会想到要填写 gorgeous，而给你 gorgeous 单词，其特征很明显会想到这可以用来形容 day、moon、girl 等等。其次 gorgeous 本身用量就没有 nice 那么多，如果再和其他上下文放在一起取质心，其很容易被忽略，从而没法充分训练。
- 速度：我觉得 Skip-Gram 的速度慢可能是因为其预测值比较多需要分别计算多个 Softmax，时间复杂度为 O(kn)，而 CBOW 虽然也有多个输入，但我们求其质心简化了操作，时间复杂度为 O(n)。
Hierarchical Softmax 对词频低的和词频高的单词有什么影响？为什么？ H-S 利用了 Huffman 树依据词频建树，词频大的节点离根节点较近，词频低的节点离根节点较远，距离远参数数量就多，在训练的过程中，低频词的路径上的参数能够得到更多的训练，所以效果会更好。
Word2Vec 有哪些局限性？ Word2Vec 作为一个简单易用的算法，其也包含了很多局限性：
- Word2Vec 只考虑到上下文信息，而忽略的全局信息；
- Word2Vec 只考虑了上下文的共现性，而忽略的了彼此之间的顺序性；

最后引用文献外也推荐一些看过的资料：

《word2vec Parameter Learning Explained》（Xin Rong 大佬）；
《word2vec 中的数学原理详解》（北漂浪子）
《万物皆Embedding，从经典的word2vec到深度学习基本操作item2vec》（王喆大佬）
《Word2Vec Tutorial》McCormick 大佬，有五篇教程，简单明了）
《Deep Learning 实战之 word2vec》（网易有道，有源码有公式推导有调参建议）

8.References

《word2vec Parameter Learning Explained》
《Word2Vec Tutorial part 2 - Negative Sampling》
《Applying word2vec to Recommenders and Advertising》
《Deep Learning 实战之 word2vec》
《Real-time Personalization using Embeddings for Search Ranking at Airbnb》
《E-commerce in Your Inbox: Product Recommendations at Scale》
《Scalable Semantic Matching of Queries to Ads in Sponsored Search Advertising》

embedding list sampling word word2vec

0 人点赞