目录

一、引言

二、传统的依存句法分析方法

1、生成式的句法分析模型

2、判别式的句法分析模型

3、决策式的句法分析模型

4、约束满足的句法分析模型

三、基于深度学习的依存句法分析方法

1、基于图模型的依存句法分析（Graph-based）

2、基于转移的依存句法分析（Transition-based）

---

看了斯坦福大学cs224依存分析的公开课后，对于依存分析仍是一脸茫然，所以查阅相关资料，对自然语言处理的依存分析这一方向做了一个简单的综述。笔者能力有限，如有错误，欢迎指正。

参考：

自然语言处理基础技术之依存分析

基于深度学习的依存句法分析

依存句法分析

常宝宝. 基于深度学习的图解码依存分析研究进展[J]. 山西大学学报:自然科学版, 2017(3).

石翠.依存句法分析研究综述[J].智能计算机与应用,2013,3(06):47-49.

杨振鹏.依存句法分析方法综述[J].无线互联科技,2018,15(22):114-116.

一、引言

句法分析（syntactic parsing）是自然语言处理中的关键技术之一，它是对输入的文本句子进行分析得到句法结构的处理过程。对句法结构进行分析，一方面是语言理解的自身需求，句法分析是语言理解的重要一环，另一方面也为其它自然语言处理任务提供支持。例如句法驱动的统计机器翻译需要对源语言或目标语言（或者同时两种语言）进行句法分析；语义分析通常以句法分析的输出结果作为输入以便获得更多的指示信息。

根据句法结构的表示形式不同，常见的句法分析任务分为：

• 句法结构分析（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）等。作用是对句子进行深层的句法以及语义分析。

下面主要介绍依存句法分析，依存句法分析是针对句子中的词汇以及词汇之间的依存关系。

依存句法分析以谓词为句子的研究中心，其他成分与动词直接或间接地产生联系。“依存”指词与词之间支配与被支配的关系，这是一种偏序关系。处于支配地位的成分称为支配者（governor，regent，head），处于被支配地位的成分属于从属者（modifier，subordinate，dependency）。句子的依存结构有三种表示方式：

 

在示例中，对于主谓关系，谓词“是”是支配者，指示代词“北京”是从属者；而“首都”在动宾关系中是从属者，在定中关系中又成了支配者。

依存分析器的性能评价：

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

二、传统的依存句法分析方法

1、生成式的句法分析模型

生成式模型采用联合概率（其中，已知序列为x，依存分析结构为y，模型参数为θ），生成一系列依存句法树，并赋予其概率分值，然后采用相关搜索算法找到概率最高的分析结果作为最后输出。

最终目标：从训练中获取使联合概率取得最大值的参数θ，得分最高的依存结构树。

（1）基于概率的上下文无关文法PCFG方法，是生成式方法的基础。这种方法与由短语结构句法分析算法相似，采用全局搜索，生成多棵依存树，每个句子对应一棵或多棵依存树，最后系统输出概率最高的那棵树

参考PCFG模型

（2）二元词汇亲和模型，该模型加入了词汇信息，将词性与词形联合。一个标记序列由马尔可夫过程产生，链接关系对词汇是敏感的，每一对词是否可以构成链接关系的决策依赖于词汇信息，最终生成词性、词形和链接关系的联合概率模型。

一个标记序列（tags）由马尔可夫（Markov）过程产生，观察每一对词（words）是否可以构成链接关系（link）的决策依赖于[tags, words]，即link对词汇是敏感的。最终生成words，tags，links的联合概率模型。

（3）选择偏好模型，该模型加入了词的选择偏好信息，不再穷举所有连接再根据约束进行剪裁，而是限制模型为每个词只选择一个父结点。

对比（2）和（3），二元词汇亲和模型后半部分考虑任意两个词的关系，再根据是否有依存关系来进行剪枝；选择偏好模型则直接根据偏好来为每个词仅选择一个父结点。

（4）递归生成模型，该模型中每个词的左子结点和右子结点分别由各自的马尔可夫模型顺次产生：左子结点的产生方向是自右向左，右子结点的产生方向自左向右的。每一个结点的生成建立在支配词和它前一个子结点上，是自顶向下的递归生成式模型。

生成式句法分析模型优点：

• 准确率较高

缺点：

• 采用联合概率模型，在进行概率乘积分解时做了不合理的假设，不易加入语言特征
• 因为采用全局搜索，算法复杂度较高，一般为O(n^3)或O(n^5)
• 不易处理非投射现象

2、判别式的句法分析模型

判别式模型为了得到正确的分类边界，从非单一样本的数据中抽取出共有的特征。判别式句法分析采用条件概率模型。

目标函数：

（1）最大生成树句法分析，基本思想：在点和边组成的生成树中找到加权和分值最高的边的组合。生成树中任意两个由词表示的结点之间都有边，根据特征和权值为每条边打分，求解最佳分析结果转化为搜索打分最高的最大生成树问题

