word2vec中的数学原理详解

简介

word2vec最初是由Tomas Mikolov 2013年在ICLR发表的一篇文章Efficient Estimation of Word Representations in Vector Space， 并且开源了代码，作用是将所有词语投影到K维的向量空间，每个词语都可以用一个K维向量表示。由于它简洁，高效的特点，引起了人们的广泛关注，并应用在很多NLP任务中，用于训练相应的词向量。

预备知识

本节介绍word2vec中将用到的一些重要知识点，包括sigmoid函数、Beyes公式和Huffman编码等

sigmoid函数

sigmoid函数是神经网络中常用的激活函数之一，其定义为 \[ \sigma (x)=\frac{1}{1+e^{-x}} \] 该函数的定义域为\((-\infty ,+\infty)\)，值域为\((0,1)\).图1给出了sigmoid函数的图像

sigmoid函数的导函数具有以下形式 \[ {\sigma (x)}'=\sigma (x)[1-\sigma (x)] \]

由此易得，函数\(\log\sigma (x)\)和\(\log(1-\sigma (x))\)的导函数分别为 \[ [{\log\sigma (x)}']=1-\sigma (x),[{\log(1-\sigma (x))}']=-\sigma (x) \] 公式(2.1)在后面的推导将用到。

逻辑回归

生活中经常会碰到二分类问题，例如，某封电子邮件是否为垃圾邮件，某个客户是否为潜在客户，某次在线交易是否存在欺诈行为，等等。设\(\left \{ ({x_i,y_i}) \right \}_{i=1}^{m}\)为一个二分类问题的样本数据，其中\({x_i}\in \mathbb{R}^{n},{y_i}\in (0,1)\)，当\({y_i}=1\)时称相应的样本为正例，当\({y_i}=0\)时称相应的样本为负例。 利用sigmoid函数，对于任意样本\(x=(x_1,x_2,...,x_n)^{T}\)，可将二分类问题的hypothesis函数写成 \[ h_\theta (x)=\sigma (\theta _0+\theta _1x_1+\theta _2x_2+...+\theta _nx_n) \] 其中\(\theta=(\theta_0,\theta_1,...,\theta_n)^{T}\)为待定参数。为了符号上简化起见，引入\(x_0=1\)将\(x\)扩展为\((x_0,x_1,...x_n)^{T}\)，且在不引起混淆的情况下仍将其记为\(x\)。于是\(h_\theta\)可简写为 \[ h_\theta (x)=\sigma (\theta ^{T}x)=\frac{1}{1+e^{-\theta ^{T}x}} \] 取阈值\(T=0.5\)，则二分类的判别公式为 \[ y(x)=\left\{\begin{matrix} 1,h_\theta (x)\geqslant 0.5\\ 0,h_\theta (x)< 0.5 \end{matrix}\right. \] 那参数\(\theta\)如何求呢？通常的做法是，先确定一个形如下式的整体损失函数 \[ J(\theta )=\frac{1}{m}\sum_{i=1}^{m}cost(X_i,y_i) \] 然后对其进行优化，从而得到最优的参数\(\theta ^{*}\)。 实际应用中，单个样本的损失函数\(cost(X_i,y_i)\)常取为对数似然函数 \[ cost(X_i,y_i)=\left\{\begin{matrix} -\log (h_\theta (X_i)) & y_i=1;\\ -\log (1-h_\theta (X_i))& y_i=0. \end{matrix}\right. \] 注意，上式是一个分段函数，也可将其写成如下的整体表达式 \[ cost(X_i,y_i)=-y_i·\log(h_\theta(X_i))-(1-y_i)·\log(1-h_\theta(X_i)). \]

Bayes公式

贝叶斯公式是英国数学家贝叶斯(Thomas Bayes)提出来的，用来描述两个条件概率之间的关系。若记\(P(A)\),\(P(B)\)分别表示事件A和事件B发生的概率，\(P(A|B)\)表示事件B发生的情况下事件A发生的概率，\(P(A,B)\)表示事件A,B同时发生的概率，则有 \[ P(A|B)=\frac{P(A,B)}{P(B)},P(B|A)=\frac{P(A,B)}{P(A)} \] 这就是Bayes公式

Huffman编码

本节简单介绍Huffman编码，为此，首先介绍Huffman树的定义及其构造算法。

Huffman树

在计算机科学中，树是一种重要的非线性数据结构，它是数据元素（在树中称为结点）按分支关系组织起来的结构。若干棵互不相交的树构成的集合称为森林。下面给出几个与树相关的常用概念。

• 路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层号为1，则从根结点到第\(L\)层结点的路径长度为\(L-1\)

• 结点的权和带权路径长度

若为树中结点赋予一个具有某种含义的（非负）数值，则这个数值称为该结点的权。结点的带权路径长度是指，从根结点到该结点之间的路径长度与该结点的权的乘积。

• 树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和。

二叉树是每个结点最多有两个子树的有序树。两个子树通常被称为“左子树”和“右子树”，定义中的“有序”是指两个子树有左右之分，顺序不能颠倒。

给定\(n\)个权值作为\(n\)个叶子结点，构造一棵二叉树，若它的带权路径长度达到最小，则成这样的二叉树为最优二叉树，也称为Huffman树

Huffman树的构造

给定\(n\)个权值\({w_1,w_2,...,w_n}\)作为二叉树的\(n\)个叶子结点，可通过以下算法来构造一棵Huffman树。

算法2.1(Huffman树构造算法)

接下来给出算法2.1的一个具体实例。

利用算法2.1，易知其构造过程如图2所示，图中第六步给出了最终的Huffman树，由图可见词频越大的词离根结点越近。

构造过程中，通过合并新增的结点被标记为黄色。由于每两个结点都要进行一次合并，因此，若叶子结点的个数为n，则构造的Huffman树新增结点的个数为n-1。本例中n=6，因此新增的结点个数为5.

注意，前面有提到，二叉树的两个子树是分左右的，对于某个非叶子结点来说，就是其两个孩子结点是分左右的，在本例中，统一将词频打的结点作为左孩子结点，词频小的作为右孩子结点。当然，这只是一个约定，你要将词频大的结点作为右孩子结点也没有问题。

Huffman编码

在数据通信中，需要将传送的文字转换成二进制的字符串，用0,1码的不同排列來表示字符.例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A, E, R, T，F, D”，各字母出现的次数为8, 4, 5, 3, 1, 1.现要求为这些字母设计编码.

要区別6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制（\(2^{3}=8>6\)),可分別用000、001、010、011、100、101对“A, E, R, T, F, D”进行编码发送，当对方接收报文时再按照三位一分进行译码.

显然编码的长度取决报文中不同字符的个数.苻报文中可能出现26个不同字符，则固定编码长度为5 (\(2^{5}=32>26\)).然而，传送报文时总是希望总长度尽可能短.在实际应用中, 各个字符的出现频度或使用次数是不相同的，如A、B、 C的使用频率远远高于X、Y、Z,自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码.

为使不等长编码为前缀编码（即要求一个字符的编码不能足另一个字符编码的前缀)，可用字符集中的毎个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度, 可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下,于是频率小编码长，频率高编码短,这作就保证了此树的最小带 权路径长度，效果上就是传送报文的最短长度.因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的Huffman树的问题。利用Huffman树设计的二进制前缀编码，称为Huffman编码，它既能满足前缀编码的条件，又能保证报文编码总长最短。

本文将介绍的word2vec工具中也将用到Huffman编码，它把训练语料中的词当成叶子结点，其在训练语料出现的次数当作权值，通过构造相应的Huffman树来对每一个词进行Huffman编码.

图3给出了例2.1中六个词的Huffman编码，其中约定（词频较大的）左孩子结点编码为1,(词频较小的）右孩子编码为0.这样一来，“我”、“喜欢”、“观看”、“巴西”、“足球”、“世界杯”这六个问的Huffman编码分別为0, 111, 110, 101, 1001和1000.

注意，到目前为止，关于Huffman树和Huffman编码，有两个约定：（1）将权值大的结点作为左孩子结点，权值小的作为右孩子结点；（2）左孩子结点编码为1，右孩子结点编码为0.在word2vec源码中将权值较大的孩子结点编码为1，较小的孩子结点编码为0。为与上述约定统一起见，下文中提到的“左孩子结点”都是权值较大的孩子结点。

背景知识

word2vec是用来生成词向量的工具，而词向量与语言模型有着密切的关系，为此，不妨先来了解一些语言模型方面的知识。

统计语言模型

当今的互联网迅猛发展，每天都在产生大量的文本、图片、语音和视频数据，要对这些数据进行处理并从中挖掘出有价值的信息，离不开自然语言处理技术，其中统计语言模型就是很重要的一环，它是所有NLP的基础，被广泛用于语音识别、机器翻译、分词、词性标注和信息检索等任务。

简单地说，统计语言模型是用来计算一个句子的概率模型，它通常基于一个语料库来构建。那什么叫一个句子的概率呢？假设，\(W=w_1^{T}:=(w_1,w_2,...,w_T)\)表示由T个词\(w_1,w_2,...,w_T\)构成的一个句子，则\(w_1,w_2,...,w_T\)的联合概率 \[ p(W)=p(w_1^{T})=p(w_1,w_2,...,w_T) \] 就是这个句子的概率。利用Bayes公式，上式可以链式的分解为 \[ p(w_1^{T})=p(w_1)·p(w_2|w_1)·p(w_3|w_1^{2})···p(w_T|w_1^{T-1}) \] 其中的（条件）概率\(p(w_1),p(w_2|w_1),...,p(w_T|w_1^{T-1})\)就是语言模型的参数，若这些参数已经全部算得，那么给定一个句子\(w_1^{T}\)，就可以很快的算出相应的\(p(w_1^{T})\)了。

看起来好像很简单，但是，具体实现起来还是有点麻烦，例如，先来看看模型参数的个数。刚才是考虑一个给定长度为T的句子，就需要计算T个参数。不妨假设语料库对应词典D的大小（即词汇量）为N，那么，如果考虑长度为T的任意句子，理论上就有\(N^{T}\)种可能，而每种可能都要计算T个参数，总共需要计算\(TN^{T}\)个参数，当然，这里只是简单估算，并没有考虑重复参数，但是这个量级还是蛮吓人的。此外，这些概率计算好后，还得保存下来，因此，存储这些信息也需要很大的内存开销。

此外，这些参数如何计算呢？常见的方法有n-gram模型、决策树、最大熵模型、最大熵马尔科夫模型、条件随机场、神经网络等方法。本文只讨论n-gram模型和神经网络两种方法。首先来看n-gram模型。

n-gram模型

考虑\(p(w_k|w_1^{k-1})(k>1)\)的近似计算，利用Bayes公式，有 \[ p(w_k|w_1^{k-1})=\frac{p(w_1^{k})}{p(w_1^{k-1})} \] 根据大数定理，当语料库足够大时，\(p(w_k|w_1^{k-1})\)可近似的表示为 \[ p(w_k|w_1^{k-1})\approx \frac{count(w_1^{k})}{count(w_1^{k-1})} \] 其中\(count(w_1^{k})\)和\(count(w_1^{k-1})\)分别表示词串\(w_1^{k}\)和\(w_1^{k-1}\)在语料库中出现的次数。可想而知，当\(k\)很大时，\(count(w_1^{k})\)和\(count(w_1^{k-1})\)的统计会多么耗时

从公式(3.1)可以看出：一个词出现的概率与它前面的所有词都相关。如果假定一个词出现的概率只与它前面固定数目的词相关呢？这就是n-gram模型的基本思想，它做了一个n-1阶的Markov假设，认为一个词出现的概率就只与它前面的n-1个词相关，即 \[ p(w_k|w_1^{k-1})\approx p(w_k|w_{k-n+1}^{k}) \]

于是，(3.2)就变成了 \[ p(w_k|w_1^{k-1})\approx \frac{count(w_{k-n+1}^{k})}{count(w_{k-n+1}^{k-1})} \] 以n=2为例，就有 \[ p(w_k|w_1^{k-1})\approx \frac{count(w_{k-1},w_k)}{count(w_{k-1})} \] 这样一简化，不仅使得单个参数的统计变得更容易（统计时需要匹配的词串更短），也使得参数的总数变少了。

那么，n-gram中的参数n取多大比较合适呢？一般来说，n的选取需要同时考虑计算复杂度和模型效果两个因素。

在计算复杂度方面，表1给出了n-gram模型中模型参数数量随着n的逐渐增大而变化的情况，其中假定词典大小N=200000（汉语的词汇量大致是这个量级）。事实上，模型参数的量级是N的指数函数(\(O(N^{n})\))，显然n不能取得太大，实际应用中最多的是采用n=3的三元模型。

在模型效果方面，理论上是n越大，效果越好。现如今，互联网的海量数据以及机器性能的提升是的计算更高阶的语言模型(如n>10)成为可能，但需要注意的是当n大到一定程度时，模型效果的提升幅度会变小。例如当n从1到2，再从2到3时，模型的效果上升显著，而从3到4时，效果提升就不显著了（具体可参考吴军在《数学之美》中的相关章节）。事实上，这里还涉及到一个可靠性和可区别性的问题，参数越多，可区别性越好，但同时单个参数的实例变少而降低了可靠性，因此需要在可靠性和可区别性之间进行折中。

另外，n-gram模型中还有一个叫做平滑化的重要环节。回到公式(3.3)，考虑两个问题：

• 若\(count(w_{k-1},w_k)=0\)，能否认为\(p(w_k|w_1^{k-1})\)就等于0呢？
• 若\(count(w_{k-1},w_k)=count(w_{k-n+1}^{k-1})\)，能否认为\(p(w_k|w_1^{k-1})\)就等于1呢？

显然不能！但是这是一个无法回避的问题，哪怕你的语料库有那么大，平滑化技术就是用来处理这个问题的，这里不展开讨论，具体可以参考维基百科。

总结起来,n-gram模型是这样一种模型,其主要工作是在语料中统计各种词串中出现的次数以及平滑化处理.概率值计算好之后就存储起来，下次需要计算一个句子的概率时，只需找到相关的概率参数，将它们连乘起來就好了。

然而，在机器学习领域有一种通用的招数数这样的：对所考虑的问题建模后先为其构造一个目标函数，然后对这个目标函数进行优化，从而求得一组最优的参数，最后利用这组最优参数对应的模型来进行预测.

对于统计语言模型而言，利用最大似然，可把目标函数设为 \[ \prod_{w\in C}p(w|Context(w)) \] 其中C表示语料(Corpus)，Context(w)表示词w的上下文(Context)即w周边的词的集合。当Context(w)为空时，就取\(p(w|Context(w))=p(w)\)。特别的，对于前面介绍的n-gram模型，就有\(Context(w_i)=w_{i-n+1}^{i-1}\).

当然，实际采用中常采用最大对数似然，即把目标函数设为 \[ L =\sum_{w\in C}\log p(w|Context(w)) \] 然后对这个函数进行最大化。

从(3.4)可见，概率\(p(w|Context(w))\)已被视为关于\(w\)和\(Context(w)\)的函数即 \[ p(w|Context(w))=F(w,Context(w),\theta), \] 其中\(\theta\)为待定参数集。这样一来，一旦对(3.4)进行优化得到最优参数集后，F也就唯一被确定了，以后任何概率\(p(w|Context(w))\)就可以通过函数\(F(w,Context(w),\theta^{*})\)来计算了。 与n-gram相比，这种方法不需要（事先计算并）保存所有的概率值，而是通过直接计算来获取，且通过选取合适的模型可使得\(\theta\)中参数的个数远小于n-gram中模型参数的个数。

很显然，对于这样一种方法，最关键的地方自安于函数F的构造了。下一小节将介绍一种通过神经网络来构造F的方法。之所以特意介绍这个方法，是因为它可以视为word2vec中算法框架的前身或者说基础。

神经概率语言模型

本小节介绍Bengio等人在文A neural probabilistic language model. Journal of Machine Learning Research中提出的一种神经概率语言模型。该模型中用到了一个重要的工具——词向量。

什么是词向量呢？简单来说就是，对词典D中的任意词\(w\)，指定一个固定长度的实值向量\(v(w)\in \mathbb{R}^{m}\),\(v(w)\)就称为\(w\)的词向量，\(m\)为词向量的长度。对于词向量的进一步理解将放到下一小节来讲解。

既然是神经概率语言模型，其中当然要用到一个神经网络啦。图4给出了这个神经网络的结构示意图，它包括四个层：输入层（Input）、投影层(Projection)、隐藏层(Hidden)和输出层(Output)。其中W,U分别为投影层与隐藏层以及隐藏层和输出层之间的权值矩阵，p,q分别为隐藏层和输出层上的偏置向量。

对于语料C中的任意一个词\(w\)，将\(Context(w)\)取为其前面的n-1个（类似于n-gram),这样二元对(\(Context(w),w\))回就是一个训练样本了、接下来，讨论样本(\(Context(w),w\))，经过如图所示的神经网络时是如何参与运算的．注意，一旦语料\(C\)和词向量长度\(m\)给定后，投影层和输出层的规模就确定了，前者为\(（n-1）m\)，后者为\(N=|D|\)即语料C的词汇量大小而隐藏层的规模砺是可调参数由用户指定.

为什么投影层的规模是（n-1)m呢？因为输人层包含\(Context(w),w\)中n-1个词的词向量，而投影层的向量xw是这样构的：将输人层的n-1个词向量按顺序首尾相接地拼起来形成一个长向量，其长度当然就是(n一1)m了．有了向量\(x_w\)，接下来的计算过程就很平凡了，具体为 \[ \left\{\begin{matrix} z_w=\tanh (W_x+p)\\ y_w=Uz_w+q \end{matrix}\right. \]

注3.4有读者可能要问：对于语料中的一个给定句子的前几个词，其前面的词不足n-1个怎么办此时，可以人为地添加一个（或几个）填充向量就可以了，它们也参与训练过程．

经过上述两步计算得到的\(y_w=(y_{w,1},y_{w,2},...y_{w,N})^{T}\)只是一个长度为N的向量，其分量不能表示概率．如果想要\(y_w\)的分量\(y_{w,i}\)表示当上下文为\(Context(w)\)时下一个词恰为词典中第个词的概率，则还需要做一个softmax归一化，归一化后，\(p(w|Context(w))\)就可以表示为 \[ p(w|Context(w))=\frac{e^{y_w,i_w}}{\sum _{1=1}^{n}e^{y_{w,i}}} \]

其中\(i_w\)表示词\(w\)在词典\(D\)中的索引。

公式(3.6)给出了概率\(p(w|Context(w))\)的函数表示，即找到了上一小节中提到的函数\(F(w,Context(w),\theta)\)，那么其中待确定的参数\(\theta\)有哪些呢？总结起来，包括两部分

• 词向量：\(v(w)\in \mathbb{R}^{m},w\in D\)以及填充向量。
• 神经网络参数：\(W\in \mathbb{R}^{n_h\times(n-1)^{m}},P\in \mathbb{R}^{n_h};U\in\mathbb{R}^{N\times n_h},q\in\mathbb{R}^{N}\)

这些参数均通过训练算法得到，值得一提的是，通常的机器学习算法中，输人都是已知的，而在上述神经概率语言模型中，输人\(v(w)\)也需要通过训练才能得到．接下来，简要地分析一下上述模型的运算量，在如图4所示的神经网络中，投影层、隐藏层和输出层的规模分别为（\(n-1）m,n_h,N\),依次看看其中涉及的参数： （1）n是一个词的上下文中包含的词数，通常不超过5； （2）m是词向量长度，通常是\(10^1\)～\(10^2\)量级； （3）\(n_h\)由用户指定，通常不需取得太大，如\(10^2\)量级； （4）N是语料词汇量的大小，与语料相关，但通常是\(10^4\)～\(10^5\)量级． 再结合（3.5）和（3.6），不难发现，整个模型的大部分计算集中在隐藏层和输出层之间的矩阵向量运算，以及输出层上的softmax归一化运算．因此后续的相关研究工作中，有很多是针对这一部分进行优化的，其中就包括了word2vec的工作．与n-gram模型相比，神经概率语言模型有什么优势呢？主要有以下两点： 1、词语之间的相似性可以通过词向量来体现． 举例来说，如果某个（英语）语料中\(S_1\)="A dog is running in the room"出现了10000次，而\(S_2\)="A cat is running in the room"只出现了1次，按照n-gram模型的做法，\(p(S_1)\)肯定会远大于\(p(S_2)\)·注意，\(S_1\)和\(S_2\)的唯一区别在于dog和cat,而这两个词无论是句法还是语义上都扮演了相同的角色，因此\(p(S_1)\)和\(p(S_2)\)应该很相近才对、然而，由神经概率语言模型算得的\(p(S_1)\)和\(p(S_2)\)是大致相等的．原因在于：（1）在神经概率语言模型中假定了“相似的”的词对应的词向量也是相似的；（2）概率函数关于词向量是光滑的，即词向量中的一个小变化对概率的影响也只是一个小变化．这样一来，对于下面这些句子

只要在语料库中出现一个，其他句子的概率也会相应的增大

2.基于词向量的模型自带平滑化功能(由(3.6)可知,\(p(w|Context(w))\in (0,1)\)不会为0)，不再需要像n-gram那样进行额外处理了

最后，我们回过头来想想，词向量在整个神经概率语言模型中扮演了什么角色呢？训练时，它是用来帮助构造目标函数的辅助参数，训练完成后，它也好像只是语言模型的一个副产品．但这个副产品可不能小觑，下一小节将对其作进一步阐述。

词向量的理解

通过上一小节的讨论，相信大家对词向量已经有一个初步的认识了、接下来，对词向量做进一步介绍。

在NLP任务中，我们将自然语言交给机器学习算法来处理，但机器无法直接理解人类的语言，因此首先要做的事情就是将语言数学化，如何对自然语言进行数学化呢？词向量提供了一种很好的方式．

一种最简单的词向量是one-hot representation就是用一个很长的向量来表示一个词，向量的长度为词典T)的大小N,向量的分量只有一个1，其它全为0，1的位置对应该词在词典中的索引．但这种词向量表示有一些缺点，如容易受维数灾难的困扰，尤其是将其用于DeepLearning场景时；又如，它不能很好地刻画词与词之间的相似性．

