【万字长文】Word2Vec计算详解（三）分层Softmax与负采样

【万字长文】Word2Vec计算详解（三）分层Softmax与负采样

写在前面

第三部分介绍Word2Vec模型的两种优化方案。

【万字长文】Word2Vec计算详解（一）CBOW模型 markdown行 9000+
【万字长文】Word2Vec计算详解（二）Skip-gram模型 markdown行 12000+
【万字长文】Word2Vec计算详解（三）分层Softmax与负采样 markdown行 18000+

优化

在原本的Word2Vec模型的 Softmax 层中，对于每一次预测，我们都要计算所有$V$个单词出现的概率，这在数量级为很大的语料库中，计算的消耗是十分巨大的。下面将介绍两种优化方式，它们均以此为切入点，优化Softmax的计算。

在分层 Softmax中，由于使用了 Huffman 树，我们最多计算$V$个单词的概率，平均计算为 $logV$次，相比与原来的 $V$次计算，在数量级巨大时，优化计算十分明显。例如当 $V=1000000$ 时，在 Softmax 层中，我们将计算 $1000000$ 次 $e^x$运算，而$log(1000000)\approx 14$ 次(Sigmoid运算)，$\frac{V}{logV}=\frac{1000000}{14}\approx 72382$倍，这个优化十分巨大，我们接下来进入 H-Softmax 的介绍。

分层 Softmax

Hierachical Softmax（分层Softmax）的基本思想就是首先将词典中的每个词按照词频大小构建出一棵 Huffman 树，保证词频较大的词处于相对比较浅的层，词频较低的词相应的处于 Huffman 树较深层的叶子节点，每一个词都处于这棵 Huffman 树上的某个叶子节点。然后我们根据我们所生成的 Huffman 树，我们将从根节点出发，计算并判断结果单词是在左子树的得分大还是在右子树的得分大，进入得分较大的分支所在的下一个节点。递归执行当前节点到达叶子节点时，代表我们找到了预测结果单词。将路径上的得分进行 Sigmoid 转换成概率，我们就可以得到这个概率（得分越高代表概率越大）。

我们本节以 CBOW 模型为例讲述分层 Softmax ，使用了分层 Softmax 进行优化的 CBOW 模型如图下所示。与 CBOW 模型优化前进行对比，可以发现加权平均层以及其之前的层与原来的 CBOW 模型一致。主要的变化是在是在权重输出层和Softmax层，我们将其优化成 H-Softmax 层。我们将在 H-Softmax 层中详细介绍。现在我们回顾一下 CBOW 模型加权平均层及其之前层的处理。

预处理

简单介绍模型输入前的处理。给定一个语料库 text，我们要将其处理成能够用于模型输入的 one-hot 向量。首先去重，然后将单词与标点符号按读入顺序放入集合corpus，并另外存储一份单词与索引直接查询的字典，word_to_id 和 id_to_word。

随后是将单词集合corpus也就是词汇表Vocabulary转换为 one-hot 表示

模型输入

在模型中，将一个词的上下文词表示为独热编码（one-hot encoding）向量然后并作为模型的一个输入。上下文的词的多少取决于窗口大小 $C$，于是我们的输入$X=(x_{i-c},x_{i-c+1},\dots ,x_{i-1}\in {\mathbb{R}}^{V\times 2C},x_{i+1},\dots ,x_{i+c})$，$x_i$为目标单词，其中 $x_i\in {\mathbb{R}}^{V\times 1}$。

权重输入层

在这一层，我们将目标单词$x_i$的上下文的 one-hot 编码与隐藏层的权重输入矩阵 $W$ 相乘再加上置偏值 $b\in {\mathbb{R}}^{D\times 1}$ 得到 $x_j^{\prime }$，即 $X_j^{\prime }=W{X}_j+b$， 其中 $x_j^{\prime }\in {\mathbb{R}}^{D\times 1}$，$j=(i-C,i-C+1,\dots ,i-1,i+1,\dots ,i+C)$。写成矩阵的形式为

$$X^{\prime }=WX+b$$

加权平均层

我们将输入层得到的所有 $x_j^{\prime }$ 进行加权平均得到 $h$。

$$h=\sum _{j=i-C,j\ne i}^{i+C}{x}_j^{\prime }=\frac{1}{2C}(x_{i-C}^{\prime }+\dots x_{i-1}^{\prime }+x_{i+1}^{\prime }+\cdots +x_{i+C}^{\prime })$$

其中 $C$ 是窗口大小， $h\in {\mathbb{R}}^{D\times 1}$。写成矩阵的形式为

$$h=\frac{1}{2C}{X}^{\prime }\vec{j}$$
其中$\vec{j}=\left[1,1,\dots ,1,1\right]\in {\mathbb{R}}^{2C\times 1}$。

接下来我们开始进入真正的分层 Softmax 模块，即 分层Softmax 层。分层 Softmax 层 的输入是隐藏层的向量 $h$，输入是预测的单词。

分层 Softmax 预处理

