自然语言处理 课件 第6章 句法分析

第六章句法分析目录成分句法分析依存句法分析句法分析工具及相关语料库第六章句法分析成分句法分析句法分析是自然语言处理的一项基本任务，该任务要求计算机以句为单位，根据给定的语法体系，自动推导出句子的语法结构，即将句子转化为一棵结构化的语法树。成分句法分析又称为短语结构分析，关注句子的语法构成规律，是根据美国语言学家乔姆斯基（Chomsky）提出的短语结构语法（phrasestructuregrammar,PSG）来分析句子所包含的语法单元。在成分句法分析中，乔姆斯基形式文法极为重要。第六章句法分析成分句法分析乔姆斯基形式文法可以表示为四元组：其中是非终结符的有限集合；是终结符的有限集合；是

中的初始符号，相当于语法范畴中的句子是重写规则，也称为生成规则，一般形式为，其中都是符号，中至少含有一个属于

中的符号文法G中不含非终结符的句子称为G生成的句子。由文法G

生成的语言记做L(G)，指G生成的所有句子的集合。第六章句法分析成分句法分析根据规则形式不同，可以将文法分为0型文法（无约束文法,unrestrictedgrammar,UG）、1型文法（上下文相关文法,context-dependentgrammar,CDG）、2型文法（上下文无关文法，context-freegrammar,CFG）、3型文法（正则文法,regulargrammar,RG）其中，上下文无关文法中所有的产生式左边只有一个非终结符，比如：上下文无关文法的描述能力强，可以描述自然语言中的大部分结构，同时又是可递归的。因此通过上下文无关文法构造句法分析器在自然语言处理中得到了广泛的应用。第六章句法分析成分句法分析成分句法分析的结果可以用句法树表示，具体分析过程就是按照语法规则对句子的终结符逐步归约为根节点的过程。规约过程中使用的语法规则一般用产生式表示，所以又叫做产生式规则，如:上述产生式规则左部只有一个非终结符号，属于上下文无关文法。第六章句法分析成分句法分析下图展示一个基于上下文无关文法的示例：其中，IP表示简单从句，HLN表示标题，NP表示名词短语，SBJ表示主语，PN表示代词，NN表示普通名词，NR表示专有名词，CC表示连词，VP表示动词短语，VV表示动词。第六章句法分析成分句法分析自然语言中存在大量的句法歧义现象，即一个句子有多个句法分析结果与其对应。下面展示一些句法歧义的例子，其中[]表示不同的短语划分：第六章句法分析成分句法分析上表中第5个示例对应的不同句法树：引起其句法歧义的原因是单字词“和”的语法性质不定。上图左边的句法树中，“和”的词性为P（介词），表示小王是小李结婚的对象，而右边的句法树中，“和”的词性为CC（连词），表示小王结婚了，小李也结婚了。第六章句法分析成分句法分析常见的成分句法分析方法：基于规则的方法、概率上下文无关文法、神经网络方法。基于规则的方法：基于规则的句法分析大致有三种策略：自底向上、自顶向下、自底向上与自顶向下相结合。自底向上的策略是从句子中的词语出发，将一个符号序列匹配归约为某个产生式规则的左部（即用产生式规则左边的符号来改写右边的符号），以逐渐减少符号序列长度直到只剩下开始符S为止。自顶向下的策略是从根节点符号S开始搜索，用某条产生式右边的符号来改写左边的符号，然后通过不同的方式搜索并改写非终结符，直到生成了输入的句子或者遍历了所有可能的句子为止。第六章句法分析成分句法分析基于规则的方法中，常用的句法分析算法有线图（chart）分析算法、CYK分析算法等。其中，线图法是一种很重要的分析方法，采用自底向上的策略，将每个词看作一个节点，通过在节点间连边的方式进行分析，该方法是基于上下文无关文法规则的分析方法，主要思想如下：第六章句法分析成分句法分析算法需要的数据结构主要有：算法过程中，引入了点规则的概念，用于表示规则右部被归约的程度，可以理解为点的左边都是匹配到的规则的一部分。如果点的左边是规则右部的所有内容，那么就说明规则右边已经被完全匹配。第六章句法分析成分句法分析线图法的优点是：简单、易实现。缺点是：算法效率低，时间复杂度为O(n3)；需要高质量的规则，因为分析结果与规则质量密切相关；难以区分歧义结构。线图法时间复杂度计算如下：设n

