在文章开端前,我先啰嗦两句。有仔细的同窗可能发明了之前的文章已经更新到了第五讲,那么这篇怎么又是第五讲呢?这是因为在我拖更(划掉)的这段时光里,这门课程更新到了2019版,"> 在文章开端前,我先啰嗦两句。有仔细的同窗可能发明了之前的文章已经更新到了第五讲,那么这篇怎么又是第五讲呢?这是因为在我拖更(划掉)的这段时光里,这门课程更新到了2019版," />

NLPCS224N,CS224N NLP with Deep Learning(五):依存分析

">

在文章开端前,我先啰嗦两句。有仔细的同窗可能发明了之前的文章已经更新到了第五讲,那么这篇怎么又是第五讲呢?这是因为在我拖更(划掉)的这段时光里,这门课程更新到了2019版,课程构造做了一些调剂,因此这篇文章以及之后的文章都会依照2019版的课程内容写作,而之前的文章我会尽快(我也不知道什么时候)更新到与新版一致。

在开端讲依存剖析(Dependency Parsing)之前,我们先来看一个例子。斟酌“Scientists count whales from space”这句话,这句话有着显明的歧义,即可以懂得为“科学家从宇宙中数鲸鱼”,也可懂得为“科学家数来自宇宙的鲸鱼”。在日常生涯中歧义的例子也不胜枚举,发生原因也多种多样。而这句话呈现歧义重要是介词短语(Prepositional Phrase, PP)“from speace”润饰的对象不明导致的。此外还存在同位语范畴不明(coordination scope ambiguity)、形容词润饰对象不明(adjectival modifier ambiguity)、动词短语润饰对象不明(Verb Phrase attachment ambiguity)等多种歧义,课程中举了很多例子,在此就不详细描写了。尽管歧义经常呈现,但是人类可以断定出句子可能表达的多种含义,但让盘算机去懂得就非常艰苦了。这时我们就自然地会想,人是怎么懂得这些句子的呢?盘算机能不能模拟人类去懂得这些句子呢?为了研讨这些问题,我们就须要斟酌语句构造(sentence structure)。