在正式进入 分层Softmax层 前我们还有一些预处理操作，即为词汇表构建 Huffman 树。Huffman 树的基础是词汇表中的词频，于是我们简单修改 preprocess函数，统计出词汇表中的每个单词的词频，并加入到返回值中，具体代码见附录优化中的分层Softmax预处理。

我们的目标是通过数组下标为单词索引，值为词频的数组word_count（由preprocess函数生成，在返回值中），来构建 Huffman 树，并生成每个单词对应的路径序列。Huffman 树的构建和路径序列生成的过程步骤如下。

1.初始化优先队列
给定单词集合 { w 1 , w 2 , … , w n } \{w_1, w_2, \ldots, w_n\} {w1​,w2​,…,wn​} 与它们的词频 { f ( w 1 ) , f ( w 2 ) , … , f ( w n ) } \{f(w_1), f(w_2), \ldots, f(w_n)\} {f(w1​),f(w2​),…,f(wn​)}，初始化优先队列 $Q$，使所有节点按词频从小到大排序。每个节点 $N_i$ 表示单词 $w_i$ 和其词频 $f(w_i)$。
定义节点 $N_i$如下：
$$N_i=(w_i,f(w_i))$$
初始化优先队列 $Q$：
$$Q=\text{min-heap}(\{(w_1,f(w_1)),(w_2,f(w_2)),\dots ,(w_n,f(w_n))\})$$

2.构建Huffman树
重复以下步骤直到 $Q$ 中只剩一个节点：
(1) 从 $Q$ 中取出两个词频最小的节点 $N_{\text{min1}}$ 和 $N_{\text{min2}}$。（通常情况下，存在两个节点值相同的情况，这时我们按照队列Q的入队顺序进行提取即可）
(2) 创建一个新的内部节点 $N_{\text{new}}$，其词频为两子节点词频之和：
$$N_{\text{new}}=(N_{\text{min1}},N_{\text{min2}},f(N_{\text{min1}})+f(N_{\text{min2}}))$$
(3) 将 $N_{\text{new}}$ 添加到 $Q$，移除 $N_{\text{min1}}$ 和 $N_{\text{min2}}$。

3.生成路径序列
为每个单词 $w_i$ 生成从根节点到叶子节点的路径序列 $P(w_i)$。路径中向左用“0”表示，向右用“1”表示：
P ( w i ) = { d 1 , d 2 , … , d k } P(w_i) = \{d_1, d_2, \ldots, d_k\} P(wi​)={d1​,d2​,…,dk​}
其中 $d_j$ 表示第 $j$ 次向左或向右的决策（“0”表示左，“1”表示右）。

根据上面的步骤，Python的代码实现见附录优化中的构建Huffman树程序代码。

至此我们完成了分层 Softmax 层的预处理，即得到了我们的Huffman树以及对应的路径信息，下面正式进入 分层Softmax 层的介绍。

分层 Softmax 层

对于预处理得到的 Huffman 树，我们为每一个非叶子节点设置一个参数向量 $\theta \in {\mathbb{R}}^{D\times 1}$ 。对于每个节点的输入均是隐藏层的 $h$，将对应的 $\theta$ 与 $h^T$ 相乘，加上置偏值 $b^{\prime }$，然后取 Sigmoid 得到正向的概率 $P_i^1$。那么负向的概率就是 $P_i^0=1-P_i^1$。

$$正向概率：P_i^1=\sigma (h^T{\theta }_i+b_i^{\prime })=\frac{1}{1+e^{-h^T{\theta }_i+b_i^{\prime }}}$$
$$负向概率：P_i^0=1-\sigma (h^T{\theta }_i+b_i^{\prime })$$

我们依据计算的正向概率和负向概率，按 Huffman 树从根节点到叶子节点单词的路径上的概率$P_i^d$进行连乘可以得到每个叶子节点单词的概率，即

$$P(wor{d}_i)=\prod _{i=1}^l{P}_i^d$$
其中 $l$ 为路径长度，$d$ 只能从0或1中选，即 d ∈ { 0 , 1 } d \in \{0,1\} d∈{0,1}。

然后我们取最大概率的单词作为预测的单词结果。

简单的分层Softmax例子

下面按照原来 CBOW 模型中的例子继续详细介绍下优化后分层 Softmax层 模型预测部分的计算过程。

首先我们的语料库为 text = ‘The cat plays in the garden, and the cat chases the mouse in the garden.’。窗口大小 $C=2$，隐藏层的维数 $D=4$ ，并且要给定 plays 的上下文进行预测。我们可以得到模型输入是$x_0$ ， $x_1$ ， $x_3$ ， $x_0$，对应单词分别为 the、cat、in、the。则 $X=(x_0,x_1,x_3,x_0)$，在下方展示。 我们对输入权重权重矩阵 $W$ 进行初始化，$W$初始值与原来的CBOW模型中的一致，我们有如下的信息。

$$X=(x_0,x_1,x_3,x_0)=\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right],b=\left[\begin{array}{c}0.0513\\ -1.1577\\ 0.8167\\ 0.4336\end{array}\right]$$

