Word2Vec 原理讲解

1.介绍

• 2013年，Google开源了一款用于词向量计算的工具—— word2vec，引起了工业界和学术界的关注。
• 提到word2vec 算法或模型，其实指的是其背后用于计算 word vector 的 CBoW 模型和 Skip-gram 模型
• 很多人以为 word2vec 指的是一个算法或模型，实际上并不正确。
• 因此通过 Word2Vec 技术 输出的词向量可以被用来做很多NLP相关的工作，比如聚类、找同义词、词性分析等等.

适用场景

1. cbow适用于小规模，或者主题比较散的语料，这是因为他的向量产生只跟临近的字有关系，更远的语料并没有被采用。
2. 而相反的skip-gram可以处理基于相同语义，义群的一大批语料。

1.1.Statistical Language Model

在深入word2vec算法的细节之前，首先回顾一下自然语言处理中的一个基本问题：如何计算一段文本序列在某种语言下出现的概率？之所为称其为一个基本问题，是因为它在很多NLP任务中都扮演着重要的角色。例如，在机器翻译的问题中，如果我们知道了目标语言中每句话的概率，就可以从候选集合中挑选出最合理的句子做为翻译结果返回。

统计语言模型给出了这一类问题的一个基本解决框架。对于一段文本序列$S=w_1, w_2, … , w_T$，它的概率可以表示为：

$$P(S)=P(w_1, w_2, …, w_T)=\prod_{t=1}^Tp(w_t|w_1, w_2, …, w_{t-1})$$

即将序列的联合概率转化为一系列条件概率的乘积。问题变成了如何去预测这些给定previous words下的条件概率。

由于其巨大的参数空间，这样一个原始的模型在实际中并没有什么卵用。我们更多的是采用其简化版本——Ngram模型：

$$p(w_t|w_1,w_2,…,w_{t-1})$$

常见的如bigram模型（$n=2$）和trigram模型（$n=3$）。事实上，由于模型复杂度和预测精度的限制，我们很少会考虑$n>3$的模型。

我们可以用最大似然法去求解Ngram模型的参数，这等价于去统计每个Ngram的条件词频。

为了避免统计中出现的零概率问题（一段从未在训练集中出现过的Ngram片段会使得整个序列的概率为00），人们基于原始的Ngram模型进一步发展出了back-off trigram模型（用低阶的bigram和unigram代替零概率的trigram）和interpolated trigram模型（将条件概率表示为unigram、bigram、trigram三者的线性函数）。

1.2. Distributed Representation

不过，Ngram模型仍有其局限性。首先，由于参数空间的爆炸式增长，它无法处理更长程的context（N>3）。其次，它没有考虑词与词之间内在的联系性。例如，考虑”the cat is walking in the bedroom”这句话。如果我们在训练语料中看到了很多类似“the dog is walking in the bedroom”或是“the cat is running in the bedroom”这样的句子，那么，即使我们没有见过这句话，也可以从“cat”和“dog”（“walking”和“running”）之间的相似性，推测出这句话的概率。然而， Ngram模型做不到。

这是因为，Ngram本质上是将词当做一个个孤立的原子单元（atomic unit）去处理的。这种处理方式对应到数学上的形式是一个个离散的one-hot向量（除了一个词典索引的下标对应的方向上是11，其余方向上都是00）。例如，对于一个大小为55的词典：{“I”, “love”, “nature”, “luaguage”, “processing”}，“nature”对应的one-hot向量为：[0,0,1,0,0]。显然，one-hot向量的维度等于词典的大小。这在动辄上万甚至百万词典的实际应用中，面临着巨大的维度灾难问题（the curse of dimensionality）

于是，人们就自然而然地想到，能否用一个连续的稠密向量去刻画一个word的特征呢？这样，我们不仅可以直接刻画词与词之间的相似度，还可以建立一个从向量到概率的平滑函数模型，使得相似的词向量可以映射到相近的概率空间上。这个稠密连续向量也被称为word的distributed representation。

事实上，这个概念在信息检索（Information Retrieval）领域早就已经被广泛地使用了。只不过，在IR领域里，这个概念被称为向量空间模型（Vector Space Model，以下简称VSM）。

