系统学习NLP（五）--句法分析

系统学习NLP（五）--句法分析

句法分析的基本任务是确定句⼦的语法结构或句⼦中词汇之间的依存关系。句法分析不是⼀个⾃然语⾔处理任务的最终⽬标，但它往往是实

现最终⽬标的关键环节。

句法分析分为句法结构分析和依存关系分析两种。以获取整个句⼦的句法结构为⽬的的称为完全句法分析，⽽以获得局部成分为⽬的的语法

分析称为局部分析，依存关系分析简称依存分析。

⼀般⽽⾔，句法分析的任务有三个：

判断输出的字符串是否属于某种语⾔

消除输⼊句⼦中词法和结构等⽅⾯的歧义

分析输⼊句⼦的内部结构，如成分构成、上下⽂关系等。

第⼆三个任务⼀般是句法分析的主要任务。

⼀般来说，构造⼀个句法分析器需要考虑两部分⼯作：⼀部分是语法的形式化表⽰和词条信息描述问题，形式化的语法规则构成了规则库，

词条信息等由词典或同义词表等提供，规则库与词典或同义词表构成了句法分析的知识库；另⼀部分就是基于知识库的解析算法了。

语法形式化属于句法理论研究的范畴，⽬前在⾃然语⾔处理中⼴泛使⽤的是上下⽂⽆关⽂法（CFG）和基于约束的⽂法，后者⼜称合⼀⽂

法。

简单的讲，句法结构分析⽅法可以分为基于规则的分析⽅法和基于统计的分析⽅法两⼤类。

基于规则的句法结构分析⽅法的基本思路是，由⼈⼯组织语法规则，建⽴语法知识库，通过条件约束和检查来实现句法结构歧义的消除。

根据句法分析树形成⽅向的区别，⼈们通常将这些⽅法划分为三种类型：⾃顶向下的分析⽅法，⾃底向上的分析⽅法和两者相结合的分析⽅

法。⾃顶向下分析算法实现的是规则推导的过程，分析树从根结点开始不断⽣长，最后形成分析句⼦的叶结点。⽽⾃底向上分析算法的实现

过程恰好想法，它是从句⼦符号串开始，执⾏不断规约的过程，最后形成根节点。

基于规则的语法结构分析可以利⽤⼿⼯编写的规则分析出输⼊句⼦所有可能的句法结构；对于特定领域和⽬的，利⽤有针对性的规则能够较

好的处理句⼦中的部分歧义和⼀些超语法（extra-grammatical）现象。

但对于⼀个中等长度的输⼊句⼦来说，要利⽤⼤覆盖度的语法规则分析出所有可能的句⼦结构是⾮常困难的，⽽且就算分析出来了，也难以

实现有效的消歧，并选择出最有可能的分析结果；⼿⼯编写的规则带有⼀定的主观性，还需要考虑到泛化，在⾯对复杂语境时正确率难以保

证；⼿⼯编写规则本⾝就是⼀件⼤⼯作量的复杂劳动，⽽且编写的规则领域有密切的相关性，不利于句法分析系统向其他领域移植。

基于规则的句法分析算法能够成功的处理程序设计语⾔的编译，⽽对于⾃然语⾔的处理却始终难以摆脱困境，是因为程序设计语⾔中使⽤的

知识严格限制的上下⽂⽆关⽂法的⼦类，但⾃然语⾔处理系统中所使⽤的形式化描述⽅法远远超过了上下⽂⽆关⽂法的表达能⼒；⽽且⼈们

在使⽤程序设计语⾔的时候，⼀切表达⽅式都必须服从机器的要求，是⼀个⼈服从机器的过程，这个过程是从语⾔的⽆限集到有限集的映射

过程，⽽在⾃然语⾔处理中则恰恰相反，⾃然语⾔处理实现的是机器追踪和服从⼈的语⾔，从语⾔的有限集到⽆限集推演的过程。

完全语法分析

基于PCFG的基本分析⽅法

基于概率上下⽂⽆关⽂法的短语结构分析⽅法，可以说是⽬前最成功的语法驱动的统计句法分析⽅法，可以认为是规则⽅法与统计⽅法的结

合。

PCFG是CFG的扩展，举个例⼦：

PCFG

当然，同⼀个符号不同⽣成式的概率之和为1。NP是名词短语、VP是动词短语、PP是介词短语。

基于PCFG的句法分析模型，满⾜以下三个条件：

位置不变性：⼦树的概率不依赖于该⼦树所管辖的单词在句⼦中的位置

上下⽂⽆关性：⼦树的概率不依赖于⼦树控制范围以外的单词

