3.1 依存句法

依存句法是由法国语言学家 Lucien Tesnière \( ^1 \)最先提出。将句子分析成一颗依存句法树，描述各个词语之间的依存关系。也即指出了词语之间在句法上的搭配关系，这种搭配关系是和语义相关联的。


图片来自 Speech and Language Processing \( ^2 \) 其与结构成份句法类似，但是依存结构更平坦，更适合分析自由词序语言。且操作单位是词，比成分句法更简单。

句法依存关注句法结构，语义依存关注有实际含义的实词，其依存关系和句法可能不一样，因为句子中有些词无实质语义。

3.2 依存句法规则

3.2.1 规则

1. 一个句子中只有一个成分是独立的
2. 句子的其他成分都从属于某一成分
3. 任何一个成分都不能依存于两个或两个以上的成分
4. 如果成分A直接从属成分B，而成分C在句子中位于A和B之间，那么，成分C或者从属于A，或者从属于B，或者从属于A和B之间的某一成分(所谓投影规则, 依存关系不能交叉)
5. 中心成分左右两边的其他成分相互不发生关系(同上)

投影和非投影:
事实上在自然语言中，即使是英文/中文这样相对严格语序的语言，也有少量句子存在非投影的情况。而对于非严格语序的语言这样的情况更多。之所以依存句法不能存在非投影规则，有几个原因：
1. 依存句法是在成份结构句法之后流行，而此时大量早期树库，例如penn treebank，其标记均为结构句法。为了便于研究，从短语结构树库转换得到的依存语料必然是投影的。
2. 广泛使用的依存分析算法存在技术限制，无法处理非投影的树结构。(可生成非投影依存树的解析算法 Nivre, J. (2009) \( ^3 \))

3.2.2 图解释

用简单的有向无环图结构 \( G=(V,A) \) 解释依存句法, \( V \) 是顶点, 对应句子中的词, \( A \) 是连接弧，对应词语之间搭配的依存关系。只有一个顶点没有输入弧, 其他所有顶点都有且只有一个输入弧, 但每个顶点可以有多个输出弧, 图结构必须有连接, 不能有孤立顶点且不能循环连接, 从根到每个顶点都必须且只能有一条唯一路径。

3.3 语料

1. 从短语树库转换得到依存语料
   PTB: Treebank-3: penn treebank https://catalog.ldc.upenn.edu/LDC99T42
   CTB: Chinese Treebank 9.0 https://catalog.ldc.upenn.edu/LDC2016T13
   使用peen2malt工具转换，head-find 规则参考 (Zhang and Clark, 2008 \( ^4 \); Zhang and Nivre, 2011 \( ^5 \))

   peen2malt headfind rule:
   非终结符标记\t搜索方向(l从左往有, r从右往左) 判断为头部词语的终结或非终结符, 多个规则用”;”分隔, 每个短语标记占一行。如名词短语的头部查找: 名词短语, 从右到左第一个名词为头部其余的依次搭配修饰此头部词, 动词短语, 从左到右第一个动词为头部词, 其搭配的形容词或副词等为依存词。 在依存句法中”动/谓词”通常作为整句根词。

2. universal dependency
   http://universaldependencies.org
   这是非投影的。

3. Chinese Dependency Treebank 1.0
   https://catalog.ldc.upenn.edu/LDC2012T05
   HIT的中文依存树库

4. NLPCC2013 语义依存评测
   http://tcci.ccf.org.cn/conference/2013/pages/page04_tdata.html

中文树库并不多，标注方案也各不相同。网上能下载到的语料只能用于算法研究。句法分析的目的是把灵活多变的自然语言转化为结构化数据，而对自然语言来说，尚无公认的结构化标准。还需在实践中逐步完善树库建设和算法改进。

3.4 评估

使用三个量化指标评估依存分析性能

1. 依存标注准确率 (Labeled Attachment Score, LAS)
2. 依存准确率 (Unlabeled Attachment Score, UAS)
3. 标注准确率 (Labeled Accuracy, LA)

令整个测试语料包含的词数为 \( N \), 任意词的依存用三元组 (word，headword，relation) 表示。其中 word 为词本身，word 以关系 relation 依附于 headword, 在被测系统输出中。令headword 正确的词数目为 \( N_a \)，relation 正确的数目为 \( N_l \), headword 和 relation 都正确的词数目为 \( N_{al} \), 量化指标计算如下：

\[\begin{align}
LAS &= \frac{N_{al}}{N} \\
UAS &= \frac{N_a}{N} \\
LA &= \frac{N_l}{N} \\
\end{align}\]