VSM是基于一种Statistical Semantics Hypothesis：语言的统计特征隐藏着语义的信息（Statistical pattern of human word usage can be used to figure out what people mean）。例如，两篇具有相似词分布的文档可以被认为是有着相近的主题。这个Hypothesis有很多衍生版本。其中，比较广为人知的两个版本是Bag of Words Hypothesis和Distributional Hypothesis。前者是说，一篇文档的词频（而不是词序）代表了文档的主题；后者是说，上下文环境相似的两个词有着相近的语义。后面我们会看到，word2vec算法也是基于Distributional的假设。

那么，VSM是如何将稀疏离散的one-hot词向量映射为稠密连续的distributional representation的呢？

简单来说，基于Bag of Words Hypothesis，我们可以构造一个term-document矩阵A：矩阵的行$A_i,:$对应着词典里的一个word；矩阵的列$A:,j$对应着训练语料里的一篇文档；矩阵里的元素$A_ij$代表着word $w_i$在文档$D_j$中出现的次数（或频率）。那么，我们就可以提取行向量做为word的语义向量（不过，在实际应用中，我们更多的是用列向量做为文档的主题向量）。

类似地，我们可以基于Distributional Hypothesis构造一个word-context的矩阵。此时，矩阵的列变成了context里的word，矩阵的元素也变成了一个context窗口里word的共现次数。

注意，这两类矩阵的行向量所计算的相似度有着细微的差异：term-document矩阵会给经常出现在同一篇document里的两个word赋予更高的相似度；而word-context矩阵会给那些有着相同context的两个word赋予更高的相似度。后者相对于前者是一种更高阶的相似度，因此在传统的信息检索领域中得到了更加广泛的应用。

不过，这种co-occurrence矩阵仍然存在着数据稀疏性和维度灾难的问题。为此，人们提出了一系列对矩阵进行降维的方法（如LSI／LSA等）。这些方法大都是基于SVD的思想，将原始的稀疏矩阵分解为两个低秩矩阵乘积的形式。

1.3. Neural Network Language Model

接下来，让我们回到对统计语言模型的讨论。鉴于Ngram等模型的不足，2003年，Bengio等人发表了一篇开创性的文章：A neural probabilistic language model。在这篇文章里，他们总结出了一套用神经网络建立统计语言模型的框架（Neural Network Language Model，以下简称NNLM），并首次提出了word embedding的概念（虽然没有叫这个名字），从而奠定了包括word2vec在内后续研究word representation learning的基础。

NNLM模型的基本思想可以概括如下：

1. 假定词表中的每一个word都对应着一个连续的特征向量；
2. 假定一个连续平滑的概率模型，输入一段词向量的序列，可以输出这段序列的联合概率；
3. 同时学习词向量的权重和概率模型里的参数。

值得注意的一点是，这里的词向量也是要学习的参数。

在03年的论文里，Bengio等人采用了一个简单的前向反馈神经网络$f(w_{t-n+1},…,w_{t})$

来拟合一个词序列的条件概率$p(w_t|w_1,w_2,…,w_{t-1})$。整个模型的网络结构见下图：

我们可以将整个模型拆分成两部分加以理解：

1. 首先是一个线性的embedding层。它将输入的N−1个one-hot词向量，通过一个共享的D×V的矩阵C，映射为N−1个分布式的词向量（distributed vector）。其中，V是词典的大小，D是embedding向量的维度（一个先验参数）。C矩阵里存储了要学习的word vector。

2. 其次是一个简单的前向反馈神经网络g。它由一个tanh隐层和一个softmax输出层组成。通过将embedding层输出的N−1个词向量映射为一个长度为V

   的概率分布向量，从而对词典中的word在输入context下的条件概率做出预估：

   $$p(w_i|w_1,w_2,…,w_{t-1}) \approx f(w_i, w_{t-1}, …, w_{t-n+1}) = g(w_i, C(w_{t-n+1}), …, C(w_{t-1}))$$

我们可以通过最小化一个cross-entropy的正则化损失函数来调整模型的参数$\theta$：

$$L(\theta)=\frac{1}{T}\sum_t{\log{f(w_t, w_{t-1}, …, w_{t-n+1})}}+R(\theta)$$