（2）最大熵。在英语的句法分析中，Ratnaparkhi最早引入了最大熵的方法，他利用上下文特征，通过最大熵的方法来预测下一步要执行的操作。其上下文特征主要包括：成分的核心词，核心词的组合，非特定组合信息，以及部分已完成的子树信息。

（3）支持向量机。支持向量机是一种基于统计学习原理的线性分类器，可以使构成的超平面分割训练数据时，能够获得最大的边缘。支持向量机具有良好的应用效果，在自然语言处理中应用较为广泛，常用于文本分类等问题。支持向量机的主要缺点是其训练效率偏低，并且对于输出结果不能准确地给出各个输出结果的概率分布，这就限制了它在概率需求较强的任务中的应用，给一些利用概率结果的处理和应用带来了麻烦。

（4）决策树。决策树是另一种比较典型的判别学习方法。它是一种“问卷表”方式的做法，利用一系列的查询问答来判断和分类某一模式，它将全部问题集用一颗有向树表示，对非度量数据而言效果较好。在英语的句法分析中，决策树的方法在英语的宾州英文树库PTB上取得了83%以上的正确率。决策树学习方法也存在一些问题，例如，在高维问题的处理上效果不够理想。

判别式句法分析模型优点：

• 避开了联合概率模型所要求的独立性假设
• 较好的可计算性，使诸多机器学习和运筹学的方法得以应用，并可处理非投射现象
• 分析准确性较高

缺点：

• 整句内的全局搜索，不易使用动态特征
• 全局搜索使得算法复杂度较高

3、决策式的句法分析模型

基本思想：模仿人的认知过程，按照特定方向每次读入一个词。每读入一个词，都要根据当前状态做出决策（比如判断是否与前一个词存在依存关系）。分析过程可以看作是一步步作用于输入句子之上的分析动作的序列。

决策式句法分析模型的典型代表是移进-归约状态转移模型。移进-归约状态转移模型在分析过程中维护一个堆栈和一个队列，堆栈用以存储到目前为止所有的依存子树，队列存储尚未被分析到的词。堆栈顶端和队列头部确定了当前分析器的状态，依据该状态决定进行移进、归约或建立栈顶元素与队首元素的依存关系的操作，从而转入新状态。

决策式句法分析的优点：

• 算法可以使用之前产生的所有句法结构作为特征
• 可以达到线性复杂度O(n)

缺点：

• 以局部最优的加和代替全局最优，导致错误传递
• 不可处理非投射现象，准确率稍逊于全局最优算法

4、约束满足的句法分析模型

将依存句法分析过程看作可以用约束满足问题（Constraint satisfaction problem，CSP）来描述的有限构造问题（finite configuration problem）。它不像上下文无关文法那样探索性地生成，而是根据已规定好的约束进行裁剪，把不符合约束的分析去掉，直到留下一棵合法的依存树。

存在的问题：可能不存在能满足所有约束的分析树，也可能有多个树满足所有约束，无法消歧。

三、基于深度学习的依存句法分析方法

1、基于图模型的依存句法分析（Graph-based）

基于图解码依存分析方法将依存分析视为一个搜索问题，令x代表由n个词组成的句子（其中代表人为添加的根词ROOT）。若用代表句子x所有可能的依存树组成的集合，则该搜索问题可以描述为：

也就是在其所有候选的依存树中，寻找得分最高的依存树。其中，依存树y的得分需要通过评分函数score(x, y)计算。

一个完整的图解码依存分析器由三个部分组成：评分模型、分析算法和学习算法。

评分模型计算候选依存树的得分，评分模型给出得分的高低反映了依存树正确性的高低。

分析算法则根据评分模型给出的得分，从众多候选依存树中找出得分最高的依存树，并把该依存树作为句子的分析结果输出。

在数据驱动的算法中，合理的评分模型需要通过一定的学习算法从作为统计样本的依存树库中学习得到。

在图解码依存分析方法中，评分模型的设计和选择居于核心位置。

深度图解码分析模型采用低维稠密的特征表示，基于神经网络的非线性评分模型，依靠模型的自我特征学习能力，来自动学习远距离依存的特征。

（1）评分模型

深度图解码依存模型基本采用一阶分解策略，因而评分模型形式上可写为：

其中，代表依存边的特征表示，θ代表需要通过训练学习来获取的网络模型参数。

1）Pei等人最早使用多层感知机作评分模型：

该评分模型是一个单隐层的多层感知机模型，特征向量a首先经过一个非线性的隐层变换得到特征的隐层表示h，再经过一个全连接的线性输出层得到依存边的得分向量。

此时计算出的是一个|L|维向量，即，其中|L|代表依存关系标签的数量。该向量的第i维的值即为依存边类型为的得分。

