Question

3.1 CBOW 模型

1. CBOW 模型（continuous bag-of-word）：根据上下文来预测下一个单词。

3.1.1 一个单词上下文

1. 在一个单词上下文的CBOW 模型中：输入是前一个单词，输出是后一个单词，输入为输出的上下文。

   由于只有一个单词作为输入，因此称作一个单词的上下文。

2. 一个单词上下文的CBOW 模型如下：

   

   其中：

   • $N$$ N $ 为隐层的大小，即隐向量$\overrightarrow{\mathbf{h}}=(h_1,h_2,\cdots ,h_N{)}^T\in {\mathbb{R}}^N$$ \mathbf{\vec h} = (h_1,h_2,\cdots,h_N)^T\in \mathbb R^N $ 。

   • 网络输入$\overrightarrow{\mathbf{x}}=(x_1,x_2,\cdots ,x_V{)}^T\in {\mathbb{R}}^V$$ \mathbf{\vec x}=(x_1,x_2,\cdots,x_V)^T \in \mathbb R^V $ ，它是输入单词（即上下文单词）的 one-hote 编码，其中只有一位为 1，其他位都为 0 。

   • 网络输出$\overrightarrow{\mathbf{y}}=(y_1,y_2,\cdots ,y_V{)}^T\in {\mathbb{R}}^V$$ \mathbf{\vec y}=(y_1,y_2,\cdots,y_V)^T \in \mathbb R^V $ ，它是输出单词为词汇表各单词的概率。

   • 相邻层之间为全连接：

     • 输入层和隐层之间的权重矩阵为$\mathbf{W}\in {\mathbb{R}}^{V\times N}$$ \mathbf W \in \mathbb R^{V\times N} $

     • 隐层和输出层之间的权重矩阵为${\mathbf{W}}^{\prime }\in {\mathbb{R}}^{N\times V}$$ \mathbf W^\prime\in \mathbb R^{N\times V} $

3. 假设没有激活函数，没有偏置项。给定输入$\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^V$$ \mathbf{\vec x} \in \mathbb R^V $ ，则其对应的隐向量$\overrightarrow{\mathbf{h}}\in {\mathbb{R}}^N$$ \mathbf{\vec h}\in \mathbb R^N $ 为：$\overrightarrow{\mathbf{h}}={\mathbf{W}}^T\overrightarrow{\mathbf{x}}$$ \mathbf{\vec h}=\mathbf W^T\mathbf{\vec x} $ 。

   令：

   $$\begin{array}{}\text{(15)}& \begin{array}{c}\mathbf{W}=\left[\begin{array}{c}{\overrightarrow{\mathbf{w}}}_1^T\\ {\overrightarrow{\mathbf{w}}}_2^T\\ ⋮\\ {\overrightarrow{\mathbf{w}}}_V^T\end{array}\right]\end{array}\end{array}$$

   由于$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 是个one-hot编码，假设它为词表$\mathbb{V}$$ \mathbb V $ 中第$j$$ j $ 个单词${\text{word}}_j$$ \text{word}_j $ ，即：

   $$\begin{array}{}\text{(16)}& x_1=0,x_2=0,\cdots ,x_{j-1}=0,x_j=1,x_{j+1}=0,\cdots ,x_V=0\end{array}$$

   则有：$\overrightarrow{\mathbf{h}}={\overrightarrow{\mathbf{w}}}_j$$ \mathbf{\vec h}=\mathbf{\vec w}_j $ 。

   即：$\mathbf{W}$$ \mathbf W $ 的第$j$$ j $ 行${\overrightarrow{\mathbf{w}}}_j^T$$ \mathbf{\vec w}_j ^T $ 就是词表$\mathbb{V}$$ \mathbb V $ 中第$j$$ j $ 个单词${\text{word}}_j$$ \text{word}_j $ 的表达，称作单词${\text{word}}_j$$ \text{word}_j $ 的输入向量。

4. 给定隐向量$\overrightarrow{\mathbf{h}}$$ \mathbf {\vec h} $ ，其对应的输出向量$\overrightarrow{\mathbf{u}}\in {\mathbb{R}}^V$$ \mathbf{\vec u} \in \mathbb R^V $ 为：$\overrightarrow{\mathbf{u}}={\mathbf{W}}^{\prime T}\overrightarrow{\mathbf{h}}$$ \mathbf{\vec u}=\mathbf W^{\prime T}\mathbf{\vec h} $ 。令：

   $$\begin{array}{}\text{(17)}& {\mathbf{W}}^{\prime }=[{\overrightarrow{\mathbf{w}}}_1^{\prime },{\overrightarrow{\mathbf{w}}}_2^{\prime },\cdots ,{\overrightarrow{\mathbf{w}}}_V^{\prime }]\end{array}$$

   则有：$u_j={\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}$$ u_j=\mathbf{\vec w}^{\prime}_j\cdot \mathbf{\vec h} $ 。

   • $u_j$$ u_j $ 表示词表$\mathbb{V}$$ \mathbb V $ 中，第$j$$ j $ 个单词${\text{word}}_j$$ \text{word}_j $ 的得分。

   • ${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}_j^{\prime } $ 为矩阵${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 的第$j$$ j $ 列，称作单词${\text{word}}_j$$ \text{word}_j $ 的输出向量。

5. $\overrightarrow{\mathbf{u}}$$ \mathbf{\vec u} $ 之后接入一层 softmax 层，则有：

   $$\begin{array}{}\text{(18)}& y_j=p({\text{word}}_j\mid \overrightarrow{\mathbf{x}})=\frac{\exp (u_j)}{\sum _{j^{\prime }=1}^V\exp (u_{j^{\prime }})},j=1,2,\cdots ,V\end{array}$$

   即$y_j$$ y_j $ 表示词汇表$\mathbb{V}$$ \mathbb V $ 中第$j$$ j $ 个单词${\text{word}}_j$$ \text{word}_j $ 为真实输出单词的概率。

   假设输入单词为${\text{word}}_I$$ \text{word}_I $ （它称作上下文） ，观测到它的下一个单词为${\text{word}}_O$$ \text{word}_O $ 。令输入单词的对应的网络输入为$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ ，其隐向量为${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ ，输入输出单词对应的输出单元为$j^{\ast }$$ j^* $ ，则采用交叉熵的损失函数为：

   $$\begin{array}{}\text{(19)}& \begin{array}{c}E({\text{word}}_I,{\text{word}}_O)=-\log \frac{\exp (u_{j^{\ast }})}{\sum _{j^{\prime }=1}^V\exp (u_{j^{\prime }})}=-{\overrightarrow{\mathbf{w}}}_{j^{\ast }}^{\prime }\cdot \overrightarrow{\mathbf{h}}+\log \sum _{j=1}^V\exp ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})\\ =-{\overrightarrow{\mathbf{w}}}_{j^{\ast }}^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I+\log \sum _{j=1}^V\exp ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I)\end{array}\end{array}$$

   考虑语料库$\mathbb{D}$$ \mathbb D $ 中所有的样本，则整体经验损失函数为：

   $$\begin{array}{}\text{(20)}& \mathcal{L}=\sum _{({\text{word}}_I,{\text{word}}_O)\in \mathbb{D}}E({\text{word}}_I,{\text{word}}_O)\end{array}$$

   则网络的优化目标为：

   $$\begin{array}{}\text{(21)}& min\mathcal{L}=\underset{\mathbf{W},{\mathbf{W}}^{\prime }}{min}\sum _{({\text{word}}_I,{\text{word}}_O)\in \mathbb{D}}(-{\overrightarrow{\mathbf{w}}}_{j^{\ast }}^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I+\log \sum _{j=1}^V\exp ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I))\end{array}$$

   设张量$\mathbf{A}$$ \mathbf A $ 为某个网络参数，则有：

   $$\begin{array}{}\text{(22)}& {\mathrm{\nabla }}_{\mathbf{A}}\mathcal{L}=\sum _{({\text{word}}_I,{\text{word}}_O)}{\mathrm{\nabla }}_{\mathbf{A}}E\end{array}$$

   则该参数的单次更新$\mathbf{A}\leftarrow \mathbf{A}-\eta {\mathrm{\nabla }}_{\mathbf{A}}\mathcal{L}$$ \mathbf A \leftarrow \mathbf A -\eta\nabla_{\mathbf A} \mathcal L $ ，可以表示为单个样本的多次更新：

   $$\begin{array}{}\text{(23)}& \begin{array}{c}\text{for}({\text{word}}_I,{\text{word}}_O)\in \mathbb{D}:\\ \mathbf{A}\leftarrow \mathbf{A}-\eta {\mathrm{\nabla }}_{\mathbf{A}}E\end{array}\end{array}$$

   因此本节的参数更新推导是关于单个样本的更新：$\mathbf{A}\leftarrow \mathbf{A}-\eta {\mathrm{\nabla }}_{\mathbf{A}}E$$ \mathbf A \leftarrow \mathbf A -\eta\nabla_{\mathbf A} E $ 。

3.1.2 参数更新

1. 定义$t_j=\mathbb{I}(j=j^{\ast })$$ t_j=\mathbb I(j=j^*) $ ，即第$j$$ j $ 个输出单元对应于真实的输出单词${\text{word}}_O$$ \text{word}_O $ 时，它为1；否则为0。定义：

   $$\begin{array}{}\text{(24)}& e_j=\frac{\partial E}{\partial u_j}=y_j-t_j\end{array}$$

   它刻画了每个输出单元的预测误差：

   • 当$j=j^{\ast }$$ j=j^* $ 时：$e_j=y_j-1<0$$ e_j=y_j-1\lt 0 $ ，它刻画了输出概率 ($y_j$$ y_j $ ) 与真实概率$1$$ 1 $ 之间的差距。小于 0 表示预测不足。

   • 当$j\ne j^{\ast }$$ j\ne j^* $ 时：$e_j=y_j>0$$ e_j=y_j \gt 0 $ ，它刻画了输出概率 ($y_j$$ y_j $ ) 与真实概率$0$$ 0 $ 之间的差距。大于 0 表示预测过量。

2. 根据：$u_j={\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}\to \frac{\partial u_j}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\overrightarrow{\mathbf{h}}$$ u_j=\mathbf{\vec w}^{\prime}_j\cdot \mathbf{\vec h}\quad \rightarrow \quad \frac{\partial u_j}{\partial \mathbf{\vec w}_j^\prime}= \mathbf{\vec h} $ ，则有：

   $$\begin{array}{}\text{(25)}& \frac{\partial E}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\frac{\partial E}{\partial u_j}\times \frac{\partial u_j}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=e_j\overrightarrow{\mathbf{h}}\end{array}$$

   则${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}_j^\prime $ 更新规则为：

   $$\begin{array}{}\text{(26)}& {\overrightarrow{\mathbf{w}}}_j^{\prime (new)}={\overrightarrow{\mathbf{w}}}_j^{\prime (old)}-\eta e_j\overrightarrow{\mathbf{h}}\end{array}$$

   其物理意义为：

   • 当估计过量 ($e_j>0\to y_j>t_j$$ e_j\gt 0 \rightarrow y_j\gt t_j $ ) 时，${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}^{\prime}_{j } $ 会减去一定比例的$\overrightarrow{\mathbf{h}}$$ \mathbf{\vec h} $ 。 这发生在第$j$$ j $ 个输出单元不对应于真实的输出单词时。

   • 当估计不足 ($e_j<0\to y_j<t_j$$ e_j\lt 0 \rightarrow y_j\lt t_j $ ) 时，${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}^{\prime}_{j } $ 会加上一定比例的$\overrightarrow{\mathbf{h}}$$ \mathbf{\vec h} $ 。这发生在第$j$$ j $ 个输出单元刚好对应于真实的输出单词时。

   • 当$y_j\simeq t_j$$ y_j\simeq t_{j} $ 时，更新的幅度将非常微小。

