word2vec

$$\begin{align} \end{align}$$

1 连续词袋模型（CBOW）与跳字模型（Skip-gram）

单词$w$；
词典$\mathcal{D}=\{w_1,w_2,\dots,w_N\}$，由单词组成的集合；
语料库$\mathcal{C}$，由单词组成的文本序列；
单词$w_t$的上下文是语料库中由单词$w_t$的前$c$个单词和后$c$个单词组成的文本序列，$w_t$称为中心词。

$$Context\left(w_t\right)=\left(w_{t-c},\cdots,w_{t-2},w_{t-1},w_{t+1},w_{t+2},\cdots,w_{t+c}\right)$$

连续词袋模型（CBOW, Continuous Bag-of-Words Model）假设中心词由该词在文本序列中的上下文来生成。
跳字模型（Skip-gram）假设中心词生成该词在文本序列中的上下文。

2 基于层序softmax（Hierarchical softmax）方法的连续词袋模型训练

基于层序softmax方法的连续词袋模型网络结构：
输入层：$\mathbf{v}\left(Context\left(w\right)_1\right),\mathbf{v}\left(Context\left(w\right)_2\right),\cdots,\mathbf{v}\left(Context\left(w\right)_{2c}\right)\in\mathbb{R}^m$，其中$\mathbf{v}\left(\cdot\right)$为单词的向量化表示；
投影层：$\mathbf{x}_w=\sum_{i=1}^{2c}\mathbf{v}\left(Context\left(w\right)_i\right)\in\mathbb{R}^m$；
输出层：$T_{Huff}\left(\mathbf{x}_w\right)=s_{q\left(\mathbf{x}_w\right)},s\in\mathbb{R}^N,q:\mathbb{R}^m\to\{1,2,\cdots,N\}$，其中$N$为哈夫曼树叶子结点个数。

记$p^w=\left(p_1^w,p_2^w\cdots,p_{l^w}^w\right)$为从根节点出发到达$w$对应的叶子结点的路径。其中，$l^w$为路径长度，即路径中结点数目；$p_i^w$为路径中的结点，$p_1^w$为根结点，$p_{l^w}^w$为$w$对应的叶子结点。

记

$$d^w=\left(d_2^w,d_3^w\cdots,d_{l^w}^w\right)$$

为$w$的Huffman编码。其中，$d_i^w\in\{0,1\}$为路径$p^w$中第$i$个结点对应的编码（根结点不对应编码）。

记

$$\theta^w=\left(\theta_1^w,\theta_2^w,\cdots,\theta_{l^w-1}^w\right)$$

为路径$p^w$中非叶子结点对应的参数向量。其中，$\theta_i^w\in\mathbb{R}^m$为路径$p^w$中第$i$个非叶子结点对应的参数向量。

条件概率

$$p\left(w|Context\left(w\right)\right)=\prod_{j=2}^{l^w}p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right)$$

其中

$$p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right)=\begin{equation} \left\{ \begin{array}{lr} \sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right),d^w_j =0; \\ 1-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right),d^w_j=1, & \end{array} \right. \end{equation}$$

或者

$$p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right)=\left[\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]^{1-d_j^w}\cdot\left[1-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]^{d_j^w}$$

似然函数

$$\begin{align} \ell&=\prod_{w\in\mathcal{C}}p\left(w|Context\left(w\right)\right)\\ &=\prod_{w\in\mathcal{C}}\prod_{j=2}^{l^w}p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right) \end{align}$$

对数似然函数

