语言学的两种观点

依存句法树和短语结构树详细解释：https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/12.%E4%BE%9D%E5%AD%98%E5%8F%A5%E6%B3%95%E5%88%86%E6%9E%90.md

如何描述语法，有两种主流观点，其中一种是上下文无关文法，英文术语是：Constituency = phrase structure grammar = context-free grammars (CFGs)。

短语结构树

这种短语语法用固定数量的rule分解句子为短语和单词、分解短语为更短的短语或单词，一个取自WSJ语料库的短语结构树示例：

上下文无关文法

语言学中，上下文无关文法由如下组件构成:

终结符结合 Σ，比如汉语的一个词表
非终结符集合 V，比如“名词短语”“动词短语”等短语结构组成的集合。
V 中至少包含一个特殊的非终结符，即句子符或初始符，计作 S
推到规则 R，即推到非终结符的一系列规则: V -> V U Σ

基于上下文无关文法理论，我们可以从 S 出发，逐步推导非终结符。一个非终结符至少产生一个下级符号，如此一层一层地递推下去，我们就得到了一棵语法树。但在NLP中，我们称其为短语结构树。也就是说，计算机科学中的术语“上下文无关文法”在语言学中被称作“短语结构语法”。

依存结构

另一种是依存结构，用单词之间的依存关系来表达语法。如果一个单词修饰另一个单词，则称该单词依赖于另一个单词。一个由HanLP输出的依存句法树如下：

依存句法树

将一个句子中所有词语的依存关系以有向边的形式表示出来，就会得到一棵树，称为依存句法树( dependency parse tree)。比如句子“弱小的我也有大梦想”的依存句法树如图所示。

现代依存语法中，语言学家 Robinson 对依存句法树提了 4 个约束性的公理。

有且只有一个词语(ROOT，虚拟根节点，简称虚根)不依存于其他词语。
除此之外所有单词必须依存于其他单词。
每个单词不能依存于多个单词。
如果单词 A 依存于 B，那么位置处于 A 和 B 之间的单词 C 只能依存于 A、B 或 AB 之间的单词。

这 4 条公理分别约束了依存句法树(图的特例)的根节点唯一性、 连通、无环和投射性( projective )。这些约束对语料库的标注以及依存句法分析器的设计奠定了基础。

歧义

通过句法树可以表达歧义，一个确定的句法树对应句子的一个确定解读，比如对介词短语依附（attachment of prepositional phrases (PPs)）：

from space这个介词短语到底依附谁？不同的答案导致对句子不同的理解。

依附歧义

很难确定如何把一个短语（介词短语、状语短语、分词短语、不定式）依附到其他成分上去，比如下列句子：

每个括号中都是一个短语，它们依附的对象各不相同。对于n个短语来讲，组成的树形结构有$C_n=\frac{(2n)!}{(n+1)!n!}$。这是Catalan数，指数级增长，常用于树形结构的计数问题。

卡特兰数

标注数据集的崛起：Universal Dependencies treebanks

虽然上下文无关文法中的语法集很容易写，无非是有限数量的规则而已，但人工费时费力标注的树库却茁壮成长了起来。在 1993 年首次面世的 Universal Dependencies treebanks 如今在 Google 的赞助下发布了 2.0，其授权大多是署名-相同方式共享，覆盖了全世界绝大多数语言（不包括简体中文）。

其官网是：http://universaldependencies.org/

GitHub主页是：https://github.com/UniversalDependencies

树库示例：

人们偏好树库多于规则的原因是显而易见的，树库虽然标注难度高，但每一份劳动都可被复用（可以用于词性标注命名实体识别等等任务）；而每个人编写的规则都不同，并且死板又丑陋。树库的多用性还是得其作为评测的标杆数据，得到了越来越多的引用。

依存文法与依存结构

这节课以及练习用的都是依存句法树，而不是短语结构树。这并不是随机选择，而是由于前者的优势。90年代的句法分析论文99%都是短语结构树，但后来人们发现依存句法树标注简单，parser准确率高，所以后来（特别是最近十年）基本上就是依存句法树的天下了（至少80%）。

不标注依存弧label的依存句法树就是短语结构树的一种：

一旦标上了，两者就彻底不同了：

