第七章 句法分析技术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 句法分析技术,什么是句法分析,判断输入的词序列能否构成一个合乎语法的句子，确定合乎语法句子的句法结构,运用句法规则和其他知识将输入句子中词之间的线性次序，变成一个非线性的数据结构（例如短语结构树或有向无环图）,为什么要进行句法分析,例一：音字转换例,一只小花猫,例二：机器翻译例（,Prepositional Phrase Attachment,）,Jan hit the girl with long hair,Jan hit the girl with a hammer,例三：信息检索例,哪个球队获得了亚洲杯冠军？,日本队击败中国队获得亚洲杯冠军,句法分析的难点,句法分析的难点：,语法歧义：一个句子对应着几种句法分析结果,“,咬死了猎人的狗,”,“那只狼咬死了猎人的狗”,“那只咬死了猎人的狗失踪了”,汉语句法分析的独特性（朱德熙,语法答问,语法讲义,）,汉语没有形态,语序灵活,词类和句法成分不存在一一对应的关系,汉语句子的构造原则与词组的构造原则基本上是一致的,汉语语法形式化工作滞后,深层分析与浅层分析,句法分析系统,一个句法分析系统通常由两部分组成,形式语法体系,匹配模式,短语结构语法,扩充转移网络,树邻接语法,(TAG),基于合一运算的语法（广义短语结构语法、词汇功能语法、功能合一语法、基于中心词驱动的短语结构语法,(HPSG),）,基于词的语法（链语法、依存语法、配价语法）,分析控制机制,模式匹配技术,基于短语结构语法分析算法（厄尔利（,Earley,）分析算法、富田胜（,Tomida,）分析算法、线图（,Chart,）分析算法、确定性分析算法等等）,基于扩充转移网络的分析算法,链分析算法,概率上下文无关文法（,Probabilistic(Stochastic)Context Free Grammar,）,随机上下文无关语法可以直接统计语言学中词与词、词与词组以及词组与词组的规约信息，并且可以由语法规则生成给定句子的概率。,定义：一个随机上下文无关语法（,PCFG,）由以下,5,部分组成：,（,1,）一个非终结符号集,N,（,2,）一个终结符号集,（,3,）一个开始非终结符,SN,（,4,）一个产生式集,R,（,5,）对于任意产生式,rR,，其概率为,P(r,),产生式具有形式,XY,，其中，,X N,Y(N)*,PCFG,的三个基本假设,CFG,的简单概率拓广,基本假设,位置无关,(Place invariance),上下文无关,(Context-free),祖先无关,(Ancestor-free),分析树的概率等于所有施用规则概率之积,举例,给定如下概率文法,G,(1)S-AA p1=1/2,(2)S-B p2=1/2,(3)A-a p3=2/3,(4)A-b p4=1/3,(5)B-,aa,p5=1/2,(6)B-bb p6=1/2,那么：,P(tree1)=1/2*2/3*,2/3,=2/9,P(tree2)=1/2*1/3*,1/3,=1/18,P(tree3)=1/2*,1/2,=1/4,P(tree4)=1/2*,1/2,=1/4,PCFG,的三个基本问题,1,、一个语句,W=w1w2.,wn,的,P(W|G),也就是产生语句,W,的概率？,2,、在语句,W,的句法结构有歧义的情况下,如何快速选择最佳的语法分析,(parse)?,3,、如何从语料库中训练,G,的概率参数,使得,P(W|G),最大,问题,1&2,思路,运用动态规划以及剪枝技术计算得出一个语句的多个句法分析形式的概率，选择概率最高的结果作为句法分析的结果,向内（,Inside,）算法,非终结符,A,的内部概率（,Inside probability,）定义为根据文法,G,从,A,推出词串 的概率，记为,称为向内变量,问题,1,1,、一个语句,W=w1w2.,wn,的,P(W|G),也就是产生语句,W,的概率？,向内概率公式,独立性假设,独立性假设,祖先无关假设,向内算法（自底向上）,输入：,G=(S,N,R,P),字符串,输出：,1,、初始化：,2,、归纳计算：,j,从,1,到,n,，,i,从,1,到,n-j,，重复下面计算,3,、结束：,向内算法计算示例,SNP VP 1.0NPNP PP 0.4,PPP NP 1.0,NPJohn,0.1,VPV NP 0.7,NPbone,0.18,VPVP PP 0.3,NPstar,0.04,Pwith,1.0,NPfish,0.18,Vate,1.0,NPtelescope,0.1,向内算法计算示例,1,2,3,4,5,6,7,初始化,8,9,10,11,向内算法计算示例,初始化,1,NPJohn,0.1,2,Vate,1.0,3,NPfish,0.18,4,Pwith,1.0,5,NPbone,0.18,递归计算,6 VPV NP 0.7,7 PPP NP 1.0,8 SNP VP 1.0,9 NPNP PP 0.4,10,VPVP PP 0.3,VPV NP 0.7,结束,SNP VP 1.0,问题,2,在语句,W,的句法结构有歧义的情况下,如何快速选择最佳的语法分析,(parse)?,Viterbi,算法,输入：,G=(S,N,R,P),字符串,输出：,t*(W,在,G,下最可能的分析树,),算法：,1,、初始化,2,、动态规划：,j,从,1,到,n,i,从,1,到,n-j,重复如下步骤,3,、结束,t*,的根节点为,S,（文法开始符号）；从 开始回溯，得到,S,的最优树结构,记录了非终结符及其统摄的起止位置,Viterbi,算法示例,问题,3,参数训练问题,从树库直接统计,Treebank Grammar,最大似然估计,依赖于艰巨的工程：树库建设,向内向外算法,迭代过程,与初始参数相关,向内向外算法,非终结符,A,的外部概率（,outside probability,）定义为：,根据文法,G,从,A,推出词串 的上下文的概率，记为：,外部概率公式,计算外部概率示例（自顶向下）,规则的概率,文法中每条规则的概率，采用下式估算,S-NP VP,VP-V NP,NP-N,NP-NP,的,NP,NP-VP,的,NP,规则的概率,Penn Treebank,(,S,(,NP-SBJ The move,),(,VP followed,(,NP,(,NP,a round,),(,PP of,(,NP,(,NP,similar increases,),(,PP by,(,NP other lenders,),(,PP against,(,NP Arizona real estate loans,),(,S-ADV,(,NP-SBJ,*),(,VP reflecting,(,NP,(,NP,a continuing decline,),(,PP-LOC in,(,NP that market,),.),规则使用次数的数学期望,规则使用次数的数学期望,向内向外算法,EM,算法运用于,PCFG,的参数估计的具体算法。,初始化：随机地给,P(A-,),赋值，使得,P(A,-)=1.,由此得到语法,G,0,.iBC),和,C(A-a),M,步骤：用,E-,步骤所得的期望值,利用,:,重新估计,P(A-,),得到语法,G,i+1,循环计算,:i+,重复,EM,步骤,直至,P(A-,),收敛,.,PCFG,的优缺点,优点,可以对句法分析的歧义结果进行概率排序,提高文法的容错能力（,robustness,）,缺点,没有考虑词对结构分析的影响,没有考虑上下文对结构分析的影响,许多当前的获得较高精度的句法分析系统以,PCFG,为基础,浅层句法分析技术,从完全句法分析（,complete parsing,）到浅层句法分析（,shallow parsing,）,真实语料的复杂性,语言知识的不足,提高分析的效率,应用目标驱动,浅层分析的其他名称：部分分析（,partial parsing,），组块分析（,chunking,）,部分分析示例,基于,HMM,的浅层分析技术,识别目标：非递归的,NP,组块分析：在线性序列中插入括号，来标示组块边界,The/DT prosecutor/NN said/VB in/IN closing/NN that/CS,短语边界,一对词性标记,表示一个,NP,组块的开始,表示一个,NP,组块的结束,表示两个,NP,组块相邻,I,表示不是,NP,组块边界，且处于,NP,内部,O,表示不是,NP,组块边界，且处于,NP,外部,基于,HMM,的,NP,组块边界标注,带有词性标记、组块边界标记的语料库,可观察符号序列：词性标记对序列,隐状态：,5,个可能的,NP,组块边界标记,通过对语料库统计，得到,状态转移矩阵,每个状态输出不同词性标记对的概率,$The prosecutor said in closing that,I O ,级联式有限状态句法分析,级联式有限状态分析（,Cascaded Finite-State Parsing,）,级联式有限状态句法分析过程,（,1,）从左向右扫描输入字符串，按照,Li,层级上的正则表达式模式进行归约，得到新的模式序列，对于输入串中无法归约的符号，直接输出；,（,2,）,i=i+1,，在新的,Li,层级上，用正则表达式模式进行归约,（,3,）不断进行上述步骤，直到无法归约为止；,（,4,）如果归约过程中有多种选择，以覆盖范围最大的归约子串为输入结果,级联式有限状态句法分析示例,分析结果示例,本章小结,本章以,PCFG,为重点介绍了近年来句法分析技术的基本原理与方法,句法分析是当前语言处理技术的瓶颈问题之一,句法分析是语义分析（更深层次的语言理解）的必由之路,句法是形式、语义是内容,句法的强制性和语义的决定性,句法系统和语义系统是两个不同的系统，它们各自独立而又相互依存，彼此的对应关系十分复杂,