祖先⽆关性：⼦树的概率不依赖于推导出⼦树的祖先节点

根据上述⽂法，『He met Jenny with flowers』有两种可能的语法结构：

⽽且我们可以通过将树中的所有概率相乘，得到两棵⼦树的整体概率，从中选择概率更⼤的⼦树作为最佳结构。

与HMM类似，PCFG也有三个基本问题：

给定⼀个句⼦W＝w1w2…wn和⽂法G，如何快速计算概率P(W|G)

给定⼀个句⼦W＝w1w2…wn和⽂法G，如何选择该句⼦的最佳结构？即选择句法结构树t使其具有最⼤概率

给定PCFG G和句⼦W＝w1w2…wn，如何调节G的概率参数，使句⼦的概率最⼤

⾸先是第⼀个问题，HMM中我们⽤的是前向算法和后向算法来计算观察序列O概率，相似的，这⾥我们⽤的是内向算法和外向算法来计算

P(W|G) 。（下⾯的推导我没仔细看，不是我转本⽂的秋季饮食 ⽬的，本⽂只是想记住基本概念，再说，我想PCFG现在已经很少⽤了）

⾸先我们定义内向变量ij(A)，与前向变量相似但⼜有不同，ij(A)即⾮终结符A推导出W中字串wiw(i+1)…wj的概率。那P(W|G)⾃然就

等于1n(S)了，S是起始符号，计算的就是由起始符号S推导出整个句⼦W=w1w2…wn的概率。

所以只要有ij(A)的递归公式就能计算出P(W|G)，递归公式如下：

根据定义，ii(A)⾃然就等同于符号A输出wi的概率；⽽ij(A)的计算思路是，这个⼦串wiw(i+1)…wj可以被切成两部分处理，前⼀部分

wiw(i+1)…wk由⾮终结符号B⽣成，后⼀部分wkw(k+1)…wj由⾮终结符号C⽣成，⽽BC由A⽣成。这样将概率依次相乘，即可将⼀个⼤问

题划分为两个⼩问题处理，两个⼩问题⼜可以进⼀步划分直到不能划分为⽌，然后递归回来得到结果。

这⾥给⼀张内向变量计算⽅法⽰意图：

这个问题也可以⽤外向算法来解决。

⾸先定义外向变量，ij(A)是，初始符号S在推导出语句W=w1w2…wn的过程中，产⽣符号串w1w2…w(i-1)Aw(j+1)…wn的概率（隐含

着A会⽣成wiw(i+1)…wj）。也就是说ij(A)是S推导出除了以A节点为根节点的⼦树以外的其他部分的概率。

《统计⾃然语⾔处理（第⼆版）》这本书⾥讲错了，这⾥我给出我⾃⼰的理解，书⾥给的算法步骤如下：

很明显的错误，初始化都把结果初始化了，那这个算法还算什么，直接等于1就完了呗。

这是作者对外向变量定义理解模糊的问题，上⾯给了外向变量的定义，⾥⾯有⼀句话『隐含着A会⽣成wiw(i+1)…wj』，那问题在于，A会

⽣成wiw(i+1)…wj，这到底算是条件还是推论。

看这个算法的初始化的意思，说1n(A)，在A=S的时候，为1，不等于S为0，意思是什么？意思就是『隐含着A会⽣成wiw(i+1)…wj』这

句话是条件，1n(S)已经隐含了S⽣成W＝w1w2…wn了，所谓的w1w2…w(i-1)Aw(j+1)…wn也就不存在了，只剩下⼀个S->S了，所以

概率⾃然为1。

但是在第三步这个地⽅，作者理解成什么意思了呢？作者⼜把『隐含着A会⽣成wiw(i+1)…wj』这句话当成推论了，认为在1n(S)，⾥S

会⽣成W＝w1w2…wn是推论，那真是就正好了，要求的结果就是S⽣成W＝w1w2…wn，这不就结束了吗，结果就导致了这个算法第⼀步

初始化都把结果初始化了。

那我的理解是什么呢，通过这个公式计算出来的1n(S)，确实是正确的，意义实中国十大超市排名 际上也是包含了『隐含着A会⽣成wiw(i+1)…wj』这句话

是推论，但是右侧式⼦⾥由于不断递归⽽产⽣的1n(S)，是把『隐含着A会⽣成wiw(i+1)…wj』这句话当条件的，所以计算上没有问题。

我倾向于为第三步中的1n(S)加⼀个星号，以表明意义的不同。

书中还给了个外向变量的计算⽅法⽰意图，我觉得也是莫名其妙：