另一种词向量是Distributed Representation它最早是Hinton于1986年提出的,可以克服one-hot representation的上述缺点、其基本想法是：通过训练将某种语言中的每一个词映射成一个固定长度的短向量（当然这里的“短"是相对于one-hot representation的“长”而言的），所有这些向量构成一个词向量空间，而每一向量则可视为该空间中的一个点，在这个空间上引人“距离"就可以根据词之间的距离来判断它们之间的（词法、语义上的）相似性了．word2vec中采用的就是这种Distributed Representation的词向量．为什么叫做Distributed Representation？很多人问到这个问题，我的一个理解是这样的：对于one-hotrepresentation，向量中只有一个非零分量，非常集中（有点孤注一掷的感觉）；而对于Distributed Representation，向量中有大量非零分量，相对分散（有点风险平摊的感觉），把词的信息分布到各个分量中去．这一点，跟并行计算里的分布式并行很像。 为更好地理解上述思想，我们来举一个通俗的例子。

上面的例子中，坐标(\(x,y\))的地位就相当于词向量，它用来将平面上一个点的位置在数学上作量化坐标系建立好以后，要得到某个点的坐标是很容易的、然而，在NLP任务中，要得到词向量就复杂得多了，而且词向量并不唯一，其质量依赖于训练语料、训练算法等因素。

