句法依存分析背景基本概念及常用方法

原创

大鹅

发布于 2021-12-21 23:54:00

1.8K0

发布于 2021-12-21 23:54:00

文章被收录于专栏：大鹅专栏：大数据到机器学习大鹅专栏：大数据到机器学习

0. 句法分析与依存分析背景

句法是指句子的各个组成部分的相互关系。

句法分析分为

句法结构分析（syntactic structure parsing）
句法结构分析又称短语结构分析（phrase structure parsing），也叫成分句法分析（constituent syntactic parsing），用于获取整个句子的句法结构；
依存关系分析(dependency parsing)

依存分析用于获取词汇之间的依存关系。

深层文法句法分析

深层文法句法分析，即利用深层文法，例如词汇化树邻接文法（Lexicalized Tree Adjoining Grammar， LTAG）、词汇功能文法（Lexical Functional Grammar， LFG）、组合范畴文法（Combinatory Categorial Grammar， CCG）等，对句子进行深层的句法以及语义分析。

目前的句法分析已经从句法结构分析转向依存句法分析。

依存语法通过分析语言单位内成分之间的依存关系揭示其句法结构，主张句子中核心动词是支配其它成分的中心成分，而它本身却不受其它任何成分的支配，所有受支配成分都以某种依存关系从属于支配者。

在20世纪70年代，Robinson提出依存语法中关于依存关系的四条公理：

一个句子中只有一个成分是独立的；
其它成分直接依存于某一成分；
任何一个成分都不能依存与两个或两个以上的成分；
如果A成分直接依存于B成分，而C成分在句中位于A和B之间，那么C或者直接依存于B，或者直接依存于A和B之间的某一成分；

1. 依存分析

依存关系是一个中心词与其从属之间的二元非对称关系，一个句子的中心词通常是动词（Verb），所有其他词要么依赖于中心词，要么通过依赖路径与它关联。

一些重要概念：

依存句法认为“谓语”中的动词是一个句子的中心，其他成分与动词直接或间接地产生联系。
依存句法理论中，“依存”指词与词之间支配与被支配的关系，这种关系不是对等的，这种关系具有方向。确切的说，处于支配地位的成分称之为支配者（governor，regent，head），而处于被支配地位的成分称之为从属者（modifier，subordinate，dependency）。
依存语法本身没有规定要对依存关系进行分类，但为了丰富依存结构传达的句法信息，在实际应用中，一般会给依存树的边加上不同的标记。
依存语法存在一个共同的基本假设：句法结构本质上包含词和词之间的依存（修饰）关系。一个依存关系连接两个词，分别是核心词（head）和依存词（dependent）。依存关系可以细分为不同的类型，表示两个词之间的具体句法关系。

依存结构是加标签的有向图，箭头从中心词指向从属，具体来说，箭头是从head指向child，从该解析树可以看出，每个Token只有一个Head。

如上图所示，和成分句法分析相比，依存句法分析更加直接的分析出句子的主语谓语等成分。另外一点，依存句法分析的结果里，词的关系更加直接。比如上面的例子中动词prefer的直接宾语是flight，在依存句法分析树中，直接有prefer到flight的边，而在成分句法分析中这种关系是不直接的（但是也是有的）。

关系标签

标签表示从属的语法功能，名词性的标签是：

root：中心词，通常是动词
nsubj：名词性主语（nominal subject）
dobj：直接宾语（direct object）
prep：介词
pobj：介词宾语
cc：连词

其他常用的标签：

compound：复合词
advmod：状语
det：限定词
amod：形容词修饰语

2. 常用方法与评价指标

基于规则的方法: 早期的基于依存语法的句法分析方法主要包括类似CYK的动态规划算法、基于约束满足的方法和确定性分析策略等。
基于统计的方法：统计自然语言处理领域也涌现出了一大批优秀的研究工作，包括生成式依存分析方法、判别式依存分析方法和确定性依存分析方法，这几类方法是数据驱动的统计依存分析中最为代表性的方法。
基于深度学习的方法：近年来，深度学习在句法分析课题上逐渐成为研究热点，主要研究工作集中在特征表示方面。传统方法的特征表示主要采用人工定义原子特征和特征组合，而深度学习则把原子特征(词、词性、类别标签)进行向量化，在利用多层神经元网络提取特征。