$$W=\left[\begin{array}{cccccccccc}-0.2047& 0.4789& -0.5194& -0.5557& 1.9657& 1.3934& 0.0929& 0.2817& 0.769& 1.2464\\ 1.0071& -1.2962& 0.2749& 0.2289& 1.3529& 0.8864& -2.0016& -0.3718& 1.669& -0.4385\\ -0.5397& 0.4769& 3.2489& -1.0212& -0.577& 0.1241& 0.3026& 0.5237& 0.0009& 1.3438\\ -0.7135& -0.8311& -2.3702& -1.8607& -0.8607& 0.5601& -1.2659& 0.1198& -1.0635& 0.3328\end{array}\right]$$

接下来是权重输入层的运算。我们将 $W$ 与 $X$ 进行矩阵乘法运算再加上置偏值 $b$，计算得到 $X^{\prime }$。

$$X^{\prime }=WX+b=\left[\begin{array}{cccc}-0.1533& 0.5302& -0.5043& -0.1533\\ -0.1506& -2.4539& -0.9288& -0.1506\\ 0.277& 1.2936& -0.2044& 0.277\\ -0.2798& -0.3974& -1.427& -0.2798\end{array}\right]$$

接下来进行加权平均层的计算，也就是将 $X^{\prime }$每行中的 $4$个值进行相加，得到 $4\times 1$ 的向量 $h$ 。

$$h=\frac{1}{4}{X}^{\prime }=\frac{1}{4}\left[\begin{array}{c}-0.1533+0.5302-0.5043-0.1533\\ -0.1506-2.4539-0.9288-0.1506\\ 0.277+1.2936-0.2044+0.277\\ -0.2798-0.3974-1.427-0.2798\end{array}\right]=\left[\begin{array}{c}-0.0701\\ -0.9209\\ 0.4108\\ -0.596\end{array}\right]$$

至此，分层Softmax层 前的准备运算工作已经完成，下面详细介绍 分层Softmax 层的计算。

首先是分层 Softmax 的预处理，我们通过对语料库使用改进的 preprocess 函数处理（参考分层 Softmax 预处理中的preprocess函数代码），我们可以得到词频信息如下表所示。

index	0	1	2	3	4	5	6	7	8	9
$x_i$	$x_0$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$x_8$	$x_9$
word	the	cat	plays	in	garden	,	and	chases	mouse	.
frequency	5	2	1	2	2	1	1	1	1	1

preprocess 函数得到后的结果（词汇表、词频信息）

简单介绍下 Huffman 树的生成的过程，首先将所有节点放入到优先队列中，每次取出两个最小频次的两个索引，例如2、6，我们组成新的节点node1，该节点的频次（权重）为2。同理我们用7、8和5、9组合成node2（权重2）和node3（权重2）节点，此时队列中最小的频次（权重）为2。我们继续取出节点进行合并，过程依次为将1、3合并为node4（权重4），node2、4合并为node5（权重4），node1、node3合并为node6（权重4），node4、node5合并成node7（权重8），然后将node6和1合并成node8（权重9），最后将node7和node8合并为node9（权重17）得到Huffman树，如下图所示。

我们规定，对应于每一个非叶子节点，向左子树方向的编码为 0 ，向右子树方向的编码为 1 。根据路径我们可以得到每个单词的路径，如下图。根据下图我们可以的得到路径信息，如下表所示。

index	0	1	2	3	4	5	6	7	8	9
word	the	cat	plays	in	garden	,	and	chases	mouse	.
path	11	000	1011	001	011	1000	1010	0101	0100	1001

词汇表经过Huffman树处理后对应单词的索引以及的路径信息

由于一共有十个单词，生成对应的 Huffman 树时，有 9 个非叶子节点，我们按顺序将这 9 个非叶子节点标记为 ${\theta }_{1\sim 9}$，并对其以及对应的置偏值$b^{\prime }$进行初始化，如下图所示。

$$({\theta }_1,\dots ,{\theta }_9)=\left[\begin{array}{ccccccccc}0.0296& 0.7952& 0.1181& -0.7485& 0.5849& 0.1526& -1.5656& -0.5625& -0.0326\\ -0.929& -0.4825& -0.0362& 1.0953& 0.9809& -0.5894& 1.5817& -0.5287& 0.457\\ 0.9299& -1.5692& -1.0224& -0.4028& 0.2204& -0.1934& 0.6691& -1.6489& -2.2527\\ -1.1668& 0.3536& 0.7021& -0.2745& -0.1391& 0.1076& -0.6065& -0.417& -0.017\end{array}\right]$$

初始化 ${\theta }_i$ 对应位置上的置偏值 $b^{\prime }=(b_1^{\prime },b_2^{\prime },\dots ,b_9^{\prime })$

$$b^{\prime }=\left[\begin{array}{ccccccccc}-1.2241& -1.8008& 1.6347& 0.989& 0.4579& 0.5551& 1.3067& -0.4405& -0.3013\end{array}\right]$$