隐层中的非线性激活函数g可以用常规的sigmoid函数、tanh函数等。为了更好地对特征之间的交互作用进行建模，Pei等人提出tanh-cube的特殊激活函数：

该函数可以很好地模拟传统模型中的组合特征效果，使得人们在设计特征时只专注于设计一些基本特征，而将组合特征的选择和学习交由神经网络模型自行学习决定。

Pei等没有把依存边方向作为特征进行建模，而是在隐层和输出层均采用了与方向相关的变换参数。

2）Kiperwasser等人同样采用单隐层的多层感知机模型，没有采用与方向相关的模型参数，对于左向边和右向边，模型共享同样的参数，激活函数使用tanh。把依存标签的预测与依存边的预测分开进行，首先进行无标签依存分析，然后再通过另一个多层感知机计算依存标签的得分。因为经过无标签依存分析后，无须对所有可能的依存边进行标签预测，从而可以提高运行效率。评分模型：

3）Dozat等人受到双线性注意力机制模型的启发，提出了一种基于双仿射变换的评分模型。采用了将依存边预测和依存关系标签预测分开进行的策略。评分模型：

在双仿射变换模型中，以及分别代表中心词和依存词的特征向量表示。针对依存边预测和关系标签预测，Dozat等人采用了不同的特征表示。从形式上看，双仿射映射函数中的可以显示捕捉中心词和依存词特征之间的交互作用。同时，Dozat等人也认为可以用来捕捉中心词所能拥有的依存词的先验分布信息，因为如果中心词的类型不同，其所能拥有的依存词的数量也会不同，例如，动词倾向于拥有更多的依存词，而虚词则倾向于没有依存词。与之类似，标签评分函数中的偏置项也可以用来捕捉类别标签的先验分布规律，因为并非所有的标签类别都按照同样的规律出现。另外，是维度为的张量矩阵，是维度为的矩阵，因为标签得分需要针对标签集中的每个标签进行。

（2）深度特征提取

除了在评分模型上的改进外，深度图解码依存分析模型也展现出了优秀的特征表达和学习能力。深度图解码依存分析的特征表示不再采用高维稀疏表示，而是采用低维稠密的特征表示；而且深度模型的特征学习能力极大减轻了人工特征工程工作。

1）特征的低维嵌入表示

在传统的图解码依存分析模型中，特征表示为高维稀疏向量，特征之间相互独立。这种特征表示方法无法捕捉特征之间的共性，也存在严重的数据稀疏问题。

在深度图解码依存分析模型中，特征被映射为低维空间中的稠密向量，句法和语义性质相近的特征被嵌入到空间中邻近的位置，使其在向量表示上呈现出共性或相似性。

具体而言，令Ｄ代表所有特征组成的集合，即，其中的每个特征均被表述为一个嵌入向量，所有特征向量堆叠即可形成一个嵌入向量矩阵。该矩阵的每一列对应着一个特征的嵌入向量表示。特征的嵌入向量并不需要人为设定，而是作为模型参数的一部分，同评分模型一起经由模型训练自动习得（即嵌入层）。一般而言，在训练开始时，这些特征向量可通过随机初始化的方式设定初值，并随同评分模型一起训练并最终得到特征的合理嵌入表示。但对于一些取值为词的特征，也常常采用word2vec、Glove等标准词向量学习技术基于大规模未标注语料预先学习词向量，并把得到的词向量用作特征向量的初值，一般把这种做法称作预训练（pre-training）机制。大部分研究都表明，引入预学习机制有助于改善特征向量学习的质量，从而对依存分析结果产生积极影响。

2）组合特征的自动学习

传统图解码依存分析模型的子图评分模型为基于特征的线性模型，特征之间相互独立。为了捕捉特征与模型评分之间的非线性关系，需要加入组合特征，即把多个基本特征组合起来作为新的特征。组合特征的引入增加了特征工程的难度，同时也爆炸地扩大了特征空间，增大了数据稀疏的风险和特征提取的时空代价。

Pei等人在图解码模型中取消设置组合特征，只使用数量有限的基本特征（原子特征）。特征之间的交互影响通过打分模型中非线性机制加以学习体现。模型输入特征是若干原子特征，形式上是这些原子特征向量的拼接向量：

激活函数为之前提到的tanh-cube函数，这个函数不仅表现出较强的组合特征学习能力，而且能加快模型训练的收敛速度。

取消组合特征可以在使用较少的特征模板情况下达到更高的分析精度与更快的分析速度。

3）基于LSTM模型的特征学习

Wang等人、Kiperwasser等人以及Dozat等人的模型中，首先通过双向LSTM模型生成句中词的双向LSTM编码向量，并用学到的编码向量取代人工特征用作评分模型的依据。 

