Word2Vec学习笔记
Word2Vec是Google开源的一款用于计算词向量的工具，它可以对海量的词典和数据集上进行高效的训练，并得到稠密连续的词向量作为其他自然语言处理任务的基础。Word2Vec并不是一种算法，而是基于NLPM的高效实现，包含了CBoW和Skip-gram两个模型。本文将介绍统计语言模型中词向量的Discrete和Distributed Representation之间的区别，Word2Vec的模型一些细节。欢迎补充、指正并参与讨论。
统计语言模型（Statistical Language Model）
在自然语言处理中的一个基本的问题就是：如何计算一段文本序列$S$，在文本中出现的概率。这样，我们可以根据概率来选择更靠谱的翻译结果和AI回答。
首先要将句子$S$表示一连串特定顺序排列的文本原子单位，在一些场景中，可能按字符(character)或者短语(phrase)为单位进行处理。但最常见的还是以词为单位，将句子$S$用$w_1,w_2,…,w_T$词序列表示，即分词任务。假设，当前词的概率可以表示为基于它前面出现的词的条件概率，那么文本序列$S=w_1,w_2,…,w_T$的概率$P(S)$可以表示为：
$$P(S)=P(w_1,w_2,…,w_T)=\prod_{t=1}^T{p(w_t|w_1,w_2,…,w_{t-1})}$$
可以预见，这样没办法去估计一个词出现的概率，因为参数空间太大。在实际中，一般采用N-gram模型去近似地表示，即当前词只与前面$N-1$个词有关。
$$p(w_t|w_1,w_2,…,w_{t-1}) \approx p(w_t|w_{t-n+1},…,w_{t-1})$$
通常使用bi-gram ($N=2$)和tri-gram ($N=3$)。但是模型的预测精度有限，且存在零概率问题，即一段从未在训练集中出现过的Ngram片段会使得整个序列的概率为0。有一些N-gram模型的变体（例如，back-off trigram和interpolated trigram模型）针对性地解决这些问题，但有一个前序问题是：如何来表示这些词呢？对，是向量。
Discrete Representation
在传统的模型中，每个词都被表示为离散的向量，常见的编码方式就是One-hot encoding。即以0-1向量来表示一个词，维度就是整个词典的数量，词向量在其对应的维度为1，其他均为零。如：
- I: [ 1 0 0 0 0 ]
- love: [ 0 1 0 0 0 ]
- mom: [ 0 0 1 0 0 ]
- and: [ 0 0 0 1 0 ]
- dad: [ 0 0 0 0 1 ]
这种表示方法的缺陷显而易见：
- 割裂了词与词之间的相似度的关系，如上文中mom和dad都是我的双亲，却无法在词向量上体现。
- 造成了维度灾难问题（the curse of dimensionality），通常词典中的词都是百万数量级的，采用One-hot编码会造成超高维超稀疏的矩阵，给计算带来了很多麻烦的问题。
Distributed Representation
为了避免上述问题，我们倾向用低维稠密的向量来表示一个词，这样的表示方法被称为Distributed Representation。在信息检索（Information Retrieval）领域，这个概念又被称为向量空间模型（Vector Space Model）[1]。
为了获取这样的连续稠密的向量，可以分为distributed和distributional两类方法，但都是基于statistical semantics distributional hypothesis，核心思想就是词义隐含在上下文统计特征中。
Distributional包括BoW、LSI、LDA等模型，统计单词共现的频率和次数，往往限定于只存在于相同的上下文环境中。通过构造PMI/PPMI矩阵，再通过SVD进行降维等操作。
Distributed包括NPLM、LBL、Glove等模型。不仅仅是统计了单词出现的频率，而是通过学习使得单词具有一定出现的概率，不一定同时出现在相同的上下文环境中。有文章证明Distributed的方法通常表现更好。[2]
Neural Probabilistic Language Model
接下来，让我们回到对统计语言模型的讨论。鉴于Ngram等模型的不足，2003年，Bengio等人发表了一篇开创性的文章：A Neural Probabilistic Language Model[3]。在这篇文章里，他们总结出了一套用神经网络建立统计语言模型的框架，想利用深度学习的方法来解决自然语言处理问题。并首次提出了连续空间的word representation，也就是后来被称为word embedding的概念，从而奠定了包括word2vec在内后续研究word representation learning的基础。
NPLM模型的基本思想可以概括如下：
- 假定词表中的每一个word都对应着一个连续的特征向量；
- 假定一个连续平滑的概率模型，输入一段词向量的序列，可以输出这段序列的联合概率；
- 同时学习词向量的权重和概率模型里的参数。
我们可以将整个模型拆分成两部分加以理解：
- 首先是一个线性的embedding层。它将输入的$N−1$个one-hot词向量，通过一个共享的$D×V$的矩阵$C$，映射为$N−1$个分布式的词向量（distributed vector）。其中，$V$是词典的大小，$D$是embedding向量的维度（一个先验参数）。$C$矩阵里存储了要学习的word vector。
- 其次是一个简单的前向反馈神经网络$g$。它由一个tanh隐层和一个softmax输出层组成。通过将embedding层输出的$N−1$个词向量映射为一个长度为$V$的概率分布向量，从而对词典中的word在输入context下的条件概率做出预估：
$$p(w_i|w_1,w_2,…,w_{t−1}) \approx f(w_i,w_{t−1},…,w_{t−n+1})=g(w_i,C(w_{t−n+1}),…,C(w_{t−1}))$$
我们可以通过最小化一个cross-entropy的正则化损失函数来调整模型的参数$\theta$：
$$L(\theta)=\frac{1}{T}\sum_t\log{f(w_t,w_{t−1},…,w_{t−n+1})}+R(\theta)$$
其中，模型的参数$\theta$包括了embedding层矩阵$C$的元素，和前向反馈神经网络模型$g$里的权重。这是一个巨大的参数空间。不过，在用SGD学习更新模型的参数时，并不是所有的参数都需要调整（例如未在输入的context中出现的词对应的词向量）。
不过NPLM只能处理定长的序列，Mikolov等人在这篇文章基础之上，提出Recurrent Neural Net Language Model[4]，即用循环神经网络代替原始模型中的前向反馈神经网络，并将embedding层和RNN中的隐藏层合并，从而解决了变长序列的问题。
Word2Vec
NPLM比较严重的问题是训练太慢了。在百万量级的数据集(AP News Corpus)上，使用了40个CPU进行训练，NPLM耗时三周只运行了5个epoch，得到了一个比较靠谱的解。显然，对于现在动辄上千万甚至上亿的真实语料库，训练一个NPLM模型几乎是一个不可能完成的任务。因此，为了简化NPLM模型，Mikolov提出了CBoW和Skip-gram两个模型，CBoW全称是Continuious Bag of Words目的是用Context预测当前词，Skip-gram则是用当前词预测周围的Context。[5,6]
Continuious Bag of Words
CBoW移除了前向反馈神经网络中非线性的hidden layer，直接将中间层的embedding layer与输出层的softmax layer连接。忽略上下文环境的序列信息：输入的所有词向量均汇总到同一个embedding layer，同时将future words纳入上下文环境。
从数学上看，CBoW模型等价于一个词袋模型的向量乘以一个embedding矩阵，从而得到一个连续的embedding向量。这也是CBoW模型名称的由来。
但由于在模型中有一个对context words向量SUM的操作，所以会损失一部分信息，往往效果不如skip-gram模型。但对于一些小量级对精度要求不高的问题情景下，可以使用CBoW快速得到词向量。
Skip-gram Models
Skip-gram模型的名称源于该模型在训练时会对上下文环境里的word进行采样，其前向计算过程如下：
$$p(w_O|w_I)=\frac{\exp u_{w_O}^T v_{w_I}}{\sum_{w \in W}\exp u_w^T v_{w_I}}$$
其中$v_I$是也被称为$w_I$的input vector。$u_I$是softmax层矩阵里的行向量，也被称为wj的output vector。
因此，Skip-gram模型的本质是计算输入word的input vector与目标word的output vector之间的余弦相似度，并进行softmax归一化。我们要学习的模型参数正是这两类词向量。
然而，直接对词典里的$W$个词计算相似度并归一化，显然是一件极其耗时的impossible mission。为此，Mikolov引入了两种优化算法：层次Softmax（Hierarchical Softmax）和负采样（Negative Sampling）。
Hierarchical Softmax
层次Softmax是对完全Softmax分类的计算效率上的优化，最主要的优势就是不用再去计算每个输出结点上面的值（假设总共有$W$个输出结点），而只需要计算$log_2(W)$个输出结点上的值就可以估计整个神经网络的概率分布。这个想法最早是Bengio等人提出的。[7]
将原有的$W$个输出结点作为一个二叉树的叶子结点，每个结点都是显示地表示其子结点的相对概率，通过随机游走得到这些word概率。在二叉树中每个word都对应着唯一一条从根结点到叶子结点的路径，$n(w,1)$到$n(w,l)$表示这条路径上的每个结点，共$L$层，所以$n(w,L)=w$。则：
$$p(w|w_I) = \prod_{l=1}^{L-1} \frac{1}{1+\exp (x)}$$
其中，$x = $[if n(w, l+1) = n(w, l).child then 1 else -1]$u_n^Tv_w$，就变为求这条唯一路径的概率问题，可以通过最大化这个似然函数来求解，降低了复杂度的量级。
与使用标准Softmax层的Skip-gram模型不同的是，标准版中得到了是关于一个词$w$的输出向量$u_w$和输入向量$v_w$，而在层次Softmax版本中，得到的是每个词的输入向量$v_w$和每个非叶结点的输出向量$u_n$。但是二叉树的构造为增加词与词之间的耦合度，即一个词概率的计算可能会间接影响另一些词的出现的概率。Mikolov等人在文章中构造一棵Huffman树，事实证明Huffman树可以满足大部分实际应用的需求。
Negative Sampling
另外一种加速计算的方法就是负采样（Negative Sampling）[8]，主要目标是对于每一轮的迭代，不必计算每个正样本的值，而是加入一些负样本来近似地估计总体概率分布。思想类源于由Gutmann and Hyvarinen提出的Noise Contrast Estimation (NCE)：一个好的模型能最大化地把正负样本分开。鉴于NCE可以近似估计Softmax的对数概率，在Skip-gram模型中对其进行了简化，只保留了高质量的向量表示，因为那才是本模型关注的重点，负采样（NEG）的目标函数为：
$$\log \sigma(u_{w_O}^T v_{w_I})+\sum_{i=1}^k \mathbb{E}_{w_i \sim P_n(W)}[\log \sigma(-u_{w_O}^T v_{w_I})])$$
其中，公式后半部分表示从人为构造的负样本的正态分布$P_n(W)$中随机选出$k$个词对（words pair）作为负样本估计总体的最大似然概率。
不是结尾的结尾
攒了好久终于把这篇学习笔记写出来了，有很多大神已经把Word2Vec讲的很透彻了，可以参见《Word2Vec的前世今生》和《Deep Learning in NLP （一）词向量和语言模型》。我follow的是集智俱乐部组织的NLP & DL课程，软广一发，写的也基于自己的理解，若有不对之处欢迎讨论和指正。下一篇将介绍word2vec的实践。
参考文献
- Turney, P. D., & Pantel, P. (2010). From frequency to meaning: vector space models of semantics. Journal of Artificial Intelligence Research, 37(1).
- Baroni M, Dinu G, Kruszewski G. Don’t count, predict! A systematic comparison of context-counting vs. context-predicting semantic vectors[C]//ACL (1). 2014: 238-247.
- Bengio, Y., Ducharme, R., Vincent, P., & Janvin, C. (2003). A neural probabilistic language model. The Journal of Machine Learning Research, 3, 1137–1155.
- Mikolov, T., Karafiát, M., Burget, L., & Cernocký, J. (2010). Recurrent neural network based language model. Interspeech.
- Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013, January 17). Efficient Estimation of Word Representations in Vector Space. arXiv.org.
- Mikolov, T., Sutskever, I., Chen, K., Corrado, G., & Dean, J. (2013, October 17). Distributed Representations of Words and Phrases and their Compositionality. arXiv.org.
- Morin, F., & Bengio, Y. (2005). Hierarchical Probabilistic Neural Network Language Model. Aistats.
- Mnih, A., & Kavukcuoglu, K. (2013). Learning word embeddings efficiently with noise-contrastive estimation, 2265–2273.