指标优先级: \( LAS > UAS > LA \)

3.5 基于转移的分析方法

来自 Speech and Language Processing \( ^2 \)

3.5.1 arc-standard

基于转移的剖析是从 “转移-规约” (Aho and Ullman, 1972 \( ^6 \)) 发展而来。 此方法原本用于分析程序语言。这个方法简单优雅，采用上下文无关文法，一个堆栈和一个需要被解析的标记列表。 用于结构句法的解析。现在把其中的语法和操作替换为依存规则相关。

在基于转移的剖析中的关键是组态(configuration)概念， 每个组态由一个堆栈，一个待剖析句子的词列表和一个表征为依存树的关系集合。 在这个框架中，剖析过程被构造为一个可能的组态空间的转换序列。
剖析过程的目标是找到一个最终组态，句子中的所有词都被剖析合成为一个合适的依存树结构。

为实现组态转换序列的搜索，我们定义一个转移算符集合。当算法应用到组态就产生新的组态(这个过程就是转移)。基于这个操作，我们可以看到剖析算符通过搜索组态空间转换序列， 引导开始组态到希望的目标组态。

在剖析过程开始前，我们创造一个初始组态，在此初始组态中的堆栈里只包含依存句法根。词列表使用句子中的词或词形初始化。依存关系集合设置为空。在最终的目标组态里，堆栈和词表都将是空的. 依存关系集合中保存最终剖析结果。

在基于转移剖析的标准方法(arc-standard)中, 算符用于产生新的组态。这非常简单且符合从左到右的顺序检查词语并构建依存树的直观动作(Covington, 2001 \( ^7 \)).

在 arc-standard 中其实只有三个转移动作：
1. 指派当前词为之前词的头部词
2. 指派之前看到的词为当前词语的头部词
3. 推迟对当前的词语任何指派，添加它到堆栈以便后续处理。

为使这些动作更明确，创建三个转移算符用于操作堆栈顶部的两个元素。
1. leftarc: 断言堆栈最顶部的词和其下紧接着的词关系为头部-依存关系， 从堆栈中删除低位的词。
2. rightarc: 断言堆栈中的的第二个词和最顶部的为头部-依存关系, 删除在堆栈最顶部的词。
3. shift: 删除输入缓冲区最前面的词，并将其放到堆栈顶部。

上面三个算符，实现了所谓基于转移的剖析方法 arc-standard (Covington 2001 \( ^7 \), Niver 2003 \( ^8 \))。

这个剖析方法有两个明显特点，转移算符仅断言堆栈顶部两个元素之间的关系, 一旦被断言,则依附词将从堆栈中删除，且在未来的处理过程中无效。存在替代此转移剖析系统的其他剖析行为，但 arc-standard 相当高效和易于实现。

为保证这些算符被适当使用，我们需添加一些使用算符的先决条件。首先，既然根据定义ROOT节点不能有任何输入弧，我们增加限制，当ROOT是堆栈第二个元素时，leftarc算符不能应用。第二，两个算符都需要在堆栈的最上面两个元素上使用。在这些先决条件下。基于转移的剖析器规范是相当简单的。

在每个步骤，剖析程序查询一个oracle函数. 它提供一个合适的转移算符用于转换当前组态, 紧接着在当前组态上应用算符, 产生一个新的组态，处理程序结束时。所有在句子中的词语都被消耗，且root是堆栈仅剩的元素。

基于转移的剖析效率在算法中体现出. 复杂性是句子长度的线性函数，因为它是从左到右的单方向处理句子中的词语，每个词语必须首先被移动到堆栈，然后才能在后续被规约。

与动态规划和基于搜索的方法不同，这是明显的贪婪算法–oracle在每个步骤提供一个单项选择，剖析器使用这个选项，没有其他选项被探索，没有回溯，并且在剖析结束后返回单个依存树。

3.5.1.1 重要事项

第一. 得到的转移序列可能不是唯一合理的剖析, 通常情况下, 可能存在多个剖析路径得到相同结果。由于路径多样， 可能存在的其他转移序列导致得到不同的但同样有效的剖析。

第二，我们假定oracle永远在剖析过程的每个位置提供正确算符。这个假设事实上是不成立的，如，考虑到算法的贪婪性质，不恰当的算符将导致不正确的剖析，因为剖析器没有机会返回并继续替代选择。