正向LSTM模型，是从一个从左向右对序列编码，捕获了之前的语境信息；逆向LSTM模型，从右向左对序列进行编码，捕获了之后的语境信息。

若待分析的句子为，相应的词类序列为，以及所对应的嵌入向量为和。采用双向LSTM编码机制可以表示为如下形式：

首先将句子中词及其词类的嵌入向量和通过某种方式进行处理（如拼接或相加，然后通过一个单层ReLU网络）变换为双向LSTM模型的输入向量。在正向LSTM编码和逆向LSTM编码向量的组合方法上（即），可以采用传统的拼接方式或是两个向量相加的方式，也可以使用ReLU网络对其进行处理。

经由双向LSTM编码得到的编码向量与一般的孤立词向量不同，结合了词在句子中的语境信息，深度图解码依存分析模型将其视作是对词的全局特征表示，可以用来取代传统模型中由人工设计的特征。

Wang等人设计的双向LSTM编码机制：

首先将句子中词及其词类的嵌入向量和拼接起来，通过一个单层ReLU网络变换为双向LSTM模型的输入向量。正向LSTM编码和逆向LSTM编码向量的组合通过将两个向量相加来实现。

Kiperwasser等人设计的双向LSTM编码机制：

Kiperwasser等人对词和词类的嵌入向量、正向LSTM编码向量和逆向LSTM编码向量均采用传统的拼接方式。

Dozat等人让正向LSTM编码向量和逆向LSTM编码向量的拼接向量通过一个单层ReLU变换，将其转换成一个维度较低的向量。这样做可以缩减维度，也可以摈弃一些噪音信息。这种加入ReLU变换层的双仿射模型称为深度双仿射模型。在进行单层ReLU变换时，Dozat等人对依存边预测和标签预测的双向LSTM编码使用了不同的变换参数。做法为：

（3）模型训练

传统图解码依存分析大多采用最大化间隔原则的训练方法，深度图解码依存分析模型训练基本延续了这一训练原则。给定训练实例，其中，Ｄ代表训练集，是句子的正确依存树，令代表句子所有可能的依存分析树。最大间隔原则的目标是寻求一组最佳模型参数θ，使得对于而言，其正确依存树的得分比错误依存树得分至少大一个间隔，且该间隔的大小正比于错误依存树的结构损失，即：

错误依存树的结构损失通常定义为：

其中，n指句子的单词数量，k是比例参数。代表句子中第j个词在依存树中所对应的中心词，函数 1[r] 的值：若r为true则函数值为1，否则为0.结构损失实际上统计了依存树相对于正确依存树的错误依存边数量，让间隔正比于结构损失可以增加对错误严重的依存树的惩罚力度。

 给定ｍ 个句子组成的依存树库，基于最大间隔原则的依存分析模型训练可表述为如下的优化问题：

在具体实现时，还可以在优化函数中增加不同的正则项，以使参数具有一些人们期望的性质。

该优化问题可以选择不同的优化算法加以实现，深度学习模型中惯常使用梯度下降算法或变种（AdaGrad算法、Adam算法）。最大间隔训练方法并非图解码依存分析模型训练的唯一方法，常见的优化原则还包括交叉熵原则。

2、基于转移的依存句法分析（Transition-based）

 基于转移的依存句法分析的基本模型如上述决策式句法分析模型的典型代表移进-归约状态转移模型，下面介绍基于前馈神经网络的基于转移依存句法分析：

（1）模型结构

基于转移的分析过程的格局C可以用一个三元组(S，I，A)来表示，S 是堆栈，I 是未处理的结点序列，A 是依存弧集合。用于分析动作决策的特征向量即取自这样的三元组。基于前馈神经网络的模型利用一个神经网络对分析过程中的C提取特征，并训练动作分类器。具体地，模型由输入层、嵌入层、隐含层和softmax 层组成：
       1、输入层。输入层的作用是从分析状态(S；I；A) 中抽取元特征（atomic feature），这些元特征包括词特征、词性特征和依存弧特征。
       2、嵌入层（embedding layer）。嵌入层由三个独立的子嵌入层组成，分别为词嵌入层、词性嵌入层和依存弧嵌入层，对应输入中的词特征、词性特征和依存弧特征。这些嵌入层的作用是将输入层抽取的离散稀疏特征转换成稠密特征。
       3、隐含层。隐含层从嵌入层获得三种稠密特征输入，并对其做非线性变换。
       4、softmax 层。与其他softmax 层的作用相同，该层用于预测多分类的结果。