如何获取词向量呢？有很多不同模型可用来估计词向量，包括有名的LSA(Latentse-mantic Analysis)和LDA(Latent Dirichlet Allocation)。此外，利用神经网络算法也是一种常用的方法，上一小节介绍的神经概率语言模型就是一个很好的实例．当然，在那个模型中， 目标是生成语言模型，词向量只是一个副产品．事实上，大部分情况下，词向量和语言模型都是捆绑在一起的，训练完成后两者同时得到．用神经网络来训练语言模型的思想最早由百度IDL（深度学习研究院）的徐伟提出（这方面最经典的文章要数Bengio于2003年发表在JMLR上的《ANeuralProbabilisticLanguageModel》，其后有一系列相关的研究工作，其中也包括谷歌Tomas Mikolov团队的word2vec. 一份好的词向量是很有价值的，例如，Ronan Collobert团队在软件包SENNA中利用词向量进行了POS、CHK、NER等任务，且取得了不错的效果（见图6中的表格）．最近了解到词向量在机器翻译领域的一个应用报道是这样的： 文【5】在引言介绍算法原理时举了一个简单的例子，可以帮助我们更好的理解词向量的工作原理，特将其介绍如下。 考虑英语和西班牙语两种语言，通过训练分别得到它们对应的词向量空间\(E(nglish)\)和\(S(panish)\)．从英语中取出五个词one,two，three，four，five，设其在E中对应的词向量分别为\(u_1,u_2,u_3,u_4,u_5\)，为方便作图，利用主成分分析(PCA)降维，得到相应的二维向量\(v_1,v_2,v_3,v_4,v_5\)，在二维平面上将这五个点描出来，如图7左图所示．

类似地在西班牙语中取出（与one，two，three,four，five对应的）uno,dos,tres，cuatro,cinco,设其在5中对应的词向量分别为\(s_1,s_2,s_3,s_4,s_5\)，用PCA降维后的二维向量分别为\(t_1,t_2,t_3,t_4,t_5\),将它们在二维平面上描出来（可能还需作适当的旋转），如图7右图所示.

观察左、右两幅图，容易发现：五个词在两个向量空间中的相对位置差不多，这说明两种不同语言对应向量空间的结构之间具有相似性，从而进一步说明了在词向量空间中利用距离刻画词之间相似性的合理性。