语句构造可以由两种方法对待:

  • 短语构造文法(constituency structure 或 phrase structure grammer):更具体地说,短语构造文法通常指高低文无关文法(context-free grammars, CFGs)。这种方法将句子看作由多个短语的组合,而短语即可由多个单词组成,也可由单词和短语或是多个短语组成。例如冠词(+形容词)+名词构成名词短语(the cat, a barking dog),介词+名词短语可以构成介词短语(in a crate, on the table, by the green door),同时冠词(+形容词)+名词+介词短语又可以构成名词短语(the cat by the door)。这样我们可以写出很多的短语构造,它们也可以递归地形成更长的短语,最终构成语法来描写语言。
  • 依存构造(dependency structure):这种方法采取了一个更简练的视角看问题,即斟酌某个单词依附于哪个单词?例如“Look for the large barking dog by the door in a crate”中的依存构造可以用下图表现
  • 其中“Look”的对象是“dog”,因此可以以为“dog”依附于“Look”;而“large”和“barking”都是形容“dog”的,因此也以为这两个词依附于“dog”,除此之外句子中的介词例如“for”、“the”也存在相应的依存关系。

    高低文无关文法并不善于处置歧义,因此也常用于精心结构、没有歧义的编程语言描写。之后的章节会更详细的讲授高低文无关文法,本章我们先关注依存构造。

    依存构造

    依存句法(dependency syntax)假设语句通常由二元非对称的单词关系(如上文图中所示的箭头)组成,称为依存(dependencies)。依存可以有多种种类,以表现不同的语义关系,例如主语(subject)、介词宾语(prepositional object)、同位语(apposition)等。由于不同的学者有不同偏好,所以在依存剖析发展的进程中,呈现了两种表现依存的方法,一种是由核心词(head, or governor, superior, regent)指向依存词(dependent, or modifier, inferior, subordinate),而另一种则恰恰相反。在本课程中,我们应用第一种方法表现依存,这也是比拟常用的一种方法。一般情形下,依存关系可以形成一颗树(单向、无环),例如

    通常在依存构造中我们还会在句子前面加一个假的根节点(ROOT),用于解决单词没有依存的情形,即单词如果没有依存的话就可以让ROOT作为其核心词。这样就可以使句子中的每个单词至少有一个依存 ,使后续处置更便利。

    依存剖析(Dependency Parsing)就是把句子中的每个词(包含ROOT)分辨作为核心词,寻找其依存词。通常依存剖析有以下条件:

    • 只有一个单词依附于ROOT
    • 依存关系不构成环

    这使得我们得到的依存是树构造。依存剖析还有一个Projectivity的问题,如果一个句子中的所有依存都不呈现交叉,则称其为projective,否则称其为non-projective。如果想让依存与高低文无关文法树对应,则请求依存必需为projective。但是在依存剖析中通常容许交叉的情形呈现,因为如果不斟酌这些non-projective的构造,有时会很难懂得语义。

    存在non-projective的依存构造(from->Who)

    依存关系有一些条件性的特征,这些特征可以作为已知信息辅助依存剖析。具体来说有以下特征:

  • 单词之间亲和,即有些单词之间会更经常呈现依存关系,例如discussion与issue
  • 依存关系通常呈现在距离较近的单词
  • 依存关系通常会有界线,例如依存很少经过动词或标点
  • 核心词有相似原子价(Valency)的特征,即核心词左右的依存数目有一些常见的值
  • 斟酌到以上特征,我们在做依存剖析的时候就可以斟酌一些策略,比如优先斟酌亲和词;优先在核心词邻近寻找依存,并且优先不超出动词、标点等;如果核心词某一侧的依存数目比惯例呈现的少,那么在该侧更远的距离寻找。

    1993年Marcus等人提出构建Treebank,一个依存关系的标注数据集。尽管在当时构建这样一个数据集看起来并没有结构语法有用,但现在看来Treebank给我们带来了很多方便,比如

    • 劳动力的反复应用,许多句法剖析器、句子成分标注器都是基于Treebank树立的
    • 范畴广,并不是只包括一些直觉上存在的依存关系
    • 包括依存关系的频率、散布信息
    • 可用于剖析器等的评估

    现在我们懂得了依存剖析的定义,也有了可以用于依存剖析模型训练和评估的数据集,接下来我们来看看依存剖析常用的方式。

    基于转移的依存剖析器(Transition-based Parser)

    Greedy Transition-based Parsing [Nivre 2003] 是一个基于转移的贪心的依存剖析模型。这里的转移与编译中的shift-reduce parser相似,它也包括shift(入栈)和reduce(归约)操作,即每次将单词入栈,并斟酌是否归约(添加依存关系),但不同的是reduce可以分为向左添加弧(left-arc)和向右添加弧(right-arc)。

    剖析器包括以下几个部分:

    • ,开端只有ROOT
    • 缓存 ,开端时是全部输入句子
    • 依存的聚集 ,开端时为空
    • 动作聚集(shift, left-arc, right-arc)

    我们可以将剖析器的开端状况、三个动作和停止状况情势化地定义为

    我们来看一个具体的例子,如下图所示,如果我们剖析“I ate fish”这句话,开端状况栈(灰色框)中只有root,缓存(黄色框)中则是全部句子。首先我们进行shift操作,将“I”参加栈中,然后再将“ate”参加栈中。

    这时候由于“I”是“ate”的主语,所以我们可以进行reduce操作,向 中参加由“ate”指向“I”的left arc,而栈中只保留核心词也就是“ate”。之后再将“fish”移入栈,此时缓存为空。这时我们发明“fish”是“ate”的宾语,因此可以向 中参加由“ate”指向“fish”的right arc。这时栈中就只剩下“root”和“ate”,只需再参加一个right arc就完成了对这句话的剖析。

    通过这个例子看该算法是非常简略的,但是有一个非常要害的问题,那就是我们人类可以很轻松地看出什么时候该选择什么操作,但是如何让盘算机断定每一步该选择什么操作呢?一个简略的想法就是直接搜索所有可能的动作序列,但这样会有指数级的序列个数,我们无法盘算。60-70年代的研讨者想出了一个更聪慧的方式,即应用动态计划(Dynamic Programming)更高效的求解,不过在此就不详细介绍了。

    MaltParser [Nivre and Hall 2005] 也是基于转移的依存剖析模型。与之前的方式不同的是它将传统的用动态计划来找到下一个动作改为应用机器学习的方式断定下一个动作应当是什么。该模型通过联合1-3个元素的属性结构了数百万的二值(0或1)特点,然后训练一个分类器从三种可能的操作中预测最好的动作。分类器可以选择逻辑回归、softmax分类器、SVM等。

    MaltParser特点结构

    研讨还表明应用该模型的话每次选择分类器断定的最佳动作就可以得到不错的模型,应用beam search等方式并不会带来很大的晋升。

    这种模型虽然表示不及state-of-the-art模型,但是其优势在于应用线性模型可以快速地得到还不错的成果。

    模型评估

    在我们介绍更多的依存剖析模型之前,我们须要先斟酌一下应当如何评价一个依存剖析模型的表示。我们来看一个简略的例子。对于“She saw the video lecture”这句话,我们有标注出的依存(Gold),然后还有由模型得到的成果(Parsed),这时我们很自然地就想到可以用正确率(accuracy)来评估模型的表示。不过在此我们可以斟酌两种正确率,一种是不斟酌依存类型的 Unlabeled Attachment Score (UAS),另一种则是斟酌依存类型的 Labeled Attachment Score (LAS)。在盘算UAS时,我们只需斟酌每个依存的核心词和依存词是否准确,而不须要斟酌依存的类型;而在盘算后者时,则须要依存的核心词、依存词、类型都准确才以为预测准确。

    基于图的依存剖析器(Graph-based Parser)

    除了基于转移的依存剖析器外,还有一类与之思路完整不同的基于图的依存剖析器。这种模型的思路也很简略,对每个单词,我们通过机器学习等方式盘算每个可能的依存的得分,然后对每个单词选择得分最高的依存。如下图所示,在“big”所有可能的依存中,“cat”得分最高,所以以为“big”依存于“cat”是准确的。

    但是该模型有一个很显明的毛病,就是对于一个长度为$n$的句子,存在$n^2$种可能的依存关系,而模型要剖析每一种可能的关系,这显然是非常耗时的。如下图所示,MSTParser与TurboParser是两种基于图的依存剖析模型,可以看出两者的正确率虽然略好于MaltParser,但它们每秒钟能处置的句子数目却要远远小于MaltParser。

    神经依存剖析器(Neural Dependency Parser)

    基于机器学习的依存剖析模型有三个很显明的毛病,首先机器学习模型中人们通常会结构上百万个特点,而每个特点都是二值的,这使得结构出的特点非常稀少。其次人类即使结构如此数量宏大的特点也难免会有不完全的情形,总会有没有斟酌到的情形。最后由于特点数量过多,模型几乎将95%的时光都花在了特点结构上,挥霍了许多时光。而神经网络模型则不须要手动结构庞杂的特点,那么用神经网络能不能结构出更好的依存剖析模型呢?Manning与陈丹琦在2014年就将该想法付诸实践提出了神经依存剖析模型。从下图的试验成果可以看出神经网络模型(C & M 2014)不仅正确率很高,效力也远远高出其他三个模型,可见其优势。

    该模型实际上非常简练,它也沿用了基于转移的依存剖析的思想,只是改用神经网络模型来预测下一步的动作。与前几章提到的神经网络模型不同,该模型不仅用词嵌入作为输入特点,而且斟酌到POS与依存关系有紧密的接洽,因此对POS也做了嵌入。此外他们还更进一步,对依存类型(dependency label)也做了嵌入。于是对于每个状况,将词嵌入、POS嵌入与依存类型嵌入拼接作为输入。如下图中的例子所示

    该状况中栈里有“ROOT”、“has”、“good”三个词,“has”有指向“He”的依存(类型为nsubj,即主语),缓存里第一个词为“control”,而“VBZ”、“JJ”、“NN”、“PRP”则是单词的POS。 表现缓存中的第一个元素, 分辨表现 左侧的child和右侧的child(即左侧和右侧的依附词), 为空。对于当前状况,就可以将 这7个元素的词嵌入、POS嵌入和依附类型嵌入拼接起来,作为模型的输入。

    注:上面只是一个状况例子,斟酌到每个状况的句子长度、栈中元素个数都不同,因此直接将状况中的所有元素的特点拼接得到的输入向量会有不同的维度,使得后续无法盘算。课上没有提到这个问题,在原论文中,实际上是人为的选取了必定数量的元素作为输入特点。具体来说,设 分辨为选取的单词聚集、单词对应的POS聚集和依存聚集。论文中 包括18个元素,分辨是栈和缓存中的前三个元素 ,栈中前两个元素最左边前两个child和最右边的前两个child,即 ,以及栈中前两个元素最左侧的child的最左侧child和最右侧child的最右侧child,即 中则是 中18个元素对应的POS, 则是除去 外所有依存的类型(共12个)。经过这样选取之后该状况的特点就是 中18个单词的词嵌入、 中18个单词的POS嵌入以及 中的12个依存类型嵌入的拼接。

    有了输入特点,后续的模型就相对简略了。输入特点通过一个以ReLU为激活函数的线性层,最后再由softmax层得到每个动作的概率。模型采取交叉熵作为丧失函数,训练时各个嵌入向量也会被训练。

    神经依存剖析模型构造

    注:原论文的模型有些细节跟课上讲的不太一样,不知道为什么,这里写的是课上讲的。

    该模型是第一个胜利的神经依存剖析模型,它应用了dense的输入表现,同时坚持了神经网络模型的简练,从而在正确率和处置速度两个方面都优于同期的模型。在此之后,许多研讨者又提出了该模型的多种改良方式,例如应用更大更深的神经网络、参加beam search、应用条件随机场(conditional random field, CRF)来预测最终概率。这些方式(Weiss et al. 2015, Andor et al. 2016)都带来了必定的性能晋升,如下图所示

    而其中Dozat & Manning 2017则是将之前提到的基于图的依存剖析与神经依存剖析相联合提出的方式,模型成果更好,但是也继承了基于图的依存剖析效力低下的毛病。

    相干浏览:

    TJH:CS224N NLP with Deep Learning(一):Introductionzhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(二):词向量之Word2Veczhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(三):词向量之GloVezhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(四):Window分类器与神经网络zhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(番外1):fastTextzhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(五):反向传布zhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(五):依存剖析zhuanlan.zhihu.comTJH:CS224N NLP with Deep Learning(六):语言模型与循环神经网络zhuanlan.zhihu.com