Word2Vec
自然语言处理问题中，一般以词作为基本单元，例如我们想要分析"我去过华盛顿州"这句话的情感，一般的做法是先将这句话进行分词，变成我，去过，华盛顿州，由于神经网络无法处理词，所以我们需要将这些词通过某些办法映射成词向量。词向量是用来表示词的向量，也可被认为是词的特征向量。把词映射为实数域向量的技术也叫词嵌入（word embedding）
为何不采用one-hot向量
假设词典中不同词的数量为$N$，每个词可以和从0到$N-1$的连续整数一一对应。假设一个词的相应整数表示为$i$，为了得到该词的one-hot向量表示，我们创建一个全0的长为$N$的向量，并将其第$i$为设为1
然而，使用one-hot词向量并不是一个好选择。一个主要的原因是，one-hot词向量无法表达不同词之间的相似度，例如，任何一对词的one-hot向量的余弦相似度都为0
word2vec
2013年，Google团队发表了word2vec工具。word2vec工具主要包含两个模型：跳字模型（skip-gram）和连续词模型（continuous bag of words，简称CBOW），以及两种高效训练的方法：负采样（negative sampling）和层序softmax（hierarchical softmax）。值得一提的是，word2vec词向量可以较好地表达不同词之间的相似度和类比关系
跳字模型
在跳字模型中，我们用一个词来预测它在文本序列周围的词。例如，给定文本序列"the","man","hit","his","son"。设背景窗口大小为2， 跳字模型所关心的是，给定"hit"，生成它邻近词"the","man"."his","son"的概率（在这个例子中，"hit"叫中心词，"the","man","his","son"叫背景词），即
$$ P(“the”,“man”,“his”,“son”\mid “hit”) $$
假设在给定中心词的情况下，背景词的生成是相互独立的，那么上式可以改写成
$$ P(“the”\mid “hit”)·P(“man”\mid “hit”)·P(“his”\mid “hit”)·P(“son”\mid “hit”) $$
我们来描述一下跳字模型。假设词典大小为$|V|$，我们将词典中的每个词与0到$|V|-1$的整数一一对应：词典索引集$V=\{0,1,...,|V|-1\}$。一个词在该词典中所对应的整数称为词的索引，给定一个长度为$T$的文本序列，$t$时刻的词为$w^{(t)}$。当时间窗口大小为$m$时，跳字模型需要最大化给定任一中心词生成背景词的概率：
$$ \prod_{t=1}^T {\prod_{-m≤j≤m,\ j\neq 0}{P(w^{(t+j)}\mid w^{(t)})}} $$
上式得最大似然估计与最小化以下损失函数等价
$$ -\frac{1}{T}\sum_{t=1}^{T}\sum_{-m≤j≤m,\ j\neq 0}logP(w^{(t+j)}\mid w^{(t)}) $$
我们可以用$\boldsymbol v$代表中心词的词向量，$\boldsymbol u$代表背景词的词向量。换言之，对于词典中一个索引为$i$的词，它本身有两个向量$\boldsymbol {v}_i$和$\boldsymbol{u}_i$进行表示，在计算的过程中，根据其所处的角色不同，选择不同的词向量。词典中所有词的这两种向量正是跳字模型所需要学习的参数。为了将模型参数植入损失函数，我们需要使用模型参数表达损失函数中的中心词生成背景词的概率。假设中心词的概率是相互独立的。给定中心词$w_c$在词典中的索引为$c$，背景词$w_o$在词典中的索引为$o$，损失函数中中心词生成背景词的概率可以使用softmax函数进行定义：
$$ P(w_o|w_c)=\frac{exp(\boldsymbol{u}_o^T\boldsymbol {v}_c)}{\sum_{i\in V}exp(\boldsymbol{u}_i^T\boldsymbol{v}_c)} $$
当序列长度$T$较大时，我们通常随机采样一个较小的子序列来计算损失函数并使用SGD优化该损失函数。通过求导，我们可以计算出上式生成概率的对数关于中心词向量$\boldsymbol {v}_c$的梯度为：
$$ \frac{\nabla logP(w_o\mid w_c)}{\nabla \boldsymbol{v}_c}=\boldsymbol{u}_o-\sum_{j\in V}\frac{exp(\boldsymbol{u}_j^T\boldsymbol{v}_c)}{\sum_{j\in v}exp(\boldsymbol{u}_i^T\boldsymbol{v}_c)}\boldsymbol{u}_j $$
而上式与下式等价：
$$ \frac{\nabla logP(w_o\mid w_c)}{\nabla \boldsymbol{v}_c}=\boldsymbol{u}_o-\sum_{j\in V}P(w_j|w_c)\boldsymbol {u}_j $$
通过上面计算得到梯度后，我们可以使用随机梯度下降来不断迭代模型参数$\boldsymbol {v}_c$。其它模型参数$\boldsymbol {u}_o$的迭代方式同理可得。最终，对于词典中任一索引为$i$的词，我们均得到该词作为中心词和背景词的两组词向量$\boldsymbol {v}_i$和$\boldsymbol {u}_i$
连续词袋模型
连续词袋模型与跳字模型类似。与跳字模型最大的不同是，连续词袋模型是用一个中心词在文本序列周围的词 来预测中心词。简单的说就是，跳字模型用中心词预测周围的词；连续词袋模型用周围的词预测中心词。例如，给定文本"the","man","hit","his","son"，连续词袋模型所关心的是，邻近词"the","man","his","son"一起生成中心词"hit"的概率
连续词袋模型需要最大化由背景词生成任一中心词的概率：
$$ \prod_{t=1}^TP(w^{(t)}\mid w^{(t-m)},...,w^{(t-1)},w^{(t+1)},...,w^{(t+m)}) $$
上式得最大似然估计与最小化以下损失函数等价
$$ -\sum_{t=1}^TlogP(w^{(t)}\mid w^{(t-m)},...,w^{(t-1)},w^{(t+1)},...,w^{(t+m)}) $$
我们可以用$\boldsymbol{v}$和$\boldsymbol{u}$分别代表背景词和中心词的向量（注意符号和跳字模型不同）。给定中心词$w_c$在词典中的索引为$c$，背景词$w_{o_1},...,w_{o_{2m}}$在词典中的索引为$o_1,...,o_{2m}$，损失函数中的背景词生成中心词的概率可以使用softmax函数定义为
$$ P(w_c\mid w_{o_1},...,w_{o_{2m}})=\frac{exp[\boldsymbol{u}_c^T(\boldsymbol{v}_{o_1}+...+\boldsymbol{v}_{o_{2m}})/(2m)]}{\sum_{j\in V}exp[\boldsymbol{u}_j^T(\boldsymbol{v}_{o_1}+...+\boldsymbol{v}_{o_{2m}})/(2m)]} $$
同样，当序列长度$T$较大时，我们通常随机采样一个较小的子序列来计算损失函数，并使用随机梯度下降优化该损失函数，通过微分，我们可以计算出上式生成概率的对数关于任一背景词向量$\boldsymbol{v}_{o_i}(i=1,...,2m)$的梯度为：
$$ \frac{\nabla logP(w_c\mid w_{o_1},...,w_{o_{2m}})}{\nabla \boldsymbol{v}_{o_i}}=\frac{1}{2m}(\boldsymbol {u}_c-\sum_{j\in V}\frac{exp(\boldsymbol u_j^T\boldsymbol v_c)}{\sum_{i\in V}exp(\boldsymbol u_i^T\boldsymbol v_c)}\boldsymbol u_j) $$
而上式与下式等价：
$$ \frac{\nabla logP(w_c\mid w_{o_1},...,w_{o_{2m}})}{\nabla \boldsymbol{v}_{o_i}}=\frac{1}{2m}(\boldsymbol {u}_c-\sum_{j\in V}P(w_j\mid w_c)\boldsymbol u_j) $$
近似训练法
可以看到，无论是跳字模型还是连续词袋模型，每一步梯度计算的开销与词典$V$的大小呈正相关。显然，当词典较大时，这种训练方法的计算开销会很大。所以使用上述训练方法在实际中是由难度的。我们可以使用近似的方法来计算这些梯度，从而减小计算开销。常用的近似训练法包括负采样和层序softmax
负采样
以跳字模型为例讨论负采样。词典$V$的大小之所以会在目标函数中出现，是因为中心词$w_c$生成背景词$w_o$的概率$P(w_o|w_c)$使用了softmax，而softmax考虑到了背景词可能是词典中任一词，并体现在了softmax的分母上
我们不妨换个角度，假设中心词$w_c$生成背景词$w_o$由以下两个互相独立的联合事件组成来近似
- 中心词$w_c$和背景词$w_o$同时出现在该训练数据窗口
- 中心词$w_c$和噪声词不同时出现在该训练数据窗口
- 中心词$w_c$和第1个噪声词$w_1$不同时出现在训练数据窗口（噪声词$w_1$按噪声词分布$P(w)$随机生成）
- ...
- 中心词$w_c$和第$K$个噪声词$w_k$不同时出现在训练数据窗口（噪声词$w_K$按噪声词分布$P(w)$随机生成）
我们可以使用$\sigma(x)=\frac{1}{1+exp(-x)}$函数来表达中心词$w_c$和背景词$w_o$同时出现在训练数据窗口的概率：
$$ P(D=1\mid w_o,w_c)=\sigma(\boldsymbol{u}_o^T,\boldsymbol{v}_c) $$
那么，中心词$w_c$生成背景词$w_o$的对数概率可以近似为
$$ logP(w_o\mid w_c)=log[P(D=1\mid w_o,w_c)\prod_{k=1,w_k\sim P(w)}^KP(D=0\mid w_k,w_c)] $$
假设噪声词$w_k$在词典中的索引为$i_k$，上式可改写为
$$ logP(w_o\mid w_c)=log\frac{1}{1+exp(-\boldsymbol u_o^T\boldsymbol{v}_c)}+\sum_{k=1,w_k\sim P(w)}^Klog[1-\frac{1}{1+exp(-\boldsymbol u_{i_k}^T\boldsymbol{v}_c)}] $$
因此，有关中心词$w_c$生成背景词$w_o$的损失函数是
$$ -logP(w_o\mid w_c)=-log\frac{1}{1+exp(-\boldsymbol u_o^T\boldsymbol{v}_c)}-\sum_{k=1,w_k\sim P(w)}^Klog\frac{1}{1+exp(\boldsymbol u_{i_k}^T\boldsymbol{v}_c)} $$
现在，训练中每一步的梯度计算开销不再与词典大小相关，而与$K$线性相关。当$K$取较小的常数时，负采样的每一步梯度计算开销也较小
同理，也可以对连续词袋模型进行负采样。有关背景词$w^{(t-m)},...,w^{(t-1)},w^{(t+1)},...,w^{(t+m)}$
生成中心词$w_c$的损失函数
$$ -logP(w^{(t)}\mid w^{(t-m)},...,w^{(t-1)},w^{(t+1)},...,w^{(t+m)}) $$
在负采样中可以近似为
$$ -log\frac{1}{1+exp[-\boldsymbol{u}_c^T(\boldsymbol{v}_{o_1}+...+\boldsymbol{v}_{o_{2m}})/(2m)]}-\sum_{k=1,w_k\sim P(w)}^Klog\frac{1}{1+exp[\boldsymbol{u}_{i_k}^T(\boldsymbol{v}_{o_1}+...+\boldsymbol{v}_{o_{2m}})/(2m)]} $$
层序softmax
层序softmax利用了二叉树。树的每个叶子节点代表着词典$V$中的每个词。每个词$w_i$对应的词向量为$\boldsymbol{v}_i$。我们以下图为例，来描述层序softmax的工作机制
设$L(w)$为从二叉树根节点到代表词$w$的叶子节点的路径上的节点数，并设$n(w,i)$为该路径上第$i$个节点，该节点的向量为$\boldsymbol{u}_{n(w,j)}$。以上图为例，$L(w_3)=4$。那么，跳字模型和连续词袋模型所需要计算的任意词$w_i$生成词$w$的概率为：
$$ P(w\mid w_i)=\prod_{j=1}^{L(w)-1}\sigma([n(w,j+1)=left\_child(n(w,j))]·\boldsymbol{u}_{n(w,j)}^T\boldsymbol{v}_i) $$
其中，如果$x$为真，$[x]=1$；反之$[x]=-1$
由于$\sigma(x)+\sigma(-x)=1$，$w_i$生成词典中任何词的概率之和为1：
$$ \sum_{w=1}^VP(w\mid w_i)=1 $$
上面公式可能比较抽象，下面举个具体的例子，计算$w_i$生成$w_3$的概率，由于在二叉树中由根到$w_3$的路径需要向左、向右、再向左地遍历，所以得到
$$ P(w_3\mid w_i)=\sigma(\boldsymbol{u}_{n(w_3,1)}^T\boldsymbol{v}_i)·\sigma(-\boldsymbol{u}_{n(w_3,2)}^T\boldsymbol{v}_i)·\sigma(\boldsymbol{u}_{n(w_3,3)}^T\boldsymbol{v}_i) $$
由此，我们就可以使用随机梯度下降在跳字模型和连续词袋模型中不断迭代计算词典中所有词向量$\boldsymbol{v}$和非叶子节点的向量$\boldsymbol{u}$。每次迭代的计算开销由$O(|V|)$降为二叉树的高度$O(log|V|)$
最后一个问题，层序softmax的二叉树是如何建立的？
这里的二叉树Huffman树，权重是语料库中word出现的频率