如何通俗理解word2vec

大家好，又见面了，我是你们的朋友全栈君。

前言

今年上半年，我在我的上一篇LSTM博客中写道：“众所周知，我们已经把SVM、CNN、xgboost、LSTM等很多技术，写的/讲的国内最通俗易懂了，接下来，我们要把BERT等技术也写的/讲的国内最通俗易懂，成为入门标准，而且不单单是从NNLM $\rightarrow$ Word2Vec $\rightarrow$ Seq2Seq $\rightarrow$ Seq2Seq with Attention $\rightarrow$ Transformer $\rightarrow$ Elmo $\rightarrow$ GPT $\rightarrow$ BERT，我们希望给所有AI初学者铺路：一步一个台阶，而不是出现理解断层。”

如今惊觉，这简直就是有意无意给自己挖了个大坑，单一个word2vec就让我断断续续看了好几个月（一方面创业嘛你懂的，二方面涉及的东西实在是太多了┭┮﹏┭┮）

今年8月份，因为要写word2vec的笔记，先看我司AI LAB陈博士在机器学习集训营上讲word2vec的视频，让对word2vec有个初步了解（等看过很多资料后，会觉得这个视频讲的足够透彻）；
网上翻阅各种资料，比如类似浅显易懂的word2vec原理讲解、以及用图形象的解释word2vec（一图胜千言）等等。心想，肯定还能写得更通俗易懂的；
继续如饿狼似的在网上查找有没更加通俗易懂的资料，包括本文的最重要的参考之一《word2vec中的数学原理详解》，部分不错的文章则注明作者和链接录入题库；
9月底，发现写清楚word2vec确实没那么简单，涉及的知识点包括神经网络、语言模型、n-gram、One-Hot、NNLM、到CBOW、Skip-gram、哈夫曼编码、反向传播、Hierarchical SoftMax、负采样等等，各种概念，一有不懂，就容易卡壳；
10月下旬，再看张俊林老师关于BERT的文章：NLP中的预训练技术发展史：从Word Embedding到Bert模型，觉得高屋建瓴、通俗细致。其实，之前bert刚火起来的时候，就看过俊林老师这篇文章，当时看的不甚了解，及至后来先学习word2vec和Transformer之后，再看此文，才觉得真是高屋建瓴，甚至醍醐灌顶，是关于bert中文介绍少有的好文章。

至此，拖了近半年之久，终于可以开写word2vec笔记了，本笔记从NNLM起步，会类似铺路一样，逐级介绍相关概念，最终完成整篇文章（关键部分得到AI LAB陈博士的审校确认），且本篇笔记重点对比了2013年Mikolov的原始论文与2014年Rong, X的文章（主要是符号表示，比如前者用N表示词汇表的大小，后者用V表示词汇表的大小，以及网络结构表示上的差别，但本质无差别），以及对训练方法HS的解析，以通俗易懂。

OK，还是那句话，若发现有何问题，欢迎随时不吝指正，thanks。

一、神经网络与语言模型

1.1 神经网络
引入word2vec之前需要先对神经网络的知识有一定了解,。

下图这个是一个简单的三层神经网络，x=[x1,x2,…xK]是模型的输入，中间经过与权重矩阵运算，矩阵运算结果再经过非线性激活函数得到隐层的结果h, 从隐层到输出层同理。

这样从输入层到输出层既有线性变换，又有非线性变换，因此可以更好刻画出输入变量的特征。

值得一提的是，有的神经网络表示中会存在没有隐藏层，只有：输入层、投影层、输出层这三层的神经网络。

为何要提到这点呢？下文你会看到，word2vec中就存在输入层、投影层、输出层三层的表示，没有隐藏层。
1.2 语言模型

语言模型的用处很广泛，比如机器翻译中要经常面对的一个问题就是如何挑选一个概率尽可能大的句子也就是尽量靠谱的句子返回，说的直白点，就是要让整条语句看起来是一句人话。

语言模型有统计语言模型，也有神经语言模型。

1.2.1 统计语言模型：N-gram模型

什么是所谓的统计语言模型(Language Model)呢？简单来说，统计语言模型就是用来计算句子概率的概率模型。计算句子概率的概率模型很多，n-gram模型便是其中的一种。