（2）元特征

 以前的基于特征工程的依存句法分析器过于依赖于专家定义的特征集合，因此研究人员为基于转移的依存句法分析方法定义了一组特征模板（见下表），这组特征显著提高了依存句法分析器的性能。这些特征被分成了三类：词特征（），词性特征（）和弧特征()。各个特征所代表的含义为：
       1、表示栈S中的第i个词；
       2、表示输入缓冲I中的第j个词；
       3、表示取词的第i个左儿子；
       4、表示取词的第i个右儿子。

 在上表中，即为栈S中的第0个词，即栈顶的单词；为输入缓冲I中第二个词；即为栈顶词的第一个左儿子；即为栈顶词的第二个左儿子。可以注意到：元特征模板中并不包含输入缓存中的词的儿子信息，因为输入缓存中的词尚未被分析，其没有儿子节点。
       将以上位置信息分别与w (word embedding)，p (pos) 或l (link)组合，即可得到不同位置上的词特征、词性特征或依存弧特征。例如，为栈顶单词的词特征；为输入缓冲I中第二个词的词性特征；表示最右儿子的词特征；表示最左儿子的词性特征。

（3）执行过程

1、依存算法：
       在执行过程中，模型采用标准的移进-归约算法（arc-standard方法），即：
       • SHIFT：将从buffer I 中弹出，并将其压入栈S.
       • LEFT-ARC(l)：在栈顶第一个词与第二个词之间添加一个弧l，将从栈S中删除。将弧() 添加到A 中。
       • RIGHT-ARC(l)：在栈顶第二个词与第一个词之间添加一个弧l，将从栈S中删除。将弧()添加到A 中。
       2、学习算法与分类模型：
       作为一个依存句法分析器的重要组成部分，分类模型的作用为预测分析动作，学习算法的作用为从训练数据中学习模型的参数。
       神经网络的输入层直接从分析格局C中抽取元特征。元特征的抽取如上图定义的特征。从表中可以看到，抽取的特征三个部分特征分别为18 个词特征、18 个词性特征和12 个依存弧特征。在分析过程中的每一步，输入层将从分析格局中抽取这些总共48 个特征，并对这48 个特征以词袋（bag of words）模型进行表示（即元素存在的位置为1，不存在的位置为0）。
       网络嵌入层的作用为将特征的稀疏表示转换成稠密表示。嵌入层分为三个部分：词嵌入层、词性嵌入层和依存弧嵌入层；这三个嵌入层分别从对应的三种输入层中获取特征（将BOW向量中元素为1的位置，置换成为相应的元素向量：如前18个词特征位，若有元素为1，则置换为该位置上词的word embedding；同理对于中间18个词性特征位和后12个依存弧特征位），得到48个特征向量。常识上，与词典大小相比，词性与依存弧弧的取值集合相对较小，故嵌入层中词性嵌入和弧嵌入的维度小于词嵌入的维度。
       模型中的隐含层将嵌入层的48 个特征向量进行首尾连接操作（也可以进行其他形式的feature fusion），将其组成一个特征向量。对特征向量进行线性与非线性变换操作，，为偏置。
       最后一层，为网络的输出层，使用softmax函数对转移动作进行分析和预测：，，是指依存句法分析系统中所有动作的集合，p是针对集合中每个元素的概率向量。

基于循环神经网络的Transition-based dependency模型： 

       基于循环神经网络的方法，和基于前馈神经网路的方法非常相似。实际上，在使用中，基于循环神经网络的方法更受欢迎，因为转移动作序列正好符合循环神经网络的时序处理优点。

       在应用循环神经网络时，每个时刻仍然是上述的输入层、嵌入层、隐含层等处理内容，只是会根据应用有所变化。转移动作序列，展开成时间序列处理。
 

依存句法分析

语法分析(syntactic parsing )是自然语言处理中一个重要的任务，其目标是分析句子的语法结构并将其表示为容易理解的结构(通常是树形结构)。同时，语法分析也是所有工具性NLP任务中较为高级、较为复杂的一种任务。 通过掌握语法分析的原理、实现和应用，我们将在NLP工程师之路上跨越一道分水岭。 本章将会介绍短语结构树和依存句法树两种语法形式，并且着重介绍依存句法分析的原理和实现。

12.1 短语结构树

语言其实具备自顶而下的层级关系，固定数量的语法结构能够生成无数句子。比如，仅仅利用下列两个语法规律，我们就能够生成所有名词短语。

• 名词短语可以由名词和名词短语组成。
• 名词短语还可以由名词和名词组成。

例如，“上海+浦东+机场+航站楼”，所以，汉语中大部分句子都可以通过这样的语法来生成。

在语言学中，这样的语法被称为上下文无关文法，它由如下组件构成:

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

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

1. 短语结构树

   短语结构语法描述了如何自顶而下的生成一个句子，反过来，句子也可以用短语结构语法来递归的分解。层级结构其实是一种树形结构，例如这句话“上海 浦东 开发 与 法制 建设 同步”，分解成如下图的短语结构树:

   

这样的树形结构称为短语结构树，相应的语法称为*短语结构语法**或上下文无关文法。至于树中的字母下面开始介绍。