注意，词向量只是针对“词”来提的，事实上，我们也可以针对更细粒度或更粗粒度来进行推广，如字向量([7]),句子尚量和文档向量([6]),它们能为字、句子、文档等单元提供更好的表示。

基于Hierarchical Softmax的模型

有了前面的准备，本节开始正式介绍word2vec中用到的两个重要模型一CBOW模型（Continuous Bag-of-Words Model)和Skip-gram模型（Continuous Skip-gram Model)、关于这两个模型，作者Tomas Mikolov在文[5]给出了如图8和图9所示的示意图．

由图可见，两个模型都包含三层：输人层、投影层和输出层前者是在已知当前词的上下文\(w_{t-2},w_{t-1},w_{t+1},w_{t+2}\)的前提下预测当前词（见图8）；而后者恰恰相反，是在已知当前词的前提下，预测其上下文\(w_{t-2},w_{t-1},w_{t+1},w_{t+2}\)（见图9）。 对于CBOW和Skip-gram两个模型，word2vec给出了两套框架，它们分别基于Hierarchical Softmax和Negative Sampling来进行设计．本节介绍基于Hierarchical Softmax的CBOW和Skip-gram模型．

在§3．2中，我们提到，基于神经网络的语言模型的目标函数通常取为如下对数似然函数 \[ L =\sum_{w\in C}\log p(w|Context(w)) \] 因此，讨论过程中我们应将重点放在\(p(w|Context(w))\)或\(p(Context(w)|w)\)的构造上，意识到这一点很重要，因为它可以让我们目标明确、心无旁骛，不至于陷入到一些繁琐的细节当中去。接下来将从数学角度对这两个模型进行详细介绍。

CBOW模型

本小节介绍word2vec中的第一个模型——CBOW模型

网络结构

图10给出了CBOW模型的网络结构，它包括三层：输入层、投影层和输出层。下面以样本\((Context(w),w)\)为例（这里假设\(Context(w)\)由w前后各c个词构造），对于这三个层做简要说明。

1、输入层：包含\(Context(w)\)中2c个词向量\(v(Context(w)_1),v(Context(w)_2),...v(Context(w)_2c)\in \mathbb{R}^{m}\).这里，m的含义同上表示词向量的长度。

2、投影层：将输入层的2c个向量做求和累加，即\(X_w=\sum_{i=1}^{2c}v(Context(w)_i)\in \mathbb{R}^{m}\).

3、输出层输出层对应一棵二叉树，它是以语料中出现过的词当叶子结点，以各词在语料中出现的次数当权值构造出来的Huffman树．在这棵Huffman树中，叶子结点共\(N(=|D|)\)个，分别对应词典中的词：非叶子结点N一1个（图中标成黄色的那些结点）.

对比§3.3中神经概率语言模型的网络图（见图4）和CBOW模型的结构图（见图10），易知它们主要有以下三处不同： 1.（从输人层到投影层的操作）前者是通过拼接，后者通过累加求和 2.（隐藏层）前者有隐藏层，后者无隐藏层 3.（输出层）前者是线性结构，后者是树形结构

在§3.3介绍的神经概率语言模型中，我们指出，模型的大部分计算集中在隐藏层和输出层之间的矩阵向量运算，以及输出层上的softmax归一化运算、而从上面的对比中可见，CBOW模型对这些计算复杂度高的地方有针对性地进行了改变，首先，去掉了隐藏层，其次，输出层改用了Huffman树，从而为利用Hierarchica1 softmax技术奠定了基础．

梯度计算

Hierarchical softmax是wor2vec中用于提高性能的一项关键技术、为描述方便起见，在具体介绍这个技术之前，先引人若干相关记号．考虑Huffman树中的某个叶子结点，假设它对应词典D中的词w，记 1.\(p^w\):从根结点出发到达w对应叶子结点的路径。 2.\(l^w\):路径的中包含结点的个数． 3.\(p_1^{w},p_2^{w},...p_{l^w}^{w}\):路径中的\(l^w\)个结点，其中\(p_1^{w}\)表示根结点，\(p_{l^w}^{w}\)表示词w对应的结 4.\(d_2^{w},d_3^{w},...p_{l^w}^{w}\in \mathbb{R}^{m}\):词w的Huffman编码，它由\(l^w-1\)位编码构成，\(d_j^w\)表示路径\(p^w\)的中第j个结点对应的编码（根结点不对应编码）． 5.\(\theta_1^w,\theta_2^w,...,\theta_{l^w-1}^w\in \mathbb{R}^{m}\):路径的\(p^w\)中非叶子结点对应的向量，\(\theta_j^w\)表示路径中第j个非叶子结点对应的向量．

注4.1按理说，我们要求的是词典D中每个词（即Huffman树中所有叶子节点）的向量，为什么这里还要为Huffman树中每一个非叶子结点也定义一个同长的向量呢?事实上，它们只是算法中的辅助向量，具体用途在下文中书会为大家解释清楚．

好了，引人了这么一大堆抽象的记号，接下来，我们还是通过一个简单的例子把它们落到实处吧，看图11，仍以预备知识中例2.1为例，考虑词w=“足球”的情形． 图11中由条红色边串起来的5个节点就构成路径，其长度\(l^w\)=5.\(p_1^{w},p_2^{w},p_3^{w},p_4^{w},p_5^{w}\)为路径上的5个结点，其中\(p_1^{w}\)对应根结点\(d_2^{w},d_3^{w},d_4^{w},d_5^{w}\)分别为1，0，0，1，即“足球"的Huffman编码为1001此外\(\theta_1^w,\theta_2^w,\theta_3^w,\theta_4^w\)分别表示路径上个非叶子结点对应的向量.

那么，在如图10所示的网络结构下，如何定义条件概率函数\(p(w|Context(w))\)呢？更具体地说，就是如何利用向量\(X_w\in \mathbb{R}^{m}\)以及Huffman树来定义函数p\(p(w|Context(w))\)呢？以图11中词w=“足球”为例．从根结点出发到达“是球"这个叶子节点，中间共经历了4次分支（每条红色的边对应一次分支），而每一次分支都可视为进行了一次二分类. 既然是从二分类的角度来考虑问题，那么对于每一个非叶子结点，就需要为其左右孩子结点指定一个类别，即哪个是正类（标签为1），哪个是负类（标签为0）．碰巧，除根结点以外，树中每个结点都对应了一个取值为0或1的Huffman编码．因此，一种最自然的做法就是将Huffman编码为1的结点定义为正类，编码为0的结点定义为负类．当然，这只是个约定而已，你也可以将编码为1的结点定义为负类，而将编码为0的结点定义为正类、事实上，word2vec选用的就是后者，为方便读者对照着文档看源码，下文中统一采用后者，即约定 \[ Label(p_i^w)=1-d_i^w,i=2,3,...,l^w \] 简言之就是，将一个结点进行分类时，分到左边就是负类，分到右边就是正类。

根据预备知识2.2中介绍的逻辑回归，易知，一个结点被分为正类的概率是 \[ \sigma (x_w ^{T}\theta)=\frac{1}{1+e^{-x_w ^{T}\theta}} \] 被分为负类的概率就等于 \[ 1-\sigma (x_w ^{T}\theta) \] 注意，上式中有个叫\(\theta\)的向量，它是待定参数，显然，在这里非叶子结点对应的那些向量\(\theta_i^{w}\)就可以扮演参数的角色（这也是为什么将它们取名为的原因）．对于从根结点出发到达“足球”这个叶子节点所经历的4次二分类，将每次分类结果的概率写出来就是

但是，我们要求的是\(p(足球|Context(足球))\)，它跟这4个概率有什么关系呢？关系就是 \[ p(足球|Context(足球))=\prod_{j=2}^{l^w}p(d_j^w|x_w,\theta _{j-1}^w) \]

