CS224N_lecture01

最近在学习CS224N，为了加深理解做此笔记，初学所以如有问题欢迎指正！

人类语言可以理解为一个用于传递消息的系统，与计算机网络系统每秒可以上传下载几十或者几百MB而言，人类语言是一个慢的网络，每秒也就只能传输几个单词(几个字节)。但人类的语言系统也十分的有意思，仅仅通过传输几个字节，就可以让对方联想出一个视觉图像(几MB)等.

语言中的单词是一个映射指定事情或者想法的符号.如何以一个很好的方式来表示单词对于NLP任务十分重要。

Word Vector

将单词映射到一个N维向量当中，以词向量的方式进行表示。直观上可以理解为词向量每一维被编码不了同意，例如某一维度代表时态（过去时、现在时、将来时）、某一位代表数量（单数or复数）。

one-hot vector

单词可以被表示为 one-hot vector，例子如下所示:
每个单词由一个具体位置来表示，向量中对应的位置值为1，其它位置全为0.

采用这种方式有以下缺点：

• 向量的维度=单词的个数，导致向量的维度巨大
• 无法表示单词的意义，无法表示单词间的远近关系，单词之间理应存在着相似关系，比如酒店与旅馆间的’距离’应该比酒店与苹果间的’距离’'更近’一些. 显然利用此种方法，任意两个单词词向量为正交的，无关系。

SVD Based Method

其想法是首先遍历巨大的数据集，计算单词一同出现的次数形成矩阵X，对矩阵 X 进行奇异值分解，获得$USV^T$USVT, 使用 U 的行向量作为词典中所有单词的词向量。

矩阵 X 的构造方式有两种一种是 Word-doucument Matrix 一种为 Window based Co-occurrence Matrix

Word-doucument Matrix

相关的单词会经常出现在同一个文档中，比如银行和股票、钱等单词通常出现在一起，而与香蕉、苹果一般不会出现在一起。所以遍历文档，单词 i 出现在文档 j 中那么就对$X_{ij} + 1$Xij​+1,最后生成矩阵 $X^{|V| \times M}$X∣V∣×M 其中 M 为文档数量

Window based Co-occurrence Matrix

基于窗口共同出现矩阵，其计算在指定大小窗口下，文中单词一同出现的次数

例子:

• I enjoy flying.
• I like NLP.
• I like deep learning.

计数矩阵为:

计算完成 X 矩阵后，使用 SVD 得到 $X = USV^T$X=USVT 然后选择U的前K列形成词向量

存在问题:

• 矩阵维度高
• 矩阵稀疏
• 需要在X上添加技巧以解决单词频率不平衡

Iteration Based Method

Distributed semantics

Distributed semantics 是指一个单词的意义是由经常出现在其上下问的单词来表示的。

A word’s meaning is given by the words that frequently appear close-by

context 上下文是指，在文本中一个单词前后出现的单词集合

通过使用单词的上下文来构建单词表征向量.这样子做的原因是在什么上下文下使用该单词，以及什么样的上下文下不使用该单词，有助于理解单词的意思。

这样可以为每一个单词都构建一个稠密的向量表示，这个词向量与那些出现在相似上下文中的单词相似.

词向量的维度一般为300，为了优化效果可以提高维度。

Word2Vec

Word2Vec 是一个学习词向量的框架，其思想设计一个模型以词向量作为模型参数，构造目标函数，通过训练不断更新参数以优化目标函数，最终获得想要的词向量。

Word2vec 主有两种算法 CBOW 和 Skip-gram. 其中 CBOW 是通过上下文来预测中心词，而 Skip-gram 是通过中心词来预测上下文单词。

Language model

在介绍两种算法之前先介绍下语言模型，好的语言模型会给一个语法正确语义明确的距自己一个高的概率，而对一个随意单词拼凑的句子一个低的概率。

一个n个单词的句子可以表示为$P(w_1,w_2...,w_n)$P(w1​,w2​...,wn​)

Unigram model:
$P(w_1,w_2...,w_n) = \prod_{i=1}^{n}P(w_i)$P(w1​,w2​...,wn​)=i=1∏n​P(wi​)在这个计算公式中假设单词间相互独立，但是实际并非如此，单词前后间有关系。