3. 定义：

   $$\begin{array}{}\text{(27)}& \overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}={\left(\frac{\partial \overrightarrow{\mathbf{u}}}{\partial \overrightarrow{\mathbf{h}}}\right)}^T\frac{\partial E}{\partial \overrightarrow{\mathbf{u}}}\end{array}$$

   根据：$\overrightarrow{\mathbf{u}}={\mathbf{W}}^{\prime T}\overrightarrow{\mathbf{h}}\to {\left(\frac{\partial \overrightarrow{\mathbf{u}}}{\partial \overrightarrow{\mathbf{h}}}\right)}^T={\mathbf{W}}^{\prime }$$ \mathbf{\vec u}=\mathbf W^{\prime T}\mathbf{\vec h} \quad \rightarrow \quad \left(\frac{\partial \mathbf{\vec u}}{\partial \mathbf{\vec h}} \right)^T= \mathbf W^\prime $ ，则有：$\overrightarrow{\mathbf{EH}}={\mathbf{W}}^{\prime }\overrightarrow{\mathbf{e}}=\sum _{j=1}^V{e}_j{\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\overrightarrow {EH}} = \mathbf W^\prime \mathbf{\vec e} =\sum_{j=1}^Ve_j \mathbf{\vec w}^{\prime }_j $ 。

   $\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 的物理意义为：词汇表$\mathbb{V}$$ \mathbb V $ 中所有单词的输出向量的加权和，其权重为$e_j$$ e_j $ 。

4. 考虑到$\overrightarrow{\mathbf{h}}={\mathbf{W}}^T\overrightarrow{\mathbf{x}}$$ \mathbf{\vec h}=\mathbf W^T\mathbf{\vec x} $ ，则有：

   $$\begin{array}{}\text{(28)}& \frac{\partial E}{\partial w_{k,i}}=\frac{\partial E}{\partial h_i}\times \frac{\partial h_i}{\partial w_{k,i}}=E{H}_i\times x_k\end{array}$$

   写成矩阵的形式为：$\frac{\partial E}{\partial \mathbf{W}}=\overrightarrow{\mathbf{x}}\otimes \overrightarrow{\mathbf{EH}}$$ \frac{\partial E}{\partial \mathbf W}=\mathbf{\vec x}\otimes \mathbf{\overrightarrow {EH}} $ ，其中$\otimes$$ \otimes $ 为克罗内克积。

   由于$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 是one-hote 编码，所以它只有一个分量非零，因此$\frac{\partial E}{\partial \mathbf{W}}$$ \frac{\partial E}{\partial \mathbf W} $ 只有一行非零，且该非零行就等于$\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 。因此得到更新方程：

   $$\begin{array}{}\text{(29)}& {\overrightarrow{\mathbf{w}}}_I^{(new)}={\overrightarrow{\mathbf{w}}}_I^{(old)}-\eta \overrightarrow{\mathbf{EH}}\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 为$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 非零分量对应的$\mathbf{W}$$ \mathbf W $ 中的行，而$\mathbf{W}$$ \mathbf W $ 的其它行在本次更新中都保持不变。

5. 考虑更新$\mathbf{W}$$ \mathbf W $ 第$I$$ I $ 行的第$k$$ k $ 列，则：

   $$\begin{array}{}\text{(30)}& w_{I,k}^{(new)}=w_{I,k}^{(old)}-\eta \sum _{j=1}^V{e}_j{w}_{j,k}^{\prime }\end{array}$$

   • 当$y_j\simeq t_j$$ y_j\simeq t_{j} $ 时，$e_j$$ e_j $ 趋近于 0 ，则更新的幅度将非常微小。

   • 当$y_j$$ y_j $ 与$t_j$$ t_{j} $ 差距越大，$e_j$$ e_j $ 绝对值越大， 则更新的幅度越大。

