词的表达

  1. 给定包含 N 篇文档的语料库 D={D1,D2,,DN} ,所有的单词来自于包含 V 个词汇的词汇表 V={word1,word2,,wordV},其中 V 表示词汇表的大小 。

    每篇文档 Di 包含单词序列 (wordw1i,wordw2i,,wordwnii) ,其中 wji{1,2,,V} 表示第 i 篇文档的第 j 个单词在词汇表中的编号,ni 表示第 i 篇文档包含 ni 个单词。

    词的表达任务要解决的问题是:如何表示每个词汇 wordv

  2. 最简单的表示方式是one-hot 编码:对于词汇表中第 v 个单词 wordv,将其表示为 wordv(0,0,,0,1,0,,0)T ,即第 v 位取值为1,剩余位取值为0

    这种表示方式有两个主要缺点:

    • 无法表达单词之间的关系:对于任意一对单词 (wordi,wordj),其向量距离均为 2

    • 向量维度过高:对于中文词汇表,其大小可能达到数十万,因此one-hot 向量的维度也在数十万维。这对于存储、计算都消耗过大。

  3. BOW:Bag of Words:词在文档中不考虑先后顺序,这称作词袋模型。

一、向量空间模型 VSM

  1. 向量空间模型主要用于文档的表达。

  2. 向量空间模型假设单词和单词之间是相互独立的,每个单词代表一个独立的语义单元。实际上该假设很难满足:

    • 文档中的单词和单词之间存在一定关联性,单词和其前面几个单词、后面几个单词可能存在语义上的相关性,而向量空间模型忽略了这种上下文的作用。

    • 文档中存在很多的一词多义和多词同义的现象,每个单词并不代表一个独立的语义单元。

1.1 文档-单词 矩阵

  1. 给定语料库 D 和词汇表 V,定义文档-单词 矩阵为:

    (1)word1word2word3wordVD10010D21010DN0110

    令矩阵为 D ,则: D(i,j)=1 表示文档 Di 中含有单词 wordjD(i,j)=0 表示文档 Di 中不含单词 wordj

    于是文档 Di 表示为:Di(0,1,0,1,,0)T ,其中文档 Di 中包含的单词对应的位置取值为1,其它位置取值为 0 。

  2. 事实上,文档的上述表达并未考虑单词的顺序,也未考虑单词出现的次数。一种改进策略是考虑单词出现的次数,从而赋予文档-单词 矩阵以不同的权重:

    (2)D=[w1,1w1,2w1,3w1,Vw2,1w2,2w2,3w2,VwN,1wN,2wN,3wN,V]

    其中 wi,j 表示单词 wordj 在文档 Di 中的权重。

    • 如果单词 wordj 在文档 Di 中未出现,则权重 wi,j=0

    • 如果单词 wordj 在文档 Di 中出现,则权重wi,j0

  3. 权重wi,j 有两种常用的选取方法:

    • 单词权重等于单词出现的频率TFwi,j=TF(Di,wordj)

      • 函数 TF(Di,wordj) 返回单词 wordj 在文档 Di 中出现的频数。

      • 其缺点是:一些高频词(如:我们大家)以较大的权重出现在每个文档中,这意味着对每篇文档这些高频词是比较重要的。事实上对于绝大多数 NLP 任务,将这些词过滤掉不会有任何影响。

    • 单词权重等于单词的TF-IDFwi,j=TF(Di,wordj)×IDF(wordj)

      • 函数 IDF(wordj) 是单词的逆文档频率:IDF(wordj)=logNDF(wordj) 。其中:N 为语料库的文档数量,DF(wordj) 为出现单词 wordj 的文档的数量,DF(wordj)N 为单词 wordj 出现在一篇文档中的概率。

      • TF-IDF 对于高频词进行降权。如果单词 wordj 出现在大多数文档中,则 DF(wordj)N 较大,因此 IDF(wordj) 会较小。

  4. TF-IDF 不仅考虑了单词的局部特征,也考虑了单词的全局特征。

    • 词频 TF(Di,wordj) 描述了单词 wordj 在文档 Di 中的局部统计特征。

    • 逆文档频率 IDF(wordj) 描述了单词 wordj 在语料库 D 中的全局统计特征。

1.2 相似度

  1. 给定 文档-单词 矩阵,则很容易得到文档的向量表达:Di(wi,1,wi,2,,wi,V)T

    给定文档 Di,Dj ,则文档的相似度为:

    (3)similar(Di,Dj)=cos(wi,wj)=wiwj||wi||||wj||

    其中 wi=(wi,1,wi,2,,wi,V)T,wj=(wj,1,wj,2,,wj,V)T

    也可以使用其它方式的相似度,如 L2 距离相似度。

二、LSA

  1. 潜在语义分析latent semantic analysis:LSA 的基本假设是:如果两个词多次出现在同一篇文档中,则这两个词具有语义上的相似性。

2.1 原理

  1. 给定文档-单词 矩阵 D

    (4)D=[w1,1w1,2w1,3w1,Vw2,1w2,2w2,3w2,VwN,1wN,2wN,3wN,V]

    其中 wi,j 表示单词 wordj 在文档 Di 中的权重,可以为:单词 wordj 在文档 Di 中是否出现的0/1 值、单词 wordj 在文档 Di 中出现的频次、或者单词 wordj 在文档 Di 中的TF-IDF 值。

  2. 定义 vj=(w1,j,w2,j,,wN,j)T, 它为矩阵 D 的第 j 列,代表单词 wordj单词-文档向量,描述了该单词和所有文档的关系。

    • 向量内积 vpvq 描述了单词 wordp 和单词 wordq 在文档集合中的相似性。

    • 矩阵乘积 DTDRV×V 包含了所有词向量内积的结果。

  3. 定义 di=(di,1,di,2,,di,V)T ,它为矩阵 D 的第 i 行,代表文档 Di文档-单词向量,描述了该文档和所有单词的关系。

    • 向量内积 dsdt 描述了文档 Ds 和文档 Dt 在文档集合中的相似性。

    • 矩阵乘积 DDTRN×N 包含了所有文档向量内积的结果。

  4. 对矩阵 D 进行SVD 分解。假设矩阵 D 可以分解为:D=PΣQT 。其中:

    • PRN×N,QRV×V 为单位正交矩阵。

    • ΣRN×V 为广义对角矩阵。

      (5)Σ=[σ100000σ200000σr000000000000]

      其中 σ1σ2σr>0 称作奇异值。

  5. SVD 分解的物理意义为:将文档按照主题分解。所有的文档一共有 r 个主题,每个主题的强度 (主题强度就是主题在数据集中出现的次数)分别为:σ1,σ2,,σr

    • i 篇文档 Di 由这 r 个主题组成,文档的主题概率分布(称作文档-主题向量)为:

      (6)p(i)=(P(i,1),P(i,2),,P(i,r))T
    • t 个主题由 V 个单词组成,主题的单词概率分布(称作主题-单词向量 )为:

      (7)q(t)=(Q(t,1),Q(t,2),,Q(t,V))T
    • j 个单词由 r 个主题组成,单词的主题概率分布(称作 单词-主题 向量)为:

      (8)v(j)=(Q(1,j),Q(2,j),,Q(r,j))T
    • 根据 D=PΣQT 有:

      (9)D=P[100010001000000]N×r[σ1000σ2000σr][100000100000100]r×VQT

      则该分解的物理意义为:文档-单词 矩阵 = 文档-主题 矩阵 x 主题强度 x 主题-单词 矩阵。

2.2 应用

  1. 得到了文档的主题分布、单词的主题分布之后,可以获取文档的相似度和单词的相似度。

    • 文档 Di 和文档 Dj 的相似度:

      (10)sim(Di,Dj)=p(i)p(j)||p(i)||×||p(j)||
    • 单词 wordi 和单词 wordj 的相似度:

      (11)sim(wordi,wordj)=v(i)v(j)||v(i)||×||v(j)||
  2. 虽然获得了文档的单词分布,但是并不能获得主题的相似度。因为 Q 是正交矩阵,因此有:

    (12)(Q(i,1),Q(i,2),,Q(i,V))T(Q(j,1),Q(j,2),,Q(j,V))T=0,ij

    则有:

    (13)sim(topici,topicj)=q(i)q(j)||q(i)||×||q(j)||=(Q(i,1),Q(i,2),,Q(i,V))T(Q(j,1),Q(j,2),,Q(j,V))T||q(i)||×||q(j)||=0,ij

    因此,任意两个主题之间的相似度为 0 。

  3. 文档-主题向量P 决定。根据: D=PΣQTP=DQΣ1PT=Σ1QTDT ,而文档-主题向量P 的行向量,也就是 PT 的列向量。文档-单词向量D 的行向量,也就是 DT 的列向量。

    因此对于一篇新的文档 Ds,假设其文档-单词向量ws ,则其文档-主题向量为:

    (14)p(s)=Σ1QTws
  4. LSA 可以应用在以下几个方面:

    • 通过对文档的文档-主题向量 进行比较,从而进行基于主题的文档聚类或者分类。

    • 通过对单词的单词-主题向量进行比较,从而用于同义词、多义词进行检测。

    • 通过将query 映射到主题空间,进而进行信息检索。