至此，通过w=“足球”的小例子Hierarchical softmax的基本思想其实就已经介绍完了．小结一下：对于词典D中的任意词些Huffman树中必存在一条从根结点到词w对应结点的路径\(p^w\)（且这条路径是唯一的）．路径\(p^w\)上存在\(l^w-1\)个分支将每个分支看做一次二分类，每一次分类就产生一个概率，将这些概率乘起来就是所需的\(p(w|Context(w))\)， 条件概率\(p(w|Context(w))\)的一般公式可写为 \[ p(w|Context(w))=\prod_{j=2}^{l^w}p(d_j^w|x_w,\theta _{j-1}^w) \] 其中 \[ p(d_j^w|x_w,\theta _{j-1}^w)=\left\{\begin{matrix} \sigma (x_w^T\theta _{j-1}^w),& d_j^w=0; \\ 1-\sigma (x_w^T\theta _{j-1}^w),& d_j^w=1, \end{matrix}\right. \]

或者整体表达式 \[ p(d_j^w|x_w,\theta _{j-1}^w)=[\sigma (x_w^T\theta _{j-1}^w)]^{1-d_j^w}·[1-\sigma (x_w^T\theta _{j-1}^w)]^{d_j^w} \]

将(4.3)代入对数似然函数，便得 \[ \begin{align*} L &=\sum_{w\in c}\log \prod_{j=2}^{l^w}{[\sigma (x_w^T\theta _{j-1}^w)]^{1-d_j^w}·[1-\sigma (x_w^T\theta _{j-1}^w)]^{d_j^w}} \\ &=\sum_{w\in c}\sum_{j=2}^{l^w}{(1-d_j^w)\log [\sigma (x_w^T\theta _{j-1}^w)]+d_j^w\log[1-\sigma (x_w^T\theta _{j-1}^w)] } \end{align*} \] 为下面梯度推导方便起见，将上式中双重求和符号和符号下花括号里的内容记为\(L(w,j)\)，即 \[ L(w,j)=(1-d_j^w)\log [\sigma (x_w^T\theta _{j-1}^w)]+d_j^w\log[1-\sigma (x_w^T\theta _{j-1}^w)] \] 至此，已经推导出对数似然函数，这就是CBOW模型的目标函数，接下来讨论它的优化，即如何将这个函数最大化word2vec里面采用的是随机梯度上升法，而梯度类算法的关键是给出相应的梯度计算公式，因此接下来重点讨论梯度的计算，随机梯度上升法的做法是：每取一个样本\((Context(w),w)\)，就对目标函数中的所有（相关）参数做一次刷新,观察目标函数£易知，该函数中的参数包括向量\(x_w,\theta_{j-1}^w,w\in C,j=2,...,l^w\)。为此：先给出函数\(L(w,j)\)，关于这些向量的梯度．

首先考虑\(L(w,j)\)关于\(\theta_{j-1}^w\)的梯度计算。

于是，\(\theta_{j-1}^w\)的更新公式可写为 \[ \theta_{j-1}^w=\theta_{j-1}^w+\eta [1-d_j^w-\sigma (x_w^T\theta _{j-1}^w)]x_w \] 其中\(\eta\)表示学习率，下同。

接下来考虑\(L(w,j)\)关于\(x_w\)的梯度，观察(4.5)可发现\(L(w,j)\)中关于变量\(x_w\)和\(\theta_{j-1}^w\)是对称的，因此，相应的梯度\(\frac{\partial L(w,j)}{\partial x_w}\)也只需在\(\frac{\partial L(w,j)}{\partial \theta_{j-1}^w}\)的基础上对这两个向量交换位置就可以了，即 \[ \frac{\partial L(w,j)}{\partial x_w}=[1-d_j^w-\sigma (x_w^T\theta _{j-1}^w)]\theta_{j-1}^w \]

读到这里，细心的读者可能已经看出问题来了：我们最终目的是要求字典D中每个词的词向量，而这里的\(x_w\)表示的是\(Context(w)\)中各词向量的累加。那么，如何利用\(\frac{\partial L(w,j)}{\partial x_w}\)来对\(v(\tilde{w}),\tilde{w}\in Context(w)\)进行更新呢？word2vec中做法很简单，直接取 \[ v(\tilde{w}):=v(\tilde{w})+\eta \sum_{j=2}^{l^w}\frac{\partial L(w,j)}{\partial x_w},\tilde{w}\in Context(w) \]

即把\(\sum_{j=2}^{l^w}\frac{\partial L(w,j)}{\partial x_w}\)贡献到\(Context(w)\)中每一个词的词向量上。这个应该很好理解，寂然\(x_w\)本身就是\(Context(w)\)中各词词向量的累加，求完梯度后当然也应该将其贡献到每个分量上去。

下面以样本\((Context(w),w)\)为例，给出CBOW模型中采取随机梯度上升法更新各参数的伪代码

Skip-gram模型

本小节介绍word2vec中另一个模型Skip-gram模型，由于推导过程与CBOW大同小异，因此会沿用上小节引入的记号。

网络结构

图12给出了Skip-gram模型的网络结构，同CBOW模型的网络结构一样，它也包括三层：输人层、投影层和输出层、下面以样本\((w,Context(w))\)为例，对这三个层做简要说明．

1.输人层．只含当前样本的中心词的词向量\(v(w)\in \mathbb{R}^m\)

2.投影层，这是个恒等投影，把\(v(w)\)投影到\(v(w)\).因此，这个投影层其实是多余的，这里之所以保留投影层主要是方便和CBOW模型的网络结构做对比．

3.输出层：和CBOW一样，输出层也是一棵Huffman树。

梯度计算

对于Skip-gram模型，已知的是当前词需要对其上下文\(Context(w)\)中的词进行预测，因此目标函数应该形如(4.2），且关键是条件概率函数\(p(Context(w)|w)\)的构造，Skip-gram模型中将其定义为 \[ p(Context(w)|w)=\prod_{u\in Context(w)}p(u|w), \] 上式中的\(p(u|w)\)可按照上小节介绍的Hierarchical Softmax思想，类似于(4.3)地写为 \[ p(u|w)=\prod_{j=2}^{l^u}p(d_j^u|v(w),\theta _{j-1}^u), \] 其中 \[ p(d_j^u|v(w),\theta _{j-1}^u)=[\sigma (v(w)^T\theta _{j-1}^u)]^{1-d_j^u}\cdot [1-\sigma (v(w)^T\theta _{j-1}^u)]^{d_j^u} \]

将上式依次代回，可得对数似然函数的具体表达式 \[ \begin{align*} L &=\sum_{w\in C}\prod_{u\in Context(w)}\prod_{j=2}^{l^u}{[\sigma (v(w)^T\theta _{j-1}^u)]^{1-d_j^u}\cdot [1-\sigma (v(w)^T\theta _{j-1}^u)]^{d_j^u}}\\ &=\sum_{w\in C}\prod_{u\in Context(w)}\prod_{j=2}^{l^u}{(1-d_j^u)\log [\sigma (v(w)^T\theta _{j-1}^u)]+d_j^u[1-\sigma (v(w)^T\theta _{j-1}^u)]} \end{align*} \]

同样，为下面梯度推导方便起见，将三重求和符号下花括号里面的内容记为\(L(w,u,j)\)，即 \[ L(w,u,j)=(1-d_j^u)\log [\sigma (v(w)^T\theta _{j-1}^u)]+d_j^u[1-\sigma (v(w)^T\theta _{j-1}^u)] \]

至此，已经推导出对数似然函数的表达式，这就是Skip-gram模型的目标函数。接下来同样利用随机梯度上升法对其进行优化，关键是要给出两类梯度。 首先考虑\(L(w,u,j)\)关于\(\theta_{j-1}^u\)的梯度计算

于是，\(\theta_{j-1}^u\)的更新公式可写为 \[ \theta_{j-1}:=\theta_{j-1}+\eta [1-d_j^u-\sigma (v(w)^T\theta_{j-1})]v(w) \]

接下来考虑\(L(w,u,j)\)关于\(v(w)\)的梯度，同样利用\(L(w,u,j)\)中\(v(w)\)和\(\theta_{j-1}^u\)的对称性，有 \[ \frac{\partial L(w,u,j)}{\partial v(w)}=[1-d_j^u-\sigma (v(w)^T\theta _{j-1}^u)]\theta _{j-1}^u \]

于是，更新公式可写为 \[ v(w):=v(w)+\eta \sum_{u\in Context(w)}\sum_{j=2}^{l^u}\frac{\partial L(w,u,j)}{\partial v(w)} \]

下面以样本\((w,Context(w))\)为例，给出Skip-gram模型中采用随机梯度上升法更新各参数的伪代码。

但是，word2vec源码中，并不是等\(Context(w)\)中所有词都处理完才刷新\(v(w)\)而是，每处理完\(Context(w)\)中的一个词u，就及时刷新一次\(v(w)\)，具体为

同样，需要注意的是，循环体内的步3和步4不能交换次序，即\(\theta_{j-1}^u\)要等到e后才更新

基于Negative Sampling的模型

本节将介绍基于Negative Sampling的CBOW和Skip-gram模型，NegativeSampling（简称为NEG)是Tomas Mikolov等人在文[4]中提出的，它是NCE（Noise contrastive Estimation)的一个简化版本，目的是用来提高训练速度并改善所得词向量的质量，与Hierarchicalsoftmax相比，NEG不再使用使用（复杂的）Huffman树，而是利用（相对简单的）随机负采样能大幅度提高性能，因而可作为Hierarchical softmax的一种替代．