6. 当给定许多训练样本（每个样本由两个单词组成），上述更新不断进行，更新的效果在不断积累。

   • 根据单词的共现结果，输出向量与输入向量相互作用并达到平衡。

     • 输出向量${\overrightarrow{\mathbf{w}}}^{\prime }$$ \mathbf{\vec w}^{\prime} $ 的更新依赖于输入向量${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ ：${\overrightarrow{\mathbf{w}}}_j^{\prime (new)}={\overrightarrow{\mathbf{w}}}_j^{\prime (old)}-\eta e_j\overrightarrow{\mathbf{h}}$$ \mathbf{\vec w}^{\prime(new)}_{j } =\mathbf{\vec w}^{\prime(old)}_{j }-\eta e_j\mathbf{\vec h} $ 。

       这里隐向量$\overrightarrow{\mathbf{h}}$$ \mathbf{\vec h} $ 等于输入向量${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 。

     • 输入向量${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 的更新依赖于输出向量${\overrightarrow{\mathbf{w}}}^{\prime }$$ \mathbf{\vec w}^{\prime} $ ：${\overrightarrow{\mathbf{w}}}_I^{(new)}={\overrightarrow{\mathbf{w}}}_I^{(old)}-\eta \overrightarrow{\mathbf{EH}}$$ \mathbf{\vec w}_I^{(new)}=\mathbf{\vec w}_I^{(old)}-\eta\mathbf{\overrightarrow{EH}} $ 。

       这里$\overrightarrow{\mathbf{EH}}=\sum _{j=1}^V{e}_j{\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\overrightarrow{EH}} = \sum_{j=1}^Ve_j \mathbf{\vec w}^{\prime }_j $ 为词汇表$\mathbb{V}$$ \mathbb V $ 中所有单词的输出向量的加权和，其权重为$e_j$$ e_j $ 。

   • 平衡的速度与效果取决于单词的共现分布，以及学习率。

3.1.3 多个单词上下文

1. 考虑输入为目标单词前后的多个单词（这些单词作为输出的上下文），输入为$C$$ C $ 个单词：${\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_C$$ \mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_C $ 。对于每个输入单词，其权重矩阵都为$\mathbf{W}$$ \mathbf W $ ，这称作权重共享。这里的权重共享隐含着：每个单词的表达是固定的、唯一的，与它的上下文无关。

   隐向量为所有输入单词映射结果的均值：

   $$\begin{array}{}\text{(31)}& \overrightarrow{\mathbf{h}}=\frac{1}{C}{\mathbf{W}}^T({\overrightarrow{\mathbf{x}}}_1+{\overrightarrow{\mathbf{x}}}_2+\cdots +{\overrightarrow{\mathbf{x}}}_C)=\frac{1}{C}({\overrightarrow{\mathbf{w}}}_{I_1}+{\overrightarrow{\mathbf{w}}}_{I_2}+\cdots +{\overrightarrow{\mathbf{w}}}_{I_C})\end{array}$$

   其中：$I_i$$ I_i $ 表示第$i$$ i $ 个输入单词在词汇表$\mathbb{V}$$ \mathbb V $ 中的编号，${\overrightarrow{\mathbf{w}}}_j$$ \mathbf{\vec w}_j $ 为矩阵$\mathbf{W}$$ \mathbf W $ 的第$j$$ j $ 行，它是对应输入单词的输入向量。

   

2. 假设给定一个单词序列${\text{word}}_{I_1},{\text{word}}_{I_2},\cdots ,{\text{word}}_{I_C}$$ \text{word}_{I_1},\text{word}_{I_2},\cdots,\text{word}_{I_C} $ （它称作上下文），观测到它的下一个单词为${\text{word}}_O$$ \text{word}_O $ 。${\text{word}}_O$$ \text{word}_O $ 对应的网络输出编号为$j^{\ast }$$ j^* $ 。

   定义损失函数为交叉熵：

   $$\begin{array}{}\text{(32)}& E=-u_{j^{\ast }}+\log \sum _{j=1}^V\exp (u_j)=-{\overrightarrow{\mathbf{w}}}_{j^{\ast }}^{\prime }\cdot \overrightarrow{\mathbf{h}}+\log \sum _{j=1}^V\exp ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   它的形式与一个单词上下文中推导的完全相同，除了这里的$\overrightarrow{\mathbf{h}}$$ \mathbf{\vec h} $ 不同。

   考虑语料库$\mathbb{D}$$ \mathbb D $ 中所有的样本，则整体经验损失函数为：

   $$\begin{array}{}\text{(33)}& \mathcal{L}=\sum _{({\text{word}}_{I_1},{\text{word}}_{I_2},\cdots ,{\text{word}}_{I_C},{\text{word}}_O)\in \mathbb{D}}E\end{array}$$

   则网络的优化目标为：

   $$\begin{array}{}\text{(34)}& min\mathcal{L}=\underset{\mathbf{W},{\mathbf{W}}^{\prime }}{min}\sum _{({\text{word}}_{I_1},{\text{word}}_{I_2},\cdots ,{\text{word}}_{I_C},{\text{word}}_O)\in \mathbb{D}}(-{\overrightarrow{\mathbf{w}}}_{j^{\ast }}^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I+\log \sum _{j=1}^V\exp ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot {\overrightarrow{\mathbf{w}}}_I))\end{array}$$

   .

3. 与一个单词上下文中推导的结果相同，这里给出参数更新规则：

   • 更新${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ ：

     $$\begin{array}{}\text{(35)}& {\overrightarrow{\mathbf{w}}}_j^{\prime (new)}={\overrightarrow{\mathbf{w}}}_j^{\prime (old)}-\eta e_j\overrightarrow{\mathbf{h}},j=1,2,\cdots ,V\end{array}$$

     其中$\overrightarrow{\mathbf{h}}=\frac{1}{C}({\overrightarrow{\mathbf{w}}}_{I_1}+{\overrightarrow{\mathbf{w}}}_{I_2}+\cdots +{\overrightarrow{\mathbf{w}}}_{I_C})$$ \mathbf{\vec h}=\frac 1C (\mathbf{\vec w}_{I_1}+\mathbf{\vec w}_{I_2}+\cdots+\mathbf{\vec w}_{I_C}) $ 。

   • 更新$\mathbf{W}$$ \mathbf W $ ：

     $$\begin{array}{}\text{(36)}& {\overrightarrow{\mathbf{w}}}_{I_i}^{(new)}={\overrightarrow{\mathbf{w}}}_{I_i}^{(old)}-\frac{1}{C}\eta \overrightarrow{\mathbf{EH}},i=1,2,\cdots ,C\end{array}$$

     其中 ：

     • $\overrightarrow{\mathbf{EH}}={\mathbf{W}}^{\prime }\overrightarrow{\mathbf{e}}=\sum _{j=1}^V{e}_j{\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\overrightarrow {EH}} = \mathbf W^\prime \mathbf{\vec e} =\sum_{j=1}^Ve_j \mathbf{\vec w}^{\prime }_j $ ，它是词汇表$\mathbb{V}$$ \mathbb V $ 中所有单词的输出向量的加权和，其权重为$e_j$$ e_j $ 。

     • $I_i$$ I_i $ 为第$i$$ i $ 个输入单词在词表$\mathbb{V}$$ \mathbb V $ 中的编号。

4. 在更新$\mathbf{W}$$ \mathbf W $ 时，如果有相同的输入单词（如：${\overrightarrow{\mathbf{x}}}_1={\overrightarrow{\mathbf{x}}}_2\to {\text{word}}_{100}$$ \mathbf{\vec x}_1=\mathbf{\vec x}_2 \rightarrow \text{word}_{100} $ )，则在参数更新时认为它们是不同的。最终的效果就是在${\overrightarrow{\mathbf{w}}}_{I_i}$$ \mathbf{\vec w}_{I_i} $ 中多次减去同一个增量$\frac{1}{C}\eta \overrightarrow{\mathbf{EH}}$$ \frac 1C\eta\mathbf{\overrightarrow{EH}} $ 。

   你也可以直接减去$\frac{n_v}{C}\eta \overrightarrow{\mathbf{EH}}$$ \frac {n_v}{C}\eta\mathbf{\overrightarrow{EH}} $ ， 其中$n_v$$ n_v $ 为词汇表中单词${\text{word}}_v$$ \text{word}_v $ 在输入中出现的次数。

3.2 Skip-Gram

1. Skip-Gram 模型是根据一个单词来预测其前后附近的几个单词（即：上下文）。

3.2.1 网络结构

1. Skip-Gram 网络模型如下。其中：

   • 网络输入$\overrightarrow{\mathbf{x}}=(x_1,x_2,\cdots ,x_V{)}^T\in {\mathbb{R}}^V$$ \mathbf{\vec x}=(x_1,x_2,\cdots,x_V)^T \in \mathbb R^V $ ，它是输入单词的 one-hot 编码，其中只有一位为 1，其他位都为 0 。

   • 网络输出${\overrightarrow{\mathbf{y}}}_1,{\overrightarrow{\mathbf{y}}}_2,\cdots ,{\overrightarrow{\mathbf{y}}}_C$$ \mathbf{\vec y}_1,\mathbf{\vec y}_2,\cdots,\mathbf{\vec y}_C $ ，其中${\overrightarrow{\mathbf{y}}}_c=(y_1^c,y_2^c,\cdots ,y_V^c{)}^T\in {\mathbb{R}}^V$$ \mathbf{\vec y}_c =(y_1^c,y_2^c,\cdots,y_V^c)^T \in \mathbb R^V $ 是第$c$$ c $ 个输出单词为词汇表各单词的概率。

   • 对于网络的每个输出${\overrightarrow{\mathbf{y}}}_c$$ \mathbf{\vec y}_c $ ，其权重矩阵都相同，为${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 。这称作权重共享。

     这里的权重共享隐含着：每个单词的输出向量是固定的、唯一的，与其他单词的输出无关。

     

2. Skip-Gram 网络模型中，设网络第$c$$ c $ 个输出的第$j$$ j $ 个分量为$u_j^c={\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}$$ u_{j}^c=\mathbf{\vec w}^{\prime}_j\cdot \mathbf{\vec h} $ ，则有：

   $$\begin{array}{}\text{(37)}& y_j^c=p({\text{word}}_j^c\mid \overrightarrow{\mathbf{x}})=\frac{\exp (u_j^c)}{\sum _{k=1}^V\exp (u_k^c)};c=1,2,\cdots ,C;j=1,2,\cdots ,V\end{array}$$

   $y_j^c$$ y_{j}^c $ 表示第$c$$ c $ 个输出中，词汇表$\mathbb{V}$$ \mathbb V $ 中第$j$$ j $ 个单词${\text{word}}_j$$ \text{word}_j $ 为真实输出单词的概率。

3. 因为${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 在多个单元之间共享，所以对于网络每个输出，其得分的分布${\overrightarrow{\mathbf{u}}}_c=(u_1^c,u_2^c,\cdots ,u_V^c{)}^T$$ \mathbf{\vec u}_c=(u_{1}^c,u_{2}^c,\cdots,u_{V}^c)^T $ 是相同的。但是这并不意味着网络的每个输出都是同一个单词。

   并不是网络每个输出中，得分最高的单词为预测单词。因为每个输出中，概率分布都相同，即：${\overrightarrow{\mathbf{y}}}_1={\overrightarrow{\mathbf{y}}}_2=\cdots ={\overrightarrow{\mathbf{y}}}_C$$ \mathbf{\vec y}_1=\mathbf{\vec y}_2=\cdots=\mathbf{\vec y}_C $ 。Skip-Gram 网络的目标是：网络的多个输出之间的联合概率最大。

4. 假设输入为单词${\text{word}}_I$$ \text{word}_I $ ，输出单词序列为${\text{word}}_{O_1},{\text{word}}_{O_2},\cdots ,{\text{word}}_{O_C}$$ \text{word}_{O_1},\text{word}_{O_2},\cdots,\text{word}_{O_C} $ 。定义损失函数为：

   $$\begin{array}{}\text{(38)}& E=-\log p({\text{word}}_{O_1},{\text{word}}_{O_2},\cdots ,{\text{word}}_{O_C}\mid {\text{word}}_I)=-\log \prod _{c=1}^C\frac{\exp (u_{j_c^{\ast }}^c)}{\sum _{j=1}^V\exp (u_j^c)}\end{array}$$

   其中$j_1^{\ast },j_2^{\ast },\cdots ,j_C^{\ast }$$ j_1^*,j_2^*,\cdots,j_C^* $ 为输出单词序列对应于词典$\mathbb{V}$$ \mathbb V $ 中的下标序列。

   由于网络每个输出的得分的分布都相同，令$u_j=u_j^c={\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}$$ u_j=u_{j}^c=\mathbf{\vec w}^{\prime}_j\cdot \mathbf{\vec h} $ ，则上式化简为：

   $$\begin{array}{}\text{(39)}& E=-\sum _{c=1}^C{u}_{j_c^{\ast }}^c+C\log \sum _{j=1}^V\exp (u_j)\end{array}$$

   .

3.2.2 参数更新

1. 定义$t_j^c=\mathbb{I}(j_c=j_c^{\ast })$$ t_{j}^c=\mathbb I(j_c=j_c^*) $ ，即网络第$c$$ c $ 个输出的第$j$$ j $ 个分量对应于第$c$$ c $ 个真实的输出单词${\text{word}}_{j_c^{\ast }}$$ \text{word}_{j_c^*} $ 时，它为 1；否则为0。

   定义：

   $$\begin{array}{}\text{(40)}& e_j^c=\frac{\partial E}{\partial u_j^c}=y_j^c-t_j^c\end{array}$$

   它刻画了网络第$c$$ c $ 个输出的第$j$$ j $ 个分量的误差：

   • 当$j_c=j_c^{\ast }$$ j_c=j_c^* $ 时：$e_j^c=y_j^c-1$$ e_{j}^c=y_{j}^c-1 $ ，它刻画了输出概率$y_j^c$$ y_{j}^c $ 与真实概率$1$$ 1 $ 之间的差距。小于 0 表示预测不足。

   • 当$j_c\ne j_c^{\ast }$$ j_c\ne j_c^* $ 时：$e_j^c=y_j^c$$ e_{j}^c=y_{j}^c $ ，它刻画了输出概率$y_j^c$$ y_{j}^c $ 与真实概率$0$$ 0 $ 之间的差距。大于 0 表示预测过量。

2. 根据：$u_j={\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}\to \frac{\partial u_j}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\overrightarrow{\mathbf{h}}$$ u_j=\mathbf{\vec w}^{\prime}_j\cdot \mathbf{\vec h}\quad \rightarrow \quad \frac{\partial u_j}{\partial \mathbf{\vec w}_j^\prime}= \mathbf{\vec h} $ ，则有：

   $$\begin{array}{}\text{(41)}& \frac{\partial E}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\sum _{c=1}^C\frac{\partial E}{\partial u_j^c}\times \frac{\partial u_j^c}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\sum _{c=1}^C{e}_j^c\overrightarrow{\mathbf{h}}\end{array}$$

   定义$E{I}_j=\sum _{c=1}^C{e}_j^c$$ EI_j=\sum_{c=1}^{C}e_{j}^c $ ，它为网络每个输出的第$j$$ j $ 个分量的误差之和。于是有：

   $$\begin{array}{}\text{(42)}& \frac{\partial E}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=E{I}_j\times \overrightarrow{\mathbf{h}}\end{array}$$

   则有更新方程：

   $$\begin{array}{}\text{(43)}& {\overrightarrow{\mathbf{w}}}_j^{\prime (new)}={\overrightarrow{\mathbf{w}}}_j^{\prime (old)}-\eta \times E{I}_j\times \overrightarrow{\mathbf{h}},j=1,2,\cdots ,V\end{array}$$

3. 定义：

   $$\begin{array}{}\text{(44)}& \overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}=\sum _{c=1}^C{\left(\frac{\partial {\overrightarrow{\mathbf{u}}}^c}{\partial \overrightarrow{\mathbf{h}}}\right)}^T\frac{\partial E}{\partial {\overrightarrow{\mathbf{u}}}^c}\end{array}$$

   根据：

   $$\begin{array}{}\text{(45)}& {\overrightarrow{\mathbf{u}}}^c={\mathbf{W}}^{\prime T}\overrightarrow{\mathbf{h}}\to {\left(\frac{\partial {\overrightarrow{\mathbf{u}}}^c}{\partial \overrightarrow{\mathbf{h}}}\right)}^T={\mathbf{W}}^{\prime }\end{array}$$

   则有：

   $$\begin{array}{}\text{(46)}& \overrightarrow{\mathbf{EH}}=\sum _{c=1}^C{\mathbf{W}}^{\prime }{\overrightarrow{\mathbf{e}}}^c=\sum _{j=1}^{V}E{I}_j{\overrightarrow{\mathbf{w}}}_j^{\prime }\end{array}$$

   $\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 的物理意义为：词汇表$\mathbb{V}$$ \mathbb V $ 中所有单词的输出向量的加权和，其权重为$E{I}_j$$ EI_j $ 。

4. 考虑到$\overrightarrow{\mathbf{h}}={\mathbf{W}}^T\overrightarrow{\mathbf{x}}$$ \mathbf{\vec h}=\mathbf W^T\mathbf{\vec x} $ ，则有：

   $$\begin{array}{}\text{(47)}& \frac{\partial E}{\partial w_{k,i}}=\frac{\partial E}{\partial h_i}\times \frac{\partial h_i}{\partial w_{k,i}}=E{H}_i\times x_k\end{array}$$

   写成矩阵的形式为：$\frac{\partial E}{\partial \mathbf{W}}=\overrightarrow{\mathbf{x}}\otimes \overrightarrow{\mathbf{EH}}$$ \frac{\partial E}{\partial \mathbf W}=\mathbf{\vec x}\otimes \mathbf{\overrightarrow {EH}} $ ，其中$\otimes$$ \otimes $ 为克罗内克积。

   由于$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 是one-hote 编码，所以它只有一个分量非零，因此$\frac{\partial E}{\partial \mathbf{W}}$$ \frac{\partial E}{\partial \mathbf W} $ 只有一行非零，且该非零行就等于$\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 。因此得到更新方程：

   $$\begin{array}{}\text{(48)}& {\overrightarrow{\mathbf{w}}}_I^{(new)}={\overrightarrow{\mathbf{w}}}_I^{(old)}-\eta \overrightarrow{\mathbf{EH}}\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 为$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 非零分量对应的$\mathbf{W}$$ \mathbf W $ 中的行，而$\mathbf{W}$$ \mathbf W $ 的其它行在本次更新中都保持不变。

3.3 优化

1. 原始的CBOW 模型和Skip-Gram 模型的计算量太大，非常难以计算。

   • 模型在计算网络输出的时候，需要计算误差 。对于CBOW 模型，需要计算$V$$ V $ 个误差（词汇表的大小），对于 Skip-Gram 模型，需要计算$C\times V$$ C \times V $ 个误差。

     另外，每个误差的计算需要用到 softmax 函数，该 softmax 函数涉及到$O(V)$$ O(V) $ 复杂度的运算：$\sum _{j=1}^V\exp (u_j)$$ \sum_{j=1}^V \exp (u_j) $ 。

   • 每次梯度更新都需要计算网络输出。

   如果词汇表有 100万 单词，模型迭代 100 次，则计算量超过 1 亿次。

2. 虽然输入向量的维度也很高，但是由于输入向量只有一位为 1，其它位均为 0，因此输入的总体计算复杂度较小。

3. word2vec 优化的主要思想是：限制输出单元的数量。

   事实上在上百万的输出单元中，仅有少量的输出单元对于参数更新比较重要，大部分的输出单元对于参数更新没有贡献。

4. 有两种优化策略：

   • 通过分层 softmax 来高效计算 softmax 函数。

   • 通过负采样来缩减输出单元的数量。

3.3.1 分层 softmax

1. 分层 softmax 是一种高效计算 softmax 函数的算法。

   经过分层 softmax 之后，计算 softmax 函数的算法复杂度从$O(V)$$ O(V) $ 降低到$O(\log V)$$ O(\log V) $ ，但是仍然要计算$V-1$$ V-1 $ 个内部节点的向量表达 。

a) 网络结构

1. 在分层softmax 中，字典$\mathbb{V}$$ \mathbb V $ 中的$V$$ V $ 个单词被组织成二叉树。

   • 叶子结点值为某个具体单词的概率（如下图中的白色结点）

   • 中间节点值也代表一个概率（如下图中的灰色结点）。它的值等于直系子节点的值之和，也等于后继的叶子结点值之和，也等于从根节点到当前节点的路径的权重的乘积。

     之所以有这些性质，是由于结点值、权重都是概率，满足和为1的性质

   • 根据定义，根节点的值等于所有叶子结点的值之和，即为 1.0

   • 二叉树的每条边代表分裂：

     • 向左的边：表示选择左子节点，边的权重为选择左子节点的概率

     • 向右的边：表示选择右子节点，边的权重为选择右子节点的概率

   

2. 对于任意一个中间节点$t$$ t $ ， 假设其向量表达为${\overrightarrow{\mathbf{v}}}_t^{\prime }$$ \mathbf{\vec v}_t^\prime $ ，它是待求的参数。

   • 选择左子节点的概率为：

     $$\begin{array}{}\text{(49)}& \begin{array}{c}p(t,left)=\sigma ({\overrightarrow{\mathbf{v}}}_t^{\prime }\cdot \overrightarrow{\mathbf{h}})\\ \sigma (x)=\frac{1}{1+e^x},\sigma (-x)=1-\sigma (x)\end{array}\end{array}$$

   • 选择右子节点的概率为 :

     $$\begin{array}{}\text{(50)}& p(t,right)=1-\sigma ({\overrightarrow{\mathbf{v}}}_t^{\prime }\cdot \overrightarrow{\mathbf{h}})=\sigma (-{\overrightarrow{\mathbf{v}}}_t^{\prime }\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   • 如果求得所有中间节点的向量表达，则根据每个中间节点的分裂概率，可以很容易的求得每个叶节点的值。

3. 在分层softmax 中，算法并不直接求解输出向量$\{{\overrightarrow{\mathbf{w}}}_1^{\prime },{\overrightarrow{\mathbf{w}}}_2^{\prime },\cdots ,{\overrightarrow{\mathbf{w}}}_V^{\prime }\}$$ \{\mathbf{\vec w}_1^\prime,\mathbf{\vec w}_2^\prime,\cdots,\mathbf{\vec w}_V^\prime\} $ ，而是求解二叉树的$V-1$$ V-1 $ 个中间节点的向量表达 。

   当需要计算某个单词的概率时，只需要记录从根节点到该单词叶子结点的路径。给定单词$w$$ w $ ：

   • 定义$n(w,j)$$ n(w,j) $ 为从根节点到单词$w$$ w $ 的路径的第$j$$ j $ 个节点（从 1 计数）。

   • 定义$L(w)$$ L(w) $ 为从根节点到单词$w$$ w $ 的路径的长度。

   • 定义$ch(t)$$ ch(t) $ 表示节点$t$$ t $ 的左子节点。

   

   输出为单词$w$$ w $ 的概率为：

   $$\begin{array}{}\text{(51)}& p(w)=\prod _{j=1}^{L(w)-1}\sigma (g(n(w,j+1)=ch(n(w,j)))\times {\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   其中：

   • $n(w,j+1)=ch(n(w,j))$$ n(w,j+1)=ch(n(w,j)) $ 表示：从根节点到单词$w$$ w $ 的路径上，第$j+1$$ j+1 $ 个节点是第$j$$ j $ 个节点的左子节点。

   • $g(x)$$ g(x) $ 是一个函数。当$x$$ x $ 是个事实时，其值为 1；当$x$$ x $ 不成立时，其值为 -1。

     $$\begin{array}{}\text{(52)}& \begin{array}{c}g(x)=\{\begin{array}{ll}1,& \text{if}x\text{is true}\\ -1,& \text{if}x\text{is false}\end{array}\end{array}\end{array}$$

   • $g(n(w,j+1)=ch(n(w,j)))$$ g(n(w,j+1)=ch(n(w,j))) $ 表示：从根节点到单词$w$$ w $ 的路径上：

     • 当第$j+1$$ j+1 $ 个节点是第$j$$ j $ 个节点的左子节点时，函数值为 1

     • 当第$j+1$$ j+1 $ 个节点是第$j$$ j $ 个节点的右子节点时，函数值为 -1

   • ${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 表示：从根节点到单词$w$$ w $ 的路径上，第$j$$ j $ 个节点的向量表达

   • 对于从根节点到单词$w$$ w $ 的路径上，从第$j$$ j $ 个节点到第$j+1$$ j+1 $ 个节点的概率为：

     $$\begin{array}{}\text{(53)}& \begin{array}{c}p(j,j+1)=\{\begin{array}{ll}\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}}),& \text{if}j+1\text{is left child of}j\\ \sigma (-{\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}}),& \text{if}j+1\text{is right child of}j\end{array}\end{array}\end{array}$$

     因此$p(w)$$ p(w) $ 刻画了：从根节点到单词$w$$ w $ 的路径上，每条边的权重（也就是分裂概率）的乘积。

4. 对于所有的叶子节点，有$\sum _{i=1}^{V}p(w_i)=1$$ \sum_{i=1}^Vp(w_i)=1 $ 。

   利用数学归纳法，可以证明：左子节点的值+右子节点的值=父节点的值。上式最终证明等于根节点的值，也就是 1.0 。

b) 参数更新

1. 为了便于讨论，这里使用CBOW 的一个单词上下文模型。

   记$g(n(w,j+1)=ch(n(w,j)))$$ g(n(w,j+1)=ch(n(w,j))) $ 为$g_{n(w,j)}$$ g_{n(w,j)} $ ， 定义损失函数对数似然：

   $$\begin{array}{}\text{(54)}& E=-\log p(w\mid \overrightarrow{\mathbf{x}})=-\sum _{j=1}^{L(w)-1}\log \sigma (g_{n(w,j)}{\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   则有：

   $$\begin{array}{}\text{(55)}& \begin{array}{c}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}=(\sigma (g_{n(w,j)}{\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})-1)g_{n(w,j)}=\{\begin{array}{ll}\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})-1& \text{if}{g}_{n(w,j)}=1\\ \sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})& \text{if}{g}_{n(w,j)}=-1\end{array}\\ =\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})-t_{n(w,j)}\end{array}\end{array}$$

   其中：

   $$\begin{array}{}\text{(56)}& \begin{array}{c}{t}_{n(w,j)}=\{\begin{array}{ll}1,& \text{if node}j+1\text{at path , root}\to w\text{, is left child of node}j\\ 0,& \text{if node}j+1\text{at path , root}\to w\text{, is right child of node}j\end{array}\end{array}\end{array}$$

   定义：

   $$\begin{array}{}\text{(57)}& e_{n(w,j)}=\frac{\partial E}{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}=\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})-t_{n(w,j)}\end{array}$$

   • $\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})$$ \sigma(\mathbf{\vec v}^\prime_{n(w,j)}\cdot \mathbf{\vec h}) $ 为预测选择$j$$ j $ 的左子节点的概率。

   • $e_{n(w,j)}$$ e_{n(w,j)} $ 的物理意义为：从根节点到单词$w$$ w $ 的路径上，第$j$$ j $ 个节点的选择误差：

     • 如果下一个节点选择第$j$$ j $ 个节点的左子节点，则$t_{n(w,j)}=1$$ t_{n(w,j)}=1 $ ， 此时$e_{n(w,j)}$$ e_{n(w,j)} $ 表示预测的不足。

     • 如果下一个节点选择第$j$$ j $ 个节点的右子节点，则$t_{n(w,j)}=0$$ t_{n(w,j)}= 0 $ ， 此时$e_{n(w,j)}$$ e_{n(w,j)} $ 表示预测的过量。