最后，为简单起见，我们已介绍的例子未包含依存关系标签。为生成带标签的依存树，我们可以使用依存标签参数化leftarc和rightarc算符。如leftarc(nsubj)或rightarc(dobj)，这等效从我们原来的包含left arc和rightarc的三个算符扩展转移算符集，在依存关系集中，再加上一个附加的shift算符。如此, 实现oracle更困难，因为它现在在一个很大的算符集合中作出选择。

3.5.1.2 实现Oracle

当前最先进的基于转移的系统使用监督机器学习方法训练分类器用于充当oracle角色。给予合适的训练数据训练一个决策函数，用于从组态映射到转移算符。

如同所有的监督机器学习方法，我们将需要合适训练数据和抽取对决策有帮助的特征，训练数据的来源是依存树库。

3.5.1.3 生成训练数据

oracle给定输入组态会返回一个转移算符。因此，要训练一个分类器，我们需要使用与转移算符成对的组态数据，不幸的是，语料树库是成对的句子和其依存树，不能直接提供我们需要组态序列和转移算符序列。

为生成必要的训练数据，我们将基于oracle分析算法使用。
我们从树库中得到参考剖析，并把训练句子按时间对应分析得到oracle的调用序列，基于算符和连续的组态模拟运行得到训练实例。为了解这一切是如何工作的. 我们首先重温我们的剖析器算符。使用一个默认的初始化组态开始，堆栈仅包含root，输入列表只是句子中的词列表。关系集合为空。leftarc和rightarc算符在堆栈的顶部添加依存关系并累积到句子对应的关系集合. 因为我们有黄金标准参考分析每个训练语句。我们知道对于给定每个句子什么依存关系是有效的。所以，我们使用参考剖析树从头到尾的在组态序列的每个步骤指导如何选择算符。

更确切地说, 给定一个参考解析和组态, 训练oracle过程如下:
* 选择leftarc: 如果它能在给定参考解析和当前组态下产生一个正确的头部-依存关系。
* 否则，选择rightarc：如果它产生一个正确的头部-依存关系且给定参考解析和在堆栈顶部的词语的所有依附词都已被剖析。
* 否则，选择shift。

选择rightarc算符的限制是必须的，确保一个词没有因在他的所有依附词被指定前被从堆栈中移除，而造成在未来处理失败。更正式的，在训练oracel期间需要访问以下信息。

• 当前组态中的堆栈 \( S \) 和 依存关系集合 \( R_c \)
• 一个由顶点\( V \)集合和依存关系参考剖析\( R_p \)集合构造参考依存树。

总的来说, 从树库得到的对应组态转移的序列导出合适的训练实例, 基于在上下文参考依存树中模拟操作解析，我们能确定整个剖析过程中的每个正确动作。从而创建我们需要训练集。

3.5.1.4 特征

可使用特征模板（回顾最大熵条件随机场，对数线性模型）。参考模板 (Zhang and Clark 2008 \( ^4 \), Huang and Sagae 2010 \( ^8 \), Zhang and Nivre 2011 \( ^9 \))。

3.5.1.5 训练

基于转移的依存解析器训练有多项式逻辑回归和支持向量机 。两者都能高效使用大量稀疏特征在上一节中描述。最近，基于转移解析使用神经网络或深度学习方法(Chen and Manning,2014 \( ^{10} \))。 神经网络方法不需要特征模板。每个步骤的orcale训练其实是局部的，在这里可以考虑全局优化方式，例如将单个句子中的转移序列orcale损失求和。

3.5.2 arc-eager

之前每次在处理rightarc依存时，都会延后。原因是被处理过的依附词会被删除，造成后续处理错误。而这种延迟有可能在依存距离过长时出错，毕竟等待时间越长，出错的可能性越大，eager算法每次发现依存关系时第一时间记录，并且将检测堆栈顶部两个元素的依存关系更改为检测堆栈顶部和输入缓存第一个元素之间的依存关系。Nivre, J. (2008) \(^{11}\)。

我使用代码试验发现，效果似乎还不如arc-standard，但有可能是特征提取未处理好引起。目前看来，在这里直接使用简单的lstm处理特征是不可行的。或许应该还是按照类似模板的方式拼接特征，直接使用前馈网络。

3.5.3 beam-search

之前的每个oracle输出类别时,因为是分类器,这里其实是可以附带概率输出的,用此概率作为组态应用对应算符后的评分,以此实现搜索多个可能算符序列只返回最高分的剖析树。算法来自 Speech and Language Processing \( ^2 \)。

3.6 基于图的分析方法