2.3 性质

  1. LSA 的本质是将矩阵 D 通过 SVD 进行降维,降维主要是由于以下原因:

    • 原始的文档-单词 矩阵 D 太大计算机无法处理,通过降维得到原始矩阵的一个近似。

    • 原始的文档-单词 矩阵 D 含有噪音,通过降维去掉原始矩阵的噪音。

    • 原始的文档-单词 矩阵 D 过于稀疏,通过降维得到一个稠密的矩阵。

  2. LSA 的降维可以解决一部分同义词的问题,也可以解决一部分二义性的问题。

    • 经过降维,意义相同的同义词的维度会因降维被合并。

    • 经过降维,拥有多个意义的词,其不同的含义会叠加到对应的同义词所在的维度上。

  3. LSA 的缺点:

    • 产生的主题维度可能存在某些主题可解释性差。即:它们并不代表一个人类理解上的主题。

    • 由于Bag of words:BOW 模型的局限性,它无法捕捉单词的前后顺序关系。

      一个解决方案是:采用二元词组或者多元词组。

    • LSA 假设单词和文档形成联合高斯分布。实际观察发现,它们是一个联合泊松分布。这种情况下,用pLSA 模型效果会更好。

三、Word2Vec

3.1 CBOW 模型

  1. CBOW 模型(continuous bag-of-word):根据上下文来预测下一个单词。

3.1.1 一个单词上下文

  1. 在一个单词上下文的CBOW 模型中:输入是前一个单词,输出是后一个单词,输入为输出的上下文。

    由于只有一个单词作为输入,因此称作一个单词的上下文。

  2. 一个单词上下文的CBOW 模型如下:

    其中:

    • N 为隐层的大小,即隐向量 h=(h1,h2,,hN)TRN

    • 网络输入 x=(x1,x2,,xV)TRV ,它是输入单词(即上下文单词)的 one-hote 编码,其中只有一位为 1,其他位都为 0 。

    • 网络输出 y=(y1,y2,,yV)TRV,它是输出单词为词汇表各单词的概率。

    • 相邻层之间为全连接:

      • 输入层和隐层之间的权重矩阵为 WRV×N

      • 隐层和输出层之间的权重矩阵为 WRN×V

  3. 假设没有激活函数,没有偏置项。给定输入 xRV,则其对应的隐向量 hRN 为: h=WTx

    令:

    (15)W=[w1Tw2TwVT]

    由于 x 是个one-hot编码,假设它为词表 V 中第 j 个单词 wordj,即:

    (16)x1=0,x2=0,,xj1=0,xj=1,xj+1=0,,xV=0

    则有:h=wj

    即:W 的第 jwjT 就是词表 V 中第 j 个单词 wordj 的表达,称作单词 wordj 的输入向量。

  4. 给定隐向量 h,其对应的输出向量 uRV为: u=WTh 。令:

    (17)W=[w1,w2,,wV]

    则有:uj=wjh

    • uj 表示词表 V 中,第 j 个单词 wordj 的得分。

    • wj 为矩阵 W 的第 j 列,称作单词 wordj 的输出向量。

  5. u 之后接入一层 softmax 层,则有:

    (18)yj=p(wordjx)=exp(uj)j=1Vexp(uj),j=1,2,,V

    yj 表示词汇表 V 中第 j 个单词 wordj 为真实输出单词的概率。

    假设输入单词为 wordI (它称作上下文) ,观测到它的下一个单词为 wordO 。令输入单词的对应的网络输入为 x ,其隐向量为 wI,输入输出单词对应的输出单元为 j,则采用交叉熵的损失函数为:

    (19)E(wordI,wordO)=logexp(uj)j=1Vexp(uj)=wjh+logj=1Vexp(wjh)=wjwI+logj=1Vexp(wjwI)

    考虑语料库 D 中所有的样本,则整体经验损失函数为:

    (20)L=(wordI,wordO)DE(wordI,wordO)

    则网络的优化目标为:

    (21)minL=minW,W(wordI,wordO)D(wjwI+logj=1Vexp(wjwI))

    设张量 A 为某个网络参数,则有:

    (22)AL=(wordI,wordO)AE

    则该参数的单次更新 AAηAL ,可以表示为单个样本的多次更新:

    (23)for (wordI,wordO)D:AAηAE

    因此本节的参数更新推导是关于单个样本的更新:AAηAE

3.1.2 参数更新

  1. 定义 tj=I(j=j) ,即第 j 个输出单元对应于真实的输出单词 wordO 时,它为1;否则为0。定义:

    (24)ej=Euj=yjtj

    它刻画了每个输出单元的预测误差:

    • j=j 时: ej=yj1<0,它刻画了输出概率 (yj) 与真实概率 1 之间的差距。小于 0 表示预测不足。

    • jj 时:ej=yj>0,它刻画了输出概率 (yj) 与真实概率 0 之间的差距。大于 0 表示预测过量。

  2. 根据:uj=wjhujwj=h ,则有:

    (25)Ewj=Euj×ujwj=ejh

    wj 更新规则为:

    (26)wj(new)=wj(old)ηejh

    其物理意义为:

    • 当估计过量 (ej>0yj>tj) 时, wj 会减去一定比例的 h 。 这发生在第 j 个输出单元不对应于真实的输出单词时。

    • 当估计不足 (ej<0yj<tj) 时, wj 会加上一定比例的 h 。这发生在第 j 个输出单元刚好对应于真实的输出单词时。

    • yjtj 时,更新的幅度将非常微小。

  3. 定义:

    (27)EH=Eh=(uh)TEu

    根据:u=WTh(uh)T=W ,则有:EH=We=j=1Vejwj

    EH 的物理意义为:词汇表 V 中所有单词的输出向量的加权和,其权重为 ej

  4. 考虑到 h=WTx ,则有:

    (28)Ewk,i=Ehi×hiwk,i=EHi×xk

    写成矩阵的形式为:EW=xEH ,其中 为克罗内克积。

    由于 xone-hote 编码,所以它只有一个分量非零,因此 EW 只有一行非零,且该非零行就等于 EH 。因此得到更新方程:

    (29)wI(new)=wI(old)ηEH

    其中 wIx 非零分量对应的 W 中的行,而 W 的其它行在本次更新中都保持不变。

  5. 考虑更新 WI 行的第 k 列,则:

    (30)wI,k(new)=wI,k(old)ηj=1Vejwj,k
    • yjtj 时,ej 趋近于 0 ,则更新的幅度将非常微小。

    • yjtj 差距越大,ej 绝对值越大, 则更新的幅度越大。

  6. 当给定许多训练样本(每个样本由两个单词组成),上述更新不断进行,更新的效果在不断积累。

    • 根据单词的共现结果,输出向量与输入向量相互作用并达到平衡。

      • 输出向量 w 的更新依赖于输入向量 wIwj(new)=wj(old)ηejh

        这里隐向量 h 等于输入向量 wI

      • 输入向量 wI 的更新依赖于输出向量 wwI(new)=wI(old)ηEH

        这里 EH=j=1Vejwj 为词汇表 V 中所有单词的输出向量的加权和,其权重为 ej

    • 平衡的速度与效果取决于单词的共现分布,以及学习率。

3.1.3 多个单词上下文

  1. 考虑输入为目标单词前后的多个单词(这些单词作为输出的上下文),输入为 C 个单词:x1,x2,,xC 。对于每个输入单词,其权重矩阵都为 W,这称作权重共享。这里的权重共享隐含着:每个单词的表达是固定的、唯一的,与它的上下文无关。

    隐向量为所有输入单词映射结果的均值:

    (31)h=1CWT(x1+x2++xC)=1C(wI1+wI2++wIC)

    其中:Ii 表示第 i 个输入单词在词汇表 V 中的编号,wj 为矩阵 W 的第 j 行,它是对应输入单词的输入向量。

  2. 假设给定一个单词序列 wordI1,wordI2,,wordIC (它称作上下文),观测到它的下一个单词为 wordOwordO 对应的网络输出编号为 j

    定义损失函数为交叉熵:

    (32)E=uj+logj=1Vexp(uj)=wjh+logj=1Vexp(wjh)

    它的形式与一个单词上下文中推导的完全相同,除了这里的 h 不同。

    考虑语料库 D 中所有的样本,则整体经验损失函数为:

    (33)L=(wordI1,wordI2,,wordIC,wordO)DE

    则网络的优化目标为:

    (34)minL=minW,W(wordI1,wordI2,,wordIC,wordO)D(wjwI+logj=1Vexp(wjwI))

    .

  3. 一个单词上下文中推导的结果相同,这里给出参数更新规则:

    • 更新 W

      (35)wj(new)=wj(old)ηejh,j=1,2,,V

      其中 h=1C(wI1+wI2++wIC)

    • 更新 W

      (36)wIi(new)=wIi(old)1CηEH,i=1,2,,C

      其中 :

      • EH=We=j=1Vejwj ,它是词汇表 V 中所有单词的输出向量的加权和,其权重为 ej

      • Ii 为第 i 个输入单词在词表 V 中的编号。

  4. 在更新 W 时,如果有相同的输入单词(如: x1=x2word100 ),则在参数更新时认为它们是不同的。最终的效果就是在 wIi 中多次减去同一个增量 1CηEH

    你也可以直接减去 nvCηEH, 其中 nv 为词汇表中单词 wordv 在输入中出现的次数。