2. 考虑内部节点$n(w,j)$$ n(w,j) $ ，其向量表达为${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 。则有：

   $$\begin{array}{}\text{(58)}& \frac{\partial E}{\partial {\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }}=\frac{\partial E}{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}{\partial {\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }}=e_{n(w,j)}\times \overrightarrow{\mathbf{h}}\end{array}$$

   得到向量表达为${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 的更新方程：

   $$\begin{array}{}\text{(59)}& {\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime (new)}={\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime (old)}-\eta \times e_{n(w,j)}\times \overrightarrow{\mathbf{h}};j=1,2,\cdots ,L(w)-1\end{array}$$

   • 对于每个单词$w$$ w $ ，由于它是叶节点，因此可以更新$L(w)-1$$ L(w)-1 $ 个内部节点的向量表达。

   • 当模型的预测概率较准确，即$\sigma ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})\simeq t_{n(w,j)}$$ \sigma(\mathbf{\vec v}^\prime_{n(w,j)}\cdot \mathbf{\vec h}) \simeq t_{n(w,j)} $ 时，则$e_{n(w,j)}$$ e_{n(w,j)} $ 接近0 。此时梯度非常小，${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 的更新幅度也会非常小。

     当模型的预测概率较不准，则$e_{n(w,j)}$$ e_{n(w,j)} $ 较大。此时梯度会较大，${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 的更新幅度也会较大。

3. 对于内部结点的向量表达${\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }$$ \mathbf{\vec v}^\prime_{n(w,j)} $ 的更新方程适用于 CBOW 模型和 Skip-Gram 模型。但是在 Skip-Gram 模型中，需要对$C$$ C $ 个输出的每一个单词进行更新。

4. CBOW 输入参数更新：对于 CBOW 模型，定义：

   $$\begin{array}{}\text{(60)}& \overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}=\sum _{j=1}^{L(w)-1}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\cdot \overrightarrow{\mathbf{h}})}{\partial \overrightarrow{\mathbf{h}}}=\sum _{j=1}^{L(w)-1}{e}_{n(w,j)}{\overrightarrow{\mathbf{v}}}_{n(w,j)}^{\prime }\end{array}$$

   $\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 的物理意义为：二叉树中所有内部节点向量表达的加权和，其权重为$e_{n(w,j)}$$ e_{n(w,j)} $ 。

   考虑到$\overrightarrow{\mathbf{h}}=\frac{1}{C}{\mathbf{W}}^T({\overrightarrow{\mathbf{x}}}_1+{\overrightarrow{\mathbf{x}}}_2+\cdots +{\overrightarrow{\mathbf{x}}}_C)$$ \mathbf{\vec h}=\frac 1C \mathbf W^T(\mathbf{\vec x}_1+\mathbf{\vec x}_2+\cdots+\mathbf{\vec x}_C) $ ，则有：

   $$\begin{array}{}\text{(61)}& \frac{\partial E}{\partial w_{k,i}}=\frac{\partial E}{\partial h_i}\times \frac{\partial h_i}{\partial w_{k,i}}=\frac{1}{C}E{H}_i\times (x_{(1,k)}+x_{(2,k)}+\cdots ,+x_{(C,k)})\end{array}$$

   写成矩阵的形式为：$\frac{\partial E}{\partial \mathbf{W}}=\frac{1}{C}\sum _{c=1}^C{\overrightarrow{\mathbf{x}}}_c\otimes \overrightarrow{\mathbf{EH}}$$ \frac{\partial E}{\partial \mathbf W}= \frac 1C \sum_{c=1}^C\mathbf{\vec x}_c\otimes \mathbf{\overrightarrow {EH}} $ ，其中$\otimes$$ \otimes $ 为克罗内克积。

   将$\mathbf{W}$$ \mathbf W $ 的更新分解为$C$$ C $ 次，每次对应于一个输入${\overrightarrow{\mathbf{x}}}_c$$ \mathbf{\vec x}_c $ 。因此得到$\mathbf{W}$$ \mathbf W $ 的更新方程：

   $$\begin{array}{}\text{(62)}& {\overrightarrow{\mathbf{w}}}_{I_i}^{(new)}={\overrightarrow{\mathbf{w}}}_{I_i}^{(old)}-\frac{1}{C}\eta \overrightarrow{\mathbf{EH}},i=1,2,\cdots ,C\end{array}$$

   其中$I_i$$ I_i $ 为第$i$$ i $ 个输入单词在词表$\mathbb{V}$$ \mathbb V $ 中的编号。

5. Skip-Gram 输入参数更新：对于 Skip-Gram 模型，定义：

   $$\begin{array}{}\text{(63)}& \begin{array}{c}\overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}=\sum _{c=1}^C\sum _{j=1}^{L(w_c)-1}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{v}}}_{n(w_c,j)}\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{v}}}_{n(w_c,j)}\cdot \overrightarrow{\mathbf{h}})}{\partial \overrightarrow{\mathbf{h}}}\\ =\sum _{c=1}^C\sum _{j=1}^{L(w_c)-1}{e}_{n(w_c,j)}\times {\overrightarrow{\mathbf{v}}}_{n(w_c,j)}\end{array}\end{array}$$

   其中：$w_c$$ w_c $ 表示网络第$c$$ c $ 个输出的输出单词。

   注意：由于引入分层softmax，导致更新路径因为输出单词的不同而不同。因此$\sum _{j=1}^{L(w_c)-1}$$ \sum_{j=1}^{L(w_c)-1} $ 会因为$c$$ c $ 的不同而不同。

   与Skip-Gram 中推导相同，$\mathbf{W}$$ \mathbf W $ 的更新方程为：

   $$\begin{array}{}\text{(64)}& {\overrightarrow{\mathbf{w}}}_I^{(new)}={\overrightarrow{\mathbf{w}}}_I^{(old)}-\eta \overrightarrow{\mathbf{EH}}\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 为$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 非零分量对应的$\mathbf{W}$$ \mathbf W $ 中的行，而$\mathbf{W}$$ \mathbf W $ 的其它行在本次更新中都保持不变。

3.3.2 负采样

a) 原理