假设一个长度为m的句子，包含这些词：[(w1,w2,w3,..,wm)，那么这个句子的概率（也就是这m个词共现的概率）是：

一般来说，语言模型都是为了使得条件概率：P(wt|w1,w2,..,wt−1)最大化，不过考虑到近因效应，当前词只与距离它比较近的n个词更加相关(一般n不超过5)，而非前面所有的词都有关。

因此上述公式可以近似为：

上述便是经典的n-gram模型的表示方式。

不过，N-gram模型仍有其局限性。首先，由于参数空间的爆炸式增长，它无法处理更长程的context（N>3）。

其次，它没有考虑词与词之间内在的联系性。例如，考虑”the cat is walking in the bedroom”这句话。

如果我们在训练语料中看到了很多类似“the dog is walking in the bedroom”或是“the cat is running in the bedroom”这样的句子；
那么，哪怕我们此前没有见过这句话”the cat is walking in the bedroom”，也可以从“cat”和“dog”（“walking”和“running”）之间的相似性，推测出这句话的概率。

然而， Ngram模型做不到。

这是因为Ngram本质上是将词当做一个个孤立的原子单元（atomic unit）去处理的。这种处理方式对应到数学上的形式是一个个离散的one-hot向量（除了一个词典索引的下标对应的方向上是1，其余方向上都是0）。

例如，对于一个大小为5的词典：{“I”, “love”, “nature”, “luaguage”, “processing”}，其中的“nature”对应的one-hot向量为：[0,0,1,0,0]。显然，one-hot向量的维度等于词典的大小。

1.2.2 神经语言模型：NNLM模型

接下来，咱们来看一下什么是神经语言模型(NNLM)，NNLM最初由Bengio在2003年发表的一篇论文《A Neural Probabilistic Language Mode》中提出来的，word2vec便是从其中简化训练而来。

咱们来考虑一个词表D的大小为N（相当于总共有N个词，词用w表示，比如N为一万，则是一万个词），词表里每个词w的维度为m，即 $C\epsilon R^{Nm}$ ，如果词的输入是one hot编码，则N = m，另外n表示词w的上下文中包含的词数，不超过5。

Bengio通过下面的一个三层神经网络来计算P(wt|wt−1,wt−2…wt−(n+1))：

首先第一层输入就是前n−1个词“ wt−(n+1), … ,wt-2,wt−1”去预测第 t 个词是 wt 的概率；
然后根据输入的前n−1个词，在同一个词汇表D中一一找到它们对应的词向量；
最后把所有词向量直接串联起来成为一个维度为(n−1)m的向量x 作为接下来三层神经网络的输入（注意这里的“串联”，其实就是n-1个向量按顺序首尾拼接起来形成一个长向量）。
隐藏层到输出层之间有大量的矩阵向量计算，在输出层之后还需要做softmax归一化计算（使用softmax函数归一化输出之后的值是[0,1]，代表可能的每个词的概率。至于为什么要用softmax，请看此文）。

常用于神经网络输出层的激励函数SOFTMAX长什么样子呢？如下图所示

从图的样子上看，和普通的全连接方式并无差异，但激励函数的形式却大不一样。

首先后面一层作为预测分类的输出节点，每一个节点就代表一个分类，如图所示，那么这7个节点就代表着7个分类的模型，任何一个节点的激励函数都是：

其中i 就是节点的下标次序，而 $z_{i} = w_{i}x + b_{i}$ ，也就说这是一个线性分类器的输出作为自然常数e的指数。最有趣的是最后一层有这样的特性：

也就是说最后一层的每个节点的输出值的加和是1。这种激励函数从物理意义上可以解释为一个样本通过网络进行分类的时候在每个节点上输出的值都是小于等于1的，是它从属于这个分类的概率。

训练数据由训练样本和分类标签组成。如下图所示，假设有7张图，分别为飞机、汽车、轮船、猫、狗、鸟、太阳，则图像的分类标签如下表示：

这种激励函数通常用在神经网络的最后一层作为分类器的输出，有7个节点就可以做7个不同类别的判别，有1000个节点就可以做1000个不同样本类别的判断。

神经语言模型构建完成之后，就是训练参数了，这里的参数包括：

词向量矩阵C；
神经网络的权重；
偏置等参数。

训练数据就是大堆大堆的语料库。训练结束之后，语言模型得到了：通过“ wt−(n+1) ,…, wt−1”去预测第 t 个词是 wt 的概率，但有点意外收获的是词向量“ wt−(n+1) ,…, wt−1”也得到了。换言之，词向量是这个语言模型的副产品。

当然，这个模型的缺点就是速度问题, 因为词汇表往往很大，几十万几百万，训练起来就很耗时，Bengo仅仅训练5个epoch就花了3周，这还是40个CPU并行训练的结果。因此才会有了后续好多的优化工作, word2vec便是其中一个。

二 Word2Vec

2.1 什么是词嵌入

在继续聊 Word2vec 之前，先聊聊 NLP (自然语言处理)。NLP 里面，最细粒度的是词语，词语组成句子，句子再组成段落、篇章、文档。所以处理 NLP 的问题，首先就要拿词语开刀。

咱们居住在各个国家的人们通过各自的语言进行交流，但机器无法直接理解人类的语言，所以需要先把人类的语言“计算机化”，那如何变成计算机可以理解的语言呢？

我们可以从另外一个角度上考虑。举个例子，对于计算机，它是如何判断一个词的词性，是动词还是名词的呢？

我们有一系列样本(x,y)，对于计算机技术机器学习而言，这里的 x 是词语，y 是它们的词性，我们要构建 f(x)->y 的映射：

首先，这个数学模型 f（比如神经网络、SVM）只接受数值型输入；
而 NLP 里的词语，是人类语言的抽象总结，是符号形式的（比如中文、英文、拉丁文等等）；
如此一来，咱们便需要把NLP里的词语转换成数值形式，或者嵌入到一个数学空间里；
我们可以把文本分散嵌入到另一个离散空间，称作分布式表示，又称为词嵌入（word embedding）或词向量。
一种简单的词向量是one-hot encoder，所谓 one-hot编码，其思想跟特征工程里处理类别变量的 one-hot 一样，本质上是用一个只含一个 1、其他都是 0 的向量来唯一表示词语。

2.2 Word2Vec登场

当然，传统的one-hot 编码仅仅只是将词符号化，不包含任何语义信息。而且词的独热表示（one-hot representation）是高维的，且在高维向量中只有一个维度描述了词的语义。多高？词典有多大就有多少维，一般至少上万的维度。所以我们需要解决两个问题：1 需要赋予词语义信息，2 降低维度。

这就轮到Word2Vec出场了。

word2vec是Google研究团队里的Tomas Mikolov等人于2013年的《Distributed Representations ofWords and Phrases and their Compositionality》以及后续的《Efficient Estimation of Word Representations in Vector Space》两篇文章中提出的一种高效训练词向量的模型，基本出发点是上下文相似的两个词，它们的词向量也应该相似，比如香蕉和梨在句子中可能经常出现在相同的上下文中，因此这两个词的表示向量应该就比较相似。

实际上，大部分的有监督机器学习模型，都可以归结为：f(x)->y。

在有些NLP问题中，把 x 看做一个句子里的一个词语，y 是这个词语的上下文词语，那么这里的 f 便是上文中所谓的『语言模型』（language model），这个语言模型的目的就是判断 (x,y) 这个样本是否符合自然语言的法则，更通俗点说就是：有了语言模型之后，我们便可以判断出：词语x和词语y放在一起，是不是人话。

当然，前面也说了，这个语言模型还得到了一个副产品：词向量矩阵。

而对于Word2vec 而言，词向量矩阵的意义就不一样了，因为Word2Vec的最终目的不是为了得到一个语言模型，也不是要把 f 训练得多么完美，而是只关心模型训练完后的副产物：词向量矩阵。

我们来看个例子，如何用 Word2vec 寻找相似词：

对于一句话：她们夸吴彦祖帅到没朋友，如果输入 x 是吴彦祖，那么 y 可以是：“她们、夸、帅、没朋友”这些词
现有另一句话：她们夸我帅到没朋友，如果输入 x 是：我，那么不难发现，这里的上下文 y 跟上面一句话一样
从而 f(吴彦祖) = f(我) = y，所以大数据告诉我们：我 = 吴彦祖（完美的结论）

所以说，word2vec模型中比较重要的概念是词汇的上下文，说白了就是一个词周围的词，比如wt的范围为1的上下文就是wt−1和wt+1。

2.3 word2vec模式下的两个模型：CBOW和SkipGram

在word2vec中提出了两个模型(假设上下文窗口为3，图来自2013年Mikolov的原始论文，注意这里没有隐藏层，只有输入层、投影层、输出层，且输入层到投影层不带权重，投影层到输出层带权重)：

CBOW(Continuous Bag-of-Word)：以上下文词汇预测当前词，即用 $w_{t-2}$ 、 $w_{t-1}$ 、 $w_{t+1}$ 、 $w_{t+2}$ 去预测 $w_{t}$
SkipGram：以当前词预测其上下文词汇，即用 $w_{t}$ 去预测 $w_{t-2}$ 、 $w_{t-1}$ 、 $w_{t+1}$ 、 $w_{t+2}$

2.4 输入输出都只有一个词的简单版本(2014年Rong, X版)

假定整个词汇表的大小为V(2013年Mikolov用的N表示词表大小，此处用V，不影响本质)，即假设全世界所有的词语总共有 V 个，这 V 个词语有自己的先后顺序，x 是one-hot编码形式的输入，y 是在这整个词汇表里 V 个词上输出的概率，我们希望跟真实的 y 的 one-hot encoder 一样。

假设『吴彦祖』这个词是第1个词，『我』这个单词是第2个词，那么『吴彦祖』就可以表示为一个 V 维全零向量、把第1个位置的0变成1，而『我』同样表示为 V 维全零向量、把第2个位置的0变成1。这样，每个词语都可以找到属于自己的唯一表示。

我们先来看个最简单的例子，输入输出都只有一个词。上面说到， y 是 x 的上下文，所以 y 只取上下文里一个词语的时候，语言模型就变成：
用当前词 x 预测它的下一个词 y。

其中，V: 词汇表长度; N: 隐层神经元个数，同时也是词向量维度

输入层到隐层的权重矩阵，其实就是词向量矩阵，其中每一行代表一个词的词向量

隐层到输出层的权重矩阵，其中每一列也可以看作额外的一种词向量

看到这，你可能开始纳闷了，怎么前一个图是输入层、投影层、输出层，且输入层到投影层不带权重，投影层到输出层带权重，而这个图是输入层、隐藏层、输出层，且输入层到隐藏层以及隐藏层到输出层都带权重呢？

仔细深究，你会发现第一个图来自2013年Mikolov的原始论文，第二个图来自一些网友推崇的2014年Rong, X的文章，虽然都是讲的Word2Vec，但这两者之间有不少微妙的差别，但再深入一想，好像又没有本质差别：

2013年，Mikolov发表Word2Vec的原始论文，Word2Vec的网络结构里没有隐藏层，只有输入层、投影层、输出层，且输入层到投影层不带权重，因为只是对输入层做累加求和，学习迭代的是原始输入，而投影层到输出层虽然一开始带了权重，但在实际训练的时候，因为投影层到输出层的计算量巨大，所以改了投影层到输出层的网络结构，去掉了权重，且训练用的方法是HS或负采样。
2014年Rong, X在以为“Word2Vec是一个深度学习模型”这个概念的影响下，Word2Vec的网络结构里涉及神经网络中经典的输入层、隐藏层、输出层，通过从输入层到隐藏层或隐藏层到输出层的权重矩阵去向量化表示词的输入，学习迭代的是两个权重矩阵（分别用W、W′表示），当然，从输入层到隐藏层的权重矩阵W的计算量还好（因为隐层的激活函数其实是线性的，相当于没做任何处理，我们要训练这个神经网络，可以用反向传播算法，本质上是链式求导梯度下降那一套。关于如何理解反向传播，请点击此文），但从隐藏层到输出层的权重矩阵W′的计算量巨大，所以和2013年Mikolov的工作一样，也是去掉了权重W′，且训练用的方法也是HS或负采样。

对于2014年Rong, X的工作，有两点值得注意：

第一点，“通过从输入层到隐藏层或隐藏层到输出层的权重矩阵去向量化表示词的输入” 这句说的是啥意思呢？

当模型训练完后，最后得到的其实是神经网络的权重，比如现在输入一个 x 的 one-hot encoder: [1,0,0,…,0]，对应刚说的那个词语『吴彦祖』，则在输入层到隐含层的权重里，只有对应 1 这个位置的权重被激活，当前词和隐藏层的结点一一进行带权重的相乘，相乘后的结果组成一个向量 vx 来表示x，而因为每个词语的 one-hot encoder 里面 1 的位置是不同的，所以，这个向量 vx 就可以用来唯一表示 x。
类似的，输出 y 也是用 V 个结点表示的，对应V个词语，所以其实，我们把输出结点置成 [1,0,0,…,0]，它也能表示『吴彦祖』这个单词，但是激活的是隐藏层到输出层的权重，当前词和输出层的结点一一进行带权重的相乘，相乘后的结果组成一个向量 vy，跟上面提到的 vx 维度一样，并且可以看做是词语『吴彦祖』的另一种词向量。而这两种词向量 vx 和 vy，正是 Mikolov 在论文里所提到的『输入向量』和『输出向量』，一般我们用『输入向量』。

第二点，2014年Rong, X的工作中提到，学习迭代的是两个权重矩阵（分别用W、W′表示），学习W还好，但学习W′的计算量巨大，所以改用的HS或负采样。但对于喜欢刨根问底的同学来说，到底具体是怎么个“还好”，怎么个“计算量巨大”呢？

1 首先，整个网络过程，我们需要做的是用输入的词去预测输出的词。其中输入层的单词 $w_{i}$ 使用one-hot来表示的, 即在上图中x1,x2,x3,…,xV只有xk为1，其余为0，其中k可以是输入的词在词汇表中的索引下标。之后就是经过词向量矩阵W连接输入层和隐藏层。其中由于X中只有一个1，因此经过与W相乘，相当于取出W中的的第k行，实际也就是输入单词的 $w_{i}$ 的N维的词向量，使用 $v_{wI}$ 表示，来作为隐藏层的值，注意word2vec的隐藏层并没有激活函数：

然后考虑从隐层的h到输出层Y，同样h经过矩阵W′相乘，得到一个V×1的向量u:

其中u中的每个元素uj 就是W′的第 j 列用表示, 与h做内积得到：，含义就是词汇表中第j个词的分数，我们的目的就是要根据输入词 $w_{i}$ 去预测输出的词，因此预测的词就取分数最高的即可。

这里为了方便概率表示，使用softmax将u归一化到[0,1]之间, 从而作为输出词的概率, 其实是一个多项分布, 也就是上图中的y:

其中 $v_{w}$ 与都称为词w的词向量，不过前面说过了，一般使用前者作为词向量，而非后者。

至此前向过程完成，就是给定一个词作为输入，来预测它的上下文词，还是比较简单的，属于简化版的神经语言模型。这个过程中需要用到的参数有两个词向量矩阵W,W′，下面就是重点了，介绍如何根据语料库来训练模型，更新参数，得到最终的词向量。

2 接着，明确训练数据的格式，对于一个训练样本(wi, wo) ，输入是词wi的one -hot编码，其维度定义为V的向量x，模型预测的输出同样也是一个维度为V的向量y，同时真实值wo也是用one-hot表示，记为t= [ 0,0,0..1,0,0] ，其中假设tj*= 1，也就是说j*是真实单词在词汇表中的下标，那么根据最大似然或者上面的语言模型，目标函数可以定义如下: .

一般我们习惯于最小化损失函数，因此定义损失函数:

然后结合反向传播一层层求梯度，使用梯度下降来更新参数。
先求隐层到输出层的向量矩阵W’的梯度：

这里面的 $y_{j}$ 和 $t_{j}$ 分别是预测和真实值的第j项，hi是隐层的第 i 项。
考虑：，直接对原始求导, 如下:
先考虑E的对数部分:

再看对 $u_{j^{}}$ 的梯度，综合求导。这个减法可以理解为输出层的第 j 项为预测值与真实值的差
因此梯度下降更新公式为：

整合为W’的列向量的形式如下:

也就是说对每个训练样本都需要做一次复杂度为V的操作去更新W’。
3 最后，考虑隐层h的更新,其实也是输入层到隐层的矩阵W的更新，继续反向传播，跟神经网络的相同，输出层的V个神经元都会影响 $h_{i}$ ：

其中是W’的第 i 行，这里为了方便书写，令，因此整合成整个隐层的向量h：

得到一个N维的向量，上面已经介绍过，h就是词向量矩阵W的一行：，但是因为X中只有一个1，因此每次只能更新的一行 $v_{w_I}$ ，其余行的梯度= 0，所以 $v_{w_I}$ 的更新公式为:

到此为止，一个训练样本的反向传播训练过程就为止了。我们可以看到，对于输入层到隐层的矩阵W，我们每次训练只需要更新一行向量即可，而对于隐层到输出层的矩阵W′的所有N×V个元素都需要更新一遍，毕竟因为是全连接，这里的计算量还是很大的。

OK，结果相信大家已经看到了，最终词向量的维度（与隐含层结点数一致）一般情况下要远远小于词语总数 V 的大小，所以 Word2vec 最有价值的是让不带语义信息的词带上了语义信息，其次把词语从 one-hot encoder 形式的表示降维到 Word2vec 形式的表示。

2.5 CBOW的一个示例(2014年Rong, X版)

上文我们看了输入输出只有一个词的情况，接下来，我们看下Word2Vec中上下文预测中心词的情况，即CBOW。

CBOW 模型训练的基本步骤包括：

将上下文词进行 one-hot 表征作为模型的输入，其中词汇表的维度为 V，上下文单词数量为C ；
然后将所有上下文词汇的 one-hot 向量分别乘以输入层到隐层的权重矩阵W；
将上一步得到的各个向量相加取平均作为隐藏层向量；
将隐藏层向量乘以隐藏层到输出层的权重矩阵W’；
将计算得到的向量做 softmax 激活处理得到 V 维的概率分布，取概率最大的索引作为预测的目标词。

下面以知乎网友 crystalajj 提供的 PPT 为例看一下 CBOW 模型训练流程。

假设我们现在的Corpus是这一个简单的只有四个单词的document：{I drink coffee everyday}
我们选coffee作为中心词，window size设为2，也就是说，我们要根据单词”I”,”drink”和”everyday”来预测一个单词，并且我们希望这个单词是coffee。

1 将上下文词和目标词都进行 one-hot 表征作为输入：

2 然后将 one-hot 表征结果分别乘以3×4的输入层到隐藏层的权重矩阵W，这个矩阵也叫嵌入矩阵，可以随机初始化生成。

3 将得到的结果向量求平均作为隐藏层向量：

4 然后将隐藏层向量乘以4×3的隐藏层到输出层的权重矩阵W’，这个矩阵也是嵌入矩阵，可以初始化得到。得到输出向量：

5 最后对输出向量做 softmax 激活处理得到实际输出，并将其与真实标签做比较，然后基于损失函数做梯度优化训练。

以上便是完整的 CBOW 模型计算过程，也是 word2vec 将词汇训练为词向量的基本方法之一。

无论是CBOW 模型还是skip-gram 模型，word2vec 一般而言都能提供较高质量的词向量表达，下图是以 50000 个单词训练得到的 128 维的 skip-gram 词向量压缩到 2 维空间中的可视化展示图：

可以看到，意思相近的词基本上被聚到了一起，也证明了 word2vec 是一种可靠的词向量表征方式。

三 CBOW

3.1 CBOW的三层正式结构(2013年Mikolov版)

我们已经知道，CBOW(Continuous Bag-of-Word)的目标是：以上下文词汇预测当前词，即用 $w_{t-2}$ 、 $w_{t-1}$ 、 $w_{t+1}$ 、 $w_{t+2}$ 去预测 $w_{t}$ ，我们事先定义context(w)表示词w的上下文，即w周边的词的集合。

对于2013年Mikolov的原始论文，前面说了，CBOW包括以下三层：

输入层：包含context(w)中2c个词的词向量 $v\left ( Context (w_{1}) \right )$ 、 $v\left ( Context({w2}) \right )$ 、 $v\left ( Context({w2c}) \right )\epsilon R^{m}$ ，其中，v表示单词的向量化表示函数，相当于此函数把一个个单词转化成了对应的向量化表示（类似one-hot编码似的），2c表示上下文取的总词数，m表示向量的维度；
投影层：将输入层的2c个向量做累加求和；
输出层：按理我们要通过确定的上下文决定一个我们想要的中心词wt，但怎么决定想要的中心词具体是{w1 w2 .. wt .. wN}中的哪个呢？通过计算各个可能中心词的概率大小，取概率最大的词便是我们想要的中心词，相当于是针对一个N维数组进行多分类，但计算复杂度太大，所以输出层改造成了一棵Huffman树，以语料中出现过的词当叶子结点，然后各个词出现的频率大小做权重。

输出层为何要改造成Huffman树呢，相信有的读者已经意识到了，为了用优化后的训练方法Hierarchical SoftMax。

3.2 优化策略：从Huffman树到Hierarchical SoftMax

因为前面我们提到不论是2013年Mikolov的原始论文中，还是2014年Rong, X的文章中，虽然两者从输入层到投影层没有权重无所谓权重计算，或输入层到隐藏层的权重W（对于每一个训练样本，CBOW更新W的C行，SG更新W其中一行，也就是每次更新有限个词的词向量）的计算量都还好，但前者从投影层到输出层以及后者从隐藏层到输出层的权重W′则不同了。

考虑到计算量大的部分都是在隐层到输出层上，尤其是W′的更新。因此word2vec使用了两种优化策略：Hierarchical Softmax 和 Negative Sampling。二者的出发点一致，就是在每个训练样本中，二者都不再使用W′这个矩阵。

这里只介绍其中一种优化算法：Hierarchical SoftMax。

首先，Hierarchical SoftMax(HS)并不是word2vec提出来的, 而是之前Bengio在2005年最早提出来专门为了加速计算神经语言模型中的softmax的一种方式。HS基于哈夫曼树(一种二叉树)将N维的多分类问题变为了一个log次的二分类的问题。

举个例子，比如围绕“我喜欢观看巴西足球世界杯”这句话构造Huffman树，而对其中的足球一词进行Huffman编码，当然，在编码的过程中我们得事先定义一套符号：

红色边串起来构成的路径便是足球一词的路径 $p^{w}$ ；
路径 $p^{w}$ 的长度定义为 $l^{w}$ ，即路径 $p^{w}$ 中包含的结点个数， $l^{w}$ = 5；
$p_{l}^{w}$ 表示词w对应的结点，所以 $p_{1}^{w}$ 、 $p_{2}^{w}$ 、 $p_{3}^{w}$ 、 $p_{4}^{w}$ 、 $p_{5}^{w}$ 便为路径 $p^{w}$ 上的五个结点，其中 $p_{1}^{w}$ 对应根结点；
$d_{j}^{w}$ 定义为路径 $p^{w}$ 中第j个结点所对应的编码，所以 $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}$ 分别表示 $p^{w}$ 上4个非叶子结点对应的向量。