3.2 Skip-Gram

  1. Skip-Gram 模型是根据一个单词来预测其前后附近的几个单词(即:上下文)。

3.2.1 网络结构

  1. Skip-Gram 网络模型如下。其中:

    • 网络输入 x=(x1,x2,,xV)TRV ,它是输入单词的 one-hot 编码,其中只有一位为 1,其他位都为 0 。

    • 网络输出 y1,y2,,yC ,其中 yc=(y1c,y2c,,yVc)TRV是第 c 个输出单词为词汇表各单词的概率。

    • 对于网络的每个输出 yc ,其权重矩阵都相同,为 W。这称作权重共享。

      这里的权重共享隐含着:每个单词的输出向量是固定的、唯一的,与其他单词的输出无关。

  2. Skip-Gram 网络模型中,设网络第 c 个输出的第 j 个分量为 ujc=wjh ,则有:

    (37)yjc=p(wordjcx)=exp(ujc)k=1Vexp(ukc);c=1,2,,C;j=1,2,,V

    yjc 表示第 c 个输出中,词汇表 V 中第 j 个单词 wordj 为真实输出单词的概率。

  3. 因为 W 在多个单元之间共享,所以对于网络每个输出,其得分的分布 uc=(u1c,u2c,,uVc)T 是相同的。但是这并不意味着网络的每个输出都是同一个单词。

    并不是网络每个输出中,得分最高的单词为预测单词。因为每个输出中,概率分布都相同,即: y1=y2==yCSkip-Gram 网络的目标是:网络的多个输出之间的联合概率最大

  4. 假设输入为单词 wordI ,输出单词序列为 wordO1,wordO2,,wordOC 。定义损失函数为:

    (38)E=logp(wordO1,wordO2,,wordOCwordI)=logc=1Cexp(ujcc)j=1Vexp(ujc)

    其中 j1,j2,,jC 为输出单词序列对应于词典 V 中的下标序列。

    由于网络每个输出的得分的分布都相同,令 uj=ujc=wjh,则上式化简为:

    (39)E=c=1Cujcc+Clogj=1Vexp(uj)

    .

3.2.2 参数更新

  1. 定义 tjc=I(jc=jc) ,即网络第 c 个输出的第 j 个分量对应于第 c 个真实的输出单词 wordjc 时,它为 1;否则为0。

    定义:

    (40)ejc=Eujc=yjctjc

    它刻画了网络第 c 个输出的第 j 个分量的误差:

    • jc=jc 时: ejc=yjc1,它刻画了输出概率 yjc 与真实概率 1 之间的差距。小于 0 表示预测不足。

    • jcjc 时:ejc=yjc,它刻画了输出概率 yjc 与真实概率 0 之间的差距。大于 0 表示预测过量。

  2. 根据:uj=wjhujwj=h ,则有:

    (41)Ewj=c=1CEujc×ujcwj=c=1Cejch

    定义 EIj=c=1Cejc ,它为网络每个输出的第 j 个分量的误差之和。于是有:

    (42)Ewj=EIj×h

    则有更新方程:

    (43)wj(new)=wj(old)η×EIj×h,j=1,2,,V
  3. 定义:

    (44)EH=Eh=c=1C(uch)TEuc

    根据:

    (45)uc=WTh(uch)T=W

    则有:

    (46)EH=c=1CWec=j=1VEIjwj

    EH 的物理意义为:词汇表 V 中所有单词的输出向量的加权和,其权重为 EIj

  4. 考虑到 h=WTx ,则有:

    (47)Ewk,i=Ehi×hiwk,i=EHi×xk

    写成矩阵的形式为:EW=xEH ,其中 为克罗内克积。

    由于 xone-hote 编码,所以它只有一个分量非零,因此 EW 只有一行非零,且该非零行就等于 EH 。因此得到更新方程:

    (48)wI(new)=wI(old)ηEH

    其中 wIx 非零分量对应的 W 中的行,而 W 的其它行在本次更新中都保持不变。

3.3 优化

  1. 原始的CBOW 模型和Skip-Gram 模型的计算量太大,非常难以计算。

    • 模型在计算网络输出的时候,需要计算误差 。对于CBOW 模型,需要计算 V 个误差(词汇表的大小),对于 Skip-Gram 模型,需要计算 C×V 个误差。

      另外,每个误差的计算需要用到 softmax 函数,该 softmax 函数涉及到 O(V) 复杂度的运算: j=1Vexp(uj)

    • 每次梯度更新都需要计算网络输出。

    如果词汇表有 100万 单词,模型迭代 100 次,则计算量超过 1 亿次。

  2. 虽然输入向量的维度也很高,但是由于输入向量只有一位为 1,其它位均为 0,因此输入的总体计算复杂度较小。

  3. word2vec 优化的主要思想是:限制输出单元的数量。

    事实上在上百万的输出单元中,仅有少量的输出单元对于参数更新比较重要,大部分的输出单元对于参数更新没有贡献。

  4. 有两种优化策略:

    • 通过分层 softmax 来高效计算 softmax 函数。

    • 通过负采样来缩减输出单元的数量。

3.3.1 分层 softmax

  1. 分层 softmax 是一种高效计算 softmax 函数的算法。

    经过分层 softmax 之后,计算 softmax 函数的算法复杂度从 O(V) 降低到 O(logV) ,但是仍然要计算 V1 个内部节点的向量表达 。