1. 在网络的输出层，真实的输出单词对应的输出单元作为正向单元，其它所有单词对应的输出单元为负向单元。

   • 正向单元的数量为 1，毋庸置疑，正向单元必须输出。

   • 负向单元的数量为$V-1$$ V-1 $ ，其中$V$$ V $ 为词表的大小，通常为上万甚至百万级别。如果计算所有负向单元的输出概率，则计算量非常庞大。

     可以从所有负向单元中随机采样一批负向单元，仅仅利用这批负向单元来更新。这称作负采样。

2. 负采样的核心思想是：利用负采样后的输出分布来模拟真实的输出分布。

   对于真实的输出分布，有：

   $$\begin{array}{}\text{(65)}& y_j=p({\text{word}}_j\mid \overrightarrow{\mathbf{x}})=\frac{\exp (u_j)}{\sum _{j^{\prime }=1}^V\exp (u_{j^{\prime }})},j=1,2,\cdots ,V\end{array}$$

   对于负采样后的输出分布，假设真实输出单词$w_O$$ w_O $ 对应于输出单元$j^{\ast }$$ j^* $ ，负采样的$K$$ K $ 个单词对应的输出单元${\mathcal{W}}_{neg}=\{j_{ne{g}_1},\cdots ,j_{ne{g}_K}\}$$ \mathcal W_{neg}=\{j_{neg_1},\cdots,j_{neg_K}\} $ ，则有：

   $$\begin{array}{}\text{(66)}& \begin{array}{c}{\hat{y}}_j=\hat{p}({\text{word}}_j\mid \overrightarrow{\mathbf{x}})=\{\begin{array}{ll}\frac{\exp (u_j)}{\sum _{j^{\prime }\in \{j^{\ast },j_{ne{g}_1},\cdots ,j_{ne{g}_K}\}}\exp (u_{j^{\prime }})},& j\in \{j^{\ast },j_{ne{g}_1},\cdots ,j_{ne{g}_K}\}\\ 0,& j\notin \{j^{\ast },j_{ne{g}_1},\cdots ,j_{ne{g}_K}\}\end{array}\end{array}\end{array}$$

   • 在参数的每一轮更新中，负采样实际上只需要用到一部分单词的输出概率。

   • 对于未被采样到的负向单元$j$$ j $ ，其输出单元的预测误差$e_j=0$$ e_j = 0 $ ， 则${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}^{\prime}_j $ 不会被更新。

   • $\overrightarrow{\mathbf{EH}}={\mathbf{W}}^{\prime }\overrightarrow{\mathbf{e}}=\sum _{j=1}^V{e}_j{\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\overrightarrow {EH}} = \mathbf W^\prime \mathbf{\vec e} =\sum_{j=1}^Ve_j \mathbf{\vec w}^{\prime }_j $ 中仅有负采样的单元$j_{ne{g}_1},\cdots ,j_{ne{g}_K}$$ j_{neg_1},\cdots,j_{neg_K} $ 起作用，因此${\overrightarrow{\mathbf{w}}}_I^{(new)}$$ \mathbf{\vec w}_I^{(new)} $ 的更新仅仅依赖于正向单元和负采样的单元。

   • 随着训练的推进，概率分布$\{y_1,y_2,\cdots ,y_V\}$$ \{y_1,y_2,\cdots,y_V\} $ 逐渐接近于真实的分布$\{0,\cdots ,0,1,0,\cdots ,0\}$$ \{0,\cdots,0,1, 0,\cdots,0\} $ （第$j^{\ast }$$ j^* $ 位为 1），其绝大部分概率接近 0 、$y_{j^{\ast }}$$ y_{j^*} $ 接近 1 。

     而概率分布$\{{\hat{y}}_1,\cdots ,{\hat{y}}_V\}$$ \{\hat y_1,\cdots,\hat y_V\} $ 也有类似的性质，因此用概率分布$\{{\hat{y}}_1,\cdots ,{\hat{y}}_V\}$$ \{\hat y_1,\cdots,\hat y_V\} $ 去模拟概率分布$\{y_1,y_2,\cdots ,y_V\}$$ \{y_1,y_2,\cdots,y_V\} $ 效果较好。

3. 负采样时，每个负向单元是保留还是丢弃是随机的。负向单元采样的概率分布称作noise 分布，记做$P_n(w)$$ P_n(w) $ 。

   $P_n(w)$$ P_n(w) $ 可以为任意的概率分布（通常需要根据经验来选择）。谷歌给出的建议是挑选 5~10 个负向单元，根据下面公式来采样：

   $$\begin{array}{}\text{(67)}& P_n(w)=\frac{freq(w{)}^{3/4}}{\sum _{w^{\prime }\ne j^{\ast }}freq(w^{\prime }{)}^{3/4}}\end{array}$$

   其中：$freq(w)$$ freq(w) $ 为单词在语料库中出现的概率，分母仅考虑负向单元（不考虑正向单元）。

   $P_n(w)$$ P_n(w) $ 的物理意义为：单词在语料库中出现的概率越大，则越可能被挑中。

b) 参数更新

1. 假设输出的单词分类两类：

   • 正类：只有一个，即真实的输出单词$w_O$$ w_O $

   • 负类：从$P_n(w)$$ P_n(w) $ 采样得到的$K$$ K $ 个单词${\mathcal{W}}_{neg}=\{j_{ne{g}_1},\cdots ,j_{ne{g}_K}\}$$ \mathcal W_{neg}=\{j_{neg_1},\cdots,j_{neg_K}\} $

   论文word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method 的作者指出：下面的训练目标能够得到更好的结果：

   $$\begin{array}{}\text{(68)}& E=-\log \sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})-\sum _{j\in {\mathcal{W}}_{neg}}\log \sigma (-{{\overrightarrow{\mathbf{w}}}^{\prime }}_j\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   其中：

   • ${{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}$$ \mathbf{\vec w^\prime}_{w_O} $ 为真实的输出单词对应的输出向量，${{\overrightarrow{\mathbf{w}}}^{\prime }}_j$$ \mathbf{\vec w^\prime}_j $ 为负采样的单词得到的输出向量。

   • $\sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})$$ \sigma(\mathbf{\vec w^\prime}_{w_O}\cdot \mathbf{\vec h}) $ ：在单词$w_O$$ w_O $ 上输出为正类的概率；$\sigma (-{{\overrightarrow{\mathbf{w}}}^{\prime }}_j\cdot \overrightarrow{\mathbf{h}})$$ \sigma(-\mathbf{\vec w^\prime}_{j}\cdot \mathbf{\vec h}) $ ：在单词$j$$ j $ 上输出为负类的概率。

   该目标函数是一个经验公式，而不是采用理论上的交叉熵$-\log \frac{\exp ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})}{\sum _{j^{\prime }=1}^V\exp ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{j^{\prime }}\cdot \overrightarrow{\mathbf{h}})}$$ -\log \frac{\exp(\mathbf{\vec w^\prime}_{w_O}\cdot \mathbf{\vec h})}{\sum_{j^\prime=1}^V \exp(\mathbf{\vec w^\prime}_{{j^\prime}}\cdot \mathbf{\vec h})} $ 。其物理意义为：在正类单词上取正类的概率尽可能大，在负类单词上取负类的概率尽可能大。

   它是从另一个角度考虑：输出为正向单元的概率 * 输出为负向单元的概率。

   $$\begin{array}{}\text{(69)}& \sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})\prod _{j^{\prime }\ne w_O}\sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{j^{\prime }}\cdot \overrightarrow{\mathbf{h}})\end{array}$$

   其负的对数似然为：

   $$\begin{array}{}\text{(70)}& \begin{array}{c}-\log (\sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})\prod _{j^{\prime }\ne w_O}\sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{j^{\prime }}\cdot \overrightarrow{\mathbf{h}}))\\ =-\log \sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})-\sum _{j^{\prime }\ne w_O}\log \sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{j^{\prime }}\cdot \overrightarrow{\mathbf{h}})\end{array}\end{array}$$

   仅仅考虑负采样，则可得到：$E=-\log \sigma ({{\overrightarrow{\mathbf{w}}}^{\prime }}_{w_O}\cdot \overrightarrow{\mathbf{h}})-\sum _{j\in {\mathcal{W}}_{neg}}\log \sigma (-{{\overrightarrow{\mathbf{w}}}^{\prime }}_j\cdot \overrightarrow{\mathbf{h}})$$ E=-\log\sigma(\mathbf{\vec w^\prime}_{w_O}\cdot \mathbf{\vec h})-\sum_{j\in \mathcal W_{neg}}\log\sigma(-\mathbf{\vec w^\prime}_j\cdot \mathbf{\vec h}) $ 。

2. 根据$E$$ E $ 的定义，有：

   $$\begin{array}{}\text{(71)}& \begin{array}{c}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}=\{\begin{array}{ll}\sigma ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})-1,& \text{if}j=w_O\\ \sigma ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}}),& \text{if}j\in {\mathcal{W}}_{neg}\end{array}=\sigma ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})-t_j\end{array}\end{array}$$

   其中$t_j$$ t_j $ 标记了单词$j$$ j $ 的标签：

   $$\begin{array}{}\text{(72)}& \begin{array}{c}{t}_j=\{\begin{array}{ll}1,& \text{if}j=w_O\\ 0,& \text{esle}\end{array}\end{array}\end{array}$$

3. 令$e_j=\sigma ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})-t_j$$ e_{j} = \sigma(\mathbf{\vec w}^\prime_{j}\cdot \mathbf{\vec h})-t_j $ ，它刻画了网络在正类单词和负类单词上的预测误差。

   • 当$j=w_O$$ j =w_O $ 时，$e_j$$ e_{j} $ 表示对正类单词预测概率的不足。

   • 当$j\in {\mathcal{W}}_{neg}$$ j \in \mathcal W_{neg} $ 时，$e_j$$ e_{j} $ 表示对负类单词预测概率的过量。

   根据：

   $$\begin{array}{}\text{(73)}& \frac{\partial E}{\partial {\overrightarrow{\mathbf{w}}}_j^{\prime }}=\frac{\partial E}{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}{\partial {\overrightarrow{\mathbf{w}}}_{w_j}^{\prime }}=e_j\times \overrightarrow{\mathbf{h}}\end{array}$$

   则有输出向量的更新方程：

   $$\begin{array}{}\text{(74)}& {\overrightarrow{\mathbf{w}}}_j^{\prime (new)}={\overrightarrow{\mathbf{w}}}_j^{\prime (old)}-\eta \times e_j\times \overrightarrow{\mathbf{h}}\end{array}$$

4. 给定一个样本，在更新输出向量时，只有$K+1$$ K+1 $ 个输出向量（ 1 个输出单词$w_O$$ w_O $ 、$K$$ K $ 个负采样单词对应的输出向量）得到更新，其中$K$$ K $ 通常数量很小。其它所有单词对应的输出向量未能得到更新。

   相比较而言：

   • 原始算法中，给定一个样本在更新输出向量时，所有输出向量（一共$V$$ V $ 个）都得到更新

   • 分层softmax 算法中，给定一个样本在更新输出向量时，$L(w)-1$$ L(w)-1 $ 个内部节点的向量表达得到更新。

5. 输出向量的更新方程可以用于CBOW 模型和 Skip-Gram 模型。

   若用于Skip-Gram 模型，则对每个输出依次执行输出向量的更新。

6. CBOW 输入向量参数更新：对于 CBOW 模型，定义：

   $$\begin{array}{}\text{(75)}& \overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}=\sum _{j\in \{w_O\}\bigcup {\mathcal{W}}_{neg}}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}{\partial \overrightarrow{\mathbf{h}}}=\sum _{j\in \{w_O\}\bigcup {\mathcal{W}}_{neg}}{e}_j\times {\overrightarrow{\mathbf{w}}}_j^{\prime }\end{array}$$

   $\overrightarrow{\mathbf{EH}}$$ \mathbf{\overrightarrow {EH}} $ 的物理意义为：负采样单词、输出单词对应输出向量的加权和，其权重为$e_j$$ e_{j} $ 。

   与分层softmax: CBOW 输入向量参数更新 中的推导相同，$\mathbf{W}$$ \mathbf W $ 的更新方程为：

   $$\begin{array}{}\text{(76)}& {\overrightarrow{\mathbf{w}}}_{I_i}^{(new)}={\overrightarrow{\mathbf{w}}}_{I_i}^{(old)}-\frac{1}{C}\eta \overrightarrow{\mathbf{EH}},i=1,2,\cdots ,C\end{array}$$

   其中$I_i$$ I_i $ 为第$i$$ i $ 个输入单词在词表$\mathbb{V}$$ \mathbb V $ 中的编号。