为输入句子的长度，C为上下文无关文法中的非终结符的数目，M为点规则的状态数目（大于规则的数目），显然M>C。由于待处理表中最大的元素个数为Cn2，所以线图中最大的元素数目为

Cn2，由于算法对于长度为n的输入句子要执行n次循环，因此，线图法最大执行的操作次数为O(n3)。上述基于规则方法的最大缺点就是难以区分或处理歧义结构。第六章句法分析成分句法分析概率上下文无关文法（ProbabilisticContext-FreeGrammar,PCFG）统计词与词、词与词组以及词组与词组之间的规约信息，并给出句子的概率。由于句法解析存在歧义性，有多个候选语法树，通过PCFG能够找出可能性最高的句法树，即概率最大的句法树。PCFG是上下文无关文法（CFG）的概率拓广，PCFG中规则的形式为：其中P

为该规则出现的概率，且满足约束：第六章句法分析成分句法分析对句子“Astronomerssawstarswithears”分别用PCFG和CFG进行句法分析的结果第六章句法分析成分句法分析基于PCFG的句法分析主要目标是在句法分析过程中计算整棵句法树出现的概率，对于有句法歧义的句子，认为概率最大的句法树为最佳句法树。如下图所示的例子，对于给定的句子S，存在两棵句法分析树t1与t2，且P(t1)>P(t2)，则句法分析树t1正确的可能性大于t2。第六章句法分析成分句法分析

第六章句法分析成分句法分析PCFGViterbi算法流程如下：基于PCFG方法的优点主要有：可以利用概率减少分析过程的搜索空间；可以对概率较小的子树剪枝，提高算法效率；还可以定量地比较句法树。第六章句法分析成分句法分析基于神经网络的方法研究者最早在句法分析过程中引入递归神经网络（RecursiveNeuralNetwork,RvNN），将处理对象在结构上分解为一系列相同的单元，这些单元组成的神经网络可以在结构上展开并传递信息。RvNN的单元结构和信息传递方式如下图所示。第六章句法分析成分句法分析在句法分析中，RvNN输出两个信息：句法分析树的分数

及其对应的句嵌入表示