Bigram model:
$P(w_1,w_2...,w_n) = \prod_{i=2}^{n}P(w_{i-1}|w_i)$P(w1​,w2​...,wn​)=i=2∏n​P(wi−1​∣wi​)该模型对于每一个单词考虑了其前一个单词

CBOW

CBOW构建两个矩阵，$\mathcal{V} \in R^{n \times|V|}$V∈Rn×∣V∣ 和 $U \in R^{|V| \times n}$U∈R∣V∣×n,

其中：

• $\mathcal{V}$V 是输入矩阵，即上下文单词向量矩阵
• U 是输出矩阵，即中心词向量矩阵
• n 是词向量空间大小
• |V| 是字典大小

算法流程:

1. 为上下文语境生成 one-hot 向量$(x^{(c-m)},...,x^{(c-1)},x^{(c+1)},...,x^{(c+m)} \in R^{V})$(x(c−m),...,x(c−1),x(c+1),...,x(c+m)∈RV)
2. 通过 x 与 $\mathcal{V}$V 相乘 $\mathcal{v_i} =\mathcal{V} x^{(i)} $获得对应的词向量 $\mathcal{v_i}$vi​
3. 获得上下文词向量的平均向量 $\hat{\mathcal{v}} = \frac{\mathcal{v}_{c-m}+ ... + \mathcal{v}_{c-1} + ... + \mathcal{v}_{c+m}}{2m}$v^=2mvc−m​+...+vc−1​+...+vc+m​​
4. 将上下文词平均向量与U相乘得到分数向量$z = U\hat{\mathcal{v}} \in R^{|V|}$z=Uv^∈R∣V∣,相似的向量得到分数高
5. 使用 softmax 将分数转化为概率$\hat{y} = softmax(z)$y^​=softmax(z)
6. 我们希望$\hat{y}$y^​ 能逼近真实的概率$y$y，概率最高的单词就是真正的中心词.而$y$y 是一个 one-hot vector

其中词向量点积运算用来计算单词间的相似度，可以理解为相似的向量在同一纬度上数值符号相同那么最后求得结果会大，反之则小.利用 softmax 将数值小的概率压缩，数值大的概率放大.

CBOW运作图如图所示，其中两个W矩阵分别对应着$\mathcal{V}$V(输入向量，私认为其等同于上下文向量) 和U(输出向量，等同于中心词向量)

如果$\hat{y},y$y^​,y 两者相似，那么就说明模型预测中心词结果很好，由于比较结果是两个概率，所以可以使用交叉熵 cross entropy $H(\hat{y},y)$H(y^​,y) 来衡量两个概率分布之间距离
$H(\hat{y},y) = -\sum_{j=1}^{|V|}{y_jlog(\hat{y_j})}$H(y^​,y)=−j=1∑∣V∣​yj​log(yj​^​)由于 y 是一个 one-hot 向量（因为一个上下文语境只会对应一个中心词），所以目标函数可以简化为
$H(\hat{y},y) = -{y_jlog(\hat{y_j})}$H(y^​,y)=−yj​log(yj​^​)为了优化模型，我们需要最小化目标函数:
$\begin{aligned} minimize J & = -log{P(w_c|w_{c-m},...w_{c-1},w_{c+1},...w_{c+m},)} \\ & = -logP(u_c|\hat{v}) \\ & = -log{\frac{exp(u_c^T\hat{v})}{\sum_{j=1}^{|V|}{exp(u_j^T\hat{v})}}} \end{aligned}$minimizeJ​=−logP(wc​∣wc−m​,...wc−1​,wc+1​,...wc+m​,)=−logP(uc​∣v^)=−log∑j=1∣V∣​exp(ujT​v^)exp(ucT​v^)​​

Skip-Gram Model

与 CBOW 相反，Skip-Gram Model 是通过中心词来预测上下文单词即中心词应该知道其周围应该出现哪些单词，输入的 x 为中心词，输出的 y 为上下文单词. PPT 中介绍的方法就是这种.

在该算法中为了方便计算，每个单词有有两种表示方法：