7. Skip-Gram 输入向量参数更新：对于 Skip-Gram 模型，定义：

   $$\begin{array}{}\text{(77)}& \begin{array}{c}\overrightarrow{\mathbf{EH}}=\frac{\partial E}{\partial \overrightarrow{\mathbf{h}}}=\sum _{c=1}^C\sum _{j\in \{w_O^c\}\bigcup {\mathcal{W}}_{neg}^c}\frac{\partial E}{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}\times \frac{\partial ({\overrightarrow{\mathbf{w}}}_j^{\prime }\cdot \overrightarrow{\mathbf{h}})}{\partial \overrightarrow{\mathbf{h}}}\\ =\sum _{c=1}^C\sum _{j\in \{w_O^c\}\bigcup {\mathcal{W}}_{neg}^c}{e}_j\times {\overrightarrow{\mathbf{w}}}_j^{\prime }\end{array}\end{array}$$

   其中：$w_O^c$$ w_O^c $ 表示网络第$c$$ c $ 个输出的输出单词，${\mathcal{W}}_{neg}^c$$ \mathcal W_{neg}^c $ 表示网络第$c$$ c $ 个输出的负采样单词集。

   注意：由于引入负采样，导致网络每个输出中，对应的输出单词有所不同，负采样单词也有所不同。因此$\{w_O^c\}\bigcup {\mathcal{W}}_{neg}^c$$ \{w_O^c\}\bigcup \mathcal W_{neg}^c $ 会因为$c$$ c $ 的不同而不同。

   与Skip-Gram 中推导相同，$\mathbf{W}$$ \mathbf W $ 的更新方程为：

   $$\begin{array}{}\text{(78)}& {\overrightarrow{\mathbf{w}}}_I^{(new)}={\overrightarrow{\mathbf{w}}}_I^{(old)}-\eta \overrightarrow{\mathbf{EH}}\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_I$$ \mathbf{\vec w}_I $ 为$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 非零分量对应的$\mathbf{W}$$ \mathbf W $ 中的行，而$\mathbf{W}$$ \mathbf W $ 的其它行在本次更新中都保持不变。

3.3.3 降采样

1. 对于一些常见单词，比如 the，我们可以在语料库中随机删除它。这有两个原因（假设使用 CBOW ）：

   • 当 the 出现在上下文时，该单词并不会为目标词提供多少语义上的信息。

   • 当 the 作为目标词时，该单词从语义上本身并没有多大意义，因此没必要频繁更新。

   降采样过程中，单词$w$$ w $ 被保留的概率为：

   $$\text{Error: '\_' allowed only in math mode}$$

   其中$z(w)$$ z(w) $ 为单词$w$$ w $ 在语料库中出现的概率，$\text{Error: '\_' allowed only in math mode}$$ \text{subsampling_rate} $ 为降采样率（默认为 0.001）。

   可以看到：随着单词在语料库中出现的词频越来越大，该单词保留的概率越来越低。

   

3.4 subword embedding

1. 论文 《Enriching Word Vectors with Subword Information》 中，作者提出通过增加字符级信息来训练词向量。

   下图给出了该方法在维基百科上训练的词向量在相似度计算任务上的表现（由人工评估模型召回的结果）。sisg- 和 sisg 模型均采用了 subword embedding，区别是：对于未登录词，sisg- 采用零向量来填充，而 sisg 采用 character n-gram embedding 来填充。

   

2. 单词拆分：每个单词表示为一组 character n-gram 字符（不考虑顺序），以单词 where、 n=3 为例：

   • 首先增加特殊的边界字符 < （单词的左边界）和 > （单词的右边界）。

   • 然后拆分出一组 character n-gram 字符：<wh, whe,her,ere,re> 。

   • 最后增加单词本身：<where>。

   为了尽可能得到多样性的 character n-gram 字符，作者抽取了所有 3<= n <= 6 的 character n-gram 。以单词 mistake 为例：

   
   <mi,mis,ist,sta,tak,ake,ke>,   // n = 3
   <mis,mist,ista,stak,take,ake>, // n = 4
   <mist,mista,istak,stake,take>, // n = 5
   <mista,mistak,istake,stake>,   // n = 6
   <mistake>                      // 单词本身

   注意：这里的 take 和 <take> 不同。前者是某个character n-gram，后者是一个单词。

3. 一旦拆分出单词，则：

   • 词典$\mathbb{V}$$ \mathbb V $ 扩充为包含所有单词和 N-gram 字符。

   • 网络输入包含单词本身以及该单词的所有 character n-gram ，网络输出仍然保持为单词本身。

   模型采用 word2vec ，训练得到每个character n-gram embedding 。最终单词的词向量是其所有 character n-gram embedding包括其本身 embedding 的和（或者均值）。

   如：单词 where 的词向量来自于下面embedding 之和：

   • 单词 <where> 本身的词向量。

   • 一组 character n-gram 字符 <wh, whe,her,ere,re> 的词向量。

4. 利用字符级信息训练词向量有两个优势：

   • 有利于低频词的训练。

     低频词因为词频较低，所以训练不充分。但是低频词包含的 character n-gram 可能包含某些特殊含义并且得到了充分的训练，因此有助于提升低频词的词向量的表达能力。

   • 有利于获取 OOV 单词（未登录词：不在词汇表中的单词）的词向量。

     对于不在词汇表中的单词，可以利用其 character n-gram 的embedding 来获取词向量。

3.5 应用

1. 模型、语料库、超参数这三个方面都会影响词向量的训练，其中语料库对训练结果的好坏影响最大。

   根据论文 How to Generate a Good Word Embedding? ，作者给出以下建议：

   • 模型选择：所有的词向量都是基于分布式分布假说：拥有相似上下文的单词，其词义相似。根据目标词和上下文的关系，模型可以分为两类：

     • 通过上下文来预测目标词。这类模型更能够捕获单词之间的可替代关系。

     • 通过目标词来预测上下文。

     通过实验发现：简单的模型（Skip-Gram) 在小语料库下表现较好。复杂的模型在大语料库下略有优势。

   • 语料库：实际上语料库并不是越大越好，语料库的领域更重要。

     • 选择了合适的领域，可能只需要 1/10 甚至 1/100 的语料就能够得到一个大的、泛领域语料库的效果。

     • 如果选择不合适的领域，甚至会导致负面效果，比随机词向量效果还差。

   • 超参数：

     • 词向量的维度：

       • 做词向量语义分析任务时，一般维度越大，效果越好。

       • 做具体NLP 任务时（用作输入特征、或者网络初始化），50 维之后效果提升就比较少了。

     • 迭代次数：由于训练词向量的目标是尽可能精确地预测目标词，这个优化目标和实际任务并不一致。因此最好的做法是：直接用实际任务的验证集来挑选迭代次数。

       如果实际任务非常耗时，则可以随机挑选某个简单任务（如：情感分类）及其验证集来挑选迭代次数。

2. word2vec 还有一些重要的超参数：

   • 窗口大小：该超参数通常和语料库中句子长度有关，可以统计句子长度分布来设置。

   • min-count：最小词频训练阈值，词频低于该阈值的词被过滤。

   • 降采样率 subsampling_rate：降采样率越低，高频词保留的越少低频词保留的越多。

3. word2vec 结果评估：

   • 通过 kmeans 聚类，查看聚类的簇分布。

   • 通过词向量计算单词之间的相似度，查看相似词。

   • 通过类比来查看类比词：a 之于 b，等价于 c 之于 d 。

   • 使用 tsne 降维可视化查看词的分布。

4. 在 word2vec 中实际上存在两种类型的embedding 向量：$\mathbf{W}\in {\mathbb{R}}^{V\times N}$$ \mathbf W \in \mathbb R^{V\times N} $ 的第$j$$ j $ 行${\overrightarrow{\mathbf{w}}}_j^T$$ \mathbf{\vec w}_j ^T $ 称作单词${\text{word}}_j$$ \text{word}_j $ 的输入向量，${\mathbf{W}}^{\prime }\in {\mathbb{R}}^{N\times V}$$ \mathbf W^\prime \in \mathbb R^{N\times V} $ 的第$j$$ j $ 列${\overrightarrow{\mathbf{w}}}_j^{\prime }$$ \mathbf{\vec w}_j^{\prime } $ 称作单词${\text{word}}_j$$ \text{word}_j $ 的输出向量。

   大多数论文中都采用输入向量${\overrightarrow{\mathbf{w}}}_j$$ \mathbf{\vec w}_j $ 作为单词${\text{word}}_j$$ \text{word}_j $ 的表达，而论文 Using the Output Embedding to Improve Language Models 综合了输入向量和输出向量。在该论文中，作者得出结论：

   • 在 skip-gram 模型中，在常见的衡量词向量的指标上，输出向量略微弱于输入向量。

   • 在基于 RNN 的语言模型中，输出向量反而强于输入向量。

   • 通过强制要求${\mathbf{W}}^T={\mathbf{W}}^{\prime }$$ \mathbf W^T = \mathbf W^\prime $ ，这可以使得输入向量等于输出向量。这种方式得到的词向量能够提升语言模型的困惑度perplexity。

5. word2vec 可以用于计算句子相似度。博客 Comparing Sentence Similarity Methods 总结了 6 种计算句子相似度的方法：

   • 无监督方法：

     • 对句子中所有的词的词向量求平均，获得sentence embedding 。

     • 对句子中所有的词的词向量加权平均，每个词的权重为 tf-idf ，获得sentence embedding 。

     • 对句子中所有的词的词向量加权平均，每个词的权重为 smooth inverse frequency:SIF ；然后考虑所有的句子，并执行主成分分析；最后对每个句子的词向量加权平均减去first principal componet，获得sentence embedding 。

       SIF 定义为：$\frac{a}{a+p(w)}$$ \frac{a}{a+p(w)} $ ，其中$a$$ a $ 是一个超参数（通常取值为 0.001），$p(w)$$ p(w) $ 为数据集中单词$w$$ w $ 的词频。

     • 通过 Word Mover's Distance:WMD ，直接度量句子之间的相似度。

       WMD 使用两个句子中单词的词向量来衡量一个句子中的单词需要在语义空间中移动到另一个句子中的单词的最小距离。

   • 有监督方法：

     • 通过分类任务来训练一个文本分类器，取最后一个 hidden layer 的输出作为 sentence embedding。

       其实这就是使用文本分类器的前几层作为 encoder 。

     • 直接训练一对句子的相似性，其优点是可以直接得到 sentence embeding 。

   最终结论是：简单加权的词向量平均已经可以作为一个较好的 baseline 。

3.6 SGNS vs 矩阵分解

1. 论文 《NeuralWord Embedding as Implicit Matrix Factorization》 证明了带负采样的 SkipGram 模型 skip-gram with negative-sampling:SGNS 等价于隐式的矩阵分解。

