word2vec是Google在2013年推出的一个NLP工具,它的特点是将所有的词向量化,这样词与词之间就可以定量的去度量他们之间的关系,挖掘词之间的联系。word2vec工具主要包含两个模型:跳字模型(skip-gram)和连续词袋模型(continuous bag of words,简称CBOW),
以及两种高效训练的方法:负采样(negative sampling)和层序softmax(hierarchical softmax)。word2vec词向量可以较好地表达不同词之间的相似和类比关系。word2vec自提出后被广泛应用在自然语言处理任务中。它的模型和训练方法也启发了很多后续的词向量模型。
词向量基础
自然语言是一套用来表达含义的复杂系统。在这套系统中,词是表义的基本单元。词向量是用来表示词的向量,通常也被认为是词的特征向量。通过以向量空间模型在N维空间中来表示单词,可以帮助不同的NLP算法实现更好的结果,因此这使得相似的文本在新的向量空间中组合在一起。用词向量来表示词并不是word2vec的首创,在很久之前就出现了,表示方式:
One-Hot 编码(独热编码)
一种最简单的词向量方式是one-hot representation,就是用一个很长的向量来表示一个词,向量的长度为词汇表的大小,向量的分量只有一个 1,其他全为 0,1 的位置对应该词在词典中的位置。比如:
'中国'表示为:[00010000000.....] '美国'表示为:[0000000010000...]
这种 One-hot Representation 采用稀疏向量方式存储,主要有2个缺点:
- 容易受维数灾难的困扰,尤其是将其用于 Deep Learning 的一些算法时:词汇表一般都非常大,比如达到百万级别,这样每个词都用百万维的向量来表示简直是内存的灾难。这样的向量其实除了一个位置是1,其余的位置全部都是0,表达的效率不高
- 不能很好地刻画词与词之间的相似性:任意两个词之间都是孤立的,这样使得算法对相关词的泛化能力不强。因为任何两个one-hot向量之间的内积都是0,很难区分他们之间的差别。光从这两个向量中看不出两个词是否有关系,哪怕是丈夫和老公这样的同义词也不能幸免于难。
举例来说,如果有一个词典[“面条”, “方便面”, “狮子”],那么“面条”对应的词向量就是[1,0,0],“方便面”对应的词向量就是[0,1,0]。比如“面条”和“方便面”显然有非常紧密的关系,但转化成向量[1,0,0]和[0,1,0]以后,就看不出两者有什么关系了,因为这两个向量相互正交。
分布式词向量/词嵌入
Distributed representation可以解决One hot representation的问题,它最早是 Hinton 于 1986 年提出的。它的思路是通过训练,将每个词都映射到一个较短的词向量上来。所有的这些词向量就构成了向量空间,进而可以用普通的统计学的方法来研究词与词之间的关系。这就是word embedding(词嵌入),即指的是将词转化成一种分布式表示,又称词向量。分布式表示将词表示成一个定长的连续的稠密向量,这个较短的词向量维度大小一般需要在训练时自己来指定。
Distributed Representation 可以创建多个层次结构或分段,其中可以为每个单词显示的信息分配不同的权重。这些分段或维度的选择可以是我们决定的,并且每个单词将由这些段中的权重分布表示。
比如上图我们将词汇表里的词用“位置”,“人口”, “面积”和“距离”4个维度来表示,Rome这个词对应的词向量可能是(0.99,0.99,0.05,0.7),也就是普通的向量表示形式。维度以 50 维和 100 维比较常见。当然在实际情况中,我们并不能对词向量的每个维度做一个很好的解释。
还是用之前的例子[“面条”, “方便面”, “狮子”],经过训练后,“面条”对应的向量可能是[1,0,1,1,0],而“方便面”对应的可能是[1,0,1,0,0],而“狮子”对应的可能是[0,1,0,0,1]。这样“面条”向量乘“方便面”=2,而“面条”向量乘“狮子”=0 。这样就体现出面条与方便面之间的关系更加紧密,而与狮子就没什么关系了。这种表示方式更精准的表现出近义词之间的关系,比之稀疏向量优势很明显。可以说这是深度学习在NLP领域的第一个运用。
分布式表示优点:
- 词之间存在相似关系:是词之间存在“距离”概念,这对很多自然语言处理的任务非常有帮助。
- 能够包含更多信息,并且每一维都有特定的含义。在采用one-hot特征时,可以对特征向量进行删减,词向量则不能。
词向量可视化
如果我们能够学习到一个 300 维的特征向量,或者说 300 维的词嵌入,通常我们可以做一件事,把这 300 维的数据嵌入到一个二维空间里,这样就可以可视化了。常用的可视化算法是t-SNE算法。
如果观察这种词嵌入的表示方法,会发现 man 和 woman 这些词聚集在一块(上图编号 1 所示), king 和queen 聚集在一块(上图编号 2 所示),这些都是人,也都聚集在一起(上图编号 3 所示)。动物都聚集在一起(上图编号 4 所示),水果也都聚集在一起(上图编号 5 所示),像 1、2、 3、 4 这些数字也聚集在一起(上图编号 6 所示)。如果把这些生物看成一个整体,他们也聚集在一起(上图编号 7 所示)。
词向量的作用
迁移学习
如果对于一个命名实体识别任务,只有一个很小的标记的训练集,训练集里可能没有某些词,但是如果有一个已经学好的词嵌入,就可以用迁移学习,把从互联网上免费获得的大量的无标签文本中学习到的知识迁移到一个命名实体识别任务中。
用词向量做迁移学习的步骤:
- 先从大量的文本集中学习词向量,或者可以下载网上预训练好的词向量模型。
- 把这些词向量模型迁移到新的只有少量标注训练集的任务中。
- 考虑是否微调,用新的数据调整词向量。
类比推理
我们用一个四维向量来表示 man,称为$e_{man}$,woman 的嵌入向量称为$e_{woman}$,对 king 和 queen 也是用一样的表示方法。在该例中,假设你用的是4维的嵌入向量,而不是比较典型的 50 到 1000 维的向量。这些向量有一个有趣的特性,就是假如你有向量$e_{man}$和$e_{woman}$,将它们进行减法运算,即
类似的,假如用$e_{king}$和$e_{queen}$,最后也会得到一样的结果,即
这个结果表示, man 和 woman 主要的差异是 gender(性别)上的差异,而 king 和 queen之间的主要差异,根据向量的表示,也是 gender( 性别)上的差异,这就是为什么$e_{man}- e_{woman}$与$e_{king}- e_{queen}$结果是相同的。所以得出这种类比推理的结论的方法就是,当算法被问及 man 对 woman 相当于 king 对什么时,算法所做的就是计算$e_{man}- e_{woman}$,然后找出一个向量也就是找出一个词,使得$e_{man}- e_{woman} \approx e_{king} – e_{queen}$,也就是说,当这个新词是 queen时,式子的左边会近似地等于右边。
计算当 man 对于 woman,那么 king 对于什么,能做的就是找到单词 w 来使得$e_{man}- e_{woman} \approx e_{king} – e_{queen}$这个等式成立,就是找到单词 w 来最大化$e_w$与$(e_{king}-e_{man}+e_{woman})$的相似度,即
$$\text {Find word w: argmax } \mathrm{sim}(e_{w}, e_{king}-e_{man}+e_{woman})$$
测算$e_w$与$(e_{king}-e_{man}+e_{woman})$的相似度,最常用的是余弦相似度。
词向量生成方式
基于统计方法
共现矩阵
通过统计一个事先指定大小的窗口内的word共现次数,以word周边的共现词的次数做为当前word的vector。具体来说,我们通过从大量的语料文本中构建一个共现矩阵来定义word representation。例如,有语料如下:
- I like deep learning.
- I like NLP.
- I enjoy flying.
则其共现矩阵如下:
矩阵定义的词向量在一定程度上缓解了one-hot向量相似度为0的问题,但没有解决数据稀疏性和维度灾难的问题。
SVD(奇异值分解)
既然基于co-occurrence矩阵得到的离散词向量存在着高维和稀疏性的问题,一个自然而然的解决思路是对原始词向量进行降维,从而得到一个稠密的连续词向量。 对1中矩阵进行SVD分解,得到正交矩阵U,对U进行归一化得到矩阵如下:
SVD得到了word的稠密(dense)矩阵,该矩阵具有很多良好的性质:语义相近的词在向量空间相近,甚至可以一定程度反映word间的线性关系。
基于语言模型(language model)
统计语言模型就是用来计算一个句子的概率分布。语言模型用处很广泛,比如机器翻译中, 如何挑选一个概率尽可能大的句子也就是尽量靠谱的句子返回. 假设一个长度为m的句子,包含词: $(w_1, w_2, w_3,..,w_m)$, 那么这个句子的概率,也就是这m个词共现的概率:
$$P(sen=(w_1, w_2, .., w_m)) = P(w_1)P(w_2|w_1)P(w_3|w_2,w_1)…P(w_m|w_{m-1}..w_1)$$
一般情况, 语言模型都是为了使得条件概率$P(w_t|w_1,w_2,..,w_{t-1})$最大化, 不过考虑到近因效应, 当前词与距离它比较近的n个词更加相关(一般n不超过5),而非前面所有的词都有关, 因此上述公式可以近似为:
$$P(w_t|w_1,w_2,..,w_{t-1})=P(w_t|w_{t-1}, w_{t-2}…w_{t-(n+1)})$$
上述便是经典的n-gram模型的近似表示方式。
神经语言模型(NNLM), 最初由Bengio提出的A Neural Probabilistic Language Mode最为经典,NNLM背后的基本思想是对出现在上下文环境里的词进行预测,这种对上下文环境的预测本质上也是一种对共现统计特征的学习。较著名的采用neural network language model生成词向量的方法有:Skip-gram、CBOW、LBL、NNLM、C&W、GloVe等。
Bengio通过下面的一个三层神经网络来计算:
第一层输入就是前$n-1$个词$w_{t-(n+1)},…,w_{t-1}$去预测第t个词是$w_t$的概率。这里面的矩阵 $C\in |V| \times d$ 维护着词汇表中所有词的词向量, 其中$|V|$是词汇表中词的个数, d是词向量的维度。然后根据输入的前n-1个词, 在C中找到它们对应的词向量, 然后直接串联起来成为一个维度为$(n-1)d$的向量x作为接下来三层神经网络的输入后面就是普通神经网络了。需要说明的是,因为我们那要预测概率最大的$w_t$, 因此最后输出层的神经元应该与词汇表大小同样为$|V|$, 这里使用使用softmax函数归一化输出层的值到[0,1], 代表可能的每个词的概率。此外在原文中, 存在一些直连边, 也就是上图中的虚线, 从输入层直接到输出层, 是一个线性变换, Bingo在文中表示, 直连边的存在大幅降低迭代次数, 但对语言模型效果无提升, 随着计算能力的提高, 后续的工作基本都去掉了直连边。
神经语言模型构建完成之后就是训练参数了,这里的参数包括词向量矩阵C以及三层神经网络的权重、偏置等参数。训练数据就是大堆大堆的预料库。训练结束之后, 语言模型得到了, 词向量也得到了。 换言之,词向量是这个语言模型的副产品。但是这个模型的缺点就是速度问题, 因为词汇表往往很大(几十万几百万), 训练起来就很耗时, Bengo仅仅训练5个epoch就花了3周, 这还是40个CPU并行训练的结果. 因此才会有了后续好多的优化工作, word2vec便是其中一个。
CBOW与Skip-Gram
用于神经网络语言模型的CBOW与Skip-Gram
在word2vec出现之前,已经有用神经网络DNN来用训练词向量进而处理词与词之间的关系了。采用的方法一般是一个三层的神经网络结构(当然也可以多层),分为输入层,隐藏层和输出层(softmax层)。这个模型是如何定义数据的输入和输出呢?一般分为CBOW(Continuous Bag-of-Words 与Skip-Gram两种模型。
CBOW模型,利用上下文或周围的单词来预测中心词。
输入:某一个特征词的上下文相关对应的词向量(单词的one-hot编码);输出:这特定的一个词的词向量(单词的one-hot编码)。
比如下面这段话,我们的上下文大小取值为4,特定的这个词是”Learning”,也就是我们需要的输出词向量(单词Learning的one-hot编码),上下文对应的词有8个,前后各4个,这8个词是我们模型的输入(8个单词的one-hot编码)。由于CBOW使用的是词袋模型,因此这8个词都是平等的,也就是不考虑他们和我们关注的词之间的距离大小,只要在我们上下文之内即可。
这样我们这个CBOW的例子里,我们的输入是8个词向量(8个单词的one-hot编码),输出是所有词的softmax概率(训练的目标是期望训练样本中心词对应的softmax概率最大);对应的CBOW神经网络模型输入层有8个神经元,输出层有词汇表大小个神经元。隐藏层的神经元个数我们可以自己指定。通过DNN的反向传播算法,我们可以求出DNN模型的参数,同时得到所有的词对应的词向量。这样当我们有新的需求,要求出某8个词对应的最可能的输出中心词时,我们可以通过一次DNN前向传播算法并通过softmax激活函数找到概率最大的词对应的神经元即可。
CBOW(Continuous Bag-of-Words Model):在已知上下文,例如$w_{t-2},w_{t-1},w_{t+1},w_{t+2}$的前提下,如何预测当前词$w_t$。学习的目标函数是最大化对数似然函数:
$$\sum_{w\in C}logp(w|Context(w))$$
Skip-gram模型,使用中心词来预测上下文词。
Skip-Gram模型和CBOW的思路是反着来的(互为镜像),即输入是特定的一个词的词向量(单词的one-hot编码),而输出是特定词对应的上下文词向量(所有上下文单词的one-hot编码)。还是上面的例子,我们的上下文大小取值为4, 特定的这个词”Learning”是我们的输入,而这8个上下文词是我们的输出。
这样我们这个Skip-Gram的例子里,我们的输入是特定词, 输出是softmax概率排前8的8个词,对应的Skip-Gram神经网络模型输入层有1个神经元,输出层有词汇表大小个神经元。隐藏层的神经元个数我们可以自己指定。通过DNN的反向传播算法,我们可以求出DNN模型的参数,同时得到所有的词对应的词向量。这样当我们有新的需求,要求出某1个词对应的最可能的8个上下文词时,我们可以通过一次DNN前向传播算法得到概率大小排前8的softmax概率对应的神经元所对应的词即可。
Skip-gram(Continuous Skip-gram Model):在已知当前词$w_t$的前提下,预测其上下文,例如$w_{t-2},w_{t-1},w_{t+1},w_{t+2}$。目标函数形如:
$$\sum_{w\in C}logp(Context(w)|w)$$
所以,只要简单理解为CBOW与Skip-Gram互为镜像,输入/输出都是词的one-hot编码,训练上下文->中心词/中心词->上下文词的关系权重就可以了。
CBOW和Skip-gram均为三层神经网络(输入层、投影层和输出层),而上下文的词的具体个数是可定义的。窗口大小为5时,两个模型的网络结构如下:
同样用于计算概率值,从模型的计算方式看,skip-gram想要预测更多(上下文),一次会更比CBOW慢一些,但有观点认为对低频词效果更好一些。
Huffman树
Huffman树是一种特殊结构的二叉树,由Huffman树设计的二进制前缀编码,也称为Huffman编码,在通信领域有着广泛的应用。在word2vec模型中,在构建层次Softmax的过程中,也使用到了Huffman树的知识。
Huffman树的基本概念
在二叉树中有一些基本的概念,对于如下所示的二叉树:
- 路径:在一棵树中,从一个节点到另一个节点之间的分支构成的通路,如从节点8到节点1的路径如图所示:
- 路径长度:路径上分支的数目,在上图中,路径长度为2。
- 节点的权:为树中的每一个节点赋予的一个非负的值,如上图中每一个节点中的值。
- 节点的带权路径长度:从根节点到该节点之间的路径长度与该节点权的乘积:如对于1节点的带权路径长度为:2。
- 树的带权路径长度:所有叶子节点的带权路径长度之和。
有了如上的概念,对于Huffman树,其定义为:给定n权值作为n个叶子节点,构造一棵二叉树,若这棵二叉树的带权路径长度达到最小,则称这样的二叉树为最优二叉树,也称为Huffman树。
由以上的定义可以知道,Huffman树是带权路径长度最小的二叉树,对于上面的二叉树,其构造完成的Huffman树为:
示例:霍夫曼树常处理符号编写工作。根据整组数据中符号出现的频率高低,决定如何给符号编码。如果符号出现的频率越高,则给符号的码越短,相反符号的号码越长。假设我们要给一个英文单字”F O R G E T”进行霍夫曼编码,而每个英文字母出现的频率分别列在如下图:
演算过程:
- 进行霍夫曼编码前,我们先创建一个霍夫曼树
- 将每个英文字母依照出现频率由小排到大,最小在左
- 每个字母都代表一个终端节点(叶节点),比较O.R.G.E.T六个字母中每个字母的出现频率,将最小的两个字母频率相加合成一个新的节点。如Fig.2所示,发现F与O的频率最小,故相加2+3=5
- 比较R.G.E.T,发现R与G的频率最小,故相加4+4=8
- 比较8.E.T,发现5与E的频率最小,故相加5+5=10
- 比较10.T,发现8与T的频率最小,故相加8+7=15
- 最后剩15,没有可以比较的对象,相加10+15=25
- 最后产生的树状图就是霍夫曼树
- 进行编码
- 给霍夫曼树的所有左链接’0’与右链接’1′
- 从树根至树叶依序记录所有字母的编码
word2vec中的CBOW与Skip-Gram
word2vec也使用了CBOW与Skip-Gram来训练模型与得到词向量,但是并没有使用传统的DNN模型,而是对其进行了改进。最先优化使用的数据结构是用霍夫曼树来代替隐藏层和输出层的神经元。
- 叶子节点:起到输出层神经元的作用,叶子节点的个数即为词汇表的大小。
- 内部节点:起到隐藏层神经元的作用。
霍夫曼树编码方式:一般对于一个霍夫曼树的节点(根节点除外),可以约定左子树编码为0,右子树编码为1。Word2vec中,约定编码方式和霍夫曼相反,即约定左子树编码为1,右子树编码为0,同时约定左子树的权重不小于右子树的权重。
CBOW模型
连续词袋模型(Continuous Bag-of-Word Model, CBOW)是一个三层神经网络,输入已知上下文,输出对下个单词的预测:
- 第一层是输入层, 输入已知上下文的词向量;
- 中间层称为线性隐含层, 它将所有输入的词向量累加;
- 第三层是一棵哈夫曼树, 树的的叶节点与语料库中的单词一一对应, 而树的每个非叶节点是一个二分类器(一般是softmax感知机等), 树的每个非叶节点都直接与隐含层相连
将上下文的词向量输入CBOW模型, 由隐含层累加得到中间向量,将中间向量输入哈夫曼树的根节点, 根节点会将其分到左子树或右子树。每个非叶节点都会对中间向量进行分类, 直到达到某个叶节点,该叶节点对应的单词就是对下个单词的预测。
训练过程:
- 根据预料库建立词汇表, 词汇表中所有单词拥有一个随机的词向量。我们从语料库选择一段文本进行训练
- 将单词W的上下文的词向量输入CBOW, 由隐含层累加, 在第三层的哈夫曼树中沿着某个特定的路径到达某个叶节点, 从给出对单词W的预测
- 根据W的哈夫曼编码确定从根节点到叶节点的正确路径, 也确定了路径上所有分类器应该作出的预测
- 采用梯度下降法调整输入的词向量, 使得实际路径向正确路径靠拢。在训练结束后从词汇表中得到每个单词对应的词向量
Skip-gram模型
Skip-gram模型同样是一个三层神经网络,skip-gram模型的结构与CBOW模型正好相反,skip-gram模型输入某个单词,输出对它上下文词向量的预测。
Skip-gram的核心同样是一个哈夫曼树, 每一个单词从树根开始到达叶节点,可以预测出它上下文中的一个单词。对每个单词进行N-1次迭代,得到对它上下文中所有单词的预测, 根据训练数据调整词向量得到足够精确的结果。
Word2vec对神经语言模型的改进
前面的CBOW与Skip-gram模型是标准的word2vec模型,或者说是神经语言模型的简化版,去掉了隐层的激活函数,其余的变化不大,因此训练效率还是很低的。我们分析下训练的复杂度。首先明确需要学习的两个词向量矩阵$W, W^{‘}$,从前面的推导中知道对于每一个训练样本,CBOW更新W的C行,Skip-gram更新W其中一行,也就是每次更新有限个词的词向量。但是对于$W^{‘}$则不同了,正如前面一直提到的,无论是CBOW还是Skip-gram,对每个训练样本(或者Mini Batch)从梯度更新中需要对$W^{‘}$的所有$V \times N$个元素,也就是词汇表中所有V个单词都需要更新词向量,考虑现实任务词汇表一般是几十万,上百万千万级别的, 这个计算成本是巨大的。,除了上面提到的训练部分,还有就是在每次前向计算的时候,隐层到输出层的softmax函数计算输出层V个元素,计算量也是很大,这样整个模型现实意义不大。
考虑到计算量大的部分都是在隐层到输出层上,尤其是$W^{‘}$的更新。因此word2vec使用了两种优化策略: Hierarchical Softmax 和 Negative Sampling。二者的出发点一致,就是在每个训练样本中,不再完全计算或者更新$W^{‘}$这个矩阵。二者都不再显示使用$W^{‘}$这个矩阵。因此这也就解释了前面说的为什么不用$W^{‘}$作为最终词向量。其实上述训练和推理的复杂度很大的根本原因是softmax的分母上的$\sum$,因此在求梯度的时候,就会有V次的计算。因此下面的两种方法其实是对softmax的优化,不仅仅限制在word2vec。
Hierarchical Softmax
首先Hierarchical SoftMax(HS)并不是word2vec提出来的,而是之前Bengio在2005年最早提出来专门为了加速计算神经语言模型中的softmax的一种方式,这里介绍如何在word2vec中使用。HS主要基于哈夫曼树(一种二叉数)将计算量大的部分变为了一种二分类的问题。先看下面的图, 原来的模型在隐层之后通过$W^{‘}$连接输出层,现在HS则去掉了$W^{‘}$,隐层h直接与下面的二叉树的root节点相连:
其中图中白色的叶子节点表示词汇表中所有的$|V|$个词,黑色节点表示非叶子节点, 每一个叶子节点也就是每一个单词,都对应唯一的一条从root节点出发的路径。而我们的目的是使的$w=w_O$这条路径的概率最大,即:$P(w=w_O | w_I)$最大,此时每一个分支都代表一个选择,向左转还是向右转。 所以如何判断向左还是向右呢? 我们用$n(w,j)$表示从root到叶子节点w的路径上的第j个非叶子节点, 并且每个非叶子节点都对应一个向量$v^{‘}_{n(w, j)}$, 维度与h相同, 然后使用一个sigmod函数:$\sigma(x)= \frac{1}{1+\exp(-x)} \in [0, 1]$, 结合向量的内积,来判断该向左还是向右,如下,第n个节点向左以及向右的概率定义:
$$P(n, left ) = \sigma({v^{‘}_{w}} \cdot \boldsymbol{h})$$
$$P(n, right) =1-\sigma(v^{‘}_w \cdot \boldsymbol{h}) = \sigma(-v_{w}^{‘} \cdot h)$$
有了上述的概率,我们可以重新定义 $P(w_O|w_i)$了:
$$P(w=w_O|w_I)= \Pi_{j=1}^{L(w)-1}P(\sigma(I(n(w,j+1==left) v^{‘}_{w} \cdot \mathbf{h}))$$
其中$I()$是指示函数,条件成立值为1,反之为-1。而$L(w)$表示整条路径的长度,这样整个概率就是从root节点到叶子节点这条路径的概率,这样我们在训练的时候,通过训练样本来更新非叶子节点的参数$v{‘}_{w}$。
举个例子, 比如上图中的加粗的黑色路径: $(n(w_2,1),n(w_2,2),n(w_2,3),w_2)$, 就是说假设有一个训练样本是$(w_I,w_2)$, 我们需要使得$P(w_O=w_2|w_I)$概率最大:
$$P(w_2=w_O) = P(n(w_2,1), left) \cdot P(n(w_2,2), left) \cdot P(n(w_2, 3), right) = \sigma({v^{‘}_{n(w_2,1)}}^T \mathbf{h}) \cdot \sigma({v^{‘}_{n(w_2,2)}}^T \mathbf{h}) \cdot \sigma(-{v^{‘}_{n(w_2,3)}}^T \mathbf{h})$$
并且在一个非叶子节点处,向左向右的概率和为1,因此一直分裂下去,最后的和肯定还是1。因此可以很容易得到:
$$\sum\limits_{j=1}^{V}P(w_j=w_O)=1$$
这一点的证明是有必要的,因为在原始的softmax本身保证了所有单词的概率和是1,而通过上式也知道了通过HS得到的输出层仍然是一个概率多项分布,输出所有的单词概率和为1。
讲完了从前向后的如何得到输出单词的概率的过程,下面开始后向传播的训练过程。首先需要明确的是训练的参数:输入层与隐层的词向量矩阵W,以及二叉树的非叶子节点对应的向量$\{v{‘}_{n(w,j)}, j =1,2,3,..,L(w)-1\}$。
为了书写方便,下面简化一部分的符号: 用$[I]$表示前面的指示函数$I(n(w,j+1)==left)$,使用$v^{‘}_{j}$表示$v^{‘}_{n(w,j)}$。
对于一组训练数据,损失函数的定义与前面相同,最大似然(注意这里以One-Word Model为例,CBOW与Skip-Gram按照上述的思路完全一样):
$$E = -\log P(w=w_O|w_I) = – \sum\limits_{j=1}^{L(w)-1}\log \sigma([I] {v^{‘}_{j}}^{T} \mathbf{h})$$
之后便可以逐项求梯度了,先考虑$v^T \mathbf{h}$, 注意$\frac{\partial \sigma(x)}{x} = \sigma(1-\sigma)$:
$$\frac{\partial E}{\partial v^{‘}_j \mathbf{h}} = (\sigma([I] {v_{j}^{‘}}^T \mathbf{h}))[I]$$
之后对$[I]$分情况讨论,可得:$\frac{\partial E}{\partial {v^{‘}_{j}}^T \mathbf{h}} = \sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j$ 这里如果$[I]=1$,那么$t_j =1$,否则$t_j=0$,这个公式与前面的$y_j-t_j$很类似,可以理解为预测值与实际值的差别。
有了上述的梯度就可以很简单的求出$v^{‘}$的梯度了:
$$\frac{\partial E}{\partial v^{‘}_j} = \frac{\partial E}{\partial {v^{‘}_{j}}^T \mathbf{h}} \frac{\partial {v^{‘}_{j}}^T \mathbf{h}}{\partial {v^{‘}_{j}}^T} = (\sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j) \mathbf{h}$$
有了梯度便可以更新了,具体公式还是梯度下降:
$${v^{‘}_{j}}^{(new)} = {v^{‘}_{j}}^{(old)} – \eta (\sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j) \mathbf{h},\ j=1,2,3,…,L(w)-1$$
也就是说对于一个训练样本, 我们只需要更新$L(w)-1$个向量就好了, 而未优化的版本需要更新$V$个, 相当于时间复杂度从$O(V)$降到了$O(\log V)$,这个提升还是非常大的,同时在考察空间复杂度,HS的二叉树的非叶子节点有$V-1$个,也就是我们需要$V-1$存储$v^{‘}_{j},\ \ j=1,2,3..V-1$,优化之前则是$V$个,空间复杂度相同,但是时间复杂度却大大降低。
然后考虑隐层h的梯度,因为我们的优化目标都是在隐层到输出层,因此前面的几乎不变,路径上的非叶子节点的表达式都含有h,因此需要对梯度求和:
$$\frac{\partial E}{\partial \mathbf{h}} = \sum\limits_{j=1}^{L(w)-1} \frac{\partial E}{\partial {v^{‘}_{j}}^T \mathbf{h}} \frac{\partial {v^{‘}_{j}}^T \mathbf{h}}{\partial \mathbf{h}} =\sum\limits_{j=1}^{L(w)-1}(\sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j)\cdot v^{‘}_{j}$$
整个Hierarchical Softmax的优化算法介绍完了,隐层到输出层的计算量从$O(V)$, 利用二叉树(更加具体来说是哈夫曼树)降为了$O(logV)$。
Negative Sampling
相比Hierarchical Softmax用复杂的树形结构来对softmax进行优化, 负采样(Negative Sampling)更加直接简单。因为softmax的存在,在使用梯度下降的时候,每个训练样本需要更新V个向量,这是根本问题。因此负采样NS仅仅更新一小部分向量,一般是5-20个,可以手工设定,而非全部V个(一般来说V都是几万到几百万的量级)。
再来考虑原始模型的训练过程,对于一个训练样本$(w_I, w_O)$, 我们要使得$P(w=w_O|w_I)$最大, 也就是说要使得输出层的其它单词的概率要比较小一些,基于这种思想, 我们将输出层的V个样本分为正例(Positive Sample)也就是w_O对应的项, 以及剩余$V-1$个负例(Negative Samples)。举个例子有个样本phone number,这样$w_I=phone, w_O=number$, 正例就是number这个词, 负例就是不太可能与phone共同出现的词。
负采样的思想便是每次训练只随机取一小部分的负例使他们的概率最小,以及对应的正例概率最大。那么如何对负例进行抽样呢? 这里就需要定义一个noise distribution,有了分布$P_n(w)$就可以依据概率分布进行带权随机抽样了。 在word2vec中,作者直接使基于词的频次的词的权重分布:
$$weight(w) = \frac{coun(w)^{0.75}}{\sum _{u}count(w)^{0.75}}$$
相比于直接使用频次作为权重, 取0.75幂的好处可以减弱不同频次差异过大带来的影响,使得小频次的单词被采样的概率变大。
下面基于上面的思想,直接给出具体的损失函数:
$$E = -\log \sigma(v^{‘}_{w_O}\mathbf{h}) – \sum\limits_{w_j \in \mathcal{W}_{neg}}\log \sigma(-v^{‘}_{w_j}\mathbf{h})$$
$\mathcal{W}_{neg}$是负例单词集合。上述公式跟原本的负采样的有些许差别,具体的推导细节可以参考这篇Goldberg, Y. and Levy, O. (2014). word2vec explained: deriving mikolov et al.’s negative- sampling word-embedding method. 这里不再赘述了。 只需要记住,NS也是对softmax函数做的优化,除了word2vec,在其他地方涉及到softmax的均可以采用类似的思想来重写目标函数。
有了损失函数,然后跟HS一样,用梯度下降的方法更新$v^{‘}$即可,推导思路跟HS也是一样,分$w_j$是否等于$w_O$来讨论,最终得到的梯度公式与HS一模一样:
$$\frac{\partial E}{\partial {v^{‘}_{j}}^T \mathbf{h}} = \sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j$$
这里的$t_j$含义跟前面提到的几次都相同。最后给出更新$v^{‘}$的公式:
$${v^{‘}_{j}}^{(new)} = {v^{‘}_{j}}^{(old)} – \eta (\sigma( {v^{‘}_{j}}^T \mathbf{h}) – t_j) \mathbf{h},\ w_j \in \{w_O \} + \mathcal{W}_{neg}$$
从公式也可以看出,对于每个训练数据,每次只需要更新很少的几个向量,而非原始的V个,大大降低了训练复杂度。
跟HS相同,NS的优化也是对隐层到输出层的优化,因此前面输入层到隐层的梯度只需要做相应修改即可,没有影响,具体可以参考HS的公式,这里不再重复了。
到此为止,两种针对softmax的优化方式介绍完毕,简单对比一下两种方式:
- HS实现比较复杂, 需要借助哈夫曼树,而且HS是专门优化softmax的方法
- NS相对简单,仅仅是简单采样,NS则是一种概率采样的方法,属于NCE(Noise Contrastive Estimation)的一种简单形式,代码实现也很简单。训练得到的词向量质量也很高,相对常用一些。
参考链接:
请问skip-gram模型,假设我有{a,b},{a,c};其中a为中心词,b和c为上下文词。
为什么我看吴恩达提到的训练语句中{a,b},{a,c}组成了两条训练语句;您文中所提到的,我的理解是,{a;b,c}组成了一条训练语句,因为a输入后,取softmax后前两个最大的概率去做反向传播,那对应的监督语料就要是b,c构成的一条向量才对吧?我看了好多文章都不甚理解,请您可以解答一下
请问这本书的名字是什么?谢谢