。对句子“我弟弟准备一切用品”采用基于RvNN的句法分析过程示例：第六章句法分析成分句法分析评价指标成分句法分析需要评估句法分析器生成的树结构与标准树结构之间的一致程度。主要采用精确率（precision）和召回率（recall）两个指标来评价，定义如下：第六章句法分析目录成分句法分析依存句法分析句法分析工具及相关语料库第六章句法分析依存句法分析依存句法分析（DependencyParsing，DP）是基于法国语言学家特思尼耶尔（Tesniere）1959年提出的依存语法理论（dependencygrammar）来分析词与词之间的依存关系。它将句子分析成一棵依存句法树，描述出各个词语之间的依存关系，即指出词语之间的句法搭配关系。这种搭配关系和语义相关联。依存语法理论与乔姆斯基生成语法等传统语言学理论有明显的区别。传统语言学突出句子中主语的地位，句中其它成分称为谓语。依存语法打破了这种主谓关系，认为谓语中的动词是一个句子的中心，其他成分与动词直接或间接产生联系，其重点是描述词与词之间的关系。第六章句法分析依存句法分析依存句法的句法结构由词汇组成，词汇之间由二元非对称关系连接，这些关系叫作依存关系。依存关系可用一个有向弧表示，该有向弧叫做依存弧，方向由支配词指向从属词。每个依存弧上有一个标记，表示该依存对中的两个词之间的依存关系类型。通常支配词体现了主要语法和语义特征；而从属词在语义上从属于支配词，起修饰补充支配词的作用，所以也称为修饰词。由于支配词和从属词在一般情况下是不能互换语义角色的，因此依存关系是非对称关系。依存句法树是非对称的有向树，上层节点是下层节点的支配词，越接近根节点越能够表达句子的语义。第六章句法分析依存句法分析1970年，研究者通过对句子中的依存关系进行约束，提出了依存语法的4条公理：（1）一个句子中只有一个成分是独立的。（2）其他成分直接依存于某一成分。（3）任何一个成分都不能同时依存于两个或两个以上的成分。（4）如果成分A直接依存于成分B，而成分C在句子中位于A和B之间，那么成分C或者依存于A，或者依存于B，或者依存于A和B之间的某一成分。第六章句法分析依存句法分析公理(1)∼(3)通常被认为是具有良好合式性的依存结构的本质特征。公理(1)(2)表明句子中只有一个词可以是没有支配词的，这个词通常被称为句子的中心词，其他所有的词都应该具有支配词。公理(3)表明除了句子的中心词外所有词的支配词都只能有一个。根据公理(1)∼(3)，可以看出任何句子的依存结构都可表示为依存句法分析树。树中的节点为句中的词，根为句子的中心词，边连接了具有直接依存关系的两个词。通过树中的路径，任意两个词直接或间接发生依存关系。公理(4)表明了依存结构具有投影性，即位于词A和词B之间的词C不能依存于A和B之外的其他词。这个性质表明依存句法分析树上不可能存在交叉的边。第六章句法分析依存句法分析下面展示一个具体的依存句法分析示例，对句子“外资企业成为外贸重要增长点”进行依存句法分析。图中带箭头弧线代表两个词存在的依存关系，从支配词指向从属词，如“企业”是“外资”的支配词。可以看出，依存句法分析就是分析句子的“主谓宾”、“定状补”这些语法成分及其关系。第六章句法分析依存句法分析常见的依存关系：第六章句法分析依存句法分析目前主流的数据驱动的依存句法分析方法主要有：基于图（graph-based）的方法、基于转移(transition-based)的方法和基于神经网络的方法。基于图的方法将依存句法分析问题看成从完全有向图中寻找最大生成树的问题，对于给定的句子x

和模型参数，在所有可能的候选句法树（即从根节点出发，包含句子中所有词的有向树）集合

中，找到概率最大的句法树

。第六章句法分析依存句法分析例如，对句子“我吃米饭”采用基于图的方法进行依存句法分析，包括以下步骤：（1）生成完全有向图（2）计算边权重：为每条边计算一个权重，表示两个词具有依存关系的可能性。这通常需要通过一个模型来计算。例如基于模型获得的权重为：(吃→米饭:0.9)等。第六章句法分析依存句法分析（3）获取最大生成树：对于完全有向图中的每一棵候选句法树，根据边权重对每条边进行打分，将各条边的分数综合起来即为整棵句法树的分数，并得到最高分数的句法树即为最大生成树（4）格式化输出：根据最大生成树，得到依存关系树并输出可视化结果。第六章句法分析依存句法分析基于转移的方法将依存树的构成过程建模为一个动作序列，将依存分析问题转化为寻找最优动作序列的问题。研究者们最初使用局部分类器（如支持向量机等）决定下一个动作。后来采用全局分类器来决定下一个动作。该方法的基本思想是从左到右遍历整个句子，每读入一个词便根据该词的特征和当前分析状态格局特征利用分类器确定当前最佳动作，最后将这些动作拼装成句法树。该方法用三元组(S,I,A)表示分析状态格局，其中S表示栈、I表示队列、A表示依存弧集合。第六章句法分析依存句法分析栈S：表示用来储存已经处理过的句法子树的根节点。初始状态下S=[ROOT]，栈顶元素为S1，从栈顶起的第i个元素为Si。队列I：用来存放未处理节点序列。初始状态下队列就是整个句子x=[w1,w2,...,wn]。例如对句子“脚步声打断了我的沉思”进行依存句法分析时，初始队列如图所示：第六章句法分析依存句法分析依存弧集合A：其中的依存弧有动作类型、依存关系名称两个信息。在经典的arc-eager分析法中，动作类型有如下4种：（1）入栈（shift）操作：读取队列I