• $v_w$vw​ 当 w 是中心单词时
• $u_{w}$uw​ 当 w 是上下文单词时
  
  所以Skip-Gram Model构建两个矩阵，$\mathcal{V} \in R^{n \times|V|}$V∈Rn×∣V∣ 和 $U \in R^{|V| \times n}$U∈R∣V∣×n

其中：

• $\mathcal{V} $ 是输入矩阵，即中心单词向量矩阵
• U 是输出矩阵，即上下文单词向量矩阵
• n 是词向量空间大小
• |V| 是字典大小

算法流程：

1. 生成 one-hot 输入向量 $x \in R^{|V|}$x∈R∣V∣ 即中心单词向量
2. 与中心词向量矩阵$\mathcal{V}$V 相乘获得中心词向量 $\mathcal{v_i} =\mathcal{V} x^{(i)} $
3. 将中心词向量与U相乘得到分数向量$z = U\hat{\mathcal{v}} \in R^{|V|}$z=Uv^∈R∣V∣,相似的向量得到分数高
4. 使用 softmax 将分数转化为概率$\hat{y} = softmax(z)$y^​=softmax(z) ，注意 $(\hat{y}_{(c-m)},...,\hat{y}_{(c-1)},\hat{y}_{(c+1)},...,\hat{y}_{(c+m)} \in R^{V})$(y^​(c−m)​,...,y^​(c−1)​,y^​(c+1)​,...,y^​(c+m)​∈RV) 是观察上下文单词的概率
5. 我们希望生成的概率与真实的概率相符合，即$(\hat{y}_{(c-m)},...,\hat{y}_{(c-1)},\hat{y}_{(c+1)},...,\hat{y}_{(c+m)} \in R^{V})$(y^​(c−m)​,...,y^​(c−1)​,y^​(c+1)​,...,y^​(c+m)​∈RV) 与 实际的ont-hot vectors 输出相匹配

与CBOW不同这里目标函数设计多个上下文单词，所以引入朴素贝叶斯，假设上下文单词相互独立使用极大似然估计.
$\begin{aligned} minimize J & = -log{P(w_{c-m},...w_{c-1},w_{c+1},...w_{c+m}|w_c)} \\ & =-log \prod_{j=0,j \neq m}^{2m}P(w_{c-m+j}|w_c) \\ & =-log \prod_{j=0,j \neq m}^{2m}P(u_{c-m+j}|v_c) \\ & =-log \prod_{j=0,j \neq m}^{2m}\frac{exp(u_{c-m+j}^Tv_c)}{\sum_{j=1}^{|V|}{exp(u_j^Tv_c)}} \\ & = \sum_{j=0,j \neq m}^{2m}{u_{c-m+j}^Tv_c} + 2mlog{\sum_{j=1}^{|V|}{exp(u_j^Tv_c)}} \end{aligned}$minimizeJ​=−logP(wc−m​,...wc−1​,wc+1​,...wc+m​∣wc​)=−logj=0,j​=m∏2m​P(wc−m+j​∣wc​)=−logj=0,j​=m∏2m​P(uc−m+j​∣vc​)=−logj=0,j​=m∏2m​∑j=1∣V∣​exp(ujT​vc​)exp(uc−m+jT​vc​)​=j=0,j​=m∑2m​uc−m+jT​vc​+2mlogj=1∑∣V∣​exp(ujT​vc​)​训练模型 训练模式时，模型的参数$\theta$θ 为词向量，利用梯度下降的方式来更新参数，最后对每个单词拥有的两个词向量$v_w$vw​ 和 $u_w$uw​ 求平均.

Negative Sampling

在算法训练进行参数更新时候，可以看到目标函数要对|V|个单词求点积并求和$log{\sum_{j=1}^{|V|}{exp(u_j^Tv_c)}}$log∑j=1∣V∣​exp(ujT​vc​)，工作量巨大消耗时间O(|V|).

所以对于每一步可以不遍历整个字典|V|，而进行负采样.负采样即对于一对中心词和上下文单词（w,c）其不出现训练集中，即我们的训练集中没有这样的一对. 比如“I like playing football”，以"playing"作为中心词，那么"like"就是正采样，比如毫无关系的单词"bank"就是负采样.