我们计算对应路径上的 $h^T$ 与 ${\theta }_i$ 的乘积的结果加上置偏 $b_i^{\prime }$ 最后再取 Sigmoid 得到一个概率值 $P$，我们将其标记为正向概率，即$P_i^1=\sigma (h^T\times {\theta }_i+b_i^{\prime })$。我们依据正向概率计算负向概率$P_i^0$，即$P_i^0=1-P_i^1$，然后我们按 Huffman 树路径对路径上的概率进行连乘可以得到每个叶子节点的概率，然后我们取最大概率的单词作为预测的单词结果。具体计算例子如下，我们从根节点开始，计算所有的 $P_i^1=\sigma (h^T\times {\theta }_i+b_i^{\prime })$ 和 $P_i^1=1-P_i^1$

$$\begin{gathered} P_1^1=\sigma (h^T\times {\theta }_1+b_1^{\prime })=0.6696，P_1^1=1-P_1^1=0.3304 \\ {P}_2^1=\sigma (h^T\times {\theta }_2+b_2^{\prime })=0.0938，P_2^1=1-P_2^1=0.9062 \\ {P}_3^1=\sigma (h^T\times {\theta }_3+b_3^{\prime })=0.6945，P_3^1=1-P_3^1=0.3055 \\ {P}_4^1=\sigma (h^T\times {\theta }_4+b_4^{\prime })=0.5077，P_4^1=1-P_4^1=0.4923 \\ {P}_5^1=\sigma (h^T\times {\theta }_4+b_5^{\prime })=0.4223，P_5^1=1-P_5^1=0.5777 \\ {P}_6^1=\sigma (h^T\times {\theta }_6+b_6^{\prime })=0.7198，P_6^1=1-P_6^1=0.2802 \\ {P}_7^1=\sigma (h^T\times {\theta }_7+b_7^{\prime })=0.6447，P_7^1=1-P_7^1=0.3553 \\ {P}_8^1=\sigma (h^T\times {\theta }_8+b_8^{\prime })=0.4150，P_8^1=1-P_8^1=0.5850 \\ {P}_9^1=\sigma (h^T\times {\theta }_9+b_9^{\prime })=0.1631，P_9^1=1-P_9^1=0.8369 \end{gathered}$$

接下来计算每个单词的概率，对路径上的$P_i^d$进行连乘，即$P(wor{d}_i)={\prod }_{i=1}^l{P}_i^d$，具体计算过程为

$$\begin{gathered} P(the)=\prod _{i=1}^2{P}_i^d=P_1^1\times P_2^1=0.4650 \\ P(cat)=\prod _{i=1}^3{P}_i^d=P_1^0\times P_2^0\times P_3^0=0.1473 \\ P(plays)=\prod _{i=1}^4{P}_i^d=P_1^1\times P_2^0\times P_3^1\times P_4^1=0.02401 \\ P(in)=\prod _{i=1}^3{P}_i^d=P_1^0\times P_2^0\times P_3^1=0.1520 \\ P(garden)=\prod _{i=1}^3{P}_i^d=P_1^0\times P_2^1\times P_3^1=0.0130 \\ P(,)=\prod _{i=1}^4{P}_i^d=P_1^1\times P_2^0\times P_3^0\times P_4^0=0.0335 \\ P(and)=\prod _{i=1}^4{P}_i^d=P_1^1\times P_2^0\times P_3^1\times P_4^0=0.1232 \\ P(chases)=\prod _{i=1}^4{P}_i^d=P_1^0\times P_2^1\times P_3^0\times P_4^1=0.0115 \\ P(mouse)=\prod _{i=1}^4{P}_i^d=P_1^0\times P_2^1\times P_3^0\times P_4^0=0.0063 \\ P(.)=\prod _{i=1}^4{P}_i^d=P_1^1\times P_2^0\times P_3^0\times P_4^1=0.0237 \end{gathered}$$

其中概率最大的值为 0.4650，代表的单词为the，所以预测的结果过单词为the。

下面按照原来模型中的例子继续详细介绍下优化后 分层Softmax 层之后的损失函数计算过程。

损失函数

在层次 Softmax 中使用的损失函数通常是二元交叉熵损失（Binary Cross-Entropy, BCE）。每个非叶节点上的决策可以被视作一个二分类问题——决定是向左还是向右，使用二元交叉熵损失可以衡量事件（向左或向右）的预测概率与实际结果之间的差异。通过计算对应路径上的 $h^T$ 与 ${\theta }_i$ 的乘积加上置偏值 $b_i$ 最后再取 Sigmoid 得到概率 $p_i$，用 $p_i$ 与标签来计算二元交叉熵损失。

$${\text{L}}_i=-[t_i\log (p_i)+(1-t_i)\log (1-p_i)]$$