他说ij(A)是这两种情况的概率和，这我们知道j⽐i⼤，那这图⾥这个k既⽐i⼩⼜⽐j⼤，这不是搞笑吗。只能说图上这俩C就不是⼀个C，k

也不是⼀个k。

那我为什么会理解成⼀个呢，除了字母相同，他前⾯还这么讲『必定运⽤了形如B->AC或者B->CA的规则』、『运⽤B->AC或者B->CA两种

规则的情况』，这明显就是给⼈以顺序交换的误解。

另外，还在内向变量的使⽤上前后不⼀，可以说这本书⾥对外向算法的讲解是⾮常失败的。⽽且对外向算法的计算仍然需要⽤到内向算法的

递归，那真的直接⽤内向算法就好了，外向算法还要多定义变量。

然后是第⼆个问题，选择句⼦的最佳结构，也即给定⼀个句⼦W＝w1w2…wn和⽂法G，

选定拥有最⼤概率的语法结构树。这⼀问题与HMM中类似，仍然采⽤动态规划的思想去解决。最后利⽤CYK算法去⽣成拥有最⼤概率的语

法结构树。

第三个问题是给定PCFG G和句⼦W＝w1w2…wn，如何调节G的概率参数，使句⼦的概率最⼤，与HMM相对的，PCFG这⾥采⽤的算法

名叫内外向算法。与前后向算法相同，也属于⼀种EM算法，其基本思想是，⾸先给G的产⽣式随机地赋予⼀个概率值（满⾜归⼀化条

件），得到⽂法G0，然后根据G0和训练数据，可以计算出每条规则使⽤次数的期望值，⽤期望值进⾏最⼤似然估计，得到语法G的新参数

值，新的语法记作G1，然后循环执⾏该过程，G的参数概率将收敛于最⼤似然估计值。

PCFG只是⼀种特殊的上下⽂⽆关⽂法模型，根据PCFG的模型和句⼦，具体去对句⼦做语法分析，⽣成语法结构树，靠的是还是CYK算

法。CYK算法是⼀个⽤来判定任意给定的字符串W是否属于⼀个上下⽂⽆关⽂法的算法。

基于PCFG的句法分析模型存在有许多问题，⽐如因为PCFG没有对词汇进⾏建模，所以存在对词汇信息不敏感的问题。因此⼈们提出了词

汇化的短语结构分析器，有效的提升了基于PCFG的句法分析器的能⼒。

⽽且，我们上⾯也提到了PCFG的三个独⽴性假设，这也导致了规则之间缺乏结构依赖关系（就像HMM的三个假设也不完全合理⼀样），

⽽在⾃然语⾔中，⽣成每个⾮终结符的概率往往是与其上下⽂结构有关系的，所以有⼈提出了⼀种细化⾮终结符的⽅法，为每个⾮终结符标

注上其⽗节点的句法标记信息。

D. Klein提出了带有隐含标记的上下⽂⽆关⽂法（PCFG with latent annotations，PCFG-LA），使得⾮终结符的细化过程可以⾃动进

⾏，并且在使⽤EM算法优化时，为避免到达局部最优，对其进⾏了改进，提出了⼀种层次化的『分裂-合并』策略，以期获取⼀个准确并且

紧凑的PCFG-LA模型。基于PCFG-LA的Berkeley Parr作为⾮词汇化句法分析器的代表，⽆论是性能表现还是运⾏速度，都是⽬前开源

的短语结构分析器中最好的。其语法树如下图：

普通句法树与PCFG-LA句法树对照实例

这个x就是隐含标记，xi的取值范围⼀般是⼈为设定的，⼀般取1~16之间的整数。⽽且PCFG-LA也类似于HMM模型，原始⾮终结符对应

HMM模型中的观察输出，⽽隐含标记对应HMM模型中的隐含状态。

浅层语法分析（局部语法分析）

由于完全语法分析要确定句⼦所包含的全部句法信息，并确定句⼦中各成分之间的关系，这是⼀项⼗分苦难的任务。到⽬前为⽌，句法分析

器的各⽅⾯都难以达到令⼈满意的程度，为了降低问题的复杂度，同时获得⼀定的句法结构信息，浅层句法分析应运⽽⽣。

浅层语法分析只要求识别句⼦中的某些结构相对简单的独⽴成为，例如⾮递归的名词短语、动词短语等，这些被识别出来的结构通常称为语

块（chunk）。

浅层句法今天我值日 分析将句法分析分解为两个主要⼦任务，⼀个是语块的识别和分析，另⼀个是语块之间的依附关系分析。其中，语块的识别和分析

