两大句法分析理论

存在不同的句法理论描写句子的句法结构

转换生成语法

转换生成语法主要为短语结构语法(Phrase structure grammar)

描写句子成分之间的组成关系(constituency relation)也叫成分语法(constituency grammars)

基于CFG的句法分析是面向短语结构语法理论的句法分析

依存句法(Dependency grammar)

描写句中词和词之间的依存关系(dependency relation)

依存句法理论

配价语法

配价语法作为依存句法的理论基础早已成为计算语言学的基础理论之一

配价理论

谓词论元

配价理论认为在一个句子中，动词处于中心地位
配价理论中的价就是指动词对句子中名词性成分的支配数量，也成为论元数量

论元脱落

在实际中，因为移位，隐含，省略等因素，动词的论元常常不能完整地凸显出来

空范畴

移位空范畴
隐含空范畴
省略空范畴

法国语言学家Lucien Tesnière(1893-1954)最早提出用句中词和词之间的依存关系描述句子的句法
结构。 (《结构句法基础》 ， 1959年)

与短语结构语法一样，也有许多现代语法理论建立在依存语法的基础上。如 Functional
Generative Description(1986)、 Meaning-Text Theory(1988)、 word grammar(1990)等。

NLP中，有大量面向依存语法的句法分析研究，即依存句法分析(Dependency Parsing)研究

依存关系(dependency relation)

句子中词和词之间存在一种从属和中心的关系

处于中心地位的词，称为中心词(head)，处于从属地位的词称为从属词(dependent)

head 有时也称作governor、 regent
dependent 有时也称作 modifier

依存关系是一种二元非对称关系，可以被进一步分成多种类型

两种分类

句法依存:如果有两类元素，其中有一类元素只是在另一类出现时才会出现
语义依存：某些词的出现只是为了限定其他词的意义

依存树

依存句法解析器工具

NLTK ： 可以显示句法树的树状图
LTP依存句法解析器：可以显示带有依存弧的依存树
Stanford Parser： 一个可以进行短语结构和依存结构分析的解析器

依存树满足的5个条件

中国著名的计算语言学家冯志伟提出依存树应满足5个条件

单纯节点条件
单一父节点条件
独立根节点条件
非交条件
互斥条件

句子的依存结构(dependency structure)

把句子中的词视作结点，词和词之间的依存关系视作边(或称弧)，句子结构可表示成带标记的有
向图，即依存图(dependency graph)

通常句子的依存图遵循如下限制

连通性限制：句子的依存表示构成连通图。 (connectivity)
单中心限制：句子中的每个词最多只有一个中心与之连接。 (single-head)
非环限制：句子依存图中不能有环。 (acyclicity)

可以证明，符合上述限制的依存图是一棵有根树，即依存树(dependency tree)。只有根结点没有与之关联的中心词。为了处理的方便，通常人为添加一个特殊的词ROOT作为根结点的中心词

投影性(projectivity)

依存弧可以表示为三元组(head, label, dependent)

令$w_{i}$为依存树中的结点，称$w_{i}$沿着依存弧可到达的结点(词)为$w_{i}$投影(projection)

投影性条件：若 $w_{i}$ 依存树中的所有投影组成句子中的连续子串，则称该结点满足投影性条件

若依存树中所有结点满足投影性条件，则依存树称为投影依存树(projective dependency tree)， 否则称为非投影依存树(non-projective dependency tree)。

依存语法

依存语法是一种词语法
依存结构中没有短语(成分)的概念
依存结构表示比短语结构表示简练
依存结构与短语结构存在大致的转换关系,目前有许多依存树库是通过短语结构树库转换生成的
通常认为依存语法更适合描述语序自由的语言: 德语、捷克语、荷兰语、土耳其语等
语言中大部分结构是投影结构
语序自由的语言中含有较多的非投影结构: 汉语、英语中的非投影结构较少

从短语结构树到依存树

短语结构树中通常不会标记词和词之间的依存关系
可以通过启发式规则(heuristics)确定成分的中心(head)成分

中心成分规则(Head rules)

让成分的其他组成成分依存中心成分
利用成分支配关系确定功能标记

给定$X \rightarrow Y_{1}Y_{2},...,Y_{n}$且 headword$(Y_{h}) \rightarrow$ headword$(Y_{d})$可依据成分支配关系$(Y_{h}, X, Y_{d})$确定相应依存关系。