其中，$t_i$ 是实际的标签，可以理解为相应节点正确的决策路径。$T=(t_1,\dots ,t_n)$ 可以表示正确单词在 Huffman 树上对应的路径。$p_i$ 是模型预测的概率，当 $p_i>0.5$ 是表示向右走（编码为 1），$p_i<0.5$ 是表示向左走（编码为0）。

每个二分类过程都可以得到一个损失 $L_i$，我们对其求和得到总的损失Loss。

$$\text{Loss}=\sum _{i=1}^n{L}_i$$

其中 $n$ 为路径的长度，通过计算路径上每次决策的损失并累加得到最终的损失。

分层 Softmax 小结

1.H-Softmax层的输入是 $h\in {\mathbb{R}}^{D\times 1}$，输出是对应的预测的单词的路径
$$T\in {\mathbb{R}}^{k\times 1}$$

和对应路径上的概率序列
$$P=(p_1,p_2,\dots ,p_k)$$
其中 $k$ 为所预测单词的路径长度。

2.预测结果单词为Huffman树路径到叶子节点之间经过的$P_i^d$连乘结果得到的概率所概率最大的位置所对应的单词，即
$$P(wor{d}_i)=\prod _{i=1}^l{P}_i^d$$
值最大对应索引的单词，其中 $l$ 为路径长度，$d$ 只能从0或1中选，即 d ∈ { 0 , 1 } d \in \{0,1\} d∈{0,1}。损失函数使用概率序列$P$和路径（标签）来计算交叉熵损失。

通过上面的解释，我们知道了分层Softmax以修改原来Word2Vec模型中的多分类Softmax的拓扑结构为多个二分类Huffuman树结构的形式减少了计算量，下面我们将介绍另一种形式的优化----负采样。负采样以训练技巧（trick）的方式对Softmax进行优化，它不再使用（复杂的）Huffman 树，而是利用随机取特定数量的负样例，从而减少计算量，下面正式进行介绍。

负采样

负采样（Negative Sampling）的基本思想是从一个概率分布中选择少数几个负样本来参与每次的训练，而不是使用全体负样本。在原本的Word2Vec模型中，在Softmax层中，我们会进行$V$次$e^x$运算，这个计算量在$V$较大时，计算的时间复杂度特别高，而当我们使用少数几个样本作为负样本，例如我们令负样本数 $k=5$（通常$k$为$5\sim 20$），这将把计算时间复杂度将为常数级。例如当$V=1000000$，传统的Word2Vec模型在Softmax层会进行$1000000$次运算，而在优化后的负采样中只会进行$5$次（假设$k=5$），这将提升 $1000000/2=500000$倍的运算效率！

在负采样中，我们通常不使用Softmax多分类，而是使用Sigmoid函数进行二分类。我们通常将这 $k$个负例分别与正例使用 Sigmoid函数做二分类计算获得每个样例的得分并组合成得分向量，最后使用Softmax归一化得分得到样例的概率值。

通过这种方式，负采样帮助模型专注于最重要的信息，避免了在大量不相关数据上浪费计算资源。分层Softmax和负采样是可以相互替代的作为Word2Vec的一种加速计算的方式。

我们本节以 CBOW 模型为例讲述负采样 ，使用了负采样进行优化的 CBOW 模型如下图所示。与 CBOW 模型优化前进行对比，可以发现加权平均层以及其之前的层与原来的 CBOW 模型一致。主要的变化是在是在权重输出层和Softmax层，我们将其优化成 负采样层。我们将在 负采样 层中详细介绍。现在我们回顾一下 CBOW 模型加权平均层及其之前层的处理。

预处理

简单介绍模型输入前的处理。给定一个语料库 text，我们要将其处理成能够用于模型输入的 one-hot 向量。首先去重，然后将单词与标点符号按读入顺序放入集合corpus，并另外存储一份单词与索引直接查询的字典，word_to_id 和 id_to_word。

随后是将单词集合corpus也就是词汇表Vocabulary转换为 one-hot 表示

模型输入

在模型中，将一个词的上下文词表示为独热编码（one-hot encoding）向量然后并作为模型的一个输入。上下文的词的多少取决于窗口大小 $C$，于是我们的输入$X=(x_{i-c},x_{i-c+1},\dots ,x_{i-1}\in {\mathbb{R}}^{V\times 2C},x_{i+1},\dots ,x_{i+c})$，$x_i$为目标单词，其中 $x_i\in {\mathbb{R}}^{V\times 1}$。

权重输入层

在这一层，我们将目标单词$x_i$的上下文的 one-hot 编码与隐藏层的权重输入矩阵 $W$ 相乘再加上置偏值 $b\in {\mathbb{R}}^{D\times 1}$ 得到 $x_j^{\prime }$，即 $X_j^{\prime }=W{X}_j+b$， 其中 $x_j^{\prime }\in {\mathbb{R}}^{D\times 1}$，$j=(i-C,i-C+1,\dots ,i-1,i+1,\dots ,i+C)$。写成矩阵的形式为

$$X^{\prime }=WX+b$$

加权平均层

我们将输入层得到的所有 $x_j^{\prime }$ 进行加权平均得到 $h$。