Consider a pair (w,c) of word and context. Did this pair come from the training data? Let’s denote by P(D = 1|w,c) the probability that (w, c) came from the corpus data. Correspondingly, P(D = 0|w,c) will be the probability that (w,c) did not come from the corpus data.

对于使用逻辑回归来计算其为正负样本的概率：
$P(D=1|w,c,\theta) = \delta(v_c^Tv_w) = \frac{1}{1+e^{-v_c^Tv_w}}$P(D=1∣w,c,θ)=δ(vcT​vw​)=1+e−vcT​vw​1​所以可以构建一个新的目标函数

we build a new objective function that tries to maximize the probability of a word and context being in the corpus data if it indeed is, and maximize the probability of a word and context not being in the corpus data if it indeed is not.

也就是说，当中心词和上下文是训练集中那么我要增大估计其为正样本的概率，当不是训练集中的那么我要估计其为负样本概率
$\begin{aligned} \theta &= \mathop{argmax}\limits_{\theta} \prod_{(w,c) \in D}P(D=1|w,c,\theta) \prod_{(w,c) \in \bar{D}}P(D=0|w,c,\theta)\\ & =\mathop{argmax}\limits_{\theta}\prod_{(w,c) \in D}P(D=1|w,c,\theta) \prod_{(w,c) \in \bar{D}}(1-P(D=1|w,c,\theta))\\ & =\mathop{argmax}\limits_{\theta}\sum_{(w,c) \in D}log(P(D=1|w,c,\theta)) + \sum_{(w,c) \in \bar{D}}log(1-P(D=1|w,c,\theta))\\ & =\mathop{argmax}\limits_{\theta}\sum_{(w,c) \in D}log(\frac{1}{1 + exp(-u_w^Tv_c)}) + \sum_{(w,c) \in \bar{D}}log(1-\frac{1}{1 + exp(-u_w^Tv_c)})\\ & =\mathop{argmax}\limits_{\theta}\sum_{(w,c) \in D}log(\frac{1}{1 + exp(-u_w^Tv_c)}) + \sum_{(w,c) \in \bar{D}}log(\frac{1}{1 + exp(u_w^Tv_c)})\\ \end{aligned}$θ​=θargmax​(w,c)∈D∏​P(D=1∣w,c,θ)(w,c)∈Dˉ∏​P(D=0∣w,c,θ)=θargmax​(w,c)∈D∏​P(D=1∣w,c,θ)(w,c)∈Dˉ∏​(1−P(D=1∣w,c,θ))=θargmax​(w,c)∈D∑​log(P(D=1∣w,c,θ))+(w,c)∈Dˉ∑​log(1−P(D=1∣w,c,θ))=θargmax​(w,c)∈D∑​log(1+exp(−uwT​vc​)1​)+(w,c)∈Dˉ∑​log(1−1+exp(−uwT​vc​)1​)=θargmax​(w,c)∈D∑​log(1+exp(−uwT​vc​)1​)+(w,c)∈Dˉ∑​log(1+exp(uwT​vc​)1​)​最大化似然函数，与最小化负的似然函数一样所以：
$J = -\sum_{(w,c) \in D}log(\frac{1}{1 + exp(-u_w^Tv_c)}) - \sum_{(w,c) \in \bar{D}}log(\frac{1}{1 + exp(u_w^Tv_c)})\\$J=−(w,c)∈D∑​log(1+exp(−uwT​vc​)1​)−(w,c)∈Dˉ∑​log(1+exp(uwT​vc​)1​)其中$\bar{D}$Dˉ 是负的语料,"“stock boil fish is toy” 这种随意拼凑非正常语言的出现的概率很低，由他们构成$\bar{D}$Dˉ.对于中心词我们可以随机的采集负样本来生产$\bar{D}$Dˉ

