续上，这篇博客我们来讨论一下基于迭代策略的词向量的学习。主要想介绍一下四个相关的神经网络来学词向量。
1. 语言模型（Language Modeling）
所有用在NLP中的神经网络模型都是基于语言模型来构建的。我们知道，一篇文章是由一系列的句子组成，每个句子都是由一系列的词组成。我们现在有单独的词（Atom），我们希望构建一系列的句子，从而构建整篇文章。在自然语言处理中有一个很出名的模型叫做N-gram 模型，它是将马尔科夫假设（Makov Assumptions）用在句子的生成过程中。例如这么一个句子：
I am a graduate student in ShanghaiTech University.
1.1.单纯的词袋模型（Bag of Words）
有图有真相！前一阵在微博上面看到下面的这个图很有意思。
BoW是指，所有的词之间相互没有关系，即在构建整个句子中不考虑词与词的顺序。因此，上面的句子跟下面的句子本质上表达的意义相同：
University student am graduate I ShanghaiTech a in.
这看起来很荒唐，但实际上像上一篇博客所说的LDA模型就是这么做的，在做主题建模时work的非常好。当然，这是看应用的。在复杂的问题下如何做出正确的Assumption正是Machine Learning想要研究的问题。对于上面这个句子，我们计算产生它的概率，可以通过这些词的联合概率来计算：
$$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=1}^{n}P\left(w^{(i)}\right)$$
但是，在产生句子这个问题时，Bags of Words模型肯定不够好，因为人在理解一句话中的某个词都会依靠其上下文的关系。因此我们可以把词与其前面n-1个词的关系加进来，这就是n-gram模型。
1.2.Binary Gram & Triple Gram
很简单，在计算一个句子产生的概率时把每个词与其前面n-1个词的关系考虑进来，可以得到：
Binary Gram:$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=2}^{n}P\left(w^{(i)}|w^{(i-1)}\right)P\left(w^{(1)}\right)$
Triple Gram:$P\left(w^{(1)},w^{(2)},…,w^{(n)}\right)=\prod_{i=3}^{n}P\left(w^{(i)}|w^{(i-1)},w^{(i-2)}\right)P\left(w^{(2)}|w^{(1)}\right)P\left(w^{(1)}\right)$
同样可以考虑前n-1个词的关系，但是，随着n的增大，模型复杂度也会随之增大。因为，实际应用中如何选择一个好的n也很有讲究，这在Machine Learning中被称为Bias-Variance Trade-off。实际应用中，我们组的师兄一般用Binary Gram或者Triple Gram就可以表达足够的信息了。
2.A Simple Neural Network Model for Word Embedding
我们在既然讨论了语言模型，就想把语言模型的idea用来构建神经网络，以此对词进行表示。在n-gram模型中，我们用前n-1个词来对第n个词进行表示。那么在神经网络中我们也可以这么做，我们的输入是n-1个词的One-hot Vectors，预测输出是第n个词。如何在一个句子中有多少个这样的神经网络呢，我们来举个例子，对于下面这个句子：
Word embedding is the collective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
我们可以构建多个窗口（window），每个窗口的大小是n。因此随着窗口的移动，一个句子可以得到$len \left(sentence\right)-n$个窗口，如下：
Word embedding is thecollective name for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
Wordembedding is the collectivename for a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
Word embeddingis the collective namefor a set of language modeling and feature learning techniques in natural language processing where words from the vocabulary…
…
对于每一个这样的窗口，我们可以构建一个神经网络来对其中的语言模型进行建模。这就是Bengio等人2003年的工作：
输入层有n-1个词，输出层包括dictionary中所有词的概率。输入层到隐藏层是通过一个Tanh函数来映射。算出Tanh后的假设我们希望在对每个词用一个$d$维度的向量来表示。因此输入的One-hot vector 通过一个look up table转换成d维的词向量表示（神经网络中的第一层到第二层）。从第二层到第三层是指将前n-1个词向量左乘一个H矩阵，映射到隐藏层。隐藏层到输出层是一个线性映射。因此我们可以得到每一个小窗口的目标函数：
$$f\left(w_c,w_{c-1},…,w_{c-n+1}\right)=P\left(w_c|w_{c-1},…,w_{c-n+1}\right)=\frac{e^{y_{w_c}}}{\sum_i e^{y_i}}$$
对于每个句子，我们有$len \left(sentence\right)-n$个窗口，那对于所有的句子来说，假设一共有$C$个窗口，则我们可以得到目标函数：
$$J(\theta)=\frac{1}{C}\sum_{c=n}^{C}\log f(w_c,w_{c-1},…,w_{c-n+1};\theta)+R(\theta)$$
每一个$f$都可以用上面的式子来算，$R(\theta)$是正则项，在神经网络，尤其是深度学习中很常见，一般是参数的$l_2$范数，其目的为了防止overfitting。对于每一个$y_{w_c}$我们应该如何求呢? 就像刚才所说，求这个output的过程就是一个forward process，我们想求所有的$y_{w_c}$，即该神经网络的最后一层：
$$y=b+Wx+Utanh(d+Hx)$$
令隐藏层的数目为$h$，$m$是每个词的词向量表示。解释一下上个式子中符号的意思，$b\in R^{|V|}$是词向量到output的偏置项（Bias term）。$d\in R^{h}$
是词向量这一层到output层的偏置项。$U\in R^{|V|\times h}$是隐藏层到output的weight matrix。词向量层到output层的weight是矩阵$W\in R^{|V|\times \left(n-1\right)m}$。隐藏层算出来的权重$H\in R^{h \times \left(n-1\right)m}$。词向量层的矩阵值是$C\in R^{|V|\times m}$，这个矩阵其实就是词向量的表示。
这里的式子比我们刚才所说的forward process多了一项，即$Wx$。在Bengio的paper中他解释到添加这一层可以使得训练速度更快，但是使得神经网络学习到更好的参数，因此$W$可以设置为0。
得到整个的目标函数，我们希望求解所有的参数:$W,U,x,d,b$。用老方法：Stochastic Gradient Desent。我们在接下来的博客里会举个例子来看一下一般神经网络模型该如何学习参数。
3.Continuous Bag of Words Model
Mikolov等人在谷歌提出了两个计算词向量的模型，分别是CBOW和skip-gram模型，我们在这一部分来介绍一下CBOW模型。继续借用上一部分说到的句子中的窗口的概念，在CBOW模型中我们假设窗口的大小$n$为奇数（3,5,7,9等）。在Bengio的工作中他希望利用前$n-1$个词来建模第n个词。而在CBOW模型中我们希望利用周围的词（称为上下文（Context））来对中间词进行建模。例如I love you在这个窗口中可以通过I和you来对中间词love来建模，我们希望$P\left(love|I,you\right)$这个概率比其他词的概率如$P\left(school|I,you\right)$要大。
$$P\left(love|I,you\right) > P\left(school|I,you\right)$$
这样我们的模型即为：
回到之前Bengio的那个神经网络，虽然模型很简单，实际上在计算的时候复杂度很高，一方面在对每一个窗口，最后一层都有$|V|$个节点，如果在一个非常大的corpus中计算复杂度非常高。另一方面在模型中存在tanh这样的函数，指数函数在计算机中求解是通过Taylor公式展开的。这样的话在做back-propagation迭代求参数的花费就非常高。Mikolov很好地解决了第二个问题，在构建神经网络模型中，我们对隐藏层不再采用非线性映射，而是普通的线性映射。在输出层我们仍然需要通过softmax函数将score转换成概率。
定义一下这个网络的一些符号：
- $w^{\left(i\right)}$：词典中第i个词
- $x_i$：第i个词的One-hot vector表示
- $W\in R^{n\times |V|}$：输入层到隐藏层的参数矩阵
- $u^{\left(i\right)}$：$W$矩阵中的第$i$列，也就是第$i$个词的enbedding后的表示。
- $W^{‘}\in R{n\times |V|}$：隐藏层到输出层的权重参数矩阵。
- $v^{\left(i\right)}$：$W^{‘}$矩阵中的第$i$列。也就是第$i$个词的输出表示。
这样整个的学习过程就是： - 1.通过词典生成一系列的one-hot vector：$(x^{\left(i-c\right)},…,x^{\left(i-1\right)},x^{\left(i+1\right)},…,x^{\left(i+c\right)})$
- 2.通过$W$得到词向量的表示：$u^{\left(j\right)}=W\cdot x^{\left(j\right)}$，j是在一个集合中：$j\in {i-c,…,i-1,i+1,…,i+c}$
- 3.取所有算出来的词向量的平均数，即隐藏层的值：$h=\frac{u^{\left(i-c\right)}+…+u^{\left(i-1\right)}+u^{\left(i+1\right)}+…+u^{\left(i+c\right)}}{2c}$
- 4.计算output层的score vector：$z=W^{‘}h$
- 5.通过softmax函数将所得到的score转换成概率：$\hat{y}=softmax\left(z\right)$
这样我们对单个窗口的目标函数即为：
\begin{align}
argmax_{\theta}~~J=\log~P(w^{\left(i\right)}|w^{\left(i-c\right)},…w^{\left(i-1\right)},w^{\left(i+1\right)},…,w^{\left(i+c\right)})
=\log \frac{exp\left(v\left(i\right)^{T}h\right)}{\sum_{j=1}^{|V|}exp \left(v\left(j\right)^{T}h\right)}
\end{align}
那么整个dataset的目标函数就是把所有窗口的目标函数加一起。不再详述~
4.Skip-Gram Model
Mikolov的paper中同时介绍了CBOW和这个模型，它俩的idea正好相反，在CBOW中我们希望通过上下文来对中心词进行建模，而Skip-Gram中我们希望通过中心词来对上下文进行建模。下图就是Skip-Gram模型：
在这个模型中，对于每一个窗口，我们想最大化$P\left(context|center word\right)$，我们知道，上下文是这个center word左右两边$c$个词。
$$argmax_{\theta}~~J=\log~P\left(w^{\left(i-c\right)},…w^{\left(i-1\right)},w^{\left(i+1\right)},…,w^{\left(i+c\right)}|w^{\left(i\right)}\right)$$
因此，直接求这个联合概率很难，我们需要做一些假设（Assumption）。在这个模型中我们做了一个非常强的假设：朴素贝叶斯假设，关于什么是Naive Bayes，可以看一下之前的博文。通过Naive Bayes Assumption，我们可以将这个目标函数写成：
$$argmax_{\theta}~J=\log~\prod_{j=0,j\neq c}^{2c} P\left(w^{\left(i-c+j\right)}|w^{\left(i\right)}\right)$$
然后呢，就是用随机梯度下降来求解啦。。。
终于把Part 2给OVER了。。下一篇博客会讲一下SENNA模型，这个模型出自一篇很牛的文章（Natural Language Processing (almost) from Scratch）。它利用一个很聪明的idea，避免了在输出层要计算$|V|$大小的score。。下次再见！
参考文献
[1] Collobert, Ronan, et al. “Natural language processing (almost) from scratch.” The Journal of Machine Learning Research 12 (2011): 2493-2537.
[2] Bengio, Yoshua, et al. “A neural probabilistic language model.” The Journal of Machine Learning Research 3 (2003): 1137-1155.
[3] Mikolov, Tomas, et al. “Efficient estimation of word representations in vector space.” arXiv preprint arXiv:1301.3781 (2013).