我们看到，从根结点到叶子结点足球一词，咱们经历了4次分支，每一次分支都相当于一二分类，而每一次分类做的决定：往左走还是往右走，都决定了其编码是0还是1，进一步，可以假定往左走为负设为1，往右走为正设为0（当然我们也可以往左为正设为1 往右走为负设为0，但本质上这不关键，考虑到2013年原始论文中Word2Vec约定左为负右为正，咱们便采取这种规则）。

一个结点被分为正类的概率是多大呢？采用logistic回归方法分类（对应的激活函数为sigmoid函数），一个结点被分为正类的概率是

于是被分为负类的概率自然就是

对于从根结点出发到达“足球”这个叶子结点所经历的4次二分类，将每次分类结果的概率写出来就是

第1次：；
第2次：; .
第3次：;
第4次：

但是，我们要求的是p(足球|Contex(足球))，它跟这4个概率值有什么关系呢?关系就是

至此，通过w = “足球”的这个例子，Hierarchical Softmax的基本思想其实就已经介绍完了，隐层到输出层的计算量从O(V)，利用Huffman树降为了O(logV)，相当于本质上咱们把 N 分类问题变成了 log(N)次二分类问题。

相当于对于词典中的任意词w，Hufman树中必存在一条从根结点到词w对应结点的路径 $p^{w}$ (且这条路径是唯一的)。路径 $p^{w}$ 上存 $l^{w}-1$ 个分支，将每个分支看做一次二分类，每一次二分类就产生一个概率，将这些概率乘起来，就是所要求的p(w|Context(w))。