中第一个词，并入栈。（2）依存弧向左指（left-arc）操作：当队列头部词与栈顶词存在依存关系，且队列头部词为支配词时执行左指操作。第六章句法分析依存句法分析依存弧集合A：其中的依存弧有动作类型、依存关系名称两个信息。在经典的arc-eager分析法中，动作类型有如下4种：（3）依存弧向右指（right-arc）操作：当队列头部词与栈顶词存在依存关系，且队列头部词为从属词时执行右指操作。第六章句法分析依存句法分析依存弧集合A：其中的依存弧有动作类型、依存关系名称两个信息。在经典的arc-eager分析法中，动作类型有如下4种：（4）出栈（reduce）操作：当S栈顶词已经有支配词时出栈。最终，得到依存关系树：第六章句法分析依存句法分析基于神经网络的方法，与基于转移的方法相似，用低维分布式表示代替复杂高维的稀疏特征表示。典型的方法是基于长短期记忆网络（LSTM）的方法，该方法将词、词性等特征信息项作为输入，由神经网络自动进行特征提取和组合。该方法将分析状态格局的栈、队列和动作分别用三个stack-LSTM（栈式LSTM）表示，所分析的格局信息为全部上下文信息，分析过程仍是每读入一个词，根据该词的当前格局和动作历史信息确定当前最佳动作，最后一步步拼装成句法树。第六章句法分析依存句法分析栈操作对stack-LSTM的影响如图所示：第六章句法分析依存句法分析神经依存分析方法还可基于序列到序列架构实现，该架构主要包含编码器、注意力层和解码器。在编码阶段，对于输入句x中的每个词语，使用词嵌入、节点嵌入（node2vec）、子词（sub-word）嵌入、字符嵌入和词性嵌入等五种特征的拼接来表示。解码阶段在输出时刻t输出的是输入句中第t个词为支配词的概率分布，即对于词xt，其支配词为yt的概率为：最后的句法分析结果为取得最大生成概率的序列y：第六章句法分析依存句法分析在句法分析中，支配词只可能来源于输入句中的词语，若继续使用建立在整个语料库上的词表，很容易使得预测的支配词落在输入句词语的范围外。为此，在预测xt的支配词时，模型预测的是支配词与在句子中相对于xt的位置，而非预测支配词本身。如下图所示，在句子Thathasoutragedsomefans.中，outraged的支配词ROOT处于outraged左边第3个位置。第六章句法分析依存句法分析评价指标无标签依存正确率（UnlabeledAttachmentScore，UAS）:带标签依存正确率（LabeledAttachmentScore，LAS）:第六章句法分析依存句法分析依存正确率（DependencyAccuracy，DA）:根正确率（RootAccuracy，RA）:完全匹配率（CompleteMatch，CM）：第六章句法分析目录成分句法分析依存句法分析句法分析工具及相关语料库第六章句法分析句法分析工具及相关语料库句法分析工具SpaCy是由ExplosionAI公司开发的工业级的自然语言处理工具，完成了NLP领域的很多任务，比如词性标注、命名实体识别、依存句法分析、归一化、停用词去除。FudanNLP是复旦大学自然语言处理实验室开发的中文自然语言处理工具包，它提供了一系列的中文自然语言处理工具，包括分词、词性标注、命名实体识别、依存句法分析、情感分析等功能。DDParser是百度自然语言处理部基于深度学