对于 skip-gram 那么其新的目标函数为(这里只针对了一个上下文单词):
$-log\delta(u_{c-m+j}^Tv_c) - \sum_{k=1}^{K}{log\delta(-u_{k}^Tv_c)}$−logδ(uc−m+jT​vc​)−k=1∑K​logδ(−ukT​vc​)原本的目标函数
$-u_{c-m+j}^Tv_c - log\sum_{k=1}^{|V|}{exp(-u_{k}^Tv_c)}$−uc−m+jT​vc​−logk=1∑∣V∣​exp(−ukT​vc​)对于CBOW 其新目标函数为：
$-log\delta(u_{c}^T\hat{v}) - \sum_{k=1}^{K}{log\delta(-\widetilde{u}_{k}^T\hat{v})}$−logδ(ucT​v^)−k=1∑K​logδ(−ukT​v^)原本目标函数
$-u_{c}^T\hat{v} + log\sum_{k=1}^{|V|}{exp(-u_{j}^T\hat{v})}$−ucT​v^+logk=1∑∣V∣​exp(−ujT​v^)其中${\{\widetilde{u}_{k}|k=1...k\}}${uk​∣k=1...k} 是从 $P_n(w)$Pn​(w) 中采样获取的,其中$P_n(w)$Pn​(w) 会对单词的概率进行调整，增大概率较小值的单词被采样的概率.例如:

Hierarchical Softmax

分层 softmax 也是替代普通 softmax 的一种方法，对于非连续单词向量表现较好，而负采样对于连续和低纬度单词表现较好.

分层 softmax 使用二叉树来表示字典，每一个叶子节点对应一个单词，每个叶子节点都有一个从根部到其的唯一路径.$P(w|w_i)$P(w∣wi​) 即为从根节点每步随机选择节点，最终结果走到w节点概率.这个计算概率时间复杂度为O(log(|V|))，减少了计算量.我们模型是要去学习树中的所有节点（除了叶子和根节点）.
$P(w|w_i) = \prod^{L(W)-1}_{j=1}\delta([n(w,j+1) = ch(n(w,j))] \cdot v^T_{n(w,j)}v_{wi} ) \\ 其中 [x] = \begin{cases} 1 & if \; x \; is \; true \\ -1 & if \; x \; is \; false\end{cases}$P(w∣wi​)=j=1∏L(W)−1​δ([n(w,j+1)=ch(n(w,j))]⋅vn(w,j)T​vwi​)其中[x]={1−1​ifxistrueifxisfalse​其中：

• L(w) 表示根节点到叶子节点距离长度
• n（w,i）表示路径上第 i 个节点
• ch(n) 表示 n 的孩子节点,这里假设是左子节点

对于一个一个节点n，其去左子节点和其去右子节点的和为1
$\delta(v^T_{n(w,j)}v_{wi}) + \delta(- v^T_{n(w,j)}v_{wi}) = 1$δ(vn(w,j)T​vwi​)+δ(−vn(w,j)T​vwi​)=1这就保证了$ \sum_{w=1}^{|V|}P(w|w_i) = 1$ 与原始的softmax相同

对于上图$P(w_2|w_i)$P(w2​∣wi​) 可表示为:
$\begin{aligned} P(w_2|w_i) &= p(n(w_2,1),left) \cdot p(n(w_2,2),left) \cdot p(n(w_2,2),right) \\ & = \delta(v^T_{n(w_2,1)}v_{wi}) \cdot \delta(v^T_{n(w_2,2)}v_{wi}) \cdot \delta(v^T_{n(w_2,3)}v_{wi}) \end{aligned}$P(w2​∣wi​)​=p(n(w2​,1),left)⋅p(n(w2​,2),left)⋅p(n(w2​,2),right)=δ(vn(w2​,1)T​vwi​)⋅δ(vn(w2​,2)T​vwi​)⋅δ(vn(w2​,3)T​vwi​)​训练模型是最小化$-logP(w|w_i)$−logP(w∣wi​),然后更新路径从路径到叶子节点上的路径节点.

总结

最近开始啃CS224N，希望能学完后能有更加深入的理解，冲冲冲！

做笔记好累呀~~~~

参考文献

1. CS2234N 学习笔记（一）https://www.cnblogs.com/wevolf/p/10781636.html
2. word2vec原理(二) 基于Hierarchical Softmax的模型 https://www.cnblogs.com/pinard/p/7243513.html