条件概率p(w|Context(w))的一般公式可写为

其中

或者写成整体表达式

通过之前对n-gram模型的分析，已知基于神经网络语言模型的目标函数通常取为如下的对数似然函数

将p(w|Context(w))的公式代入上述对数似然函数的目标函数式中，可得

为下面梯度推导方便起见，将上式中双重求和符号下花括号里的内容简记为，即

至此，得到的这个对数似然函数，便是CBOW模型的目标函数，接下来讨论它的优化：即如何将这个函数最大化。

word2vec里面采用的是随机梯度上升法，而梯度类算法的关键是给出相应的梯度计算公式，因此接下来重点讨论梯度的计算。

随机梯度上升法的做法是：每取一个样本(Context(w),w)，就对目标函数中的所有相关的参数做一一次更新，观察目标函数易知，该函数中的参数包括向量 $x_{w}$ 、 $\theta _{j-1}^{w}$ 、w、j，为此，先给出函数关于这些向量的梯度

于是， $\theta _{j-1}^{w}$ 的更新公式可写为

其中， $\eta$ 表示梯度。

接下来，接下来考虑关于 $x_{w}$ 的梯度。

观察之前这个式子可发现，中关于变量 $x_{w}$ 和 $\theta _{j-1}^{w}$ 是对称的(即两者可交换位置)，因此，相应的梯度也只需在的基础上对这两个向量交换位置就可以了，即，