其中，模型的参数$\theta$包括了embedding层矩阵C的元素，和前向反馈神经网络模型g里的权重。这是一个巨大的参数空间。不过，在用SGD学习更新模型的参数时，并不是所有的参数都需要调整（例如未在输入的context中出现的词对应的词向量）。计算的瓶颈主要是在softmax层的归一化函数上（需要对词典中所有的word计算一遍条件概率）。

然而，抛却复杂的参数空间，我们不禁要问，为什么这样一个简单的模型会取得巨大的成功呢？

仔细观察这个模型就会发现，它其实在同时解决两个问题：一个是统计语言模型里关注的条件概率$p(w_t|context)$的计算；一个是向量空间模型里关注的词向量的表达。而这两个问题本质上并不独立。通过引入连续的词向量和平滑的概率模型，我们就可以在一个连续空间里对序列概率进行建模，从而从根本上缓解数据稀疏性和维度灾难的问题。另一方面，以条件概率$p(w_t|context)$为学习目标去更新词向量的权重，具有更强的导向性，同时也与VSM里的Distributional Hypothesis不谋而合。

2. NNLM存在的几个问题

第一个问题是，同Ngram模型一样，NNLM模型只能处理定长的序列。在03年的论文里，Bengio等人将模型能够一次处理的序列长度N提高到了5，虽然相比bigram和trigram已经是很大的提升，但依然缺少灵活性。

因此，Mikolov等人在2010年提出了一种RNNLM模型，用递归神经网络代替原始模型里的前向反馈神经网络，并将embedding层与RNN里的隐藏层合并，从而解决了变长序列的问题。

另一个问题就比较严重了。NNLM的训练太慢了。即便是在百万量级的数据集上，即便是借助了40个CPU进行训练，NNLM也需要耗时数周才能给出一个稍微靠谱的解来。显然，对于现在动辄上千万甚至上亿的真实语料库，训练一个NNLM模型几乎是一个impossible mission。

这时候，还是那个Mikolov站了出来。他注意到，原始的NNLM模型的训练其实可以拆分成两个步骤：

1. 用一个简单模型训练出连续的词向量；
2. 基于词向量的表达，训练一个连续的Ngram神经网络模型。
   而NNLM模型的计算瓶颈主要是在第二步。

2.1. CBoW 模型（Continuous Bag-of-Words Model）

如果我们只是想得到word的连续特征向量，是不是可以对第二步里的神经网络模型进行简化呢？

Mikolov是这么想的，也是这么做的。他在2013年一口气推出了两篇paper，并开源了一款计算词向量的工具——至此，word2vec横空出世，主角闪亮登场。

下面简单剖析下word2vec算法的原理。有了前文的基础，理解word2vec算法就变得很简单了。

首先，我们对原始的NNLM模型做如下改造：

1. 移除前向反馈神经网络中非线性的hidden layer，直接将中间层的embedding layer与输出层的softmax layer连接；
2. 忽略上下文环境的序列信息：输入的所有词向量均汇总到同一个embedding layer；
3. 将future words纳入上下文环境
4. CBOW模型的输入是某个词A周围的n个单词的词向量之和，输出是词A本身的词向量.

从数学上看，CBoW模型等价于一个词袋模型的向量乘以一个embedding矩阵，从而得到一个连续的embedding向量。这也是CBoW模型名称的由来。

CBoW模型依然是从context对target word的预测中学习到词向量的表达。反过来，我们能否从target word对context的预测中学习到word vector呢？答案显然是可以的：

2.2. Skip-gram 模型

这个模型被称为Skip-gram模型（名称源于该模型在训练时会对上下文环境里的word进行采样）。

如果将Skip-gram模型的前向计算过程写成数学形式，我们得到：

$$p(w_o|w_i)=\frac{e^{U_o \cdot V_i}}{\sum_j{e^{U_j \cdot V_i}}}$$

其中，$V_i$是embedding层矩阵里的列向量，也被称为$w_i$的input vector。$U_j$是softmax层矩阵里的行向量，也被称为$w_j$的output vector。

因此，Skip-gram模型的本质是计算输入word的input vector与目标word的output vector之间的余弦相似度，并进行softmax归一化。我们要学习的模型参数正是这两类词向量。