CBOW模型

在CBOW模型中，已知词伊的上下文\(Context(w)\)，需要预测\(w\)，因此，对于给定的\(Context(w)\)，词就是一个正样本，其它词就是负样本了．负样本那么多，该如何选取呢？这个问题比较独立，我们放到后面再进行介绍.

假定现在已经选好了一个关于\(Context(w)\)的负样本子集\(NEG(w)\neq 0\)且对\(\forall \tilde{w}\in D\),定义 \[ L^{w}=\left\{\begin{matrix} 1, & \tilde{w}=w;\\ 0,& \tilde{w}\neq w, \end{matrix}\right. \]

表示词\(\tilde{w}\)的标签，即正样本的标签为1，负样本的标签为0.

对于一个给定的正样本\((Context(w),w)\)，我们希望最大化 \[ g(w)=\prod_{u\in \left \{ w \right \} \cup NEG(w)}p(u|Context(w)) \]

其中 \[ p(u|Context(w))=\left\{\begin{matrix} \sigma (x_w^T\theta ^u), &L^w(u)=1; \\ 1-\sigma (x_w^T\theta ^u),& L^w(u)=0, \end{matrix}\right. \] 或者写成整体表达式 \[ p(u|Context(w))=[\sigma (x_w^T\theta ^u)]^{L^w(u)}\cdot [1-\sigma (x_w^T\theta ^u)]^{1-L^w(u)} \]

这里\(x_w\)仍表示\(Context(w)\)中各词的词向量之和，而\(\theta ^u\in \mathbb{R}^m\)表示词u对应的一个（辅助）向量，为待训练参数。

为什么要最大化\(g(w)\)呢？让我们先看看\(g(w)\)的表达式，将(5.2)代入（5.1）,有 \[ g(w)=\sigma (x_w^T\theta ^u)\prod_{u\in \left \{ w \right \} \cup N EG(w)}[1-\sigma (x_w^T\theta ^u)] \]

其中\(\sigma (x_w^T\theta ^u)\)表示当上下文为\(Context(w)\)时，预测中心词为\(w\)的概率，而\(\sigma (x_w^T\theta ^u),u\in NEG(w)\)则表示当上下文为\(Context(w)\)时，预测中心词为的概率（这里可看成一个二分类问题，具体可参见预备知识中的逻辑回归）．从形式上看，最大化g(w),相当于最大化\(\sigma (x_w^T\theta ^w)\)，同时最小化所有的\(\sigma (x_w^T\theta ^u),u\in NEG(w)\).这不正是我们希望的吗？增大正样本的概率同时降低负样本的概率．于是，对于一个给定的语料库\(C\)，函数 \[ G=\prod_{w\in C}g(w) \]

就可以作为整体优化目标。当然，为计算方便，对G取对数，最终的目标函数就是 \[ \begin{align*} L &=\log G=\log \prod_{w\in C}g(w)=\sum_{w\in C}\log g(w)\\ &=\sum_{w\in C}\log \prod_{u\in \left \{ w \right \} \cup NEG(w)}\left \{ [\sigma (x_w^T\theta ^u)]^{L^w(u)}\cdot [1-\sigma (x_w^T\theta ^u)]^{1-L^w(u)} \right \}\\ &=\sum_{w\in C}\log \sum_{u\in \left \{ w \right \} \cup NEG(w)}\left \{L^w(u)\cdot \log [\sigma (x_w^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (x_w^T\theta ^u)] \right \} \end{align*} \]

为下面梯度推导方便起见，将上式双重求和符号下花括号里的内容记为\(L(w,u)\)即 \[ L(w,u)=L^w(u)\cdot \log [\sigma (x_w^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (x_w^T\theta ^u)] \]

接下来利用梯度上升法对（5.3）进行优化，关键是要给出\(L\)的两类梯度，首先考虑\(L(w,u)\)关于\(\theta^u\)的梯度计算。 \[ \begin{align*} \frac{\partial L(w,u)}{\partial \theta ^u} &=\frac{\partial }{\partial \theta ^u}\left \{ L^w(u)\cdot \log [\sigma (x_w^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (x_w^T\theta ^u)] \right \}\\ &=L^w(u)[1-\sigma (x_w^T\theta ^u)]x_w-(1-L^w(u))\sigma (x_w^T\theta ^u)x_w\\ &=\left \{ L^w(u)[1-\sigma (x_w^T\theta ^u)]-(1-L^w(u))\sigma (x_w^T\theta ^u) \right \}x_w\\ &=[L^w(u)-\sigma (x_w^T\theta ^u)]x_w \end{align*} \]

于是\(\theta^u\)的更新公式可写为 \[ \theta^u:=\theta^u+\eta[L^w(u)-\sigma (x_w^T\theta ^u)]x_w \]

接下来考虑\(L(w,u)\)关于\(x_w\)的梯度，同样利用\(L(w,u)\)中\(x_w\)和\(\theta^u\)的对称性，有 \[ \frac{\partial L(w,u)}{\partial \theta x_w}=[L^w(u)-\sigma (x_w^T\theta ^u)]\theta ^u \]

于是利用\(\frac{\partial L(w,u)}{\partial \theta x_w}\)，可得\(v(\tilde{w}),\tilde{w}\in Context(w)\)的更新公式为 \[ v(\tilde{w}):=v(\tilde{w})+\eta \sum_{u\in \left \{ w \right \} \cup NEG(w)}\frac{\partial L(w,u)}{\partial \theta x_w},\tilde{w}\in Context(w). \]

下面以样本\((Context(w),w)\)为例，给出基于Negative Sampling的CBOW模型中采用的随机梯度上升法更新各参数的伪代码

注意，步3.3和步3.4不能交换次序，即\(\theta ^u\)要等贡献到e后才更新

Skip-gram模型

本小节介绍基于Negative Sampling的Skip-gram模型，它和上小节介绍的CBOW模型所用的思想是一样的，因此，这里我们直接从目标函数出发，且沿用之前的记号． 对于一个给定的样本\((w，context(w))\),我们希望最大化 \[ g(w)=\prod_{\tilde{w}\in Context(w)}\prod_{u\in \left \{ w \right \} \cup NEG(w)}p(u|\tilde{w}), \]

其中 \[ p(u|\tilde{w})=\left\{\begin{matrix} \sigma (v(\tilde{w})^T\theta ^u), &L^w(u)=1; \\ 1-\sigma (v(\tilde{w})^T\theta ^u),& L^w(u)=0, \end{matrix}\right. \]

或者写成整体表达式 \[ p(u|\tilde{w})=[\sigma (v(\tilde{w})^T\theta ^u]^{L^w(u)}\cdot [1-\sigma (v(\tilde{w})^T\theta ^u)]^{1-L^w(u)} \]

这里\(NEG^{\tilde{w}}(w)\)表示处理词\(\tilde{w}\)是生成的负样本子集。于是，对于一个给定的语料库C，函数 \[ G=\prod_{w\in C}g(w) \]

就可以作为整体优化的目标。同样，我们取G的对数，最终的目标函数就是 \[ \begin{align*} L &=\log G=\log \prod_{w\in C}g(w)=\sum_{w\in C}\log g(w)\\ &=\sum_{w\in C}\log \prod_{\tilde{w}\in Context(w)}\prod_{u\in \left \{ w \right \} \cup NEG^{\tilde{w}}(w)}\left \{ [\sigma (v(\tilde{w})^T\theta ^u]^{L^w(u)}\cdot [1-\sigma (v(\tilde{w})^T\theta ^u)]^{1-L^w(u)} \right \}\\ &=\sum_{w\in C}\sum_{\tilde{w}\in Context(w)} \sum_{u\in \left \{ w \right \} \cup NEG^{\tilde{w}}(w)}\left \{L^w(u)\cdot \log [\sigma (v(\tilde{w})^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (v(\tilde{w})^T\theta ^u)] \right \} \end{align*} \]

为下面梯度推导方便起见，将三重求和符号下花括号的内容记为\(L(w,\tilde{w},u)\)，即 \[ L(w,\tilde{w},u)=L^w(u)\cdot \log [\sigma (v(\tilde{w})^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (v(\tilde{w})^T\theta ^u)] \]

接下来利用随机梯度上升法对（5.9）进行优化，关键是要给出\(L\)的两类梯度。首先考虑\(L(w,\tilde{w},u)\)关于\(\theta ^u\)的梯度计算 \[ \begin{align*} \frac{\partial L(w,\tilde{w},u)}{\partial \theta ^u} &=\frac{\partial }{\partial \theta ^u}\left \{ L^w(u)\cdot \log [\sigma (v(\tilde{w})^T\theta ^u)]+(1-L^w(u))\cdot \log [1-\sigma (v(\tilde{w})^T\theta ^u)] \right \}\\ &= L^w(u)[1-\sigma (v(\tilde{w})^T\theta ^u)]v(\tilde{w})-[1-L^w(u)]\sigma (v(\tilde{w})^T\theta ^u)v(\tilde{w})\\ &=\left \{L^w(u)[1-\sigma (v(\tilde{w})^T\theta ^u)]-[1-L^w(u)]\sigma (v(\tilde{w})^T\theta ^u) \right \}v(\tilde{w})\\ &=[L^w(u)-\sigma (v(\tilde{w})^T\theta ^u)]v(\tilde{w}) \end{align*} \]

于是，\(v(\tilde{w})\)的更新公式可写为 \[ v(\tilde{w}):=v(\tilde{w})+\eta[L^w(u)-\sigma (v(\tilde{w})^T\theta ^u)]v(\tilde{w}) \] 接下来考虑\(L(w,\tilde{w},u)\)关于\(v(\tilde{w})\)的梯度，利用\(L(w,\tilde{w},u)\)中\(v(\tilde{w})\)和\(\theta ^u\)的对称性，有 \[ \frac{\partial L(w,\tilde{w},u)}{\partial v(\tilde{w})}=[L^w(u)-\sigma (v(\tilde{w})^T\theta ^u)]\theta ^u \]

于是，\(v(\tilde{w})\)的更新公式可写为 \[ v(\tilde{w}):=v(\tilde{w})+\eta \sum_{u\in \left \{ w \right \} \cup NEG^{\tilde{w}}(w)}\frac{\partial L(w,\tilde{w},u)}{\partial v(\tilde{w})} \] 下面以样本\((w,Context(w))\)为例，给出基于Negative Sampling的Skip-gram模型中采用随机梯度上升法更新各参数的伪代码

负采样算法

顾名思义，在基于Negative Sampling的CBOW和Skip-gram模型中，负采样是个很重要的环节，对于一个给定的词\(w\)，如何生成\(NEG(w)\)呢？

词典D中的词在语料c中出现的次数有高有低，对于那些高频词，被选为负样本的概率就应该比较大，反之，对于那些低频词，其被选中的概率就应该比较小．这就是我们对采样过程的一个大致要求，本质上就是一个带权采样问题相关的算法有很多，我之前在博文[19]中就给出过两个具体算法．

下面先用一段通俗的描述来帮助读者理解带权采样的机理.

接下来来谈谈word2vec中具体做法。记\(l_0=0,l_k=\sum_{j=1}^{k}len(w_j),k=1,2,...,N\)，这里\(w_j\)表示词典D中第j个词，则以\(\left \{ l_i \right \}_0^N\)为剖分节点可得到区间[0,1]上的一个非等距剖分，\(I_i=(l_{i-1},l_i),i=1,2,...,N\)为其N个剖分区间。进一步引入区间[0,1]上的一个等距离剖分，剖分节点为\(\left \{ m_j \right \}_{j=0}^M\)，其中\(M\gg N\)，具体见图13给出的示意图。

将内部剖分节点\(\left \{ m_j \right \}_{j=1}^{M-1}\)投影到非等距剖分上，如图13中的红色虚线所示，则可建立\(\left \{ m_j \right \}_{j=1}^{M-1}\)与区间\(\left \{ I_j \right \}_{j=1}^N\)的映射关系 \[ Table(i)=w_k,where m_i\in I_k, i=1,2,...,M-1 \]

有了这个映射，采样就简单了：每次生成一个\([1,M-1]\)间的随机整数\(r\)，\(Table(r)\)就是一个样本，当然，这里还有一个细节，当对\(w_i\)进行负采样时，如果碰巧选到\(w_i\)自己怎么办？那就跳过去，代码也是这么处理的。

值得一提的是，word2vec源码中为词典D中词设置权值时，不是直接用\(counter(w)\)，而是对其做了$\(次幂，其中\)$=0.75，即(5.12)编程了 \[ len(w)=\frac{[counter(w)]^{0.75}}{\sum_{u\in D[counter(w)]^{0.75}}} \]

此外，代码中取\(M=10^8\)(对应源码中变量table_size)，而映射择时通过一个名为InitUnigramTable的函数来完成。

若干代码细节

\(\sigma (x)\)的近似计算

由图像1可见，sigmoid函数a(x)在=0附近变化剧烈，往两边逐渐趋于平缓，当\(x<-6\)或者\(x>6\)时函数值就基本不变了，前者趋于0，后者趋于1.如果在某种应用场景中需要计算大量不同\(s\)对应的\(\sigma (x)\)，且对\(\sigma (x)\)值的精确度不是非常严格，那么，基于上述观察，我们就可以采用这样一种近似计算方法.

将区间[-6，6]等距剖分为K等份，剖分节点分别记为\(x_0,x_1,...,x_k\)它们可表为\(x_i=x_0+ih\)，其中\(x_0=-6\)，步长\(h=\frac{12}{K}\)

事先将\(\sigma (x)\)的值计算好保存起来，计算\(\sigma (x)\)时，采用如下近似公式 \[ \sigma (x)=\left\{\begin{matrix} 0, &x\leq -6 ;\\ \sigma (x_k)&x\in (-6,6); \\ 1& x\geq 6 \end{matrix}\right. \]

其中，\(k\)等于\(\frac{x-x_0}{h}\)对小数点后第一位四舍五入后的整数值（即\(x_k\)表示与x距离最近的剖分节点），或者简单地取为\(\frac{x-x_0}{h}\)的向上或向下取整都可以，公式（6.1）有点像查表，word2vec源码中采用了这种技巧来提高效率。

采用查表方式为什么能提高运算效率呢？因为\(\sigma (x)\)中设计到指数运算\(e^z\)，它是一个初等超越函数，内部实现时通常利用幂级数展开 \[ e^{z}=1+\frac{z}{1!}+\frac{z^2}{w!}+\frac{z^3}{3!}+... \]

取其前\(n\)项做近似计算．其优点是当\(z\)较小（\(|z|<1\)）时，很小的\(n\)就可以做很好的近似，因此计算速度较快；但当\(z\)较大时，展开项数较多，运算量也较大．查表的方法是一次性计算好一批节点的值,以后就只需进行匹配查词了.

词典的存储

在word2vec源码中，词典D是通过哈希技术来存储的，为简单起见，这里直接用代码中用到的变量来进行描述．

首先，开设一个长度为vocab_hash_size（默认值为\(2\times 10^7\)）的整型数组vocab_hash，并将每个分量初始化为-1.然后，为词典D中的词建立如下映射 \[ vocab_hash[hv(w_j)]=j, \]

其中\(hv(w_j)\)表示词\(w_j\)的哈希值，当然，可能出现 \[ hv(w_i)=hv(w_j),i\neq j \]

的情形，此时采用线性探测的开放定址法来解决冲突，即如果计算\(w_i\)的哈希值\(hv(w)\)后，发现vocab_hash中的该位置已被其他词占用，则顺序往下查找，直到找到一个未被占用的位置（若已到数组末尾，则从头开始查找）．

在字典中查找某个词（如\(w\)时，先计算其哈希值hv(w),然后在vocab_hash中找到hv(w)对应的位置，如果\(vocab_hash[hv(w_j)]=-1\)，则表示\(w\)未被收录在词典中；否则，需将\(w\)和\(w_{vocab_hash[hv(w_j)]}\)（即词典中第\(vocab_hash[hv(w_j)]\)个词）进行比较，如果相同，则\(w\) 在词典中的索引就是\(vocab_hash[hv(w_j)]\)，如果不同，则继续往下匹配，直到\(w\)和某个\(w_k\)匹配上或者vocab_hash的值为-1为止，前者表示\(w\)在词典中的索引就是\(k\)，后者表示\(w\)未被收录在词典中。

换行符

构建词典D时，其中包含一个特殊的词，它被放在词典的第一个位置上．该词代表语料中出现的换行符，它虽然也对应一个词向量，但这个向量在训练过程中并不参与运算．其作用主要是用来判别一个句子的结束． word2vec源码的函数sortvocab中有一段代码是删除词典中出现次数小于min_count的低频词，并重新为词典建立哈希映射．由于这段代码前已对字典中的词按照出现次数进行了降序排列，因此，按理说，只需对词典从后往前遍历，剔除出现次数小于min_count的低频词即可，word2vec相应部分的代码是这样的：

注意，换行符对应的词并没有参与排序，因此，当碰巧换行符在语料中出现的次数小于min_count，则有可能多删除一个出现次数大于等于min_count的词．

低频词和高频词

在word2vec源码中，对语料中的低频词和高频词都进行了一些特殊处理。

低频词的处理

利用语料C建立词典时，并不是每个出现过的词都能收录到词典中．代码中引人一个叫做min——count的阀值参数（默认取值为5），若某个词在语料中出现的次数小于它，则将其从词典中删除、如果不想做任何删除，则只需将min_count取为0或1即可注意，这些未能进人词典的词在训练时也是不可见的．可以简单地理解为训练前语料进行了这样一次预处理：将所有出现次数小于min_count的词都挖走了.

此外，为提高效率，在利用语料构建词典时，代码中会根据词典当前的规模来决定是否需要对词典中的低频词进行清理，具体做法如下：预先设定一个阀值参数min_reduce（默认值为1），如果当前词典\(D_{current}\)的规模|\(D_{current}\)|满足 \[ |D_current|>0.7\cdot vocab_hash_size, \] 则从\(D_{current}\)删除所有出现次数小于等于min_reduce的词。

高频词的处理

文[4]中提到，在一个大语料库中，那些最常见的词(the most frequent words）将出现百万甚至千万次，如“的”、“是”等．同低频词相比，这些词提供的有用信息更少．而且这次词对应的词向量在众多样本上进行训练时也不会发生显著的变化、因此，文[4]中提出了一种叫做subsampling的技巧，用来提高训练速度（提高2～10倍，而且可提高那些相对来说词频没那么高的词的词向量精度），具体做法如下：给定一个词频阀值参数（即word2vec源码中叫做sample的变量），词\(w\)将以 \[ prob(w)=1-\sqrt{\frac{t}{f(w)}} \] 的概率被舍弃，其中 \[ f(w)=\frac{counter(w)}{\sum_{u\in D}counter(u)},w\in D \] 表示\(w\)的频率，显然，Subsampling只是针对那些满足\(f(w)>t\)的所谓高频词。

值得一提的是，word2vec源码中实际用的公式不是（6.2），而是 \[ prob(w)=1-(\sqrt{\frac{t}{f(w)}}+\frac{t}{f(w)}) \] 具体实现是这样的：假设当前处理词\(w\)，先计算\(ran=\sqrt{\frac{t}{f(w)}}+\frac{t}{f(w)}\)的值，然后产生一个（0,1）上的随机实数r，如果\(r>ran\)，则舍弃词\(w\)。由于在区间(0,1)上产生一个大于\(ran\)的随机数的概率是\(1-ran\)，因此上述做法就等同于以\(1-ran\)的概率舍弃词\(w\)。

窗口及上下文

模型训练是以行为单位进行的（因此，如果语料文件每行存储一个句子，则训练时每次就是处理一个句子），利用特殊词进行分割．当然，句子不能太长（极端情况就是将整个语料存成一个超长的句子），源码中设置了一个阀值参数MAX_SENTENCE_LENGTH（默认值为1000），如果一行的词数超过MAX_SENTENCE_LENGTH,则强行进行截断．

对于一个给定的行设它包含\(T\)个词，则可以得到\(T\)个训练样本，因为每一个词都对应一个样本．考虑该行中的某个词些只需定义好\(Contex(w)\),就可得到样本\((Contex(w),w)\).

那么如何定义\(Contex(w)\)呢？前面的描述中采用的是在词的前后各取c个词，但word2vec中采用的策略是这样的：事先设置一个窗口阀值参数window（默认值为5），每次构造\(Contex(w)\)时，首先生成区间[1，window]上的一个随机（整）数\(\tilde{c}\),\(w\)前后各取\(\tilde{c}\)个词就构成了\(Contex(w)\).

前文中对比§3、3中神经概率语言模型和CBOW时，我们有提到它们在投影方式上有一个不同，前者采用的是首尾相接，后者则是直接累加，采用直接相加的投影方式除了可使所得向量更短外，还有一个好处：对于一行的首尾的某些词，其前、后的词数可能不足\(\tilde{c}\)个,此时如果是首尾相接的方式则需要补充填充向量，但直接相加就没有这个问题，无非是求和项里少了几项罢了．

自适应学习率

前文中谈及学习率时，统一使用的是常数\(\eta\),而在word2vec源码中，用到了自适应技术.具体是这样的:预先设置一个初始的学习率\(\eta _0\)（默认值为0，025），每处理完10000（源码里直接指定，没有设置参数，但可以根据经验调整）个词，则按照以下公式对学习率进行一次调整 \[ \eta =\eta _0\left ( 1-\frac{word\_count\_actual}{train\_words+1} \right ) \] 其中word_count_actual表示当前已处理过的次数，\(train_{words}=\sum_{w\in D}counter(w)\),+1是为了防止分母为0.

由（6.3）可见，\(\eta\)将随着训练的进行而逐渐变小，且趋于0.但是，学习率也不能过小，因此，源码加入了一个阈值\(\eta_{min}\)，一旦\(\eta< \eta_{min}\)，则将\(\eta\)固定为\(\eta_{min}\)，其中\(\eta_{min}=10^{-4}\cdot \eta_0\).

参数初始化与训练

模型训练采用的是随机梯度上升法，且只对语料遍历一次，这也是其高效的原因之一模型中需要训练的参数包括逻辑回归对应的参数向量，以及词典中每个词的词向量。在对这些参数进行初始化时，前者采用的是零初始化，后者采用的是随机初始化，word2vec源码中的具体公式为 \[ \frac{rand()/RAND_MAX-0.5}{m} \] 易知，初始词向量的分量均落在区间\([-\frac{0.5}{m}，\frac{0.5}{m}]\)，这里m仍表示词向量的长度．

关于词向量和参数向量，word2vec源码中出现了syn0，syn1和synlneg三个一维数组，其中syn0对应Huffman树所有叶子结点的词向量，syn1对应Huffman树中所有非叶子结点的参数向量，syn1neg对应基于Negative Sampling的模型中与词相关的参数向量.

多线程并行

word2vec中支持多线程并行，源码中有个参数num_threads，其中与线程相关的主要代码如下

其中TrainModelThread是单线程训练模块．对于多线程情形，需要对语料文件进行负载平衡地划分，每个线程处理一部分，具体为

其中file_size表示整个训练语料文件的总字节数．由此可见，划分是基于字节而不是基于词.

当然，我们也可以把word2vec作分布式并行实现．不过呢，文國在引言中介绍Skip-gram模型时有提到：

这样的效率应该已经能满足大多数人的要求了吧.

几点疑问和思考

1、word2vec源码的函数TrainModelThread中，当走Hierarchical Softmax那一支时，有一段代码是用来求近似\(\sigma (·)\)值的，具体如下

if(f<=-MAX_EXP)
	continue;
	
else if (f>=-MAX_EXP)
	continue;
	
else
	f = expTable[(int)(f+MAX_EXP)*(EXP_TABLE_SIZE/MAX_EXP/2)];
	
g = (1-vocab[word].code[d]-f)*alpha;

按照公式（6.1），当f<=-MAX_EXP时，应该取f=0;当f>=MAX_EXP时，应该取f=1.代码中的continue简单地跳过去了、显然，当f等于0或1时，代人g中，其值不一定为零，因此，这里应该是有一个近似，但奇怪的是，走NegativeSampling那一支的时候，在相应部分作者又特别注意了这一点，看以下代码片段.

if(f > MAX_EXP)
	g = (label - 1) * alpha;
	
else if (f < -MAX_EXP)
	g = (label - 0) * alpha;

else

不知道作者这样处理是不是为了提高效率。

2、前面讨论算法时，都是假定语料已经分好词．对于英文语料，分词不是什么问题，但对于中文语料，分词的预处理则是必须的，不同分词器会得到不同的分词结果，那么word2vec所得词向量的质量是如何依赖于中文分词的质量的呢？

3、Hierarchical Softmax和Negative Sampling是两大类不同的方法，但word2vec源码中对这两个分支采用的并不是二择一的方式，用户可以通过参数选取（如取negative=5，hs=1）同时选中这两支，相当于是一种混合方法，在这种情况下，训练得到的词向量质量如何呢？

4、投影层采用累积相加的方式，会使得\(Context(w)\)中各词的顺序不再敏感，例如“我爱足球"和“足球爱我"在训练过程中会视为同一样本．因此，如果在投影层换回首尾相接的方式会怎么样呢？

5、word2vec几个模型中的目标函数中均未考虑正则项，如果加人正则会怎么样呢？

6、前文介绍的算法都是针对一个静态的语料库来讨论的，如果用户的语料数据是动态阶段性地获取的，譬如，当前只有一批语料，过一段时间后又有另一批语料,...,针对这种情形，如果想进行增量训练，该如何调整现有的框架？

参考文献

Word2Vec源码解析

基于深度学习的自然语言处理

数据结构和算法——Huffman树和Huffman编码

机器学习算法实现解析——word2vec源码解析