《句法分析技术》PPT课件.ppt
第七章 句法分析技术什么是句法分析判断输入的词序列能否构成一个合乎语法的句子，确定合乎语法句子的句法结构运用句法规则和其他知识将输入句子中词之间的线性次序，变成一个非线性的数据结构（例如短语结构树或有向无环图）为什么要进行句法分析例一：音字转换例一只小花猫例二：机器翻译例（Prepositional Phrase Attachment）Jan hit the girl with long hairJan 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/9P(tree2)=1/2*1/3*1/3=1/18P(tree3)=1/2*1/2=1/4P(tree4)=1/2*1/2=1/4PCFG的三个基本问题1、一个语句W=w1w2.wn的P(W|G),也就是产生语句W的概率？2、在语句W的句法结构有歧义的情况下,如何快速选择最佳的语法分析(parse)?3、如何从语料库中训练G的概率参数,使得P(W|G)最大问题1&2思路运用动态规划以及剪枝技术计算得出一个语句的多个句法分析形式的概率，选择概率最高的结果作为句法分析的结果向内（Inside）算法非终结符A的内部概率（Inside probability）定义为根据文法G从A推出词串 的概率，记为 称为向内变量问题11、一个语句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.4PPP NP 1.0NPJohn 0.1VPV NP 0.7NPbone 0.18VPVP PP 0.3NPstar 0.04Pwith 1.0NPfish 0.18Vate 1.0NPtelescope 0.1向内算法计算示例1234567初始化891011向内算法计算示例初始化1 NPJohn 0.1 2 Vate 1.0 3 NPfish 0.184 Pwith 1.05 NPbone 0.18递归计算6 VPV NP 0.77 PPP NP 1.08 SNP VP 1.09 NPNP PP 0.410 VPVP PP 0.3VPV 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 VPVP-V NPNP-NNP-NP 的 NPNP-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.由此得到语法G0.iBC)和C(A-a)M步骤：用E-步骤所得的期望值,利用:重新估计P(A-),得到语法Gi+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为重点介绍了近年来句法分析技术的基本原理与方法句法分析是当前语言处理技术的瓶颈问题之一句法分析是语义分析（更深层次的语言理解）的必由之路句法是形式、语义是内容句法的强制性和语义的决定性句法系统和语义系统是两个不同的系统，它们各自独立而又相互依存，彼此的对应关系十分复杂