1. 宾州树库和中文树库

   语言学家制定短语结构语法规范，将大量句子人工分解为树形结构，形成了一种语料库，称为树库( treebank )。常见的英文树库有宾州树库，相应地，中文领域有CTB。上图中叶子节点(词语)的上级节点为词性，词性是非终结符的一种，满足“词性生成词语”的推导规则。

   常见的标记如下:

   标记	释义
   IP-HLN	单句-标题
   NP-SBJ	名词短语-主语
   NP-PN	名词短语-代词
   NP	名词短语
   VP	动词短语

   但是由于短语结构语法比较复杂，相应句法分析器的准确率并不高，现在研究者绝大部分转向了另一种语法形式。

12.2 依存句法树

不同于短语结构树，依存句法树并不关注如何生成句子这种宏大的命题。依存句法树关注的是句子中词语之间的语法联系，并且将其约束为树形结构。

1. 依存句法理论

   依存语法理论认为词与词之间存在主从关系，这是一种二元不等价的关系。在句子中，如果一个词修饰另一个词，则称修饰词为从属词( dependent )，被修饰的词语称为支配词(head),两者之间的语法关系称为依存关系( dependency relation)。比如句子“大梦想”中形容词“大”与名词“梦想”之间的依存关系如图所示:

   

   图中的箭头方向由支配词指向从属词，这是可视化时的习惯。将一个句子中所有词语的依存关系以有向边的形式表示出来，就会得到一棵树，称为依存句法树( dependency parse tree)。比如句子“弱小的我也有大梦想”的依存句法树如图所示。

   

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

• 有且只有一个词语(ROOT，虚拟根节点，简称虚根)不依存于其他词语。

• 除此之外所有单词必须依存于其他单词。

• 每个单词不能依存于多个单词。

• 如果单词 A 依存于 B，那么位置处于 A 和 B 之间的单词 C 只能依存于 A、B 或 AB 之间的单词。

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

1. 中文依存句法树库

   目前最有名的开源自由的依存树库当属UD ( Universal Dependencies)，它以“署名-非商业性使用-相同方式共享4.0”等类似协议免费向公众授权。UD是个跨语种的语法标注项目，一共有 200 多名贡献者为 70 多种语言标注了 100 多个树库。具体到中文，存在4个不同领域的树库。本章选取其中规模最大的 UD_ Chinese GSD 作为示例。该树库的语种为繁体中文，将其转换为简体中文后，供大家下载使用。

   http://file.hankcs.com/corpus/chs-gsd-ud.zip

   该树库的格式为 CoNLL-U，这是一种以制表符分隔的表格格式。CoNLL-U 文件有10列，每行都是一个单词， 空白行表示句子结束。单元中的下划线 _ 表示空白， 结合其中一句样例，解释如表所示。

   

词性标注集合依存关系标注集请参考 UD 的官方网站:

http://niversaldependencies.org/guidelines.html

另一份著名的语料库依然是 CTB，只不过需要额外利用一些工具将短语结构树转换为依存句法树。读者可以直接下载转换后的 CTB 依存句法树库，其格式是类似于 CoNLl-U 的 CoNLL。

1. 依存句法树的可视化

   工具如下:

   • 南京大学汤光超开发的 Dependency Viewer。导入 .conll 扩展名的树库文件即可。
   • brat 标注工具。

   可视化工具可以帮助我们理解句法树的结构，比较句子之间的不同。

12.3 依存句法分析

依存句法分析( dependency parsing )指的是分析句子的依存语法的一种中高级 NLP任务，其输人通常是词语和词性，输出则是一棵依存句法树。 本节介绍实现依存句法分析的两种宏观方法，以及依存句法分析的评价指标。

1. 基于图的依存句法分析

   正如树是图的特例一样，依存句法树其实是完全图的一个子图。如果为完全图中的每条边是否属于句法树的可能性打分，然后就可以利用 Prim 之类的算法找出最大生成树( MST )作为依存句法树了。这样将整棵树的分数分解( factorize )为每条边上的分数之和，然后在图上搜索最优解的方法统称为基于图的算法。

   在传统机器学习时代，基于图的依存句法分析器往往面临运行开销大的问题。这是由于传统机器学习所依赖的特征过于稀疏，训练算法需要在整个图上进行全局的结构化预测等。考虑到这些问题，另一种基于转移的路线在传统机器学习框架下显得更加实用。

2. 基于转移的依存句法分析

   我们以“人 吃 鱼”这个句子为例子，手动构建依存句法树。

   • 从“吃”连线到“人”建立依存关系，主谓关系。
   • 从“吃”连线到“鱼”建立依存关系，动宾关系。

   如此，我们将一棵依存句法树的构建过程表示为两个动作。如果机器学习模型能够根据句子的某些特征准确地预测这些动作，那么计算机就能够根据这些动作拼装出正确的依存句法树了。这种拼装动作称为转移( transition),而这类算法统称为基于转移的依存句法分析。