2. 给定语料库$\mathbb{C}=\{w_1,w_2,\cdots ,w_N\},w_i\in \mathbb{V}$$ \mathbb C = \{w_1,w_2,\cdots,w_N\},w_i \in \mathbb V $ 。对于单词$w_i$$ w_i $ ，将其右侧两侧距离为$L$$ L $ 范围内单词$c_j\in {\mathcal{N}}_{w_i}=\{w_{i-L},\cdots ,w_{i-1},w_{i+1},\cdots ,w_{i+L}\}$$ c_j \in \mathcal N_{w_i} = \{ w_{i-L},\cdots,w_{i-1},w_{i+1},\cdots,w_{i+L}\} $ 作为上下文。定义：

   • 定义$\mathbb{D}=\{(w_i,c_j)\mid w_i\in \mathbf{C},c_j\in {\mathcal{N}}_{w_i}\}$$ \mathbb D = \{(w_i,c_j)\mid w_i \in \mathbf C,c_j\in \mathcal N_{w_i} \} $ 为所有观察到的 word-context 组合。

   • 定义${\mathbb{V}}_C=\{c_j\mid w_i\in \mathbf{C},c_j\in {\mathcal{N}}_{w_i}\}$$ \mathbb V_C = \{ c_j \mid w_i \in \mathbf C,c_j\in \mathcal N_{w_i} \} $ 为所有 context 单词的词汇表，通常有${\mathbb{V}}_C=\mathbb{V}$$ \mathbb V_C = \mathbb V $ 。

   • 定义$n(w,c)$$ n(w,c) $ 为给定 word-context 组合在$\mathbb{D}$$ \mathbb D $ 中出现的次数，$n(w)$$ n(w) $ 为单词$w\in \mathbb{V}$$ w\in \mathbb V $ 在$\mathbb{D}$$ \mathbb D $ 中出现的次数，$n(c)$$ n(c) $ 为上下文$c\in {\mathbb{V}}_C$$ c\in \mathbb V_C $ 在$\mathbb{D}$$ \mathbb D $ 中出现的次数。

     其中：

     $$\begin{array}{}\text{(79)}& \begin{array}{c}n(w)=\sum _{c\in {\mathbb{V}}_c}n(w,c),n(c)=\sum _{w\in \mathbb{V}}n(w,c)\\ |\mathbb{D}|=\sum _{w\in \mathbb{V},c\in {\mathbb{V}}_c}n(w,c)=\sum _{w\in \mathbb{V}}n(w)=\sum _{c\in {\mathbb{V}}_c}n(c)\end{array}\end{array}$$

   • 定义单词${\text{word}}_i$$ \text{word}_i $ 作为current word 时 embedding 向量为${\overrightarrow{\mathbf{w}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec w}_i\in \mathbb R^d $ ，作为context 时embedding 向量为${\overrightarrow{\mathbf{w}}}_i^{\prime }\in {\mathbb{R}}^d$$ \mathbf{\vec w}_i^\prime\in \mathbb R^d $ 。

     定义单词的 representation 矩阵为$\mathbf{W}\in {\mathbb{R}}^{V\times d}$$ \mathbf W\in \mathbb R^{ V \times d} $ ，其每一行代表词汇表$\mathbb{V}$$ \mathbb V $ 中每个单词的embeddign 向量。

     定义上下文的 representation 矩阵为${\mathbf{W}}^{\prime }\in {\mathbb{R}}^{|{\mathbb{V}}_C|\times d}$$ \mathbf W^\prime \in \mathbb R^{ |\mathbb V_C| \times d} $ ，其每一行代表词汇表${\mathbb{V}}_C$$ \mathbb V_C $ 中每个单词作为上下文时的embeddign 向量。

   给定一对 word-context$(w,c)$$ (w,c) $ ，假设单词$w$$ w $ 作为 current word 的 embedding 为${\overrightarrow{\mathbf{w}}}_w$$ \mathbf{\vec w}_w $ ，上下文$c$$ c $ 作为context 的 embedding 为${\overrightarrow{\mathbf{w}}}_c^{\prime }$$ \mathbf{\vec w}_c^\prime $ 。定义$(w,c)$$ (w,c) $ 被观察到（即 postive ）的概率为：

   $$\begin{array}{}\text{(80)}& p(D=1\mid w,c)=\sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })}\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_w,{\overrightarrow{\mathbf{w}}}_c^{\prime }$$ \mathbf{\vec w}_w,\mathbf{\vec w}_c^\prime $ 为模型需要学习的参数。

   SGNS 最大化观察到的 word-context 组合、最小化未观察到的 word-context 组合。由于$\mathbb{D}$$ \mathbb D $ 中所有的 word-context 组合都是观察到的，属于postive 样本，因此SGNS 需要通过随机采样一些 word-context 作为负样本。这就是负采样名称的由来。

   • 理论而言只有随机采样的、未观察到的 word-context 才能作为负样本。这里直接使用随机采样的结果作为负样本有两个原因：

     • 便于理论上推导。但是二者并不影响 SGNS 等价于矩阵分解的性质。

     • 由于$\mathbb{V}\times {\mathbb{V}}_C$$ \mathbb V\times \mathbb V_C $ 的空间巨大，观察到的 word-context 集合仅仅占据很小的部分，因此采样得到的 word-context 组合是未观察到的概率几乎为 1 。

   • 理论而言未观察到的 word-context 组合不一定是负样本，某些word-context 组合是合理的，只是它们从未在语料库中出现过。

   对于每一对观察到的 word-context 组合$(w,c)$$ (w,c) $ ，SGNS 的损失函数为：

   $$\begin{array}{}\text{(81)}& l(w,c)=\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })+k\times {\mathbb{E}}_{c_N\sim P_D}[\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })]\end{array}$$

   其中$k$$ k $ 为负采样的数量，$c_N$$ c_N $ 为给定 current word$w$$ w $ 进行负采样的上下文。$P_D$$ P_D $ 为负采样中上下文的分布，有两种常见的分布：

   • 非均匀分布：

     $$\begin{array}{}\text{(82)}& p_D(c)=\frac{n(c{)}^{3/4}}{\sum _{c^{\prime }\in {\mathbb{V}}_C}n(c^{\prime }{)}^{3/4}}\end{array}$$

     这和前面介绍的一致。

   • 均匀分布：

     $$\begin{array}{}\text{(83)}& p_D(c)=\frac{n(c)}{|\mathbb{D}|}\end{array}$$

     虽然非均匀分布在某些任务上能够产生更好的结果，但是这里采用均匀分布从而得到更好的理论推导。另外，二者并不影响 SGNS 等价于矩阵分解的性质。

   最终得到 SGNS 总的损失函数为：

   $$\begin{array}{}\text{(84)}& \mathcal{L}=\sum _{(w,c)\in \mathbb{D}}l(w,c)=\sum _{w\in \mathbb{V}}\sum _{c\in {\mathbb{V}}_C}n(w,c)(\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })+k\times {\mathbb{E}}_{c_N\sim P_D}[\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })])\end{array}$$

3. SGNS 的优化目标使得：

   • 观察到的 word-context$(w,c)$$ (w,c) $ 具有相似的 embedding，即$p(D=1\mid w,c)=\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })$$ p(D=1 \mid w,c) = \log\sigma(\mathbf{\vec w}_w\cdot\mathbf{\vec w}_c^\prime) $ 较大。

   • 未观察到的 word-context$(w,c_N)$$ (w,c_N) $ 具有不相似的 embedding，即$p(D=1\mid w,c_N)=\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })$$ p(D=1 \mid w,c_N) = \log\sigma(\mathbf{\vec w}_w\cdot\mathbf{\vec w}_{c_N}^\prime) $ 较小。

4. 当$P_D$$ P_D $ 采用均匀分布时有：

   $$\begin{array}{}\text{(85)}& {\mathbb{E}}_{c_N\sim P_D}[\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })]=\sum _{c_N\in {\mathbb{V}}_C}\frac{n(c_N)}{|\mathbb{D}|}\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })\end{array}$$

   因此有：

   $$\begin{array}{}\text{(86)}& \begin{array}{c}\mathcal{L}=\sum _{(w,c)\in \mathbb{D}}l(w,c)=\sum _{w\in \mathbb{V}}\sum _{c\in {\mathbb{V}}_C}n(w,c)(\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }))+\sum _{w\in \mathbb{V}}n(w)(k\times {\mathbb{E}}_{c_N\sim P_D}[\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })])\\ =\sum _{w\in \mathbb{V}}\sum _{c\in {\mathbb{V}}_C}n(w,c)(\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }))+\sum _{w\in \mathbb{V}}\sum _{c_N\in {\mathbb{V}}_C}n(w)(k\times \frac{n(c_N)}{|\mathbb{D}|}\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime }))\\ =\sum _{w\in \mathbb{V}}\sum _{c\in {\mathbb{V}}_C}(n(w,c)\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })+k\times \frac{n(w)n(c)}{|\mathbb{D}|}\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }))\end{array}\end{array}$$

   因此样本空间$\mathbb{V}\times {\mathbb{V}}_C$$ \mathbb V\times \mathbb V_C $ 中每一对 word-context 组合$(w,c)$$ (w,c) $ 的损失为：

   $$\begin{array}{}\text{(87)}& \mathcal{L}(w,c)=n(w,c)\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })+k\times \frac{n(w)n(c)}{|\mathbb{D}|}\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })\end{array}$$

   由于样本空间$\mathbb{V}\times {\mathbb{V}}_C$$ \mathbb V\times \mathbb V_C $ 中的组合$(w,c)$$ (w,c) $ 之间是相互独立的，因此当每一对组合$(w,c)$$ (w,c) $ 的$\mathcal{L}(w,c)$$ \mathcal L (w,c) $ 最小时$\mathcal{L}$$ \mathcal L $ 最小。定义$e={\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }$$ e= \mathbf{\vec w}_w\cdot \mathbf{\vec w}^\prime_{c} $ ，根据：

   $$\begin{array}{}\text{(88)}& \frac{\partial \mathcal{L}(w,c)}{\partial e}=0\end{array}$$

   解得：

   $$\begin{array}{}\text{(89)}& e={\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }=\log \left(\frac{n(w,c)\times |\mathbb{D}|}{n(w)\times n(c)}\right)-\log k\end{array}$$

5. 给定随机变量$X,Y$$ X,Y $ ，Pointwise Mutual Information :PMI 定义为

   $$\begin{array}{}\text{(90)}& \text{PMI}(X,Y)=\log \frac{P(X,Y)}{P(X)\times P(Y)}\end{array}$$

   记单词$w$$ w $ 出现在$\mathbb{D}$$ \mathbb D $ 中的概率为$P(w)=\frac{n(w)}{|\mathbb{D}|}$$ P(w) = \frac{n(w)}{|\mathbb D|} $ ，记上下文$c$$ c $ 出现在$\mathbb{D}$$ \mathbb D $ 中的概率为$P(c)=\frac{n(c)}{|\mathbb{D}|}$$ P(c) = \frac{n(c)}{|\mathbb D|} $ ，记 word-context 组合$(w,c)$$ (w,c) $ 出现在$\mathbb{D}$$ \mathbb D $ 中的概率为$P(w,c)=\frac{n(w,c)}{|\mathbb{D}|}$$ P(w,c) = \frac{n(w,c)}{|\mathbb D|} $ 。则有：

   $$\begin{array}{}\text{(91)}& \log \left(\frac{n(w,c)\times |\mathbb{D}|}{n(w)\times n(c)}\right)=\text{PMI}(w,c)\end{array}$$