依存分析器的性能评价：

无标记依存正确率（UAS）：测试集中找到其正确支配词的词（包括没有标注支配词的根结点）所占总词数的百分比。
带标记依存正确率（LAS）：测试集中找到其正确支配词的词，并且依存关系类型也标注正确的词（包括没有标注支配词的根结点）占总词数的百分比。
依存正确率（DA）：测试集中找到正确支配词非根结点词占所有非根结点词总数的百分比。
根正确率（RA）：有二种定义，一种是测试集中正确根结点的个数与句子个数的百分比。另一种是指测试集中找到正确根结点的句子数所占句子总数的百分比。
完全匹配率（CM）：测试集中无标记依存结构完全正确的句子占句子总数的百分比。

3. 传统方法：arc-standard算法

arc-standard配置(configuration)定义为c=(s, b, A)。

其中s是一个栈，b是一个buffer(队列)，Ａ是已经parse得到的边(依存关系，包括label)。初始配置的s=[ROOT], b=[w1,…,wn]b=[w1,…,wn]，A=ΦA=Φ。一个配置是终止(terminal)配置的条件是：buffer为空并且s里只有ROOT。sisi从栈顶往下的第i个元素，因此s1s1是栈顶的元素。bibi是buffer的第i个元素。arc-standard算法定义了3种操作：

LEFT-ARC(l) 往A里添加边s1→s2s1→s2，边的label是l，然后把s2s2从栈中删除。这个操作要求|s|≥2|s|≥2
RIGHT-ARC(l) 往A里添加边s2→s1s2→s1，边的label是l，然后把s1s1从栈中删除。这个操作要求|s|≥2|s|≥2
SHIFT 把b1b1移到s的顶部。这个操作要求|b|≥1|b|≥1

对于带label的版本，总共有|T|=2Nl+1|T|=2Nl+1个不同的操作，这里NlNl是不同label的数量。下图是一个例子，左上是正确的依存关系；右上是parse过程中的一个配置。下边是一个正确的操作序列和配置的变化。

对于贪心的parser来说，输入是一个配置，输出是|T||T|中的一个。这是一个分类问题，输入的配置里有很多有用的信息，传统的机器学习会手工提取很多特征，就像我们在前面的例子里介绍的那样，它们的缺点我们也介绍过来，那么接下来就是怎么用神经网络来改进这个分类器了。

4. 基于神经网络方法

对于一个配置，我们首先抽取一些相关的词、词性和已经parse的关系的label。词的集合是Sw，词性的集合是St，label的集合是Sl。并且假设这些集合的大小分别是nw,nt,nl。假设Sw=[w1,…,wnw]，我们对这nw个词都进行Embedding，这样得到xw=[eww1,eww2,…,ewwnw]，类似的，我们可以得到xt和xl，然后我们把xw,wt,wl接入全连接网络，并且使用3次方的激活函数得到：

h=(W_1^wx^w+W_1^tx^t+W_1^lx^l+b_1)^3

然后再加一个全连接层，激活是softmax，得到分类的概率：

p = softmax(W_2 h)

通常我们会对词进行Embedding，但是作者认为对词性和label进行Embedding也是有必要的，比如词性，NN和NNS会有相似的性质。SwSw有18个词，分别是栈顶和buffer头部的3个词：s1,s2,s3,b1,b2,b3；s1和s2最左的2个孩子，最右的2个孩子；s1和s2最左孩子的最左孩子(这是孩子的孩子！)，最右孩子的最右孩子。6+8+4=18。

为了方便，我们用记号lc1(s1)表示栈顶(s1)元素的最左的孩子，而lc2(s1)示栈顶(s1)元素的第二左的孩子。类似的用rc1,rc2表示最右和第二右的孩子。因此最左孩子的最左孩子可以这样表示lc1(lc1(s1))。

St有18个词性，是和SwSw对应的。而Sl有12=8+4个，因为s1,s2,s3,b1,b2,b3并没有label。我们抽取的label是来自与边(孩子)，比如s1和它最左的2个孩子会对应两条边。因此label总共可以抽取8+4=12个。