这里箭头的尾部是head（被修饰的主题），箭头指向的是dependent（修饰语）。

其他

每个句子都有一个虚根，代表句子之外的开始，这样句子中的每个单词都有自己的依存对象了。

句法分析可用的特征

双词汇亲和（Bilexical affinities），比如discussion与issues。

词语间距，因为一般相邻的词语才具有依存关系

中间词语，如果中间词语是动词或标点，则两边的词语不太可能有依存

词语配价，一个词语最多有几个依赖者。

依存句法分析

有几个约束条件：

ROOT只能被一个词依赖
无环

英语中大部分句子是 projective 的，少数是 non-projective 的：

依存句法分析方法

Dynamic programming
    估计是找出以某head结尾的字串对应的最可能的句法树。
Graph algorithms
    最小生成树。
Constraint Satisfaction
    估计是在某个图上逐步删除不符合要求的边，直到成为一棵树。
“Transition-based parsing” or “deterministic dependency parsing”
    主流方法，基于贪心决策动作拼装句法树。

Arc-standard transition

arc-standard方法，通过SHIFT、LEFT-ARC和RIGHT-ARC三种动作来决定单词之间是否依赖以及依赖关系。每个单词只能被修饰（指向）一次，但是可以多次修饰（指向）其他单词。

SHIFT 指两个词 A 与 B 之间没有依存关系；
LEFT-ARC 指两个词 A 与 B 之间是 A <- B 的左链接关系；
RIGHT-ARC 指两个词 A 与 B 之间是 A -> B 的右链接关系。

动作体系的 formal 描述如下：

图片原地址：https://www.hankcs.com/nlp/parsing/neural-network-based-dependency-parser.html

截图来自：https://github.com/NLP-LOVE/Introduction-NLP/blob/master/chapter/12.%E4%BE%9D%E5%AD%98%E5%8F%A5%E6%B3%95%E5%88%86%E6%9E%90.md

MaltParser模型(没看懂)

传统特征表示(没看懂)

传统的特征表示使用二元的稀疏向量，一个超长的稀疏01向量。

特征模板：通常由配置中的1 ~ 3个元素组成
Indicator features

依赖解析的评估：（标记）依赖精度/准确率评价

继续化简得 $LSA = \frac{2 * |A∩B|}{|A| + |B|}$

求 LAS 时，对于该图 |A∩B| = 2，比对的时两幅图得 1，2 列相同的行

求 UAS 时，对于该图 |A∩B| = 4，比对的时两幅图得 1 列相同的行

|A| = |B| = 5

其他评价指标

投影

所谓投射性是指：如果词p依存于词q，那么p和q之间的任意词r就不能依存到p和q所构成的跨度之外（用白话说，就是任意构成依存的两个单词构成一个笼子，把它们之间的所有单词囚禁在这个笼子里，只可内部交配，不可与外族通婚）。比如：

再比如：

非投射

非投射就没有上述限制了，这会导致依存边有交叉，怎么都理不顺：

投射性

CFG转换得到的依存树一定是投射性的，但依存理论允许非投射性的依存句法树（一些语义需要通过非投射性表达）。

arc-standard算法只能拼装投射性的句法树，但换个体系、加上后处理、采用graph-based方法就能得到非投射的句法树。

为什么需要神经网络句法分析器

https://blog.csdn.net/yu5064/article/details/82186738

http://fancyerii.github.io/books/nndepparser/#dp-nn-2

因为：传统特征表示稀疏、不完全、计算代价大，SVM之类的线性分类器本身是很快的，但传统 parser 的95%时间都花在拼装查询特征上了。

无非是传统方法拼接单词、词性、依存标签，新方法拼接它们的向量表示：

经过一个神经网络

模型的作用

如何找输入的词向量

事实上，在“深度学习”“神经网络”与传统的graph-based方法相比较，花了这么多功夫得到的只是0.1%的LAS提升：

非线性函数

未来的工作

Chen&Manning的工作被许多人继续往前推进，走在最前沿的是Google。趋势是：

更大更深调参调得更好（更昂贵）的神经网络
Beam Search
在决策序列全局进行类似CRF推断的方法（CRF宝刀未老，老当益壮啊）

Google的SyntaxNet 中的 Parsey McParseFace的效果：