到这里，细心的读者可能已经看出问题来了:我们的最终目的是要求词典中每个词的词向量，而这里的 $x_{w}$ 表示的是Context(w)中各词词向量的累加.那么，如何利用对进行更新呢? word2vec中的做法很简单，直接取

即把贡献到Context(w)中每一个词的词向量上。这个应该很好理解，既然 $x_{w}$ 本身就是Context(w)中各词词向量的累加，求完梯度后当然也应该将其贡献到每个分量上去。

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

注意，上述步骤3.3和步骤3.4不能交换次序，即 $\theta _{j-1}^{w}$ 应等贡献到e后再做更新。

我们再次总结下CBOW中对词向量（源码中对应 syn0）的训练步骤，如下：

读取语料，统计词频信息
构建词典，并初始化Huffman树以及随机初始化每个词的对应向量（维度默认是200）
以行为单位训练模型（输入文件都在一行上，会按照最大1000个词切割为多行）
获取当前行中的一个输入样本（当前词向量以及相邻几个的词的词向量）
累加上下文词向量中每个维度的值并求平均得到投影层向量X(w)（neu1）
遍历当前词到根节点（输出层的Huffman树）经过的每个中间节点
计算中间节点对应的梯度 g * 学习速率（与中间节点的权重向量 syn1 和投影层向量 neu1 相关）
刷新投影层到该中间节点的误差向量（与梯度和中间节点向量相关）
刷新中间结点向量（与梯度和投影层向量相关）
刷新上下文词向量（其实就是将误差向量累加到初始向量中）