依存句法分析

对给定的自然语言句子，分析并得到其依存句法树
依存句法分析的主要方法

基于图的依存分析(Graph-based dependency parsing)
基于转移的依存分析(Transition-based dependency parsing)

模型：寻找得分最高的依存树

$$\tilde{y} = \arg \max_{y \in y(x)} s(x,y)$$

x 待分析的句子， y(x) 是所有可能的依存树， s(x,y) 是依存树是 y 得分。

基于图的依存分析

评分模型(scoring model): 如何计算依存树的得分s(x,y)？
分析算法(parsing algorithm): 给定评分模型，如何搜索得分最高的依存树？

评分模型: 将依存树分解为子图(用c表示)，子图独立评分，依存树得分定义为子图得分之和

$$s(x ,y) = \sum_{c \in y} s(x,c)$$

弧-分解模型（一阶模型）

(1)、如何定义子图？

存在不同做法，最简单的是弧-分解模型(arc-factored model)

子图定义为依存边(弧)，依存树分解为依存边的集合
依存树的得分定义为所有依存边的得分之和

$$s(x,y) = \sum_{(i,j) \in y} s(i,j)$$

(i,j) 为树中的依存边，即依存树中存在依存边 $x_{i} \rightarrow x_{j}$

(2)、如何计算依存边的得分？

依存边的得分通常定义为一个特征向量与权重向量的內积

$$s(i,j) = \overrightarrow{w} \cdot \overrightarrow{f}(i,j)$$

$s(i,j) \neq s(j,i)$

特征选择

计算边(i,j)的得分，需要针对依存边提取特征
权重向量 $\overrightarrow{w}$ 是模型参数，需通过依存树库训练得到

通常通过结构化学习技术学习参数

参数学习

结构化参数学习基本思想