$$h=\sum _{j=i-C,j\ne i}^{i+C}{x}_j^{\prime }=\frac{1}{2C}(x_{i-C}^{\prime }+\dots x_{i-1}^{\prime }+x_{i+1}^{\prime }+\cdots +x_{i+C}^{\prime })$$

其中 $C$ 是窗口大小， $h\in {\mathbb{R}}^{D\times 1}$。写成矩阵的形式为

$$h=\frac{1}{2C}{X}^{\prime }\vec{j}$$
其中$\vec{j}=\left[1,1,\dots ,1,1\right]\in {\mathbb{R}}^{2C\times 1}$。

接下来我们开始进入真正的负采样 模块，即 “负采样” 层。“负采样” 层 的输入是隐藏层的向量 $h$。

负采样层

Word2Vec中使用负采样，只是通过优化计算改善了词向量的质量，而并没有改变预测的方法，在预测过程中，我们通常将 Word2Vec 模型中隐藏层的向量$h$ 乘成正例的权重输出矩阵 ${\theta }_1$，即 $S_1={\theta }_1\times h+b_1^{\prime }$，得到我们需要预测单词的得分向量$S_1$，然后使用Softmax将得分向量转换为概率，即$P=Softmax(S_1)$最后将最大概率位置的值设为1，其他位置设为0，得到对应的单词的one-hot表示，最后得到one-hot向量的相应的单词。

简单的负采样例子

以Word2Vec中，前面的CBOW模型为例子进行解释。

首先我们的语料库为 text = ‘The cat plays in the garden, and the cat chases the mouse in the garden.’。窗口大小 $C=2$，隐藏层的维数 $D=4$ ，并且要给定 plays 的上下文进行预测。我们可以得到模型输入是$x_0$ ， $x_1$ ， $x_3$ ， $x_0$，对应单词分别为 the、cat、in、the。则 $X=(x_0,x_1,x_3,x_0)$，在下方展示。 我们对输入权重权重矩阵 $W$ 进行初始化，$W$初始值与原来的CBOW模型中的一致，我们有如下的信息。

$$X=(x_0,x_1,x_3,x_0)=\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right],b=\left[\begin{array}{c}0.0513\\ -1.1577\\ 0.8167\\ 0.4336\end{array}\right]$$

$$W=\left[\begin{array}{cccccccccc}-0.2047& 0.4789& -0.5194& -0.5557& 1.9657& 1.3934& 0.0929& 0.2817& 0.769& 1.2464\\ 1.0071& -1.2962& 0.2749& 0.2289& 1.3529& 0.8864& -2.0016& -0.3718& 1.669& -0.4385\\ -0.5397& 0.4769& 3.2489& -1.0212& -0.577& 0.1241& 0.3026& 0.5237& 0.0009& 1.3438\\ -0.7135& -0.8311& -2.3702& -1.8607& -0.8607& 0.5601& -1.2659& 0.1198& -1.0635& 0.3328\end{array}\right]$$

接下来是权重输入层的运算。我们将 $W$ 与 $X$ 进行矩阵乘法运算再加上置偏值 $b$，计算得到 $X^{\prime }$。

$$X^{\prime }=WX+b=\left[\begin{array}{cccc}-0.1533& 0.5302& -0.5043& -0.1533\\ -0.1506& -2.4539& -0.9288& -0.1506\\ 0.277& 1.2936& -0.2044& 0.277\\ -0.2798& -0.3974& -1.427& -0.2798\end{array}\right]$$

接下来进行加权平均层的计算，也就是将 $X^{\prime }$每行中的 $4$个值进行相加，得到 $4\times 1$ 的向量 $h$ 。

$$h=\frac{1}{4}{X}^{\prime }=\frac{1}{4}\left[\begin{array}{c}-0.1533+0.5302-0.5043-0.1533\\ -0.1506-2.4539-0.9288-0.1506\\ 0.277+1.2936-0.2044+0.277\\ -0.2798-0.3974-1.427-0.2798\end{array}\right]=\left[\begin{array}{c}-0.0701\\ -0.9209\\ 0.4108\\ -0.596\end{array}\right]$$

至此，我们正式进入负采样，并将介绍是如何计算出预测单词的。

我们初始化正例的权重 ${\theta }_1$，然后进行运算 $Score={\theta }_1\times h$。
$$Score={\theta }_1\times h=\left[\begin{array}{cccc}0.0296& 0.7952& 0.1181& -0.7485\\ 0.5849& 0.1526& -1.5656& -0.5625\\ -0.0326& -0.929& -0.4825& -0.0362\\ 1.0953& 0.9809& -0.5894& 1.5817\\ -0.5287& 0.457& 0.9299& -1.5692\\ -1.0224& -0.4028& 0.2204& -0.1934\\ 0.6691& -1.6489& -2.2527& -1.1668\\ 0.3536& 0.7021& -0.2745& -0.1391\\ 0.1076& -0.6065& -0.417& -0.017\\ -1.2241& -1.8008& 1.6347& 0.989\end{array}\right]\times \left[\begin{array}{c}-0.0701\\ -0.9209\\ 0.4108\\ -0.596\end{array}\right]=\left[\begin{array}{c}-0.2397\\ -0.4894\\ 0.6811\\ -2.1649\\ 0.9334\\ 0.6484\\ 1.2415\\ -0.7012\\ 0.3898\\ 1.8262\end{array}\right]$$

