零、 句法分析基础
句法分析（syntactic parsing）是NLP的关键技术，对input句子进行分析得到对应的句法结构；语义分析通常以句法分析的输出，作为input，以获得更多的指示信息。
0.0 NLP基础任务
（1）语音、图像和文本
自然语言处理系统的输入源一共有3个，即语音、图像与文本。语音和图像这两种形式一般经过识别后转化为文字，转化后就可以进行后续的NLP任务了。
（2）中文分词、词性标注和命名实体识别
这3个任务都是围绕词语进行的分析，所以统称词法分析。词法分析的主要任务是将文本分隔为有意义的词语(中文分词)，确定每个词语的类别和浅层的歧义消除(词性标注)，并且识别出一些较长的专有名词(命名实体识别)。对中文而言，词法分析常常是后续高级任务（如句法分析等）的基础。
（3）信息抽取
词法分析之后，文本已经呈现出部分结构化的趋势，根据分析出来的每个单词和附有自己词性及其他标签的数据，抽取出一部分有用的信息，关键词、专业术语等，也可以根据统计学信息抽取出更大颗粒度的文本。
（4）文本分类与文本聚类
将文本拆分为一系列词语之后，就可以对文本进行分类和聚类操作，找出相类似的文本。
（5）句法分析
词法分析只能得到零散的词汇信息，计算机不知道词语之间的关系。在一些问答系统中，需要得到句子的主谓宾结构，这就是句法分析得到的结果，如下图所示：
不仅是问答系统或搜索引擎，句法分析还经常应用有基于短语的机器翻译，给译文的词语重新排序。
（6）语义分析与篇章分析
相较于句法分析，语义分析侧重语义而非语法。它包括词义消歧(确定一个词在语境中的含义，而不是简单的词性)、语义角色标注(标注句子中的谓语与其他成分的关系)乃至语义依存分析(分析句子中词语之间的语义关系)。
（7）其他高级任务
自动问答、自动摘要、机器翻译
注意，一般认为信息检索(Information Retrieve，IR)是区别于自然语言处理的独立学科，IR的目标是查询信息，而NLP的目标是理解语言。
0.1 句法分析任务分类
根据句法结构的表示形式不同，最常见的句法分析任务可以分为以下三种：
句法结构分析（syntactic structure parsing），又称短语结构分析（phrase structure parsing），也叫成分句法分析（constituent syntactic parsing）。作用是识别出句子中的短语结构以及短语之间的层次句法关系。
依存关系分析，又称依存句法分析（dependency syntactic parsing），简称依存分析，作用是识别句子中词汇与词汇之间的相互依存关系。依存句法分析属于浅层句法分析。
深层文法句法分析，即利用深层文法，例如词汇化树邻接文法（Lexicalized Tree Adjoining Grammar， LTAG）、词汇功能文法（Lexical Functional Grammar， LFG）、组合范畴文法（Combinatory Categorial Grammar， CCG）等，对句子进行深层的句法以及语义分析。
句法分析语料库：
汉语中常用的句法分析语料库有CTB(Chinese Treebank，中文树库)，其中一个句子可视化后如下图所示。中文单词上面的英文标签标示词性，而箭头表示有语法联系的两个单词，具体是何种联系由箭头上的标签标示。
0.2 依存句法分析
依存句法假设：句法结构包含相互之间是双边不对称关系的词典（lexical）元素，这种不对称的关系成为依存（dependency），在图中的表现是单向箭头。
箭头通常还会打上这种语法关系的名字（主语，前置宾语等等）
箭头一边连接中心词head (governor, superior, regent)，一边则连接依存词dependent (modifier, inferior, subordinate)。
这种关系表现为树结构
0.3 依存分析方法分类
基于规则的方法: 早期的基于依存语法的句法分析方法主要包括类似CYK的动态规划算法、基于约束满足的方法和确定性分析策略等。
基于统计的方法：统计自然语言处理领域也涌现出了一大批优秀的研究工作，包括生成式依存分析方法、判别式依存分析方法和确定性依存分析方法，这几类方法是数据驱动的统计依存分析中最为代表性的方法。
基于深度学习的方法：近年来，深度学习在句法分析课题上逐渐成为研究热点，主要研究工作集中在特征表示方面。传统方法的特征表示主要采用人工定义原子特征和特征组合，而深度学习则把原子特征（词、词性、类别标签）进行向量化，在利用多层神经元网络提取特征。
一、Syntactic Structure: Consistency and Dependency 语言结构的两种角度
依存分析一般有两个视角：
（1）组成关系（Consistency）：Constituency Grammar。使用短语结构语法将单词放入嵌套的组件中。
（2）依赖关系（Dependency）：Dependency Parsing。句子的从属结构显示哪些词依赖于(修饰或是)哪些词。这些单词之间的二元非对称关系称为依赖关系，并被描述为从head到dependent。通常这些依赖关系形成一个树结构。经常用语法关系的名称进行分类(主语，介词宾语，同位语等)。有时会将假根节点作为head添加到树中，所以每个单词都依赖于一个节点。
1.1 角度1：Constituency Parsing
语言结构的两种角度：
Constituency = phrase structure grammar = context-free grammars (CFGs)
这里的CFG即无上下文语法，也称为短语结构语法。
PS：不过该句法分析器准确率不高，现在研究较少，现在用角度2的依存句法树比较多。
通过短语结构，可以组织出嵌套的consistent：
如果标注上对应的词性：
Det 指的是 Determiner，在语言学中的含义为 限定词
NP 指的是 Noun Phrase ，在语言学中的含义为 名词短语
VP 指的是 Verb Phrase ，在语言学中的含义为 动词短语
P 指的是 Preposition ，在语言学中的含义为 介词
PP 指的是 Prepositional Phrase ，在语言学中的含义为 介词短语
1.2 角度2：Dependency Parsing
依存语法理论：
认为词与词之间存在主从关系，这是一种二元不等价的关系。
修饰词为从属词( dependent )，被修饰的词语称为支配词(head),两者之间的语法关系称为依存关系( dependency relation)。
比如句子“大梦想”中形容词“大”与名词“梦想"之间的依存关系如下图，被修饰词——>修饰词
依赖结构显示了哪些单词依赖于(修改、附加或作为参数)哪些其他单词。
look是整个句子的root，look依赖于crate
in，the，large都是crate的依赖
in，the都是kitchen的依赖
by the door是crate的依赖
小结：理解句子结构才能语言，要知道哪些词是哪些词的修饰词。
（0）基于LTP依存句法分析
利用哈工大的LTP中文工具集。
注意：在依存句法当中，虚节点ROOT占据了0位置，因此节点的下标从1开始。
from ltp import LTP ltp = LTP() # 对句子进行分词 # 分词结果用segment访问，hidden用于访问每个词的隐含层向量 seg, hidden = ltp.seg(["他叫汤姆去拿外衣。"]) dep = ltp.dep(hidden) print(dep)
结果：
# [['他', '叫', '汤姆', '去', '拿', '外衣', '。']] # [ # [ # (1, 2, 'SBV'), # (2, 0, 'HED'), # 叫 --|HED|--> ROOT # (3, 2, 'DBL'), # (4, 2, 'VOB'), # (5, 4, 'COO'), # (6, 5, 'VOB'), # (7, 2, 'WP') # ] # ]
（1）上面结果的第1、2行为例：(1, 2, 'SBV')，(2, 0, 'HED')，依存句法树会有默认的虚拟root节点，其索引为0，分词后的索引是从1开始的：
（2）第二行的(2, 0, 'HED')第二列为0，代表索引为2的结点（叫）的父节点是索引为0的虚拟root节点。
（3）第一行的(1, 2, 'SBV')的SBV是表示两个节点的依存关系是主谓关系，即“叫”和“他”是主谓关系。
利用hanlp工具可以对上面那句话进行语法分析的可视化：
语义分析的可视化：
（1）Prepositional phrase attachment ambiguity
介词短语依附歧义。
San Jose cops kill man with knife.
cops用knife kill了那个男子。
cops 是 kill 的 subject (subject 指 主语)
man 是 kill 的 object (object 指 宾语)
knife 是 kill 的 modifier (modifier 指 修饰符)
cops kill了那个有knife的男子
knife 是 man 的 modifier (名词修饰符，简称为 nmod )
Scientists count whales from space.
from space 这⼀介词短语修饰的是前面的动词 count 还是名词 whales。
PP attachment ambiguities multiply
介词短语依附歧义。
关键的解析决策是我们如何 “依存” 各种成分：介词短语、状语或分词短语、不定式、协调等。
上述句子中有四个介词短语
board 是 approved 的 主语， acquisition 是 approved 的谓语
by Royal Trustco Ltd. 是修饰 acquisition 的，即董事会批准了这家公司的收购
of Toronto 可以修饰 approved, acquisition, Royal Trustco Ltd. 之⼀，经过分析可以
得知是修饰 Royal Trustco Ltd. 即表示这家公司的位置
for $27 a share 修饰 acquisition
at its monthly meeting 修饰 approved ，即表示批准的时间地点
这样复杂的句子结构，需要考虑指数级个可能结构，即卡特兰数：
C n = ( 2 n ) ! / [ ( n + 1 ) ! n ! ] C_{n}=(2 n) ! /[(n+1) ! n !]
C
n
=(2n)!/[(n+1)!n!]
一个指数增长的序列，出现在许多类似树的情况中。
ex：一个n+2边的多边形可能的三角形数，三角形概率图模型（CS228课程有提）。
（2）Coordination scope ambiguity
协调范围模糊。
例句：Shuttle veteran and longtime NASA executive Fred Gregory appointed to board
一个人：[[Shuttle veteran and longtime NASA executive] Fred Gregory] appointed to board
两个人：[Shuttle veteran] and [longtime NASA executive Fred Gregory] appointed to board
例句：Doctor: No heart, cognitive issues
（3）Adjectival/Adverbial Modifier Ambiguity
形容词修饰语歧义。
例句：Students get first hand job experience
first hand 表示 第一手的，直接的，即学生获得了直接的工作经验
first 是 hand 的形容词修饰语(amod)
first 修饰 experience, hand 修饰 job
（4）Verb Phrase (VP) attachment ambiguity
动词短语(VP)依存歧义。
例句：Mutilated body washes up on Rio beach to be used for Olympic beach volleyball.
to be used for Olympic beach volleyball 是 动词短语 (VP)
修饰的是 body 还是 beach
（5）Dependency paths identify semantic relations
依赖路径识别语义关系。
通过依赖路径确定语义关系，如可以研究蛋白质之间的交互作用。
二、Dependency Grammar and Treebanks (15 mins)
2.1 Dependency Grammar and Dependency Structure
关联语法假设句法结构包括词汇项之间的关系，通常是二元不对称关系(“箭头”)，称为依赖关系
Dependency Structure有两种表现形式
一种是直接在句子上标出依存关系箭头及语法关系
另⼀种是将其做成树状机构（Dependency Tree Graph）
2.2 Dependency Grammar/Parsing History
依赖结构的概念可以追溯到很久以前
Pāṇini的语法(公元前5世纪)
一千年 阿拉伯语的语法的基本方法
选区/上下文无关文法是⼀个新奇的发明
20世纪发明(R.S.Wells,1947; then Chomsky)
现代依赖工作经常源于 L. Tesnière(1959)
是20世纪“东方”的主导方法(俄罗斯，中国，…)
有利于更自由的语序语言
NLP中最早类型的解析器在美国
David Hays 是美国计算语言学的创始人之一，他很早就构建了依赖解析器(Hays 1962)
2.3 Dependency Grammar and Dependency Structure
大家对箭头指向的方式不⼀致：有些人把箭头朝⼀个方向画；有人是反过来的
ps：Tesnière 从头开始指向依赖，cs224也是用这种方式（即箭头指向依赖者dependent）。
通常添加⼀个伪根指向整个句子的头部，这样每个单词都精确地依赖于另⼀个节点。
在哈工大车万翔老师的《自然语言处理》书里，依存结构句法树（如下图），也是有添加一个虚拟根结点。
2.4 The rise of annotated data: Universal Dependencies treebanks
标记数据集的崛起：Universal Dependencies treebanks 树库
[Universal Dependencies: http://universaldependencies.org/ ; cf. Marcus et al. 1993, The Penn Treebank, Computational Linguistics]
Universal Dependencies：我们想要拥有⼀个统一的、并行的依赖描述，可用于任何人类语言
从前手工编写语法然后训练得到可以解析句子的解析器
用⼀条规则获得所需信息虽然有效，但是随着语法规则符号越来越复杂，这样做并没有共享和重用人类所做的工作
句子结构上的treebanks 支持结构更有效
The rise of annotated data：从一开始，构建 treebank 似乎比构建语法慢得多，也没有那么有用，但是 treebank 给我们提供了许多东西
劳动力的可重用性
许多解析器、词性标记器等可以构建在它之上
语言学的宝贵资源
广泛的覆盖面，而不仅仅是⼀些直觉
频率和分布信息
一种评估系统的方法
2.5 Dependency Conditioning Preferences
依赖项解析的信息来源是什么？
Bilexical affinities (两个单词间的密切关系)
[discussion 和 issues] 是看上去有道理的
Dependency distance 依赖距离
主要是与相邻词
Intervening material 介于中间的物质
依赖很少跨越介于中间的动词或标点符号（即如果中间的词语是动词或者标点，则两边的词语不太可能有依存）
Valency of heads
How many dependents on which side are usual for a head?
2.6 Dependency Parsing
依存关系句法分析。
通过为每个单词选择它所依赖的其他单词(包括根)来解析⼀个句子。
通常有⼀些限制
只有一个单词是依赖于根的
不存在循环
这使得依赖项成为树
最后一个问题是箭头是否可以交叉(非投影的 non-projective)；没有交叉的就是non-projectice
2.7 Projectivity
定义：当单词按线性顺序排列时，没有交叉的依赖弧，所有的弧都在单词的上方
与CFG树并行的依赖关系必须是投影的
通过将每个类别的⼀个子类别作为头来形成依赖关系
但是依赖理论通常允许非投射结构来解释移位的成分
如果没有这些非投射依赖关系，就不可能很容易获得某些结构的语义
2.8 Methods of Dependency Parsing
Dynamic programming
Eisner(1996)提出了一个复杂度为O ( n 3 ) O(n^3)O(n
3
)的算法，它生成头部位于末尾而不是中间的解析项
Graph algorithms
为一个句子创建一个最小生成树
McDonald et al.’s (2005) MSTParser 使用ML分类器独立地对依赖项进行评分(他使用MIRA进行在线学习，但它也可以是其他东西)
Constraint Satisfaction
去掉不满足硬约束的边 Karlsson(1990), etc.
“Transition-based parsing” or “deterministic dependency parsing“
良好的机器学习分类器 MaltParser(Nivreet al. 2008) 指导下的依存贪婪选择。已证明非常有效。
三、Methods of Dependency Parsing
Transition-based dependency parsing (15 mins)
3.1 Greedy transition-based parsing
3.2 Basic transition-based dependency parser
利用一个栈和队列：初始时栈为空，队列中存储未处理的词，算法结束后栈中存储依存结构子树序列。
转移算法定义三种转移动作：
SH：将队列中的第一个元素移入栈顶，形成一个仅包含一个节点的依存子树；
RL：将栈顶的两棵依存子树采用左弧合并；
RR：将栈顶的两棵依存子树采用右弧合并；
3.3 Arc-standard transition-based parser
标准弧（Arc-standard）转移算法。
中文句子的栗子：他喜欢下象棋。
图源自 车万翔《基于预训练模型的自然语言处理》
3.4 MaltParser
我们需要解释如何选择下⼀步行动
Answer：机器学习
每个动作都由⼀个有区别分类器(例如softmax classifier)对每个合法的移动进行预测
最多三种无类型的选择，当带有类型时，最多∣ R ∣ × 2 + 1 |R| \times 2+1∣R∣×2+1 种
Features：栈顶单词，POS；buffer中的第⼀个单词，POS；等等
在最简单的形式中是没有搜索的
但是，如果你愿意，你可以有效地执行⼀个 Beam search 束搜索(虽然速度较慢，但效果更好)：你可以在每个时间步骤中保留 k个好的解析前缀
该模型的精度略低于依赖解析的最高水平，但它提供了非常快的线性时间解析，性能非常好
3.5 传统的特征表示
Conventional Feature Representation
传统的特征表示使用二元（0和1表示）的稀疏向量，维度为1 0 6 − 1 0 7 10^6- 10^710
6
−10
7
之间。
特征模板：通常由配置中的1 ~ 3个元素组成
Indicator features
3.6 依存分析的评价和表现
Evaluation of Dependency Parsing: (labeled) dependency accuracy：
对每个单词标上序号，列出每个依存关系对应的序号和类型。分为两种正确率的计算：
UAS (unlabeled attachment score) 指 无标记依存正确率 ，不考虑依存关系的类型，只考虑依存关系的对应单词是否正确，如父节点被正确识别的准确率；
LAS (labeled attachment score) 指有标记依存正确率，同时考虑依存关系的对应单词以及依存关系类型，即词的父节点，以及与父节点的句法关系都被正确识别的概率。
3.6 Handling non-projectivity
提出的弧标准算法只构建投影依赖树
头部可能的方向
在非投影弧上宣布失败
只具有投影表示时使用依赖形式
CFG只允许投影结构
使用投影依赖项解析算法的后处理器来识别和解析非投影链接
添加额外的转换，至少可以对大多数非投影结构建模（添加⼀个额外的交换转换，冒泡排序）
转移到不使用或不需要对投射性进行任何约束的解析机制(例如，基于图的MSTParser)
四、Neural dependency parsing
Indicator Features的问题
稀疏
不完整
计算复杂：超过95%的解析时间都用户特征计算