是主要任务。在某种程度上说，浅层句法分析使句法分析的任务得到了简化，同时也有利于句法分析系统在⼤规模真实⽂本处理系统中迅速

得到应⽤。

基本名词短语（ba NP）是语块中的⼀个重要类别，它指的是简单的、⾮嵌套的名词短语，不含有其他⼦项短语，并且ba NP之间结构

上是独⽴的。⽰例如下：

ba NP识别就是从句⼦中识别出所有的ba NP，根据这种理解，⼀个句⼦中的成分和简单的分为baNP和⾮ba NP两类，那么ba

NP识别就成了⼀个分类问题。

ba NP的表⽰⽅法有两种，⼀种是括号分隔法，⼀种是IOB标注法。括号分隔法就是将ba NP⽤⽅括号界定边界，内部的是ba NP，

外部的不属于ba NP。IOB标注法中，字母B表⽰ba NP的开端，I表⽰当前词语在ba NP内，O表⽰词语位于ba NP之外。

基于SVM的ba NP识别⽅法

由于ba NP识别是多值分类问题，⽽基础SVM算法解决的是⼆值分类问题，所以⼀般可以采⽤配对策略（pairwi method）和⼀⽐其

余策略（one vs. other method）。

SVM⼀般要从上下⽂的词、词性、ba NP标志中提取特征来完成判断。⼀般使⽤的词语窗⼝的长度为5（当前词及其前后各两个词）时识

别的效果最好。

基于WINNOW的ba NP识别⽅法

WINNOW是解决⼆分问题的错误驱动的机器学习⽅法，该⽅法能从⼤量不相关的特征中快速学习。

WINNOW的稀疏⽹络（SNoW）学习结构是⼀种多类分类器，专门⽤于处理特征识别领域的⼤规模学习任务。WINNOW算法具有处理⾼维

度独⽴特征空间的能⼒，⽽在⾃然语⾔处理中的特征向量恰好具有这种特点，因此WINNOW算法也常⽤于词性标注、拼写错误检查和⽂本

分类等等。

简单WINNOW的基本思想是，已知特征向量和参数向量和实数阈值，先将参数向量均初始化为1，将训练样本代⼊，求特征向量和参数向

量的内积，将其与⽐较，如果⼤于，则判定为正例，⼩于则判定为反例，将结果与正确答案作⽐较，依据结果来改变权值。

如果将正例估计成了反例，那么对于原来值为1的x，把它的权值扩⼤。如果将反例估计成了正例，那么对于原来值为1的x，把它的权值缩

⼩。然后重新估计重新更改权重，直到训练完成。

这其实让我想到了LR算法，因为LR算法也是特征向量与参数向量的内积，最后将其送到Sigmoid函数中去拿到判定结果，然后⼤于0.5的

为正例，⼩于0.5的为反例，实际上只要反过来，Sigmod函数输出0.5时候的输⼊就是WINNOW算法⾥的那个实数阈值。但是区别在于

WINNOW算法只判定⼤⼩，不判定概率，⽽LR利⽤Sigmoid函数给出了概率。LR利⽤这给出的概率，通过使训练集的⽣成概率最⼤化来

调整参数，⽽WINNOW则是直接朴素的错误情况来增⼤或缩⼩相关参数。⽬测LR因为使⽤了梯度下降，它的收敛速度要快于WINNOW，

⽽WINNOW的优势则在于可以处理⼤量特征。

基于CRF的ba NP识别⽅法

基于CRF的ba NP识别⽅法拥有与SVM⽅法⼏乎⼀样的效果，优于基于WINNOW的识别⽅法、基于MEMM的识别⽅法和感知机⽅法，

⽽且基于CRF的ba NP识别⽅法在运⾏速度上较其他⽅法具有明显优势。

依存语法理论

在⾃然语⾔处理中，我们有时不需要或者不仅仅需要整个句⼦的短语结构树，⽽且要知道句⼦中词与词之间的依存关系。⽤词与词之间的依

存关系来描述语⾔结构的框架成为依存语法，⼜称从属关系语法。利⽤依存语法进⾏句法分析也是⾃然语⾔理解的重要⼿段之⼀。

有⼈认为，⼀切结构语法现象可以概括为关联、组合和转位这三⼤核⼼。句法关联建⽴起词与词之间的从属关系，这种从属关系由⽀配词和

从属词联结⽽成，谓语中的动词是句⼦的中⼼并⽀配别的成分，它本⾝不受其他任何成分⽀配。

依存语法的本质是⼀种结构语法，它主要研究以谓词为中⼼⽽构句时由深层语义结构映现为表层语法结构的状况及条件，谓词与体词之间的