得分最高的值为 $1.8262$，也就是索引为 $9$ 的单词 ‘.’。

以上就是使用了负采样的CBOW模型的预测过程的计算，预测的过程比较简单，而训练，即损失函数的计算过程会复杂一些，我们接着上面CBOW模型的例子介绍损失函数的计算过程。

损失函数

使用了负采样的Word2Vec模型的损失函数的计算包括两个部分，一是正例损失的计算，二是负例损失的计算。在使用负采样的Word2Vec模型中，预测单词时，只用到了正例的权重输出矩阵${\theta }_1$，但在计算损失时，我们需要同时考虑正例和负例的的损失。

正例损失的计算：在预测过程中，我们计算了单词的得分向量，也就是 $S_1={\theta }_{1}h+b_1^{\prime }$。我们使用交叉熵损失计算损失，即

$$\begin{array}{rl}Loss& =-\left[t_1\times log(P_1)+t_2\times log(P_2)+\cdots +t_{V-1}\times log(P_{V-1})+t_V\times log(P_V)\right]\end{array}$$

其中$T_1$是正确的标签，即 $T_1=(t_1,t_2,\dots ,t_V{)}^T$，$P$是每个单词对应的概率，即$P=(P_1,P_2,\dots ,P_V)$，此处我们进行优化。在$T$中，由于只有正确索引位置为为$1$，在进行交叉熵损失运算时，只会保留正确索引位置单词的得分概率，于是我们将得分向量中正确的得分直接取出，记为 $S_1=({\theta }_{1}h{)}^T{T}_1$。

随后我们将得分转换为概率，由于此处均为二分类问题（即预测单词是否为目标单词），我们使用$Sigmoid$函数将得分转换正例的概率$P_1\in R$，最后应用于交叉熵损失函数，即

$$P_1=\sigma (S_1)=\sigma (({\theta }_{1}h+b_1^{\prime }{)}^T{T}_1)=\frac{1}{1+e^{-(({\theta }_{1}h+b_1^{\prime }{)}^T{T}_1)}}$$

$$Los{s}_{+}=-log(P_1)=-log(\frac{1}{1+e^{-(({\theta }_{1}h+b_1^{\prime }{)}^T{T}_1)}})$$

负例的计算：负例的计算与正例类似，不过我们先需要进行采样，下面先介绍如何对负例进行采样。

从预料库中选取负例的集合，要求词频高的词容易被随机到，而词频低的词不容易被随机到。Word2Vec负采样方法如下：

1. 我们根据词汇表中的单词，按照词频给出每个单词的概率分布，公式如下为
   $$f(w)=\frac{[count(w){]}^{\frac{3}{4}}}{{\sum }_{i=1}^V[count(i){]}^{\frac{3}{4}}}$$ 其中函数$count(index)$计算索引位置为$index$位置单词的词频，$w$表示目标单词的索引，$V$为词汇表的大小。$len$函数分母计算了所有单词的一个权重和，$f(w)$函数求得索引位置为$w$位置的单词按照词频在词汇表中概率分布。
2. 我们根据概率分布进行抽样，若抽到正例则重新抽样，于是我们得到了若干负例。

在Word2Vec原文中，数据量较大时，我们通常使用的负例个数 $k$ 通常为5，当数据量较小时，则通常为$5\sim 20$个。

通过采样后，我们得到了负样本，下面介绍负例的计算。对于采样出的负例，我们计算对应的得分之后将其取负号再使用 $Sigmoid$ 函数，然后使用原来计算正例的方式进行计算。考虑负例的权重输出函数 ，我们将负例的权重矩阵${\theta }_0$与隐藏层向量$h$相乘得到单词的得分向量，取出分别出采样单词对应的得分，即$S_{0,i}=({\theta }_{0}h+b_0^{\prime }{)}^T{T}_{0,i}$，其中$T_{0,i}$是取出的负样例中，对应负样例的标签（one-hot向量），$i$是负样例标签的索引，即负采样采样出负样例中的第几个，且$i\in 1,2,\dots ,k$，$k$为负样例个数。随后对 $S_{0,i}$ 取负号后使用 $Sigmoid$ 函数得到负样例概率 $P_{0,i}$，即$P_{0,i}=\sigma (-S_{0,i})$，然后将所有的概率取使用交叉熵损失计算方法得到负样例的损失。

$$P_{0,i}=\sigma (S_{0,i})=\sigma (({\theta }_{0}h+b_0^{\prime }{)}^T{T}_{0,i})=\frac{1}{1+e^{-(({\theta }_{0}h+b_0^{\prime }{)}^T{T}_{0,i})}}$$