12.4 基于转移的依存句法分析

1. Arc-Eager 转移系统

   一个转移系统 S 由 4 个部件构成: S = (C,T,Cs,Ct)，其中:

   • C 是系统状态的集合
   • T 是所有可执行的转移动作的集合。
   • Cs 是一个初始化函数
   • Ct 为一系列终止状态，系统进入该状态后即可停机输出最终的动作序列。

   而系统状态又由 3 元祖构成: C = (σ,β,A) 其中:

   • σ 为一个存储单词的栈。
   • β 为存储单词的队列
   • A 为已确定的依存弧的集合。

   Arc-Eager 转移系统的转移动作集合详见下表:

   动作名称	条件	解释
   Shift	队列 β 非空	将队首单词 i 压栈
   LeftArc	栈顶单词 i 没有支配词	将栈顶单词 i 的支配词设为队首单词 j，即 i 作为 j 的子节点
   RightArc	队首单词 j 没有支配词	将队首单词 j 的支配词设为栈顶单词 i，即 j 作为 i 的子节点
   Reduce	栈顶单词 i 已有支配词	将栈顶单词 i 出栈

对于上面的“人 吃 鱼”案例，Arc-Eager 的执行步骤如下:

装填编号	σ	转移动作	β	A
0	[]	初始化	[人,吃,鱼,虚根]	{}
1	[人]	Shift	[吃,鱼,虚根]	{}
2	[]	LeftArc(主谓)	[吃,鱼,虚根]	人主谓←−−吃人←主谓吃
3	[吃]	Shift	[鱼,虚根]	人主谓←−−吃人←主谓吃
4	[吃,鱼]	RightArc(动宾)	[虚根]	人主谓←−−吃,吃动宾−−→鱼人←主谓吃,吃→动宾鱼
5	[吃]	Reduce	[虚根]	人主谓←−−吃,吃动宾−−→鱼人←主谓吃,吃→动宾鱼
6	[]	LeftArc(核心)	[虚根]	人主谓←−−吃,吃动宾−−→鱼,吃核心←−−虚根人←主谓吃,吃→动宾鱼,吃←核心虚根

此时集合 A 中的依存弧为一颗依存句法树。

1. 训练原理

   对基于转移的依存句法分析器而言，它学习和预测的对象是一系列转移动作。然而依存句法树库是一棵树，并不是现成的转移动作序列。这时候就需要一个算法将语料库中的依存句法树转移为正确地转移动作序列。

   这里可以使用感知机进行训练得到转移动作序列

   训练句法分析器时，结构化感知机算法迭代式的优化线性模型，目标是使其将最高的分值赋予可抵达正确句法树的转移序列。

   训练分为以下几个步骤:

   • 读入一个训练样本，提取特征，创建 ArcEager 的初始状态 c。
   • 若 c 不是终止状态，反复进行转移序列，修正参数。
   • 算法终止，返回返回模型参数 w。

12.5 依存句法分析 API

1. 训练模型

   本节使用的语料库是 CTB8.0

   训练时间比较长，结果如下:

   人 人 N NN _ 2 nsubj _ _
   吃 吃 V VV _ 0 ROOT _ _
   鱼 鱼 N NN _ 2 dobj _ _
   UAS=83.3% LAS=81.0%
   

2. 标准化评测

   给定两棵树，一棵树为标准答案(来自测试集)，一棵树为预测结果，评测的目标是衡量这两棵树的差异。如果将树的节点编号，拆解为依存弧并分别存入两个集合 A ( 标准答案)和 B (预测结果)，则可以利用分类任务的 F1 评价指标。

   依存句法分析任务采用的评测指标为 UAS (unlabeled atachment score) 和 LAS (labeled attachment score )，分别对应忽略标签和包括标签的 F1 值。以 LAS 为例，具体计算方式如下:
   
   UAS 的计算也是同理，只不过将每条依存弧上的标签去掉后放人集合参与运算即可。相较于 LAS, UAS 仅仅衡量支配词的预测准确率，不衡量依存关系的准确率，一般分数更高。

   在上面的训练模型中已经做了评测

   UAS=83.3% LAS=81.0%
   

   这个分数说明，在测试集上有 83% 的支配词被准确预测，有 81% 的依存弧被准确预测。

12.6 案例: 基于依存句法分析的意见抽取

其实许多人都有一个疑问，依存句法分析究竟可以用来干什么。本节就来利用依存句法分析实现一个意见抽取的例子，提取下列商品评论中的属性和买家评价。

电池非常棒，机身不长，长的是待机，但是屏幕分辨率不高。

为了提取“电池”“机身”“待机”和“分辨率”所对应的意见，朴素的处理方式是在分司和词性标注之后编写正则表达式，提取名词后面的形容词。然而正则表达式无法处理“长的是待机”这样句式灵活的例子。