同现关系，并据此划分谓词的词类太子参的副作用 。

常⽤的依存于法结构龙舌 图⽰有三种：

计算机语⾔学家J. Robinson提出了依存语法的四条公理：

⼀个句⼦只有⼀个独⽴的成分

句⼦的其他成分都从属于某⼀成分

任何⼀个成分都不能依存于两个或两个以上的成分

如果成分A直接从属于成分B，⽽成分C在句⼦中位于A和B之间，那么，成分C或者属于成分A，或者从属于B，或者从属于A和B之间的某⼀

成分。

这四条公理相当于对依存图和依存树的形式约束：单⼀⽗节点、连通、⽆环和可投射，由此来保证句⼦的依存分析结果是⼀棵有根的树结

构。

这⾥提⼀下可投射，如果单词之间的依存弧画出来没有任何的交叉，就是可投射的（参考上⾯的两个有向图）。

为了便于理解，我国学者提出了依存结构树应满⾜的5个条件：

单纯结点条件：只有终结点，没有⾮终结点

单⼀⽗结点条件：除根节点没有⽗结点外，所有的结点都只有⼀个⽗结点

独根结点条件：⼀个依存树只能有⼀个根结点，它⽀配其他结点

⾮交条件：依存树的树枝不能彼此相交

互斥条件：从上到下的⽀配关系和从左到右的前于关系之间是相互排斥的，如果两个结点之间存在着⽀配关系，它们就不能存在于前于关系

这五个条件是有交集的，但它们完全从依存表达的空间结构出发，⽐四条公理更直观更实⽤。

Gaifman 1965年给出了依存语法的形式化表⽰，证明了依存语法与上下⽂⽆关⽂法没有什么不同..

类似于上下⽂⽆关⽂法的语⾔形式对被分析的语⾔的投射性进⾏了限制，很难直接处理包含⾮投射现象的⾃由语序的语⾔。20世纪90年代

发展起来了约束语法和相应的基于约束满⾜的依存分析⽅法，可以处理此类⾮投射性语⾔问题。

基于约束满⾜的分析⽅法建⽴在约束依存语法之上，将依存句法分析看做可以⽤约束满⾜问题来描述的有限构造问题。

约束依存语法⽤⼀系列形式化、描述性的约束将不符合约束的依存分析去掉，直到留下⼀棵合法的依存树。

⽣成式依存分析⽅法、判别式依存分析⽅法和确定性依存分析⽅法是数据驱动的统计依存分析中具有代表性的三种⽅法。

⽣成性依存分析⽅法

⽣成式依存分析⽅法采⽤联合概率模型⽣成⼀系列依存语法树并赋予其概率分值，然后采⽤相关算法找到概率打分最⾼的分析结果作为最后

输出。

⽣成式依存分析模型使⽤起感谢生活 来⽐较⽅便，它的参数训练时只在训练集中寻找相关成分的计数，计算出先验概率。但是，⽣成式⽅法采⽤联合

概率模型，再进⾏概率乘积分解时做了近似性假设和估计，⽽且，由于采⽤全局搜索，算法的复杂度较⾼，因此效率较低，但此类算法在准

确率上有⼀定优势。但是类似于CYK算法的推理⽅法使得此类模型不易处理⾮投射性问题。

判别式依存分析⽅法

判别式依存分析⽅法采⽤条件概率模型，避开了联合概率模型所要求的独⽴性假设（考虑判别模型CRF舍弃了⽣成模型HMM的独⽴性假

设），训练过程即寻找使⽬标函数（训练样本⽣成概率）最⼤的参数（类似Logistic回归和CRF）。

判别式⽅法不仅在推理时进⾏穷尽搜索，⽽且在训练算法上也具有全局最优性，需要在训练实例上重复句法分析过程来迭代参数，训练过程

也是推理过程，训练和分析的时间复杂度⼀致。

确定性依存⽅法

确定性依存分析⽅法以特定的⽅向逐次取⼀个待分析的词，为每次输⼊的词产⽣⼀个单⼀的分析结果，直⾄序列的最后⼀个词。

这类算法在每⼀步的分析中都要根据当前分析状态做出决策（如判断其是否与前⼀个词发⽣依存关系），因此，这种⽅法⼜称决策式分析⽅

法。

通过⼀个确定的分析动作序列来得到⼀个唯⼀的句法表达，即依存图（有时可能会有回溯和修补），这是确定性句法分析⽅法的基本思想。

短语结构与依存结构之间的关系

短语结构树可以被⼀⼀对应地转换成依存关系树，反之则不然。因为⼀棵依存关系树可能会对应多棵短语结构树。