$${\text{Loss}}_{-}=-\sum _{i=1}^k{\text{Loss}}_{-,i}=-\sum _{i=1}^k\log (P_{0,i})=-\sum _{i=1}^k\log (\frac{1}{1+e^{-(({\theta }_{0}h+b_0^{\prime }{)}^T{T}_{0,i})}})$$

最后我们将正例损失与负例损失相加得到总的损失。
$$\text{Loss}={\text{Loss}}_{+}+{\text{Loss}}_{-}$$

负采样小结

1.负采样层的输入是隐藏层的向量 $h\in {\mathbb{R}}^{D\times 1}$（隐藏层通常有Word2Vec模型的输入进行词嵌入获得），$D$为隐藏层层数，输出是对应的预测的单词。负采样层通过正例的权重输出矩阵${\theta }_1\in V\times D$ 与隐藏层向量$h$进行相乘直接得到了单词的得分向量，$V$ 为词汇表大小，取得分向量中最大得分位置索引的单词作为预测结果单词。

2.负采样损失函数的计算包括两个部分，正例损失的计算和负例损失的计算。对于正例损失，我们将正例权重输出矩阵${\theta }_1$与隐藏层的向量$h$相乘得到单词得分向量，随后取出正例对于索引位置单词的得分，即
$$S_1=({\theta }_{1}h+b_1^{\prime }{)}^T{T}_1$$
其中$T_1$为正例对应的标签。然后我们使用$Sigmoid$函数将得分转换为概率，即
$$P_1=\sigma (S_1)$$
然后我们使用交叉熵计算损失，即
$${\text{Loss}}_{+}=-\log (P_1)$$

对于负例损失的计算，我们首先通过词频加权处理得到每个单词的概率分布，依据概率分布进行抽样，抽取出$k$个负例，随后我们进行负例计算。我们将负例权重输出矩阵${\theta }_0$与隐藏层的向量$h$相乘得到单词得分向量，随后依次取出每个负例对于索引位置单词的得分然后取负号，即
$$S_{0,i}=-({\theta }_{0}h+b_0^{\prime }{)}^T{T}_{0,i}$$
其中$T_{0,i}$为负例对应的标签。然后我们使用$Sigmoid$函数将得分转换为概率，即
$$P_1=\sigma (S_{0,i})$$
然后我们使用交叉熵计算损失，即
$${\text{Loss}}_{-}=-\sum _{i=1}^k\log (P_{0,i})$$

最后我们将$Los{s}_{+}$ 与$Los{s}_{-}$相加得到总的损失Loss，即
$$\text{Loss}={\text{Loss}}_{+}+{\text{Loss}}_{-}$$

到此，负采样算法的损失函数已经介绍完毕！

以上我们介绍了Word2Vec以及两种优化方法，Word2Vec的内容到此结束。

附录

分层Softmax预处理程序代码

def preprocess(text):text = text.lower()text = text.replace('.', ' .')text = text.replace(',', ' ,')text = text.replace('!', ' !')words = text.split(' ')word_to_id = {}id_to_word = {}word_count = {}for word in words:if word not in word_to_id:new_id = len(word_to_id)word_to_id[word] = new_idid_to_word[new_id] = wordword_count[new_id] = 1else:word_count[word_to_id[word]] += 1corpus = np.array([word_to_id[w] for w in words])return corpus, word_to_id, id_to_word, word_count

构建Huffman数程序代码

import heapq	class HuffmanNode:def __init__(self, char, freq):self.char = charself.freq = freqself.left = Noneself.right = None# 使节点成为可比较的，基于频率def __lt__(self, other):return self.freq < other.freqdef build_huffman_tree(frequencies):# 初始化优先队列priority_queue = [HuffmanNode(char, freq) for char, freq in enumerate(frequencies)]heapq.heapify(priority_queue)# 当只剩下一个节点时停止while len(priority_queue) > 1:# 取出两个最小的节点left = heapq.heappop(priority_queue)right = heapq.heappop(priority_queue)# 创建新的内部节点merged = HuffmanNode(None, left.freq + right.freq)merged.left = leftmerged.right = right# 将新节点添加回优先队列heapq.heappush(priority_queue, merged)# 返回根节点return priority_queue[0]def get_huffman_codes(node, current_code="", codes={}):# 如果是叶子节点，记录路径if node.char is not None:codes[node.char] = current_codereturn codes# 向左递归if node.left:get_huffman_codes(node.left, current_code + "0", codes)# 向右递归if node.right:get_huffman_codes(node.right, current_code + "1", codes)return codes# 示例
frequencies = [5, 2, 1, 2, 2, 1, 1, 1, 1, 1]  # 词频数组
root = build_huffman_tree(frequencies)
codes = get_huffman_codes(root)print(codes)		
# {1: '000', 3: '001', 8: '0100', 7: '0101', 4: '011', 5: '1000', 9: '1001', 6: '1010', 2: '1011', 0: '11'}