6. 定义矩阵$\mathbf{M}$$ \mathbf M $ 为：

   $$\begin{array}{}\text{(92)}& M_{i,j}=\text{PMI}(w={\text{word}}_i,c={\text{word}}_j)-\log k=\log \left(\frac{n(w={\text{word}}_i,c={\text{word}}_j)\times |\mathbb{D}|}{n(w={\text{word}}_i)\times n(c={\text{word}}_j)}\right)-\log k\end{array}$$

   则有：

   $$\begin{array}{}\text{(93)}& \mathbf{M}=\mathbf{W}({\mathbf{W}}^{\prime }{)}^T\end{array}$$

   • 这里的推导只有当维度$d$$ d $ 足够大时成立，因为如果$d$$ d $ 太小，则$\mathbf{W}$$ \mathbf W $ 和${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 容量太小表达能力太弱，无法完美的重建矩阵$\mathbf{M}$$ \mathbf M $ 。

     设矩阵$\mathbf{M}$$ \mathbf M $ 的秩为$r_M$$ r_M $ ，则维度$d$$ d $ 应该满足$d\ge r_M$$ d\ge r_M $ 。如果$d<r_M$$ d \lt r_M $ ，则右侧$\mathbf{W}({\mathbf{W}}^{\prime }{)}^T$$ \mathbf W(\mathbf W^\prime)^T $ 的秩$r\le d<r_M$$ r\le d\lt r_M $ ，这种分解难以成立。

   • 当负采样个数$k=1$$ k= 1 $ 时$M_{i,j}=\text{PMI}(w={\text{word}}_i,c={\text{word}}_j)$$ M_{i,j} = \text{PMI}(w = \text{word}_i,c = \text{word}_j) $ ，此时 SGNS 等价于分解 PMI 矩阵。

7. 直接计算 PMI 矩阵非常具有挑战性：

   • 矩阵的维度$|\mathbb{V}|\times |{\mathbb{V}}_C|$$ |\mathbb V|\times |\mathbb V_C| $ 非常高。

   • 绝大多数组合$(w,c)\in \mathbb{V}\times {\mathbb{V}}_C$$ (w,c) \in \mathbb V\times \mathbb V_C $ 从未出现语料库中从而导致$\text{PMI}(w,c)=\log 0=-\mathrm{\infty }$$ \text{PMI}(w,c) = \log 0 = -\infty $ 。

     这可以通过引入一些先验概率使得未见过的$(w,c)$$ (w,c) $ 的 PMI 为一个有效的数来解决。

   • PMI 矩阵是 dense 矩阵。

   一个解决方案是：当$n(w,c)=0$$ n(w,c) = 0 $ 时令$\text{PMI}(w,c)=0$$ \text{PMI}(w,c) = 0 $ ，这使得 PMI 矩阵成为一个巨大的稀疏矩阵，称作${\mathbf{M}}_0$$ \mathbf M_0 $ 。

   事实上当$P(w),P(c)$$ P(w),P(c) $ 都很高、但是$P(w,c)$$ P(w,c) $ 很低时，这表明$w$$ w $ 和$c$$ c $ 分别单独出现的次数跟高，但是一起出现的次数很低。因此可以认为：

   • $P(w,c)>P(w)\times p(c)$$ P(w,c) \gt P(w)\times p(c) $ 时$\text{PMI}(w,c)>0$$ \text{PMI}(w,c) \gt 0 $ ，表明观察到的 word-context$(w,c)$$ (w,c) $ 是相关的。

   • $P(w,c)\le P(w)\times p(c)$$ P(w,c) \le P(w)\times p(c) $ 时$\text{PMI}(w,c)\le 0$$ \text{PMI}(w,c) \le 0 $ ，表明观察到的 word-context$(w,c)$$ (w,c) $ 是不相关的。

   考虑到未观察到的 word-context$(w,c)$$ (w,c) $ 有$\text{PMI}(w,c)=0$$ \text{PMI}(w,c) = 0 $ ，因此可以将所有不相关 word-context 的 PMI 都设置为零，仅考虑正的PMI （即 PPMI）：

   $$\begin{array}{}\text{(94)}& \text{PPMI}(w,c)=max(\text{PMI}(w,c),0)\end{array}$$

   这和人类的直觉相符：人们很容易联想到正的关联，如 “加拿大” 和 “滑雪” ，但是很难关注一些无关的组合，如“加拿大” 和 “沙漠” 。因此将无效的信息丢弃（PMI 置为零）而仅保留有效信息更符合经验和直觉。

8. 如果继续在 PPMI 中考虑偏移，则得到 Shifted PPMI:SPPMI：

   $$\begin{array}{}\text{(95)}& {\text{SPPMI}}_k(w,c)=max(\text{PMI(w,c)}-\log k,0)\end{array}$$

9. 可以直接将PMI 矩阵、PPMI 矩阵 或者 SPPMI 矩阵中，单词$w$$ w $ 对应的行作为其 representation，此时单词的 representatioin 是一个高维向量。对于 PPMI,SPPMI，该向量还是稀疏的。此时有：$\mathbf{W}=\mathbf{M},{\mathbf{W}}^{\prime }=\mathbf{I}$$ \mathbf W = \mathbf M,\mathbf W^\prime = \mathbf I $ 。

   也可以通过降维获得单词的低维representatiion，如：可以通过 SVD 分解来求解$\mathbf{W}$$ \mathbf W $ 和${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 。

   首先将$\mathbf{M}$$ \mathbf M $ 进行 SVD 分解：

$$\begin{array}{}\text{(96)}& \mathbf{M}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T\end{array}$$

其中$\mathbf{U},\mathbf{V}$$ \mathbf U,\mathbf V $ 均为正交矩阵，$\mathbf{\Sigma }$$ \mathbf \Sigma $ 为所有奇异值从大到小排列的对角矩阵。

选择最大的$d$$ d $ 个奇异值组成对角矩阵${\mathbf{\Sigma }}_d$$ \mathbf\Sigma_d $ 、$\mathbf{U}$$ \mathbf U $ 的前$d$$ d $ 列组成矩阵${\mathbf{U}}_d$$ \mathbf U_d $ 、$\mathbf{V}$$ \mathbf V $ 的前$d$$ d $ 列组成矩阵${\mathbf{V}}_d$$ \mathbf V_d $ ，则有：

$$\begin{array}{}\text{(97)}& \mathbf{M}\simeq {\mathbf{M}}_d={\mathbf{U}}_d{\mathbf{\Sigma }}_d({\mathbf{V}}_d{)}^T\end{array}$$

可以选择$\mathbf{W}={\mathbf{U}}_d{\mathbf{\Sigma }}_d,{\mathbf{W}}^{\prime }={\mathbf{V}}_d$$ \mathbf W =\mathbf U_d\mathbf \Sigma_d , \mathbf W^\prime = \mathbf V_d $ 。但是实际应用中发现该方法求解的$\mathbf{W}$$ \mathbf W $ 要比 SGNS 效果较差。注意到这种分解方法中，${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 是正交矩阵而$\mathbf{W}$$ \mathbf W $ 不是正交矩阵，这表明$\mathbf{W}$$ \mathbf W $ 和${\mathbf{W}}^{\prime }$$ \mathbf W^\prime $ 的性质不对称。而在 SGNS 中，求解的这两个矩阵都不是正交矩阵，因此可以进行如下分解：

$$\begin{array}{}\text{(98)}& \mathbf{W}={\mathbf{U}}_d\sqrt{{\mathbf{\Sigma }}_d},{\mathbf{W}}^{\prime }={\mathbf{V}}_d\sqrt{{\mathbf{\Sigma }}_d}\end{array}$$

虽然理论上无法证明这种方式的效果更好，但是实践中发现它确实表现更佳。

10. 基于随机梯度下降的 SGNS 和基于矩阵分解的方式各有优点：

    • 基于矩阵分解的优点：

      • 无需精心调优学习率等超参数。

      • 可以按照 word-context 聚合之后的频次数据来训练，这种方式可以训练比 SGNS 大得多得语料库。

        与之相反，SGNS 中每个 word-context 出现一次就需要训练一次。

    • 基于 SGNS 的优点：

      • SGNS 可以区分观测值和未观测值，而 SVD 无法判断一个 word-context 为零是因为未观测还是因为 PMI 较低。这在 word-context 矩阵中非常常见。

      • SGNS 的目标函数对不同的$(w,c)$$ (w,c) $ 进行加权：越频繁出现的$(w,c)$$ (w,c) $ 权重越高，误差越低；越稀疏出现的$(w,c)$$ (w,c) $ 权重越低，因此允许其误差较大。

        在 SVD 分解中，无法区分$(w,c)$$ (w,c) $ 的重要性，对所有的$(w,c)$$ (w,c) $ 给与相同的权重，因此也无法使得权重较大的$(w,c)$$ (w,c) $ 的误差更低。

      • SGNS 仅仅关注于观测值，因此它不要求底层的矩阵是稀疏的，可以直接优化 dense 矩阵。

        因为 SVD 的求解困难，所以SVD 通常要求底层矩阵是稀疏的，因此它通常采用 PPMI/SPPMI 。

11. noise-contrastive estimation:NCE 采用类似的推导过程可以分解为：

    $$\begin{array}{}\text{(99)}& M_{i,j}=\log P(w={\text{word}}_i\mid c={\text{word}}_j)-\log k=\log \left(\frac{n(w={\text{word}}_i,c={\text{word}}_j)}{n(c={\text{word}}_j)}\right)-\log k\end{array}$$

12. 实验：

    • 数据集：英文维基百科。经过清理非文本字符、句子拆分、词干化之后，数据集包含 7750万句子、15亿 token 。

      • 每个token 分别取左右两侧2 个token 作为上下文从而生成 word-context 集合$\mathbb{D}$$ \mathbb D $ 。

      • 过滤掉$\mathbb{D}$$ \mathbb D $ 中频次低于 100次的 word-context 组合。

      最终得到$\mathbb{V}$$ \mathbb V $ 和${\mathbb{V}}_C$$ \mathbb V_C $ 包含 189533 个单词。

    • 模型：SPPMI、SGNS 以及 SVD 。其中：

      • 所有模型评估当$k=1,5,15$$ k=1,5,15 $ 的结果

      • 对于 SPPMI，将该矩阵的各行作为对应单词的 representation

      • 对于 SVD 采用分解$\mathbf{W}={\mathbf{U}}_d\sqrt{{\mathbf{\Sigma }}_d},{\mathbf{W}}^{\prime }={\mathbf{V}}_d\sqrt{{\mathbf{\Sigma }}_d}$$ \mathbf W =\mathbf U_d\sqrt{\mathbf \Sigma_d} ,\quad \mathbf W^\prime = \mathbf V_d \sqrt{\mathbf \Sigma_d} $

    • 我们根据训练目标函数和理论目标函数来评估各算法的优化算法效果。

      考虑目标函数：

      $$\begin{array}{}\text{(100)}& \mathcal{L}=\sum _{w\in \mathbb{V}}\sum _{c\in {\mathbb{V}}_C}n(w,c)(\log \sigma ({\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime })+k\times {\mathbb{E}}_{c_N\sim P_D}[\log \sigma (-{\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_{c_N}^{\prime })])\end{array}$$

      • 对于 SGNS 我们直接通过随机梯度下降结束时的目标函数值作为$\hat{\mathcal{L}}$$ \hat{\mathcal L} $ 。

      • 对于 SVD 我们根据$M_{w,c}=max(\text{PMI}(w,c)-\log k,0)$$ M_{w,c} = \max(\text{PMI}(w,c) -\log k,0 ) $ 填充$\mathbf{M}$$ \mathbf M $ ，然后根据矩阵分解的结果计算$\mathcal{L}$$ \mathcal L $ 得到$\hat{\mathcal{L}}$$ \hat{\mathcal L} $ 。

      • 对于 SPPMI，我们将它的各行作为对应单词的 representatioin，上下文采用 one-hot 向量的形式，因此有：${\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }=max(\text{PMI(w,c)}-\log k,0)$$ \mathbf{\vec w}_w\cdot \mathbf{\vec w}^\prime_{c} = \max(\text{PMI(w,c)} - \log k,0) $ 。

      • 然后根据${\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }=\text{PMI}(w,c)-\log k$$ \mathbf{\vec w}_w\cdot \mathbf{\vec w}^\prime_{c} = \text{PMI}(w,c) -\log k $ 求解目标函数的理论值${\mathcal{L}}_{OPT}$$ \mathcal L_{OPT} $ 。

      然后我们评估优化目标函数值和理论目标函数值的相对误差：

      $$\text{Error: '\_' allowed only in math mode}$$

      结果见下表。其中 PMI-log k 表示理论误差，SPPMI 表示采用${\overrightarrow{\mathbf{w}}}_w\cdot {\overrightarrow{\mathbf{w}}}_c^{\prime }=max(\text{PMI}(w,c)-\log k,0)$$ \mathbf{\vec w}_w\cdot \mathbf{\vec w}^\prime_{c} = \max(\text{PMI}(w,c) -\log k,0 ) $ 直接计算得到（而不是矩阵分解）的SPPMI 理论值对应的误差。

      • 尽管 SPPMI 仅考虑非负元素而丢弃大量信息，它与最优解的理论值非常接近。

      • SVD 方法中，维度$d$$ d $ 越大效果越好。

      • 对于$k=1$$ k=1 $ ：当$d\le 500$$ d\le 500 $ 时 SVD 优化效果比 SGNS 更好；但是当维度更高时 SGNS 的优化误差比 SVD 的降低得多得多。

      • SVD 对于$k$$ k $ 值非常敏感，随着$k$$ k $ 值的增加优化误差迅速增长。作者猜测这是由于当$k$$ k $ 越大时$\mathbf{M}$$ \mathbf M $ 中零元素数量也越多，这导致 SVD 的分解结果更接近零矩阵。因为 SVD 的目标函数是无权重的，它无法 “更关注” 那些观测结果。

      

    • 在四个数据集上评估 word similarity 单词相似任务和单词类比任务。

      • 在数据集 WordSim353 和 MEN 上评估单词相似任务。这些数据集包含人工标注的 pair-wise 单词相似度得分。

      • 在数据集 Syntactic 和 Mixed 上评估单词类比任务。

      $d=1000$$ d=1000 $ 时结果如下图所示：

      • 在单词相似任务上 SVD 超越了SPPMI （采用随机梯度下降），而 SPPMI 超越了 SGNS 。

      • 在单词相似任务上对于 SGNS 任务$k$$ k $ 越大效果越好，但是对于 SPPMI,SVD 随着$k$$ k $ 的上升性能先上升后下降。

        这是因为SPPMI,SVD 中仅保留正的值，随着$k$$ k $ 越大信息丢失越多。

      • 在单词类比任务上 SGNS 超越了 SVD 。这是因为单词类比任务中更依赖于那些上下文中频繁出现的单词，如the,each,many 以及辅助动词 will,had 。SGNS 训练过程会更关注于这些频繁出现的 word-context 组合，而 SVD 对所有的 word-context 是无权重的。