迭代训练
给定句子 x 及其标准依存树 y (gold-standard)
根据当前参数 $\overrightarrow{w}$ 计算得分最高的依存树 $y^{'}$
增加出现在 y 中但未出现在 $y^{'}$ 中的特征对应的权重
降低出现在 $y^{'}$ 中但未出现在 y 中的特征对应的权重

分析算法

依存分析可被视作据有向图求解最大生成树(Maximum Spanning Tree)的问题

给定句子 x 构造带权有向图 $G_{x} = (V_{x}, E_{x})$, 其中

结点集合: $V_{x} = \\{ x_{0} = ROOT ,x_{1},x_{2},...,x_{n} \\}$
有向边集合: $E_{x} = \\{(i,j): x_{i} \neq x_{j}, x_{i} \in V_{x}, x_{j} \in V_{x} - ROOT\\}$
边(i,j) 的权值为s(i,j)

$G_{x}$ 的生成树 $G_{x}^{'} = (V_{x}^{'}, E_{x}^{'})$

$V_{x}^{'} = V_{x}$, $E_{x}^{'} \subset E_{x}$
结点ROOT的入度为0， 其余结点的入度为1

$G_{x}$的最大生成树: $G_{x}$生成树中权值最大的树

对于投影结构依存树，需要满足投影性条件
可采用CKY算法、 Eisner算法

CKY算法

可以使用CKY分析算法进行依存句法分析

依存树可以转换为一种词汇化的短语结构树

叶子结点是句中的词
分支结点是相应成分的中心词

因此可通过CKY算法进行句法分析(Viterbi算法)

CKY算法的时间复杂度$O(n^{3}|G|)$, 其中|G|是文法规模
句子中任何两个词都可对应两条规则
利用CKY算法进行依存分析，时间复杂度是$O(n^{5})$

Eisner算法

在CKY算法中，表(chart)的单元格C[s,t]中存放的是对应$x_{s}x_{s+1},...,x_{t}$ 分析结果的完整子树。该子树由两个更小的子树组合形成

$$s(T) = s(T_{1}) + s(T_{2}) + s(h_{1},h_{2})$$

Eisner算法也是一种自底而上的分析算法
Eisner也是基于表的分析算法

在Eisner算法中，表的单元格C[s,t]中存放的是子树片段(span)，该片段可能是完整的子树，可能不是完整的子树

在一个span中，中心词(head)必须位于span的边界处
span内部的词不存在与span外部词的依存连接。也就是span和span组合时，依存连接只在span边界处发生
对应完整子树的span被称为complete span，不对应完整子树的span称作incomplete span

因为head位于span的边界， Eisner算法的复杂度为 $O(n^{3})$

Span的表示是一个四元组 (s,t,d,c)

s和t示span的起止位置
d表示head位置, left 或 right
c表示完成状态, complete或incomplete

数据结构: Csd
与CKY算法类似，自底而上填表，依次增加处理的span的长度

算法初始化： 长度为1的span，初始化两个complete span，分别为左中心和右中心， score为0。

算法总结

Eisner算法是CKY算法的改进$O(n^{5}) \rightarrow O(n^{3})$
Eisner算法仅能生成投影依存树
增加依存关系标记 (s,t,l,d,c) 和记录树结构
对于基于图的依存分析而言， Eisner算法是基础算法

高阶模型，代价是时间复杂度提高

对于非投影结构：朱-刘算法(Chu-Liu-Edmond Algorithm)

基于转移的依存分析

在短语结构句法分析中，常采用移入-归约(shift-reduce)策略进行句法分析。依存句法分析，也可以采用类似的策略

依存树是通过执行一个分析动作序列逐步构造出来的

句法分析始于一个初始格局(configuration)，应用分析动作后，产生新的格局，再应用分析动作，又产生更新的格局， ……

分析过程表现为一种格局转移过程，所以称为基于转移的依存分析。（transition-based dependency parsing）

待分析的句子为 $x = x_{0}x_{1},...,x_{n}$

分析格局 $c=(\delta, \beta, A)$, 其中

$\delta$ 是分析栈，存放处理中的结点(词)
$\beta$ 是输入缓冲区，存放尚未处理的结点(词)
A 是依存弧的集合，代表分析过程中得到的部分依存树

基于转移的系统是一个四元组$S = (C,T,c_{s}, C_{t})$

C分析格局的集合
T分析动作的集合
$c_{s}$是初始格局，通常$c_{s}(x) = ([x_{0}],[x_{1}x_{2},...,x_{n}],\emptyset)$
$c_{t}$是终止格局集合，通常$C_{t} = \\{c | c = (\delta,[],A), c \in C \\}$

栈与缓冲区的表示

栈 ： $\delta | i$ i是栈顶元素、 $\delta$是其余元素
缓冲区 ：$j|\beta$ j 是缓冲区头部元素, $\beta$为其余元素

基于转移的依存分析算法

arc-standard分析算法
arc-eager分析算法

两种分析算法支持不同的分析动作

arc-standard算法：三种分析动作
arc-eager算法：四种分析动作

arc-standard算法与arc-eager算法的区别

arc-standard算法会延迟进行RIGHT-ARC动作，要等待从属词的所有从属词均已完成分析后才进行RIGHT-ARC动作
arc-eager算法会尽早进行RIGHT-ARC动作，不等待从属词完成分析就会进行RIGHT-ARC动作

基于转移的依存分析本质上是非确定性的

每个分析格局下，有多种动作可同时进行。

在每个分析格局下，若能够确定可以进行的最佳动作，则算法变成确定性的分析算法

确定性分析算法时间复杂度为O(n)

在每个分析格局下，引入一个分类器，由分类器给出当前格局下的最佳分析动作

$$\tilde{t} = \arg \max_{t \in \Re(c)} s(c,t)$$

c是分析格局， $\Re(c)$是当前分析格局下所有可能的分析动作， s(c, t)是分析动作 t 得分

预测最佳分析动作，通常采用线性分类器

$$s(c,t) = \overrightarrow{w} \cdot \overrightarrow{f}(c,t)$$

针对分析格局提取特征，形成特征向量 $\overrightarrow{f}(c,t)$

特征选择

计算动作 t 的得分，需要针对分析格局提取特征

参数学习

权重向量 $\overrightarrow{w}$ 模型参数，需通过依存树库训练得到

需要将树库转换成分析动作转移序列，该转移序列称为Oracle转移序列
可采用任何分类器并进行相应的参数学习，如SVM、Perceptron等

依存分析算法比较

基于转移的依存分析采用greedy search策略，有错误积累问题
基于转移的依存分析具有高效的优势$O(n)$
Eisner算法采用Global search策略，没有错误积累问题
Eisner算法效率低于基于转移的依存分析$O(n^{3})$
两者均不能处理非投影依存结构

基于图的依存分析： Chu-Liu-Edmond算法
基于转移的依存分析： list-based分析算法