流程懂了，coding则再不是难事：

    word = sen[sentence_position];
    if (word == -1) continue;
    for (c = 0; c < layer1_size; c++) neu1[c] = 0;
    for (c = 0; c < layer1_size; c++) neu1e[c] = 0;
    next_random = next_random * (unsigned long long)25214903917 + 11;
    b = next_random % window; //随机取窗口

    if (cbow) {  //train the cbow architecture
      // in -> hidden
      //输入层到隐藏层
      cw = 0;
      for (a = b; a < window * 2 + 1 - b; a++) if (a != window) {
        c = sentence_position - window + a;
        if (c < 0) continue;
        if (c >= sentence_length) continue;
        last_word = sen[c];
        if (last_word == -1) continue;
        //cbow 将上下文词的vector 相加
        for (c = 0; c < layer1_size; c++) neu1[c] += syn0[c + last_word * layer1_size];
        cw++;
      }

      if (cw) {
        //归一化，上下文词的个数
        for (c = 0; c < layer1_size; c++) neu1[c] /= cw;
        //hierarchical softmax
        if (hs){
          for (d = 0; d < vocab[word].codelen; d++) {
            f = 0;
            l2 = vocab[word].point[d] * layer1_size;
            // Propagate hidden -> output
            for (c = 0; c < layer1_size; c++) 
              f += neu1[c] * syn1[c + l2];
            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' is the gradient multiplied by the learning rate
            // g 是梯度乘以学习速率
            g = (1 - vocab[word].code[d] - f) * alpha;
            // Propagate errors output -> hidden
            // 累计误差率
            for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1[c + l2];
            // Learn weights hidden -> output
            // 更新参数权重值
            for (c = 0; c < layer1_size; c++) syn1[c + l2] += g * neu1[c];
          }
        }

OK，大功告成。至于对于来自2014年Rong, X的文章来说，CBOW 用上下文预测这个词的网络结构如下（跟 Skip-gram 相似，只不过：Skip-gram 是预测一个词的上下文）：