投影结构,使用 Eisner algorithm \( ^{12} \), 非投影结构的图分析在 McDonald et al. 2005. \( ^{13} \)引进，使用特征模板， 而在 Stanford’s Graph-based Neural Dependency Parser at the CoNLL 2017 Shared Task \( ^{14} \)中使用RNN简化了手工预设特征模板。考虑到自然语言其实或多或少有非投影现象，只试验了非投影结构的图分析算法(使用Chu-Liu-Edmonds生成依存树(最大生成树)）。但我找到的中文依存树库均为投影结构。

3.7 试验

只找到三个中文语料试验依存解析算法, CTB8(penn2malt转换为依存句法), NLPCC2013(内含清华和哈工大语义评测语料， 因无gold样本，将dev作为gold使用，原train集随机抽样部分作为dev). 算法参考 (Chen and Manning,2014 \( ^{10} \)) 但试验发现对CTB语料可行，对语义依存语料效果很差，于是用bilstm替代,准确了得到了提高，但速度比较慢。维基百科训练的128_word2vec作为embedding. 使用tensorflow实现.

Chen and Manning,2014 \( ^{10} \), 特征: s1, s2, s3, b1, b2, b3, s1.lc1, s1.rc1, s1.lc2, s1.rc2, s2.lc1, s2.rc1, s2.lc2, s2.rc2, s1.lc1.lc1, s1.rc1.rc1, s2.lc1.lc1, s2.rc1.rc1, pos和lable嵌入维度64, 隐层1024, L2=1e-7, 训练过程中不优化word_embedding.

Corpus	Algorithm	LAS	UAS	AS
CTB	standard	0.786522	0.802340	0.907334
CTB	standard-beam64	0.802355	0.817068	0.915685

使用bilstm替代前馈网络。

Corpus	Algorithm	LAS	UAS	AS
CTB	arc-standard	0.784596	0.800540	0.908250
CTB	arc-eager	0.743259	0.763199	0.880249
HIT	arc-standard	0.589145	0.731555	0.722813
HIT	arc-eager	0.575977	0.735826	0.695178
THU	arc-standard	0.682811	0.768639	0.758525
THU	arc-standard-beam64	0.692637	0.771298	0.763842
THU	arc-eager	0.641390	0.727630	0.720689

试验发现：句子越长，依存关系越多(HIT,THU的依存类型远远多于CTB, 但CTB的只适合评估测试算法，其转换的依存树用于后续信息抽取会比较困难，依存关系与标签过于模糊,在中文头部词和依附的区分也不够本土化)。简单粗暴的使用LSTM处理特征效果并不好，这里或许应换成其他非RNN结构, 在这里或许应该引入注意力机制判断词汇依存关系，例如堆栈和缓冲区乘起来作为软对齐试试。且在试验中发现，已剖析的依存结构是否作为oracle函数的输入对预测有很大影响，在arc-standard中加上比较好，而arc-eager中加上已剖析依存特征后效果反倒更差。这里需要更多时间尝试优化。现资源和时间不足，也没有足够生产环境可用语料, 今后用到时再试验。

在开放环境(web,chat)性能大约降低5%-7%。

3.8 参考

1. Lucien Tesnière: https://en.wikipedia.org/wiki/Lucien_Tesni%C3%A8re
2. Daniel Jurafsky, James H. Martin “Speech and Language Processing”
3. Nivre, J. (2009). Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 – Volume 1, Stroudsburg, PA, USA, pp. 351–359. Association for Computational Linguistics.
4. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graphbased and transition-based dependency parsing using beam-search. In EMNLP
5. Aho, A. V. and Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling, Vol. 1. Prentice Hall.
6. Covington, M. (2001). A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM
   Southeast Conference, pp. 95–102.
7. Nivre, J. (2003). An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies.
8. Huang, L. and Sagae, K. (2010). Dynamic programming for linear-time incremental parsing. In Proceedings of ACL, pp. 1077–1086. Association for Computational Linguistics.
9. Zhang, Y. and Nivre, J. (2011). Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers-Volume 2, pp. 188–193. Association for Computational Linguistics.
10. Chen, D. and Manning, C. D. (2014). A fast and accurate dependency parser using neural networks.. In EMNLP, pp. 740–750.
11. Nivre, J. (2008). Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553.
12. Eisner algorithm
13. Ryan McDonald, Fernando Pereira: Non-projective Dependency Parsing using Spanning Tree Algorithms
14. Timothy Dozat,Peng Qi,Christopher D. Manning: Stanford’s Graph-based Neural Dependency Parser at the CoNLL 2017 Shared Task