然而，直接对词典里的VV个词计算相似度并归一化，显然是一件极其耗时的impossible mission。为此，Mikolov引入了两种优化算法：层次Softmax（Hierarchical Softmax）和负采样（Negative Sampling）。

• skip-gram与CBOW相比，只有细微的不同。skip-gram的输入是当前词的词向量，而输出是周围词的词向量。
• Skip-gram 模型: 能够根据词本身来预测周围有哪些词.

接下来介绍这两种优化算法。

2.2.1. Hierarchical Softmax

层次Softmax的方法最早由Bengio在05年引入到语言模型中。它的基本思想是将复杂的归一化概率分解为一系列条件概率乘积的形式：

$$p(v|context)=\prod_{i=1}^m{p(b_i(v)|b_1(v), …, b_{i-1}(v), context)}$$

其中，每一层条件概率对应一个二分类问题，可以通过一个简单的逻辑回归函数去拟合。这样，我们将对个词的概率归一化问题，转化成了对个词的概率拟合问题。

我们可以通过构造一颗分类二叉树来直观地理解这个过程。首先，我们将原始字典$D$划分为两个子集$D_1$、$D_2$，并假设在给定context下，target word属于子集$D_1$的概率$p(w_t \in D_1|context)$服从logistical function的形式：

$$p(w_t \in D_1|context)=\frac{1}{1+e^{-U_{D_{root}} \cdot V_{w_t}}}$$

其中，$U_{D_{root}}$和$V_{w_t}$都是模型的参数。

接下来，我们可以对子集$D_1$和$D_2$进一步划分。重复这一过程，直到集合里只剩下一个word。这样，我们就将原始大小为$V$的字典$D$转换成了一颗深度为$\log V$的二叉树。树的叶子节点与原始字典里的word一一对应；非叶节点则对应着某一类word的集合。显然，从根节点出发到任意一个叶子节点都只有一条唯一路径——这条路径也编码了这个叶子节点所属的类别。

同时，从根节点出发到叶子节点也是一个随机游走的过程。因此，我们可以基于这颗二叉树对叶子节点出现的似然概率进行计算。例如，对于训练样本里的一个target word $w_t$，假设其对应的二叉树编码为{1,0,1,…,1}，则我们构造的似然函数为：

$$p(w_t|context)=p(D_1=1|context)p(D_2=0|D_1=1)\dots p(w_t|D_k=1)$$

乘积中的每一项都是一个逻辑回归的函数。

我们可以通过最大化这个似然函数来求解二叉树上的参数——非叶节点上的向量，用来计算游走到某一个子节点的概率。

层次Softmax是一个很巧妙的模型。它通过构造一颗二叉树，将目标概率的计算复杂度从最初的$V$降低到了$\log V$的量级。不过付出的代价是人为增强了词与词之间的耦合性。例如，一个word出现的条件概率的变化，会影响到其路径上所有非叶节点的概率变化，间接地对其他word出现的条件概率带来不同程度的影响。因此，构造一颗有意义的二叉树就显得十分重要。实践证明，在实际的应用中，基于Huffman编码的二叉树可以满足大部分应用场景的需求。

2.2.2. Negative Sampling

负采样的思想最初来源于一种叫做Noise-Contrastive Estimation的算法，原本是为了解决那些无法归一化的概率模型的参数预估问题。与改造模型输出概率的层次Softmax算法不同，NCE算法改造的是模型的似然函数。

以Skip-gram模型为例，其原始的似然函数对应着一个Multinomial的分布。在用最大似然法求解这个似然函数时，我们得到一个cross-entropy的损失函数：

$$J(\theta)=-\frac{1}{T}\sum_{t=1}^T{\sum_{-c \leq j \leq c, j \neq 0}{\log p(w_{t+j}|w_t)}}$$
式中的$p(w_{t+j}|w_t)$是一个在整个字典上归一化了的概率。

而在NCE算法中，我们构造了这样一个问题：对于一组训练样本<context, word>，我们想知道，target word的出现，是来自于context的驱动，还是一个事先假定的背景噪声的驱动？显然，我们可以用一个逻辑回归的函数来回答这个问题：