a) 网络结构
  1. 在分层softmax 中,字典 V 中的 V 个单词被组织成二叉树。

    • 叶子结点值为某个具体单词的概率(如下图中的白色结点)

    • 中间节点值也代表一个概率(如下图中的灰色结点)。它的值等于直系子节点的值之和,也等于后继的叶子结点值之和,也等于从根节点到当前节点的路径的权重的乘积。

      之所以有这些性质,是由于结点值、权重都是概率,满足和为1的性质

    • 根据定义,根节点的值等于所有叶子结点的值之和,即为 1.0

    • 二叉树的每条边代表分裂:

      • 向左的边:表示选择左子节点,边的权重为选择左子节点的概率

      • 向右的边:表示选择右子节点,边的权重为选择右子节点的概率

  2. 对于任意一个中间节点 t, 假设其向量表达为 vt ,它是待求的参数。

    • 选择左子节点的概率为:

      (49)p(t,left)=σ(vth)σ(x)=11+ex,σ(x)=1σ(x)
    • 选择右子节点的概率为 :

      (50)p(t,right)=1σ(vth)=σ(vth)
    • 如果求得所有中间节点的向量表达,则根据每个中间节点的分裂概率,可以很容易的求得每个叶节点的值。

  3. 在分层softmax 中,算法并不直接求解输出向量 {w1,w2,,wV},而是求解二叉树的 V1 个中间节点的向量表达 。

    当需要计算某个单词的概率时,只需要记录从根节点到该单词叶子结点的路径。给定单词 w

    • 定义 n(w,j) 为从根节点到单词 w 的路径的第 j 个节点(从 1 计数)。

    • 定义 L(w) 为从根节点到单词 w 的路径的长度。

    • 定义 ch(t) 表示节点 t 的左子节点。

    输出为单词 w 的概率为:

    (51)p(w)=j=1L(w)1σ(g(n(w,j+1)=ch(n(w,j)))×vn(w,j)h)

    其中:

    • n(w,j+1)=ch(n(w,j)) 表示:从根节点到单词 w 的路径上,第 j+1 个节点是第 j 个节点的左子节点。

    • g(x) 是一个函数。当 x 是个事实时,其值为 1;当 x 不成立时,其值为 -1。

      (52)g(x)={1,if x is true1,if x is false
    • g(n(w,j+1)=ch(n(w,j))) 表示:从根节点到单词 w 的路径上:

      • 当第 j+1 个节点是第 j 个节点的左子节点时,函数值为 1

      • 当第 j+1 个节点是第 j 个节点的右子节点时,函数值为 -1

    • vn(w,j) 表示:从根节点到单词 w 的路径上,第 j 个节点的向量表达

    • 对于从根节点到单词 w 的路径上,从第 j 个节点到第 j+1 个节点的概率为:

      (53)p(j,j+1)={σ(vn(w,j)h), if j+1 is left child of jσ(vn(w,j)h), if j+1 is right child of j

      因此 p(w) 刻画了:从根节点到单词 w 的路径上,每条边的权重(也就是分裂概率)的乘积。

  4. 对于所有的叶子节点,有 i=1Vp(wi)=1

    利用数学归纳法,可以证明:左子节点的值+右子节点的值=父节点的值。上式最终证明等于根节点的值,也就是 1.0 。

b) 参数更新
  1. 为了便于讨论,这里使用CBOW一个单词上下文模型。

    g(n(w,j+1)=ch(n(w,j)))gn(w,j), 定义损失函数对数似然:

    (54)E=logp(wx)=j=1L(w)1logσ(gn(w,j)vn(w,j)h)

    则有:

    (55)E(vn(w,j)h)=(σ(gn(w,j)vn(w,j)h)1)gn(w,j)={σ(vn(w,j)h)1ifgn(w,j)=1σ(vn(w,j)h)ifgn(w,j)=1=σ(vn(w,j)h)tn(w,j)

    其中:

    (56)tn(w,j)={1,if node j+1 at path , root w , is left child of node j0,if node j+1 at path , root w , is right child of node j

    定义:

    (57)en(w,j)=E(vn(w,j)h)=σ(vn(w,j)h)tn(w,j)
    • σ(vn(w,j)h) 为预测选择 j 的左子节点的概率。

    • en(w,j) 的物理意义为:从根节点到单词 w 的路径上,第 j 个节点的选择误差:

      • 如果下一个节点选择第 j 个节点的左子节点,则 tn(w,j)=1, 此时 en(w,j) 表示预测的不足。

      • 如果下一个节点选择第 j 个节点的右子节点,则 tn(w,j)=0, 此时 en(w,j) 表示预测的过量。

  2. 考虑内部节点 n(w,j),其向量表达为 vn(w,j)。则有:

    (58)Evn(w,j)=E(vn(w,j)h)×(vn(w,j)h)vn(w,j)=en(w,j)×h

    得到向量表达为 vn(w,j) 的更新方程:

    (59)vn(w,j)(new)=vn(w,j)(old)η×en(w,j)×h;j=1,2,,L(w)1
    • 对于每个单词 w ,由于它是叶节点,因此可以更新 L(w)1 个内部节点的向量表达。

    • 当模型的预测概率较准确,即 σ(vn(w,j)h)tn(w,j) 时,则 en(w,j) 接近0 。此时梯度非常小,vn(w,j) 的更新幅度也会非常小。

      当模型的预测概率较不准,则 en(w,j) 较大。此时梯度会较大,vn(w,j) 的更新幅度也会较大。

  3. 对于内部结点的向量表达 vn(w,j) 的更新方程适用于 CBOW 模型和 Skip-Gram 模型。但是在 Skip-Gram 模型中,需要对 C 个输出的每一个单词进行更新。

  4. CBOW 输入参数更新:对于 CBOW 模型,定义:

    (60)EH=Eh=j=1L(w)1E(vn(w,j)h)×(vn(w,j)h)h=j=1L(w)1en(w,j)vn(w,j)

    EH 的物理意义为:二叉树中所有内部节点向量表达的加权和,其权重为 en(w,j)

    考虑到 h=1CWT(x1+x2++xC) ,则有:

    (61)Ewk,i=Ehi×hiwk,i=1CEHi×(x(1,k)+x(2,k)+,+x(C,k))

    写成矩阵的形式为:EW=1Cc=1CxcEH ,其中 为克罗内克积。

    W 的更新分解为 C 次,每次对应于一个输入 xc 。因此得到 W 的更新方程:

    (62)wIi(new)=wIi(old)1CηEH,i=1,2,,C

    其中Ii 为第 i 个输入单词在词表 V 中的编号。

  5. Skip-Gram 输入参数更新:对于 Skip-Gram 模型,定义:

    (63)EH=Eh=c=1Cj=1L(wc)1E(vn(wc,j)h)×(vn(wc,j)h)h=c=1Cj=1L(wc)1en(wc,j)×vn(wc,j)

    其中:wc 表示网络第 c 个输出的输出单词。

    注意:由于引入分层softmax,导致更新路径因为输出单词的不同而不同。因此 j=1L(wc)1 会因为 c 的不同而不同。

    Skip-Gram 中推导相同, W 的更新方程为:

    (64)wI(new)=wI(old)ηEH

    其中 wIx 非零分量对应的 W 中的行,而 W 的其它行在本次更新中都保持不变。

3.3.2 负采样

a) 原理
  1. 在网络的输出层,真实的输出单词对应的输出单元作为正向单元,其它所有单词对应的输出单元为负向单元。

    • 正向单元的数量为 1,毋庸置疑,正向单元必须输出。

    • 负向单元的数量为 V1,其中 V 为词表的大小,通常为上万甚至百万级别。如果计算所有负向单元的输出概率,则计算量非常庞大。

      可以从所有负向单元中随机采样一批负向单元,仅仅利用这批负向单元来更新。这称作负采样。

  2. 负采样的核心思想是:利用负采样后的输出分布来模拟真实的输出分布。

    对于真实的输出分布,有:

    (65)yj=p(wordjx)=exp(uj)j=1Vexp(uj),j=1,2,,V

    对于负采样后的输出分布,假设真实输出单词 wO 对应于输出单元 j ,负采样的 K 个单词对应的输出单元 Wneg={jneg1,,jnegK},则有:

    (66)y^j=p^(wordjx)={exp(uj)j{j,jneg1,,jnegK}exp(uj),j{j,jneg1,,jnegK}0,j{j,jneg1,,jnegK}
    • 在参数的每一轮更新中,负采样实际上只需要用到一部分单词的输出概率。

    • 对于未被采样到的负向单元 j,其输出单元的预测误差 ej=0, 则 wj 不会被更新。

    • EH=We=j=1Vejwj 中仅有负采样的单元 jneg1,,jnegK 起作用,因此 wI(new) 的更新仅仅依赖于正向单元和负采样的单元。

    • 随着训练的推进,概率分布 {y1,y2,,yV} 逐渐接近于真实的分布 {0,,0,1,0,,0} (第 j 位为 1),其绝大部分概率接近 0 、 yj 接近 1 。

      而概率分布 {y^1,,y^V} 也有类似的性质,因此用概率分布 {y^1,,y^V} 去模拟概率分布 {y1,y2,,yV} 效果较好。

  3. 负采样时,每个负向单元是保留还是丢弃是随机的。负向单元采样的概率分布称作noise 分布,记做 Pn(w)

    Pn(w) 可以为任意的概率分布(通常需要根据经验来选择)。谷歌给出的建议是挑选 5~10 个负向单元,根据下面公式来采样:

    (67)Pn(w)=freq(w)3/4wjfreq(w)3/4

    其中:freq(w) 为单词在语料库中出现的概率,分母仅考虑负向单元(不考虑正向单元)。

    Pn(w) 的物理意义为:单词在语料库中出现的概率越大,则越可能被挑中。

b) 参数更新
  1. 假设输出的单词分类两类:

    • 正类:只有一个,即真实的输出单词 wO

    • 负类:从 Pn(w) 采样得到的 K 个单词 Wneg={jneg1,,jnegK}

    论文word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method 的作者指出:下面的训练目标能够得到更好的结果:

    (68)E=logσ(wwOh)jWneglogσ(wjh)

    其中:

    • wwO 为真实的输出单词对应的输出向量,wj 为负采样的单词得到的输出向量。

    • σ(wwOh) :在单词 wO 上输出为正类的概率;σ(wjh) :在单词 j 上输出为负类的概率。

    该目标函数是一个经验公式,而不是采用理论上的交叉熵 logexp(wwOh)j=1Vexp(wjh) 。其物理意义为:在正类单词上取正类的概率尽可能大,在负类单词上取负类的概率尽可能大。

    它是从另一个角度考虑:输出为正向单元的概率 * 输出为负向单元的概率。

    (69)σ(wwOh)jwOσ(wjh)

    其负的对数似然为:

    (70)log(σ(wwOh)jwOσ(wjh))=logσ(wwOh)jwOlogσ(wjh)

    仅仅考虑负采样,则可得到:E=logσ(wwOh)jWneglogσ(wjh)

  2. 根据 E 的定义,有:

    (71)E(wjh)={σ(wjh)1,ifj=wOσ(wjh),ifjWneg=σ(wjh)tj

    其中 tj 标记了单词 j 的标签:

    (72)tj={1,if j=wO0,esle
  3. ej=σ(wjh)tj ,它刻画了网络在正类单词和负类单词上的预测误差。

    • j=wO 时,ej 表示对正类单词预测概率的不足。

    • jWneg 时,ej 表示对负类单词预测概率的过量。

    根据:

    (73)Ewj=E(wjh)×(wjh)wwj=ej×h

    则有输出向量的更新方程:

    (74)wj(new)=wj(old)η×ej×h
  4. 给定一个样本,在更新输出向量时,只有 K+1 个输出向量( 1 个输出单词 wOK 个负采样单词对应的输出向量)得到更新,其中 K 通常数量很小。其它所有单词对应的输出向量未能得到更新。

    相比较而言:

    • 原始算法中,给定一个样本在更新输出向量时,所有输出向量(一共 V 个)都得到更新

    • 分层softmax 算法中,给定一个样本在更新输出向量时,L(w)1 个内部节点的向量表达得到更新。

  5. 输出向量的更新方程可以用于CBOW 模型和 Skip-Gram 模型。

    若用于Skip-Gram 模型,则对每个输出依次执行输出向量的更新。

  6. CBOW 输入向量参数更新:对于 CBOW 模型,定义:

    (75)EH=Eh=j{wO}WnegE(wjh)×(wjh)h=j{wO}Wnegej×wj

    EH 的物理意义为:负采样单词、输出单词对应输出向量的加权和,其权重为 ej

    分层softmax: CBOW 输入向量参数更新 中的推导相同, W 的更新方程为:

    (76)wIi(new)=wIi(old)1CηEH,i=1,2,,C

    其中Ii 为第 i 个输入单词在词表 V 中的编号。

  7. Skip-Gram 输入向量参数更新:对于 Skip-Gram 模型,定义:

    (77)EH=Eh=c=1Cj{wOc}WnegcE(wjh)×(wjh)h=c=1Cj{wOc}Wnegcej×wj

    其中:wOc 表示网络第 c 个输出的输出单词,Wnegc 表示网络第 c 个输出的负采样单词集。

    注意:由于引入负采样,导致网络每个输出中,对应的输出单词有所不同,负采样单词也有所不同。因此 {wOc}Wnegc 会因为 c 的不同而不同。

    Skip-Gram 中推导相同, W 的更新方程为:

    (78)wI(new)=wI(old)ηEH

    其中 wIx 非零分量对应的 W 中的行,而 W 的其它行在本次更新中都保持不变。

3.3.3 降采样

  1. 对于一些常见单词,比如 the,我们可以在语料库中随机删除它。这有两个原因(假设使用 CBOW ):

    • the 出现在上下文时,该单词并不会为目标词提供多少语义上的信息。

    • the 作为目标词时,该单词从语义上本身并没有多大意义,因此没必要频繁更新。

    降采样过程中,单词 w 被保留的概率为:

    Error: '_' allowed only in math mode

    其中 z(w) 为单词 w 在语料库中出现的概率,Error: '_' allowed only in math mode 为降采样率(默认为 0.001)。

    可以看到:随着单词在语料库中出现的词频越来越大,该单词保留的概率越来越低。

3.4 subword embedding

  1. 论文 《Enriching Word Vectors with Subword Information》 中,作者提出通过增加字符级信息来训练词向量。

    下图给出了该方法在维基百科上训练的词向量在相似度计算任务上的表现(由人工评估模型召回的结果)。sisg-sisg 模型均采用了 subword embedding,区别是:对于未登录词,sisg- 采用零向量来填充,而 sisg 采用 character n-gram embedding 来填充。

  2. 单词拆分:每个单词表示为一组 character n-gram 字符(不考虑顺序),以单词 wheren=3 为例:

    • 首先增加特殊的边界字符 < (单词的左边界)和 > (单词的右边界)。

    • 然后拆分出一组 character n-gram 字符:<wh, whe,her,ere,re>

    • 最后增加单词本身:<where>

    为了尽可能得到多样性的 character n-gram 字符,作者抽取了所有 3<= n <= 6character n-gram 。以单词 mistake 为例:

    注意:这里的 take<take> 不同。前者是某个character n-gram,后者是一个单词。

  3. 一旦拆分出单词,则:

    • 词典 V 扩充为包含所有单词和 N-gram 字符。

    • 网络输入包含单词本身以及该单词的所有 character n-gram ,网络输出仍然保持为单词本身。

    模型采用 word2vec ,训练得到每个character n-gram embedding 。最终单词的词向量是其所有 character n-gram embedding包括其本身 embedding 的和(或者均值)。

    如:单词 where 的词向量来自于下面embedding 之和:

    • 单词 <where> 本身的词向量。

    • 一组 character n-gram 字符 <wh, whe,her,ere,re> 的词向量。

  4. 利用字符级信息训练词向量有两个优势:

    • 有利于低频词的训练。

      低频词因为词频较低,所以训练不充分。但是低频词包含的 character n-gram 可能包含某些特殊含义并且得到了充分的训练,因此有助于提升低频词的词向量的表达能力。

    • 有利于获取 OOV 单词(未登录词:不在词汇表中的单词)的词向量。

      对于不在词汇表中的单词,可以利用其 character n-gramembedding 来获取词向量。

3.5 应用

  1. 模型、语料库、超参数这三个方面都会影响词向量的训练,其中语料库对训练结果的好坏影响最大。

    根据论文 How to Generate a Good Word Embedding? ,作者给出以下建议:

    • 模型选择:所有的词向量都是基于分布式分布假说:拥有相似上下文的单词,其词义相似。根据目标词和上下文的关系,模型可以分为两类:

      • 通过上下文来预测目标词。这类模型更能够捕获单词之间的可替代关系。

      • 通过目标词来预测上下文。

      通过实验发现:简单的模型(Skip-Gram) 在小语料库下表现较好。复杂的模型在大语料库下略有优势。

    • 语料库:实际上语料库并不是越大越好,语料库的领域更重要。

      • 选择了合适的领域,可能只需要 1/10 甚至 1/100 的语料就能够得到一个大的、泛领域语料库的效果。

      • 如果选择不合适的领域,甚至会导致负面效果,比随机词向量效果还差。

    • 超参数:

      • 词向量的维度:

        • 做词向量语义分析任务时,一般维度越大,效果越好。

        • 做具体NLP 任务时(用作输入特征、或者网络初始化),50 维之后效果提升就比较少了。

      • 迭代次数:由于训练词向量的目标是尽可能精确地预测目标词,这个优化目标和实际任务并不一致。因此最好的做法是:直接用实际任务的验证集来挑选迭代次数。

        如果实际任务非常耗时,则可以随机挑选某个简单任务(如:情感分类)及其验证集来挑选迭代次数。

  2. word2vec 还有一些重要的超参数:

    • 窗口大小:该超参数通常和语料库中句子长度有关,可以统计句子长度分布来设置。

    • min-count:最小词频训练阈值,词频低于该阈值的词被过滤。

    • 降采样率 subsampling_rate:降采样率越低,高频词保留的越少低频词保留的越多。

  3. word2vec 结果评估:

    • 通过 kmeans 聚类,查看聚类的簇分布。

    • 通过词向量计算单词之间的相似度,查看相似词。

    • 通过类比来查看类比词:a 之于 b,等价于 c 之于 d

    • 使用 tsne 降维可视化查看词的分布。

  4. word2vec 中实际上存在两种类型的embedding 向量:WRV×N 的第 jwjT 称作单词 wordj 的输入向量, WRN×V 的第 jwj 称作单词 wordj 的输出向量。

    大多数论文中都采用输入向量 wj 作为单词 wordj 的表达,而论文 Using the Output Embedding to Improve Language Models 综合了输入向量和输出向量。在该论文中,作者得出结论:

    • skip-gram 模型中,在常见的衡量词向量的指标上,输出向量略微弱于输入向量。

    • 在基于 RNN 的语言模型中,输出向量反而强于输入向量。

    • 通过强制要求 WT=W,这可以使得输入向量等于输出向量。这种方式得到的词向量能够提升语言模型的困惑度perplexity

  5. word2vec 可以用于计算句子相似度。博客 Comparing Sentence Similarity Methods 总结了 6 种计算句子相似度的方法:

    • 无监督方法:

      • 对句子中所有的词的词向量求平均,获得sentence embedding

      • 对句子中所有的词的词向量加权平均,每个词的权重为 tf-idf ,获得sentence embedding

      • 对句子中所有的词的词向量加权平均,每个词的权重为 smooth inverse frequency:SIF ;然后考虑所有的句子,并执行主成分分析;最后对每个句子的词向量加权平均减去first principal componet,获得sentence embedding

        SIF 定义为: aa+p(w),其中 a 是一个超参数(通常取值为 0.001), p(w) 为数据集中单词 w 的词频。

      • 通过 Word Mover's Distance:WMD ,直接度量句子之间的相似度。

        WMD 使用两个句子中单词的词向量来衡量一个句子中的单词需要在语义空间中移动到另一个句子中的单词的最小距离。

    • 有监督方法:

      • 通过分类任务来训练一个文本分类器,取最后一个 hidden layer 的输出作为 sentence embedding

        其实这就是使用文本分类器的前几层作为 encoder

      • 直接训练一对句子的相似性,其优点是可以直接得到 sentence embeding

    最终结论是:简单加权的词向量平均已经可以作为一个较好的 baseline

3.6 SGNS vs 矩阵分解

  1. 论文 《NeuralWord Embedding as Implicit Matrix Factorization》 证明了带负采样的 SkipGram 模型 skip-gram with negative-sampling:SGNS 等价于隐式的矩阵分解。

  2. 给定语料库 C={w1,w2,,wN},wiV 。对于单词 wi,将其右侧两侧距离为 L 范围内单词 cjNwi={wiL,,wi1,wi+1,,wi+L} 作为上下文。定义:

    • 定义 D={(wi,cj)wiC,cjNwi} 为所有观察到的 word-context 组合。

    • 定义 VC={cjwiC,cjNwi} 为所有 context 单词的词汇表,通常有 VC=V

    • 定义 n(w,c) 为给定 word-context 组合在 D 中出现的次数,n(w) 为单词 wVD 中出现的次数, n(c) 为上下文 cVCD 中出现的次数。

      其中:

      (79)n(w)=cVcn(w,c),n(c)=wVn(w,c)|D|=wV,cVcn(w,c)=wVn(w)=cVcn(c)
    • 定义单词 wordi 作为current wordembedding 向量为 wiRd,作为contextembedding 向量为 wiRd

      定义单词的 representation 矩阵为 WRV×d,其每一行代表词汇表 V 中每个单词的embeddign 向量。

      定义上下文的 representation 矩阵为 WR|VC|×d,其每一行代表词汇表 VC 中每个单词作为上下文时的embeddign 向量。

    给定一对 word-context (w,c) ,假设单词 w 作为 current wordembeddingww ,上下文 c 作为contextembeddingwc 。定义 (w,c) 被观察到(即 postive )的概率为:

    (80)p(D=1w,c)=σ(wwwc)=11+exp(wwwc)

    其中 ww,wc 为模型需要学习的参数。

    SGNS 最大化观察到的 word-context 组合、最小化未观察到的 word-context 组合。由于 D 中所有的 word-context 组合都是观察到的,属于postive 样本,因此SGNS 需要通过随机采样一些 word-context 作为负样本。这就是负采样名称的由来。

    • 理论而言只有随机采样的、未观察到的 word-context 才能作为负样本。这里直接使用随机采样的结果作为负样本有两个原因:

      • 便于理论上推导。但是二者并不影响 SGNS 等价于矩阵分解的性质。

      • 由于 V×VC 的空间巨大,观察到的 word-context 集合仅仅占据很小的部分,因此采样得到的 word-context 组合是未观察到的概率几乎为 1

    • 理论而言未观察到的 word-context 组合不一定是负样本,某些word-context 组合是合理的,只是它们从未在语料库中出现过。

    对于每一对观察到的 word-context 组合 (w,c)SGNS 的损失函数为:

    (81)l(w,c)=logσ(wwwc)+k×EcNPD[logσ(wwwcN)]

    其中 k 为负采样的数量,cN 为给定 current word w 进行负采样的上下文。PD 为负采样中上下文的分布,有两种常见的分布:

    • 非均匀分布:

      (82)pD(c)=n(c)3/4cVCn(c)3/4

      这和前面介绍的一致。

    • 均匀分布:

      (83)pD(c)=n(c)|D|

      虽然非均匀分布在某些任务上能够产生更好的结果,但是这里采用均匀分布从而得到更好的理论推导。另外,二者并不影响 SGNS 等价于矩阵分解的性质。

    最终得到 SGNS 总的损失函数为:

    (84)L=(w,c)Dl(w,c)=wVcVCn(w,c)(logσ(wwwc)+k×EcNPD[logσ(wwwcN)])
  3. SGNS 的优化目标使得:

    • 观察到的 word-context (w,c) 具有相似的 embedding,即 p(D=1w,c)=logσ(wwwc) 较大。

    • 未观察到的 word-context (w,cN) 具有不相似的 embedding,即 p(D=1w,cN)=logσ(wwwcN) 较小。

  4. PD 采用均匀分布时有:

    (85)EcNPD[logσ(wwwcN)]=cNVCn(cN)|D|logσ(wwwcN)

    因此有:

    (86)L=(w,c)Dl(w,c)=wVcVCn(w,c)(logσ(wwwc))+wVn(w)(k×EcNPD[logσ(wwwcN)])=wVcVCn(w,c)(logσ(wwwc))+wVcNVCn(w)(k×n(cN)|D|logσ(wwwcN))=wVcVC(n(w,c)logσ(wwwc)+k×n(w)n(c)|D|logσ(wwwc))

    因此样本空间 V×VC 中每一对 word-context 组合 (w,c) 的损失为:

    (87)L(w,c)=n(w,c)logσ(wwwc)+k×n(w)n(c)|D|logσ(wwwc)

    由于样本空间 V×VC 中的组合 (w,c) 之间是相互独立的,因此当每一对组合 (w,c)L(w,c) 最小时 L 最小。定义 e=wwwc,根据:

    (88)L(w,c)e=0

    解得:

    (89)e=wwwc=log(n(w,c)×|D|n(w)×n(c))logk
  5. 给定随机变量 X,YPointwise Mutual Information :PMI 定义为

    (90)PMI(X,Y)=logP(X,Y)P(X)×P(Y)

    记单词 w 出现在 D 中的概率为 P(w)=n(w)|D|,记上下文 c 出现在 D 中的概率为 P(c)=n(c)|D|,记 word-context 组合 (w,c) 出现在 D 中的概率为 P(w,c)=n(w,c)|D| 。则有:

    (91)log(n(w,c)×|D|n(w)×n(c))=PMI(w,c)
  6. 定义矩阵 M 为:

    (92)Mi,j=PMI(w=wordi,c=wordj)logk=log(n(w=wordi,c=wordj)×|D|n(w=wordi)×n(c=wordj))logk

    则有:

    (93)M=W(W)T
    • 这里的推导只有当维度 d 足够大时成立,因为如果 d 太小,则 WW 容量太小表达能力太弱,无法完美的重建矩阵 M

      设矩阵 M 的秩为 rM,则维度 d 应该满足 drM 。如果 d<rM,则右侧 W(W)T 的秩 rd<rM,这种分解难以成立。

    • 当负采样个数 k=1Mi,j=PMI(w=wordi,c=wordj) ,此时 SGNS 等价于分解 PMI 矩阵。

  7. 直接计算 PMI 矩阵非常具有挑战性:

    • 矩阵的维度 |V|×|VC| 非常高。

    • 绝大多数组合 (w,c)V×VC 从未出现语料库中从而导致 PMI(w,c)=log0=

      这可以通过引入一些先验概率使得未见过的 (w,c)PMI 为一个有效的数来解决。

    • PMI 矩阵是 dense 矩阵。

    一个解决方案是:当 n(w,c)=0 时令 PMI(w,c)=0,这使得 PMI 矩阵成为一个巨大的稀疏矩阵,称作 M0

    事实上当 P(w),P(c) 都很高、但是 P(w,c) 很低时,这表明 wc 分别单独出现的次数跟高,但是一起出现的次数很低。因此可以认为:

    • P(w,c)>P(w)×p(c)PMI(w,c)>0 ,表明观察到的 word-context (w,c) 是相关的。

    • P(w,c)P(w)×p(c)PMI(w,c)0,表明观察到的 word-context (w,c) 是不相关的。

    考虑到未观察到的 word-context (w,c)PMI(w,c)=0 ,因此可以将所有不相关 word-contextPMI 都设置为零,仅考虑正的PMI (即 PPMI):

    (94)PPMI(w,c)=max(PMI(w,c),0)

    这和人类的直觉相符:人们很容易联想到正的关联,如 “加拿大”“滑雪” ,但是很难关注一些无关的组合,如“加拿大”“沙漠” 。因此将无效的信息丢弃(PMI 置为零)而仅保留有效信息更符合经验和直觉。

  8. 如果继续在 PPMI 中考虑偏移,则得到 Shifted PPMI:SPPMI

    (95)SPPMIk(w,c)=max(PMI(w,c)logk,0)
  9. 可以直接将PMI 矩阵、PPMI 矩阵 或者 SPPMI 矩阵中,单词 w 对应的行作为其 representation,此时单词的 representatioin 是一个高维向量。对于 PPMI,SPPMI,该向量还是稀疏的。此时有: W=M,W=I

    也可以通过降维获得单词的低维representatiion,如:可以通过 SVD 分解来求解 WW

    首先将 M 进行 SVD 分解:

(96)M=UΣVT

其中 U,V 均为正交矩阵,Σ 为所有奇异值从大到小排列的对角矩阵。

选择最大的 d 个奇异值组成对角矩阵 ΣdU 的前 d 列组成矩阵 UdV 的前 d 列组成矩阵 Vd ,则有:

(97)MMd=UdΣd(Vd)T

可以选择 W=UdΣd,W=Vd 。但是实际应用中发现该方法求解的 W 要比 SGNS 效果较差。注意到这种分解方法中,W 是正交矩阵而 W 不是正交矩阵,这表明 WW 的性质不对称。而在 SGNS 中,求解的这两个矩阵都不是正交矩阵,因此可以进行如下分解:

(98)W=UdΣd,W=VdΣd

虽然理论上无法证明这种方式的效果更好,但是实践中发现它确实表现更佳。

  1. 基于随机梯度下降的 SGNS 和基于矩阵分解的方式各有优点:

    • 基于矩阵分解的优点:

      • 无需精心调优学习率等超参数。

      • 可以按照 word-context 聚合之后的频次数据来训练,这种方式可以训练比 SGNS 大得多得语料库。

        与之相反,SGNS 中每个 word-context 出现一次就需要训练一次。

    • 基于 SGNS 的优点:

      • SGNS 可以区分观测值和未观测值,而 SVD 无法判断一个 word-context 为零是因为未观测还是因为 PMI 较低。这在 word-context 矩阵中非常常见。

      • SGNS 的目标函数对不同的 (w,c) 进行加权:越频繁出现的 (w,c) 权重越高,误差越低;越稀疏出现的 (w,c) 权重越低,因此允许其误差较大。

        SVD 分解中,无法区分 (w,c) 的重要性,对所有的 (w,c) 给与相同的权重,因此也无法使得权重较大的 (w,c) 的误差更低。

      • SGNS 仅仅关注于观测值,因此它不要求底层的矩阵是稀疏的,可以直接优化 dense 矩阵。

        因为 SVD 的求解困难,所以SVD 通常要求底层矩阵是稀疏的,因此它通常采用 PPMI/SPPMI

  2. noise-contrastive estimation:NCE 采用类似的推导过程可以分解为:

    (99)Mi,j=logP(w=wordic=wordj)logk=log(n(w=wordi,c=wordj)n(c=wordj))logk
  3. 实验:

    • 数据集:英文维基百科。经过清理非文本字符、句子拆分、词干化之后,数据集包含 7750万句子、15亿 token

      • 每个token 分别取左右两侧2token 作为上下文从而生成 word-context 集合 D

      • 过滤掉 D 中频次低于 100次的 word-context 组合。

      最终得到 VVC 包含 189533 个单词。

    • 模型:SPPMISGNS 以及 SVD 。其中:

      • 所有模型评估当 k=1,5,15 的结果

      • 对于 SPPMI,将该矩阵的各行作为对应单词的 representation

      • 对于 SVD 采用分解 W=UdΣd,W=VdΣd

    • 我们根据训练目标函数和理论目标函数来评估各算法的优化算法效果。

      考虑目标函数:

      (100)L=wVcVCn(w,c)(logσ(wwwc)+k×EcNPD[logσ(wwwcN)])
      • 对于 SGNS 我们直接通过随机梯度下降结束时的目标函数值作为 L^

      • 对于 SVD 我们根据 Mw,c=max(PMI(w,c)logk,0) 填充 M ,然后根据矩阵分解的结果计算 L 得到 L^

      • 对于 SPPMI,我们将它的各行作为对应单词的 representatioin,上下文采用 one-hot 向量的形式,因此有:wwwc=max(PMI(w,c)logk,0)

      • 然后根据 wwwc=PMI(w,c)logk 求解目标函数的理论值 LOPT

      然后我们评估优化目标函数值和理论目标函数值的相对误差:

      Error: '_' allowed only in math mode

      结果见下表。其中 PMI-log k 表示理论误差,SPPMI 表示采用 wwwc=max(PMI(w,c)logk,0) 直接计算得到(而不是矩阵分解)的SPPMI 理论值对应的误差。

      • 尽管 SPPMI 仅考虑非负元素而丢弃大量信息,它与最优解的理论值非常接近。

      • SVD 方法中,维度 d 越大效果越好。

      • 对于 k=1 :当 d500SVD 优化效果比 SGNS 更好;但是当维度更高时 SGNS 的优化误差比 SVD 的降低得多得多。

      • SVD 对于 k 值非常敏感,随着 k 值的增加优化误差迅速增长。作者猜测这是由于当 k 越大时 M 中零元素数量也越多,这导致 SVD 的分解结果更接近零矩阵。因为 SVD 的目标函数是无权重的,它无法 “更关注” 那些观测结果。

    • 在四个数据集上评估 word similarity 单词相似任务和单词类比任务。

      • 在数据集 WordSim353MEN 上评估单词相似任务。这些数据集包含人工标注的 pair-wise 单词相似度得分。

      • 在数据集 SyntacticMixed 上评估单词类比任务。

      d=1000 时结果如下图所示:

      • 在单词相似任务上 SVD 超越了SPPMI (采用随机梯度下降),而 SPPMI 超越了 SGNS

      • 在单词相似任务上对于 SGNS 任务 k 越大效果越好,但是对于 SPPMI,SVD 随着 k 的上升性能先上升后下降。

        这是因为SPPMI,SVD 中仅保留正的值,随着 k 越大信息丢失越多。

      • 在单词类比任务上 SGNS 超越了 SVD 。这是因为单词类比任务中更依赖于那些上下文中频繁出现的单词,如the,each,many 以及辅助动词 will,hadSGNS 训练过程会更关注于这些频繁出现的 word-context 组合,而 SVD 对所有的 word-context 是无权重的。

四、GloVe

  1. 学习词向量的所有无监督方法最终都是基于语料库的单词共现统计,因此这些模型之间存在共性。

  2. 词向量学习算法有两个主要的模型族:

    • 基于全局矩阵分解的方法,如:latent semantic analysis:LSA

      • 优点:能够有效的利用全局的统计信息。

      • 缺点:在单词类比任务(如:国王 vs 王后 类比于男人 vs 女人)中表现相对较差。

    • 基于局部上下文窗口的方法,如:word2vec

      • 优点:在单词类比任务中表现较好。

      • 缺点:因为word2vec 在独立的局部上下文窗口上训练,因此难以利用单词的全局统计信息。

  3. Global Vectors for Word Representation:GloVe 结合了LSA 算法和Word2Vec 算法的优点,既考虑了全局统计信息,又利用了局部上下文。

4.1 原理

  1. 单词-单词 共现矩阵为 X ,其中 Xi,j 表示在整个语料库中单词 wordj 在单词 wordi 上下文中出现的次数。 令:

    • Xi=k=1VXi,k ,它表示:单词 wordi 上下文中出现的所有单词的总数。

    • Pi,j=P(wordjwordi)=Xi,jXi ,它表示:单词 wordj 出现在单词 wordi 的上下文中的概率。

    • Ratioi,jk=Pi,kPj,k ,它表示:单词 wordk 出现在单词 wordi 的上下文中的概率,相对于单词 wordk 出现在单词 wordj 的上下文中的概率的比值。

    从经验中可以发现以下规律:

     单词 wordk 和单词 wordi 相关单词 wordk 和单词 wordi 不相关
    单词 wordk 和单词 wordj 相关Ratioi,jk 趋近于 1Ratioi,jk 比较小
    单词 wordk 和单词 wordj 不相关Ratioi,jk 比较大Ratioi,jk 趋近于 1

    因此 Ratioi,jk 能够反映单词之间的相关性。

  2. 假设单词 wordi,wordj,wordk 的词向量分别为 wi,wj,wk

    GloVe 认为:这三个单词的词向量经过某个函数的映射之后等于 Ratioi,jk 。即:词向量中包含了共现矩阵的信息。

    假设这个映射函数为 F ,则有:

    (101)F(wi,wj,wk)=Ratioi,jk=Pi,kPj,k

    现在的问题是 F() 未知,词向量 wi,wj,wk 也是未知。如果能够确定 F() ,则可以求解词向量。

  3. 由于 F() 映射的是向量空间,而向量空间是一个线性空间。因此从右侧的除法 Pi,kPj,k 可以联想到对 wiwj 做减法。即 F() 的形式为:

    (102)F(wiwj,wk)=Pi,kPj,k

    由于 wiwjwk 均为向量,而 Pi,kPj,k 为标量。因此可以联想到向量的内积。即 F() 的形式为:

    (103)F((wiwj)Twk)=F(wiTwkwjTwk)=Pi,kPj,k

    上式左边为差的形式,右边为商的形式。因此联想到函数 exp() 。即 F() 的形式为:

    (104)F()=exp()wiTwkwjTwk=logPi,klogPj,k

    要想使得上式成立,只需要令 wiTwk=logPi,k,wjTwk=logPj,k 即可。

    • 向量的内积具有对称性,即 wiTwk=wkTwi 。而 logXi,kXilogXk,iXk ,即: logPi,klogPk,i

      为了解决这个问题,模型引入两个偏置项:

      (105)logXi,k=wiTwk+bi+b~k
    • 上面的公式仅仅是理想状态,实际上只能要求左右两边尽可能相等。于是设计代价函数为:

      (106)J=i,k(wiTwk+bi+b~klogXi,k)2

      其中 w,b,b~ 均为模型参数。

  4. 根据经验,如果两个词共现的次数越多,则这两个词在代价函数中的影响就应该越大。因此可以设计一个权重来对代价函数中的每一项进行加权,权重为共现次数的函数:

    (107)J=i,kf(Xi,k)(wiTwk+bi+b~klogXi,k)2

    其中权重函数应该符合三个条件:

    • f(0)=0 。即:如果两个词没有共现过,则权重为 0 。

      这是为了确保 limx0f(x)log2x 是有限值。

    • f() 是非递减的。即:两个词共现次数越大,则权重越大。

    • f() 对于较大的 Xi,k 不能取太大的值。即:有些单词共现次数非常大(如单词 与其它词的组合) ,但是它们的重要性并不是很大。

    GloVe 论文给出的权重函数 f() 为:

    (108)f(x)={(xxmax)αifx<xmax1,otherwise

    其中:

    • GloVe 论文给出参数 αxmax 的经验值为:α=34,xmax=100

    • GloVe 论文指出: xmax 对模型的性能影响较小。

  5. 考虑对所有词向量增加一个常量 c,则有:

    (109)(wi+c)T(wk+c)+(bicTwi||c||22)+(b~kcTwk||c||22)logXi,k=wiTwk+bi+b~klogXi,k

    b^i=bicTwi||c||22b~^k=b~kcTwk||c||22,则:如果 w1,w2,,wVGlove 的解,则 w1+c,w2+c,,wV+c 也是Glove 的解。

    因此假设 c 是一个非常大的值,则会导致几乎所有的词向量都相似。

4.2 应用

  1. GloVe 模型的算法复杂度取决于共现矩阵 X 中的非零元素的个数,最坏的情况下为 O(V2) 。由于词汇表的数量通常很庞大,因此 V2 会非常大。

    实际上单词共现的次数满足齐普夫定律(Zipf's Law),因此算法复杂度较低,约为 O(|C|), 其中 C 为语料库的大小。

    Zipf's Law:如果有一个包含 n 个词的文章,将这些词按其出现的频次递减地排序,那么序号 r 和其出现频次 f 之积 f×r,将近似地为一个常数,即 f×r=const

  2. GloVe 模型评估任务:

    • semantic 任务: 语义任务。如:'雅典'之于'希腊' = '柏林'之于'_'?

    • syntactic 任务:语法任务。如:'dance'之于'dancing' = 'fly'之于'_'?

  3. GloVe 模型性能与语料库大小的关系:

    • 在语法任务中,模型性能随着语料库大小的增长而单调增长。

      这是因为语料库越大,则语法的统计结果越可靠。

    • 在语义任务中,模型性能与语料库绝对大小无关,而与语料库的有效大小有关。

      有效大小指的是语料库中,与目标语义相关的内容的大小。

  4. GloVe 模型超参数选择:

    • 词向量大小:词向量大小越大,则模型性能越好。但是词向量超过 200 维时,维度增加的收益是递减的。

    • 窗口对称性:计算一个单词的上下文时,上下文窗口可以是对称的,也可以是非对称的。

      • 对称窗口:既考虑单词左侧的上下文,又考虑单词右侧的上下文。

      • 非对称窗口:只考虑单词左侧的上下文。

        因为语言的阅读习惯是从左到右,所以只考虑左侧的上下文,不考虑右侧的上下文。

    • 窗口大小:

      • 在语法任务中,选择小的、非对称的窗口时,模型性能更好。

        因为语法是局部的,所以小窗口即可;因为语法是依赖于单词顺序的,所以需要非对称窗口。

      • 对于语义任务,则需要选择更大的窗口。

        因为语义是非局部的。

五、FastText

  1. fastTextFacebook AI Research2016 年开源的文本分类器,其提出是在论文 《Bag of Tricks for Efficient Text Classification》 中。目前 fastText 作为文本分类的基准模型。

    fastText 的优点是:在保持分类效果的同时,大大缩短了训练时间。

    • 在 8个 数据集上,不同模型的测试误差:

    • 单个 epoch 的训练时间(char-CNNVDCNNfastText ):

  2. fastText 的网络结构与 word2vecCBOW 非常相似。区别在两个地方:

    • 输入:单篇文档的所有单词都作为网络的输入。因此这里的参数 C 是动态的,它等于当前文档的单词数量。

    • 输出:这里网络的输出是各类别的概率。通常文本分类的类别 K 远小于词典大小 V ,因此可以不必进行分层 softmax 和负采样。

  3. 隐向量为所有输入单词映射结果的均值:

    (110)h=1CWT(x1+x2++xC)=1C(wI1+wI2++wIC)

    其中:Ii 表示第 i 个输入单词在词汇表 V 中的编号,wj 为矩阵 W 的第 j 行,它是对应输入单词的输入向量。

    单个样本的损失函数为(k 为真实类别标签):

    (111)E=uk+logk=1Kexp(uk)=wkh+logk=1Kexp(wkh)

    定义每个输出单元的预测误差 ek=Euk=yktk ,与CBOW 多个单词上下文的推导相同:

    • 更新 W

      (112)wk(new)=wk(old)ηekh,k=1,2,,K

      其中 h=1C(wI1+wI2++wIC)

    • 更新 W

      (113)wIi(new)=wIi(old)1CηEH,i=1,2,,C

      其中 :

      • EH=We=k=1Kekwk ,它是所有类别输出向量的加权和,其权重为 ek

      • Ii 为第 i 个输入单词在词表 V 中的编号。

  4. 如果考虑词序则分类的效果还可以进一步提升,因此在 fastText 中可以引入 N-gram 特征。如:2-gram 合并文档中连续的2个单词作为特征。

  5. fastText 生成的词向量嵌入的是分类的信息,而word2vec 生成的词向量更多的嵌入了通用语义信息。

    • fastText 词向量得到的相似度是基于分类类别的相似。如:商品评论情感分类任务中,好吃好玩 是相似的,因为它们都是正向情感词。

    • word2vec 词向量得到的相似度是基于语义的相似。此时 好吃美味 是相似的,因为这二者经常出现在类似的上下文中。

六、ELMo

  1. ELMo:Embeddings from Language Models 引入了一种新的单词表示方式,该 表示方式的建模目标是:对单词的复杂特征建模(如:语法特征、语义特征),以及能适应不同的上下文(如:多义词)。

    • ELMo 词向量是由双向神经网络语言模型的内部多层向量的线性加权组成。

      • LSTM 高层状态向量捕获了上下文相关的语义信息,可以用于语义消岐等任务。

        如下图中的左图为语义消岐任务的结果,第一层、第二层分别表示单独使用 biLMrepresentation 的效果。结果表明:越高层的状态向量,越能够捕获语义信息。

      • LSTM 底层状态向量捕获了语法信息,可以用于词性标注等任务。

        如下图中的右图为词性标注任务的结果,第一层、第二层分别表示单独使用 biLMrepresentation 的效果。结果表明:越低层的状态向量,越能够捕获语法信息。

    • ELMo 词向量与传统的词向量(如:word2vec )不同。在ELMo 中每个单词的词向量不再是固定的,而是单词所在的句子的函数,由单词所在的上下文决定。因此ELMo 词向量可以解决多义词问题。

      下图中,GloVe 无法区分 play 这个单词的多种含义。而 ELMo 由于引入了上下文,因此可以区分其不同含义。

    • 实验表明,ELMo 在多个任务上取得了广泛的提升。

  2. 给定一个句子 : {wordw1,wordw2,,wordwN},其中 wi{1,2,,V}N 为句子的长度。用 (w1,w2,,wN) 代表该句子, 则生成该句子的概率为:

    (114)p(w1,w2,,wN)=i=1Np(wiw1,w2,,wi1)

    可以用一个 L 层的前向 LSTM 模型来实现该概率。其中:

    • xi 表示输入 wiembedding 向量, hi,j 表示第 jLSTM 层的第 i 个单元的输出隐向量。

    • LLSTM 的输出经过 softmax 输出层输出对应的条件概率。

      • softmax 输出层由一个全连接函数和一个softmax 函数组成。

      • 由于 RNN 的性质,所有softmax 输出层的参数都共享。

  3. ELMo 模型采用双向神经网络语言模型,它由一个前向LSTM 网络和一个逆向 LSTM 网络组成。ELMo 最大化句子的对数前向生成概率和对数逆向生成概率。

    (115)E=i=1N[logp(wiw1,w2,,wi1;Θx,ΘLSTM,Θs)+logp(wiwi+1,ww+2,,wN;Θx,ΘLSTM,Θs)]

    其中:

    • 前向 LSTM 网络和逆向 LSTM 网络共享embedding 层的参数 Θx、共享softmax 输出层的参数 Θs

    • ΘLSTM 为前向 LSTM 网络的参数, ΘLSTM 为逆向 LSTM 网络的参数,二者不同。

    ELMo 认为单词 wi 的表达由 2L+1 个向量组成:Hi={xi,hi,j,hi,jj=1,2,,L} ,是这 2L+1 个向量的函数。

    • 最简单的情况下,ELMo 取出第 L 层(或者其它单层)的输出作为词的表达:ELMOi=hi,L:hi,L 。其中 : 表示向量的拼接。

    • 也可以直接采用这 2L+1 个向量的均值作为单词 wi 的表达。

    • 可以给每层的向量一个权重,而这些权重(一共 2L+1 个)可以从具体任务中学习到。

      此时ELMo 通用的词表达为:这 2L+1 个向量的加权:

      (116)ELMOi=γtaskvkHisktaskvk

      其中 sktask 为对应层的权重的 softmax 归一化结果, k=0,1,2,,2L;而 γtask 是所有层的缩放因子(与层的位置无关,由具体任务决定)。

  4. 应用 ELMo 时,首先训练无监督的 ELMo 模型,获取每个单词的 2L+1 个中间表示。然后在监督学习任务中,训练这 2L+1 个向量的线性组合,方法为:

    • 冻结 ELMo 的模型参数并计算得到 ELMOi

    • 拼接 xitaskELMOi,作为监督学习网络的输入,其中 xitask 是监督学习网络的单词输入 embedding

    • 对于 RNN 网络,还可以将 ELMOi 拼接隐层输出 hitask ,其中 hitask 是监督学习网络的隐向量。

  5. 实验表明:在 ELMo 中添加 dropout 是有增益的。另外在损失函数中添加 L2 正则化能使得训练到的ELMo权重倾向于接近所有ELMo权重的均值。