$$\begin{align}\mathcal{L} &= \log\prod_{w\in\mathcal{C}}\prod_{j=2}^{l^w}p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right) \\ &=\sum_{w\in\mathcal{C}}\log \prod_{j=2}^{l^w} p\left(d_j^w|\mathbf{x}_w,\theta_{j-1}^w\right) \\ &=\sum_{w\in\mathcal{C}}\sum_{j=2}^{l^w}\left\{\left(1-d_j^w\right)\cdot\log\left[\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]+d_j^w\cdot\log\left[1-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\right\} \end{align}$$

对数似然函数$\mathcal{L}$关于$\theta_{j-1}^w$的偏导

$$\begin{align}\frac{\partial\mathcal{L}}{\partial\theta_{j-1}^w}&= \frac{\partial}{\partial\theta_{j-1}^w}\left\{\sum_{w\in\mathcal{C}}\sum_{j=2}^{l^w}\left\{\left(1-d_j^w\right)\cdot\log\left[\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]+d_j^w\cdot\log\left[1-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\right\}\right\} \\ &=\left(1-d_j^w\right)\left[1-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\mathbf{x}_w-d_j^w\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\mathbf{x}_w \\ &=\left[1-d_j^w-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\mathbf{x}_w\end{align}$$

$\theta_{j-1}^w$的更新

$$\theta_{j-1}^w=\theta_{j-1}^w+\eta\left[1-d_j^w-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\mathbf{x}_w$$

其中，$\eta$为学习率。

对数似然函数$\mathcal{L}$关于$\mathbf{x}_w$的偏导

$$\frac{\partial\mathcal{L}}{\partial\mathbf{x}_w}=\sum_{j=2}^{l^w}\left[1-d_j^w-\sigma\left(\mathbf{x}^\top_w\theta^w_{j-1}\right)\right]\theta_{j-1}^w$$

$\mathbf{v}\left(\tilde{w}\right)$的更新

$$\mathbf{v}\left(\tilde{w}\right)=\mathbf{v}\left(\tilde{w}\right)+\eta\frac{\partial\mathcal{L}}{\partial\mathbf{x}_w}$$

其中，$\tilde{w}\in Context\left(w\right)$。

3 基于层序softmax（Hierarchical softmax）方法的跳字模型训练

基于层序softmax方法的跳字模型网络结构：
输入层：$\mathbf{v}\left(w\right)\in\mathbb{R}^m$
输出层：$T_{Huff}\left(\mathbf{v}_w\right)=s_{q\left(\mathbf{v}_w\right)},s\in\mathbb{R}^N,q:\mathbb{R}^m\to\{1,2,\cdots,N\}$

条件概率

$$p\left(Context\left(w\right)|w\right)=\prod_{u\in Context\left(w\right)}p\left(u|w\right)$$

其中

$$p\left(u|w\right)=\prod_{j=2}^{l^u}p\left(d_j^u|\mathbf{v}\left(w\right),\theta_{j-1}^u\right)$$

且

$$p\left(d_j^u|\mathbf{v}\left(w\right),\theta_{j-1}^u\right)=\left[\sigma\left(\mathbf{v}\left(w\right)^\top\theta^u_{j-1}\right)\right]^{1-d_j^u}\cdot\left[1-\sigma\left(\mathbf{v}\left(w\right)^\top\theta^u_{j-1}\right)\right]^{d_j^u}$$

似然函数

$$\begin{align} \ell&=\prod_{w\in\mathcal{C}} p\left(Context\left(w\right)|w\right)\\ &=\prod_{w\in\mathcal{C}}\prod_{u\in Context\left(w\right)}\prod_{j=2}^{l^u}p\left(d_j^u|\mathbf{v}\left(w\right),\theta_{j-1}^u\right) \end{align}$$

对数似然函数

$$\begin{align}\mathcal{L}&=\sum_{w\in\mathcal{C}}log\prod_{u\in Context\left(w\right)}\prod_{j=2}^{l^u}\left\{\left[\sigma\left(\mathbf{v}\left(w\right)^\top\theta^u_{j-1}\right)\right]^{1-d_j^u}\cdot\left[1-\sigma\left(\mathbf{v}\left(w\right)^\top\theta^u_{j-1}\right)\right]^{d_j^u}\right\} \\ &=\sum_{w\in\mathcal{C}}\sum_{u\in Context\left(w\right)}\sum_{j=2}^{l^u}\left\{\left(1-d_j^u\right)\cdot\log\left[\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]+d_j^u\cdot\log\left[1-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\right\}\end{align}$$

对数似然函数$\mathcal{L}$关于$\theta_{j-1}^u$的偏导

$$\begin{align}\frac{\partial\mathcal{L}}{\partial\theta_{j-1}^u} &= \frac{\partial}{\theta_{j-1}^u}\left\{\sum_{w\in\mathcal{C}}\sum_{u\in Context\left(w\right)}\sum_{j=2}^{l^u}\left\{\left(1-d_j^u\right)\cdot\log\left[\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]+d_j^u\cdot\log\left[1-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\right\}\right\}\\ &=\sum_{w\in\mathcal{C}}\left\{\left(1-d_j^u\right)\left[1-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\mathbf{v}\left(w\right)-d_j^u\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\mathbf{v}\left(w\right)\right\} \\ &=\sum_{w\in\mathcal{C}}\left[1-d_j^u-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\mathbf{v}\left(w\right)\end{align}$$

$\theta_{j-1}^u$的更新

$$\theta_{j-1}^u=\theta_{j-1}^u+\eta\sum_{w\in\mathcal{C}}\left[1-d_j^u-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\mathbf{v}\left(w\right)$$

其中，$\eta$为学习率。

对数似然函数$\mathcal{L}$关于$\mathbf{v}\left(w\right)$的偏导

$$\frac{\partial\mathcal{L}}{\partial\mathbf{v}\left(w\right)}=\sum_{u\in Context\left(w\right)}\sum_{j=2}^{l^u}\left[1-d_j^u-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\theta_{j-1}^u$$

$\mathbf{v}\left(w\right)$的跟新

$$\mathbf{v}\left(w\right)=\mathbf{v}\left(w\right)+\eta\sum_{u\in Context\left(w\right)}\sum_{j=2}^{l^u}\left[1-d_j^u-\sigma\left(\mathbf{v}\left(w\right)^\top\theta_{j-1}^u\right)\right]\theta_{j-1}^u$$

4 基于负采样（Negative Sampling）方法的连续词袋模型训练

设$Context\left(w\right)$的负样本子集为

$$NEG\left(w\right)\neq\emptyset$$

对于$\forall\tilde{w}\in\mathcal{D}$，定义

$$\begin{equation} L^w\left(\tilde{w}\right)=\left\{ \begin{array}{lr} 1,\tilde{w}=w & \\ 0,\tilde{w}\neq w \end{array} \right. \end{equation}$$

表示词$\tilde{w}$的标签，正样本标签为$1$，负样本标签为$0$。

关于字典$\mathcal{D}$的子集$\{w\}\bigcup NEG\left(w\right)$的似然函数

$$g\left(w\right)=\prod_{u\in\{w\}\bigcup NEG\left(w\right)} p\left(u|Context\left(w\right)\right)=\sigma\left(\mathbf{x}_w^\top\theta^w\right)\prod_{u\in NEG\left(w\right)}\left[1-\sigma\left(\mathbf{x}_w^\top\theta^w\right)\right]$$

其中

$$\begin{equation} p\left(u|Context\left(w\right)\right)=\left\{ \begin{array}{lr} \sigma\left(\mathbf{x}_w^\top\theta^u\right),L^w\left(u\right)=1 & \\ 1-\sigma\left(\mathbf{x}_w^\top\theta^u\right),L^w\left(u\right)=0 \end{array} \right. \end{equation}$$

或者

$$p\left(u|Context\left(w\right)\right)=\left[\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]^{L^w\left(u\right)}\cdot\left[1-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]^{1-L^w\left(u\right)}$$

$\mathbf{x}_w$为$Context\left(w\right)$词向量之和，$\theta^u\in\mathbb{R}^m$为模型参数。

关于语料库$\mathcal{C}$的对数似然函数

$$\begin{align}\mathcal{L}& =\log\prod_{w\in\mathcal{C}}g\left(w\right)=\sum_{w\in\mathcal{C}}\log g\left(w\right) \\ &=\sum_{w\in\mathcal{C}}\log\prod_{u\in\{w\}\bigcup NEG\left(w\right)}\left\{\left[\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]^{L^w\left(u\right)}\cdot\left[1-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]^{1-L^w\left(u\right)}\right\} \\ &=\sum_{w\in\mathcal{C}}\sum_{u\in\{w\}\bigcup NEG\left(w\right)}\left\{L^w\left(u\right)\cdot\log\left[\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]+\left[1-L^w\left(u\right)\right]\cdot\log\left[1-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\right\}\end{align}$$

对数似然函数$\mathcal{L}$关于$\theta^u$的偏导

$$\begin{align}\frac{\partial\mathcal{L}}{\partial\theta^u}&=\frac{\partial}{\partial\theta^u}\left\{\sum_{w\in\mathcal{C}}\sum_{u\in\{w\}\bigcup NEG\left(w\right)}\left\{L^w\left(u\right)\cdot\log\left[\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]+\left[1-L^w\left(u\right)\right]\cdot\log\left[1-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\right\}\right\}\\ &=L^w\left(u\right)\left[1-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\mathbf{x}_w-\left[1-L^w\left(u\right)\right]\sigma\left(\mathbf{x}_w^\top\theta^u\right)\mathbf{x}_w \\ &=\left[L^w\left(u\right)-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\mathbf{x}_w\end{align}$$

$\theta^u$的更新

$$\theta^u=\theta^u+\eta\left[L^w\left(u\right)-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\mathbf{x}_w$$

对数似然函数$\mathcal{L}$关于$\mathbf{x}_w$的偏导

$$\frac{\partial\mathcal{L}}{\partial\mathbf{x}_w}=\sum_{u\in\left(w\right)\bigcup NEG\left(w\right)}\left[L^w\left(u\right)-\sigma\left(\mathbf{x}_w^\top\theta^u\right)\right]\theta^u$$

$\mathbf{v}\left(\tilde{w}\right)$的更新

$$\mathbf{v}\left(\tilde{w}\right)=\mathbf{v}\left(\tilde{w}\right)+\eta\frac{\partial\mathcal{L}}{\partial\mathbf{x}_w}$$

其中，$\tilde{w}\in Context\left(w\right)$。

5 基于负采样（Negative Sampling）方法的跳字模型训练

关于字典$\mathcal{D}$的子集$\{w\}\bigcup NEG^{\tilde{w}}\left(w\right)$的似然函数

$$g\left(w\right)=\prod_{\tilde{w}\in Context\left(w\right)}\prod_{u\in\{w\}\bigcup NEG^{\tilde{w}}\left(w\right)} p\left(u|\tilde{w}\right)$$

其中

$$\begin{equation} p\left(u|\tilde{w}\right)=\left\{ \begin{array}{lr} \sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right),L^w\left(u\right)=1 & \\ 1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right),L^w\left(u\right)=0 \end{array} \right. \end{equation}$$

或者

$$p\left(u|\tilde{w}\right)=\left[\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]^{L^w\left(u\right)}\cdot\left[1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]^{1-L^w\left(u\right)}$$

$NEG^{\tilde{w}}\left(w\right)$为处理词$\tilde{w}$时生成的负样本子集。

关于语料库$\mathcal{C}$的对数似然函数

$$\begin{align}\mathcal{L}& =\log\prod_{w\in\mathcal{C}}g\left(w\right)=\sum_{w\in\mathcal{C}}\log g\left(w\right) \\ &=\sum_{w\in\mathcal{C}}\log\prod_{\tilde{w}\in Context\left(w\right)}\prod_{u\in\{w\}\bigcup NEG^{\tilde{w}}\left(w\right)}\left\{\left[\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]^{L^w\left(u\right)}\cdot\left[1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]^{1-L^w\left(u\right)}\right\} \\ &=\sum_{w\in\mathcal{C}}\sum_{\tilde{w}\in Context\left(w\right)}\sum_{u\in\{w\}\bigcup NEG^{\tilde{w}}\left(w\right)}\left\{L^w\left(u\right)\cdot\log\left[\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]+\left[1-L^w\left(u\right)\right]\cdot\log\left[1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)\top\theta^u\right)\right]\right\}\end{align}$$

对数似然函数$\mathcal{L}$关于$\theta^u$的偏导

$$\begin{align}\frac{\partial\mathcal{L}}{\partial\theta^u}&=\frac{\partial}{\partial\theta^u}\left\{\sum_{w\in\mathcal{C}}\sum_{\tilde{w}\in Context\left(w\right)}\sum_{u\in\{w\}\bigcup NEG\left(w\right)}\left\{L^w\left(u\right)\cdot\log\left[\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]+\left[1-L^w\left(u\right)\right]\cdot\log\left[1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]\right\}\right\}\\ &=L^w\left(u\right)\left[1-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]\mathbf{v}\left(\tilde{w}\right)-\left[1-L^w\left(u\right)\right]\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\mathbf{v}\left(\tilde{w}\right) \\ &=\left[L^w\left(u\right)-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]\mathbf{v}\left(\tilde{w}\right)\end{align}$$

$\theta^u$的更新

$$\theta^u=\theta^u+\eta\left[L^w\left(u\right)-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]\mathbf{v}\left(\tilde{w}\right)$$

对数似然函数$\mathcal{L}$关于$\mathbf{v}\left(\tilde{w}\right)$的偏导

$$\frac{\partial\mathcal{L}}{\partial\mathbf{v}\left(\tilde{w}\right)}=\sum_{u\in\left(w\right)\bigcup NEG^{\tilde{w}}\left(w\right)}\left[L^w\left(u\right)-\sigma\left(\mathbf{v}\left(\tilde{w}\right)^\top\theta^u\right)\right]\theta^u$$

$\mathbf{v}\left(\tilde{w}\right)$的更新

$$\mathbf{v}\left(\tilde{w}\right)=\mathbf{v}\left(\tilde{w}\right)+\eta\frac{\partial\mathcal{L}}{\partial\mathbf{v}\left(\tilde{w}\right)}$$

负采样算法

设词典$\mathcal{D}$中词$w_i$对应线段$l\left(w_i\right)$，长度为

$$len\left(w_i\right)=\frac{counter\left(w_i\right)}{\sum_{u\in\mathcal{D}}counter\left(u\right)}$$

其中，$counter\left(\cdot\right)$为词在语料$\mathcal{C}$中的出现次数。可将线段$l\left(w_1\right)\cdots l\left(w_N\right)$拼接为长度为$1$的单位线段。

记

$$\begin{align}l_0&=0 \\ l_k&=\sum_{j=1}^k len\left(w_j\right),k=1,2,\cdots,N \end{align}$$

则以$\{l_j\}_{j=0}^N$为剖分点可得到区间$\left[0,1\right]$上的一个非等距剖分

$$I_i=(l_{i-1},l_i],i=1,2,\cdots,N$$

在区间$\left[0,1\right]$上以剖分点$\left\{m_j\right\}_{j=0}^M$做等距剖分，其中$M\gg N$。

将等距剖分的内部点$\left\{m_j\right\}_{j=1}^{M-1}$投影到非等距剖分。则可建立$\left\{m_j\right\}_{j=1}^{M-1}$与区间$\left\{I_j\right\}_{j=1}^N$的映射，进一步建立与词$\left\{w_j\right\}_{j=1}^M$之间的映射

$$w_k=Table\left(i\right),m_i\in I_k,i=1,2,\cdots,M-1$$