$$p(D=1|w, context)=\frac{p(w|context)}{p(w|context)+kp_n(w)}=\sigma (\log p(w|context) - \log kp_n(w))$$

这个式子给出了一个target word $w$来自于context驱动的概率。其中，$k$是一个先验参数，表明噪声的采样频率。$p(w|context)$是一个非归一化的概率分布，这里采用softmax归一化函数中的分子部分。$p_n(w)$则是背景噪声的词分布。通常采用word的unigram分布。

通过对噪声分布的kk采样，我们得到一个新的数据集：<context, word, label>。其中，label标记了数据的来源（真实数据分布还是背景噪声分布？）。在这个新的数据集上，我们就可以用最大化上式中逻辑回归的似然函数来求解模型的参数。

而Mikolov在2013年的论文里提出的负采样算法， 是NCE的一个简化版本。在这个算法里，Mikolov抛弃了NCE似然函数中对噪声分布的依赖，直接用原始softmax函数里的分子定义了逻辑回归的函数，进一步简化了计算：

$$p(D=1|w_o, w_i)=\sigma (U_o \cdot V_i)$$
此时，模型相应的目标函数变为：

$$J(\theta) = \log \sigma(U_o \cdot V_i) + \sum_{j=1}^k{E_{w_j \sim p_n(w)}[\log \sigma(- U_j \cdot V_i)]}$$

除了这里介绍的层次Softmax和负采样的优化算法，Mikolov在13年的论文里还介绍了另一个trick：下采样（subsampling）。其基本思想是在训练时依概率随机丢弃掉那些高频的词：

$$p_{discard}(w) = 1 - \sqrt{\frac{t}{f(w)}}$$
其中，$t$是一个先验参数，一般取为$10^{-5}$。是在语料中出现的频率。

实验证明，这种下采样技术可以显著提高低频词的词向量的准确度。

3. 模型的应用

word2vec模型可以被应用于机器翻译和推荐系统领域。

3.1. Machine Translation

与后来提出的在sentence level上进行机器翻译的RNN模型不同，word2vec模型主要是用于词粒度上的机器翻译。

具体来说，我们首先从大量的单语种语料中学习到每种语言的word2vec表达，再借助一个小的双语语料库学习到两种语言word2vec表达的线性映射关系$W$。构造的损失函数为：

$$J(W)=\sum_{i=1}^n{||Wx_i - z_i||^2}$$

在翻译的过程中，我们首先将源语言的word2vec向量通过矩阵$W$映射到目标语言的向量空间上；再在目标语言的向量空间中找出与投影向量距离最近的word做为翻译的结果返回。

其原理是，不同语言学习到的word2vec向量空间在几何上具有一定的同构性。映射矩阵$W$本质上是一种空间对齐的线性变换。

3.2. Item2Vec

本质上，word2vec模型是在word-context的co-occurrence矩阵基础上建立起来的。因此，任何基于co-occurrence矩阵的算法模型，都可以套用word2vec算法的思路加以改进。

比如，推荐系统领域的协同过滤算法。

协同过滤算法是建立在一个user-item的co-occurrence矩阵的基础上，通过行向量或列向量的相似性进行推荐。如果我们将同一个user购买的item视为一个context，就可以建立一个item-context的矩阵。进一步的，可以在这个矩阵上借鉴CBoW模型或Skip-gram模型计算出item的向量表达，在更高阶上计算item间的相似度。

参考资料：

[1]: Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013, January 17). Efficient Estimation of Word Representations in Vector Space. arXiv.org.

[2]: Mikolov, T., Sutskever, I., Chen, K., Corrado, G., & Dean, J. (2013, October 17). Distributed Representations of Words and Phrases and their Compositionality. arXiv.org.

[3]: Bengio, Y., Ducharme, R., Vincent, P., & Janvin, C. (2003). A neural probabilistic language model. The Journal of Machine Learning Research, 3, 1137–1155.

[4]: Turney, P. D., & Pantel, P. (2010). From frequency to meaning: vector space models of semantics. Journal of Artificial Intelligence Research, 37(1).

[5]. Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., & Kuksa, P. (2011). Natural Language Processing (Almost) from Scratch. Journal of Machine Learning Research, 12(Aug), 2493–2537.