这时就可以对这句话进行依存句法分析，分析代码如下:

from pyhanlp import *

CoNLLSentence = JClass('com.hankcs.hanlp.corpus.dependency.CoNll.CoNLLSentence')
CoNLLWord = JClass('com.hankcs.hanlp.corpus.dependency.CoNll.CoNLLWord')
IDependencyParser = JClass('com.hankcs.hanlp.dependency.IDependencyParser')
KBeamArcEagerDependencyParser = JClass('com.hankcs.hanlp.dependency.perceptron.parser.KBeamArcEagerDependencyParser')
parser = KBeamArcEagerDependencyParser()
tree = parser.parse("电池非常棒，机身不长，长的是待机，但是屏幕分辨率不高。")
print(tree)

运行结果如下:

电池  电池  N NN  _ 3 nsubj _ _
非常  非常  A AD  _ 3 advmod  _ _
棒 棒 V VA  _ 0 ROOT  _ _
， ， P PU  _ 3 punct _ _
机身  机身  N NN  _ 7 nsubj _ _
不 不 A AD  _ 7 neg _ _
长 长 V VA  _ 3 conj  _ _
， ， P PU  _ 7 punct _ _
长 长 V VA  _ 11  top _ _
的 的 D DEC _ 9 cpm _ _
是 是 V VC  _ 7 conj  _ _
待机  待机  N NN  _ 11  attr  _ _
， ， P PU  _ 3 punct _ _
但是  但是  A AD  _ 18  advmod  _ _
屏幕  屏幕  N NN  _ 16  nn  _ _
分辨率 分辨率 N NN  _ 18  nsubj _ _
不 不 A AD  _ 18  neg _ _
高 高 V VA  _ 3 conj  _ _
。 。 P PU  _ 3 punct _ _

进行可视化后:

仔细观察，不难发现“电池”与“棒”、“机身”与“长”、“分辨率”与“高”之间的依存关系都是 nsubj (名词性主语)。

1. 利用这一规律， 不难写出第一版遍历算法， 也就是用个for 循环去遍历树中的每个节点。对于算法遍历树中的每一个词语， 如果其词性为名词且作为某个形容词的名词性主语，则认为该名词是属性，而形容词是意见。运行代码如下:

   def extactOpinion1(tree):
       for word in tree.iterator():
           if word.POSTAG == "NN" and word.DEPREL == "nsubj":
               print("%s = %s" % (word.LEMMA, word.HEAD.LEMMA))
   print("第一版")
   extactOpinion1(tree)
   

结果如下:

   第一版
   电池 = 棒
   机身 = 长
   分辨率 = 高

1. 虽然的确提取出了一些意见，然而后两个都是错误的。这一版算法存在的问题之一是没有考虑到“机身不长””“分辨率不高”等否定修饰关系。否定修饰关系在依存句法中的标记为 neg，于是我们只需检查形容词是否存在否定修饰的支配词即可。于是得出第二版算法:

   def extactOpinion2(tree):
       for word in tree.iterator():
           if word.POSTAG == "NN" and word.DEPREL == "nsubj":
               if tree.findChildren(word.HEAD, "neg").isEmpty():
                   print("%s = %s" % (word.LEMMA, word.HEAD.LEMMA))
               else:
                   print("%s = 不%s" % (word.LEMMA, word.HEAD.LEMMA))
   print("第二版")
   extactOpinion2(tree)
   

结果如下:

   第二版
   电池 = 棒
   机身 = 不长
   分辨率 = 不高

1. 接下来思考如何提取“待机”的意见，“待机”与“长”之间的公共父节点为“是”，于是我们得到第三版算法如下:

   def extactOpinion3(tree):
       for word in tree.iterator():
           if word.POSTAG == "NN":
             
              # 检测名词词语的依存弧是否是“属性关系”，
               # 如果是，则寻找支配词的子节点中的主题词
               # 以该主题词作为名词的意见。
               if word.DEPREL == "nsubj":  # ①属性
   
                   if tree.findChildren(word.HEAD, "neg").isEmpty():
                       print("%s = %s" % (word.LEMMA, word.HEAD.LEMMA))
                   else:
                       print("%s = 不%s" % (word.LEMMA, word.HEAD.LEMMA))
               elif word.DEPREL == "attr":
                   top = tree.findChildren(word.HEAD, "top")  # ②主题
   
                   if not top.isEmpty():
                       print("%s = %s" % (word.LEMMA, top.get(0).LEMMA))
   print("第三版")
   extactOpinion3(tree)
   

   结果如下:

   第三版
   电池 = 棒
   机身 = 不长
   待机 = 长
   分辨率 = 不高
   

至此，4 个属性被完整正确地提取出来了，读者可以尝试搜集更多的句子，通过分析句法结构总结更多的提取规则。