第七章 句法分析技术

第七章句法分析技术什么是句法分析•判断输入的词序列能否构成一个合乎语法的句子，确定合乎语法句子的句法结构•运用句法规则和其他知识将输入句子中词之间的线性次序，变成一个非线性的数据结构（例如短语结构树或有向无环图）为什么要进行句法分析•例一：音字转换例–一只小花猫•例二：机器翻译例（PrepositionalPhraseAttachment）–Janhitthegirlwithlonghair–Janhitthegirlwithahammer•例三：信息检索例–哪个球队获得了亚洲杯冠军？–日本队击败中国队获得亚洲杯冠军句法分析的难点•句法分析的难点：–语法歧义：一个句子对应着几种句法分析结果–“咬死了猎人的狗”–“那只狼咬死了猎人的狗”–“那只咬死了猎人的狗失踪了”•汉语句法分析的独特性（朱德熙《语法答问》《语法讲义》）–汉语没有形态–语序灵活–词类和句法成分不存在一一对应的关系–汉语句子的构造原则与词组的构造原则基本上是一致的–汉语语法形式化工作滞后•深层分析与浅层分析句法分析系统•一个句法分析系统通常由两部分组成–形式语法体系•匹配模式•短语结构语法•扩充转移网络•树邻接语法(TAG)•基于合一运算的语法（广义短语结构语法、词汇功能语法、功能合一语法、基于中心词驱动的短语结构语法(HPSG)）•基于词的语法（链语法、依存语法、配价语法）–分析控制机制•模式匹配技术•基于短语结构语法分析算法（厄尔利（Earley）分析算法、富田胜（Tomida）分析算法、线图（Chart）分析算法、确定性分析算法等等）•基于扩充转移网络的分析算法•链分析算法概率上下文无关文法（Probabilistic(Stochastic)ContextFreeGrammar）•随机上下文无关语法可以直接统计语言学中词与词、词与词组以及词组与词组的规约信息，并且可以由语法规则生成给定句子的概率。•定义：一个随机上下文无关语法（PCFG）由以下5部分组成：–（1）一个非终结符号集N–（2）一个终结符号集∑–（3）一个开始非终结符S∈N–（4）一个产生式集R–（5）对于任意产生式r∈R，其概率为P(r)–产生式具有形式X→Y，其中，X∈N,Y∈(N∪∑)*()1PXPCFG的三个基本假设•CFG的简单概率拓广•基本假设–位置无关(Placeinvariance)–上下文无关(Context-free)–祖先无关(Ancestor-free)•分析树的概率等于所有施用规则概率之积()1PX举例•给定如下概率文法G–(1)S-AAp1=1/2–(2)S-Bp2=1/2–(3)A-ap3=2/3–(4)A-bp4=1/3–(5)B-aap5=1/2–(6)B-bbp6=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)最大(|)PWGargmax(|,)treePtreeWGargmax(|)GPWG问题1&2•思路–运用动态规划以及剪枝技术计算得出一个语句的多个句法分析形式的概率，选择概率最高的结果作为句法分析的结果向内（Inside）算法•非终结符A的内部概率（Insideprobability）定义为根据文法G从A推出词串的概率，记为•称为向内变量SABC11...iww...ikww1...kjww1...jnww...ijww,()ijAij,()ijA问题1•1、一个语句W=w1w2….wn的P(W|G),也就是产生语句W的概率？(|)PWG向内概率公式•,()(...|)ijijAPwwAij1,,(...,,...,|)ikkjBCkPwwBwwCA1,,(,|)(...|,,)(...|...,,,)ikkjikBCkPBCAPwwABCP1,,(,|)(...|)(...|)ikkjBCkPBCAPwwBPwwC,1,,,()()()ikkjBCkPABCBC独立性假设独立性假设祖先无关假设,()()ijiAPAwij向内算法（自底向上）•输入：G=(S,N,∑,R,P),字符串•输出：•1、初始化：•2、归纳计算：j从1到n，i从1到n-j，重复下面计算•3、结束：12...n1,(|)()nPWGS,()(),,1iiiAPAwANin,,1,,()()()()iijikkijBCNikijAPABCBC11,(...|)()nnPSwwGS向内算法计算示例•S→NPVP1.0NP→NPPP0.4•PP→PNP1.0NP→John0.1•VP→VNP0.7NP→bone0.18•VP→VPPP0.3NP→star0.04•P→with1.0NP→fish0.18•V→ate1.0NP→telescope0.1向内算法计算示例1234567初始化891011向内算法计算示例•初始化–1NP→John0.1–2V→ate1.0–3NP→fish0.18–4P→with1.0–5NP→bone0.18•递归计算–6VP→VNP0.7–7PP→PNP1.0–8S→NPVP1.0–9NP→NPPP0.4–10–VP→VPPP0.3–VP→VNP0.7•结束–S→NPVP1.01,1()0.1NP2,2()1.0V4,4()1.0P3,3()0.18NP5,5()0.18NP2,3()0.7*1.0*0.180.126VP4,5()1.0*1.0*0.180.18PP1,3()1.0*0.1*0.1260.0126S3,5()0.4*0.18*0.180.01296S2,5()0.3*0.126*0.180.7*1.0*0.012960.015876S1,5()1*0.1*0.015876=0.0015876S问题2•在语句W的句法结构有歧义的情况下,如何快速选择最佳的语法分析(parse)?argmax(|,)treePtreeWGViterbi算法•输入：G=(S,N,∑,R,P),字符串•输出：t*(W在G下最可能的分析树)•算法：•1、初始化•2、动态规划：j从1到n,i从1到n-j,重复如下步骤•3、结束t*的根节点为S（文法开始符号）；从开始回溯，得到S的最优树结构•记录了非终结符及其统摄的起止位置1,(*)()nPtS12...n,()()iiiAPAw,1ANin,,1,,;,,1,,;()max()()()()argmax()()()iijikkijBCNikijiijikkijBCNikijAPABCBCAPABCBC1,()nS,()iijAViterbi算法示例问题3参数训练问题•从树库直接统计——TreebankGrammar–最大似然估计–依赖于艰巨的工程：树库建设•向内向外算法–迭代过程–与初始参数相关向内向外算法•非终结符A的外部概率（outsideprobability）定义为：•根据文法G从A推出词串的上下文的概率，记为：...ijww,()ijA...ijwwij外部概率公式1,1,()0,nASAAS,1111111,,1111,,,1,,,1,,,()(...,,...|)(...,,...)()(...)(...,,...)()(...)()()()()()()ijijniknjkBCjkhjnhiBChiikjkhjhiBCjkBAPwwAwwGPwwCwwPCABPBwwPwwCwwPCBAPBwwCPCABBCPCBAB,Chi计算外部概率示例（自顶向下）规则的概率•文法中每条规则的概率，采用下式估算•S-NPVP•VP-VNP•NP-N•NP-NP的NP•NP-VP的NP()()()NumberAPANumberA()()()()()NumberNPNPNPNNumberNPNNumberNPNPNPNumberNPVPNP的的规则的概率•PennTreebank–((S(NP-SBJThemove)–(VPfollowed–(NP(NParound)–(PPof–(NP(NPsimilarincreases)–(PPby–(NPotherlenders))–(PPagainst–(NPArizonarealestateloans)))))–,–(S-ADV(NP-SBJ*)–(VPreflecting–(NP(NPacontinuingdecline)–(PP-LOCin–(NPthatmarket))))))–.))规则使用次数的数学期望规则使用次数的数学期望向内向外算法•EM算法运用于PCFG的参数估计的具体算法。–初始化：随机地给P(A-μ)赋值，使得ΣμP(A-μ)=1.由此得到语法G0.i-0.–EM步骤：•E步骤：计算期望值C(A-BC)和C(A-a)•M步骤：用E-步骤所得的期望值,利用:重新估计P(A-μ),得到语法Gi+1–循环计算:i++,重复EM步骤,直至P(A-μ)收敛.)()()(ACACAPPCFG的优缺点•优点–可以对句法分析的歧义结果进行概率排序–提高文法的容错能力（robustness）•缺点–没有考虑词对结构分析的影响–没有考虑上下文对结构分析的影响•许多当前的获得较高精度的句法分析系统以PCFG为基础浅层句法分析技术•从完全句法分析（completeparsing）到浅层句法分析（shallowparsing）–真实语料的复杂性–语言知识的不足–提高分析的效率–应用目标驱动–浅层分析的其他名称：部分分析（partialparsing），组块分析（chunking）部分分析示例基于HMM的浅层分析技术•识别目标：非递归的NP•组块分析：在线性序列中插入括号，来标示组块边界•[The/DTprosecutor/NN]said/VBin/IN[closing/NN]that/CS…短语边界•一对词性标记–[表示一个NP组块的开始–]表示一个NP组块的结束–][表示两个NP组块相邻–I表示不是NP组块边界，且处于NP内部–O表示不是NP组块边界，且处于NP外部,基于HMM的NP组块边界标注•带有词性标记、组块边界标记的语料库•可观察符号序列：词性标记对序列•隐状态：5个可能的NP组块边界标记•通过对语料库统计，得到–状态转移矩阵–每个状态输出不同词性标记对的概率,$Theprosecutorsaidinclosingthat…$,DTDT,NNNN,VBVB,ININ,NNNN,CS[I]O[]级联式有限状态句法分析•级联式有限状态分析（CascadedFinite-StateParsing）级联式有限状态句法分析过程•（1）从左向右扫描输入字符串，按照Li层级上的正则表达式模式进行归约，得到新的模式序列，对于输入串中无法归约的符号，直接输出；•（2）i=i+1，在新的Li层级上，用正则表达式模式进行归约•（3）不断进行上述步骤，直到无法归约为止；•（4）如果归约过程中有多种选择，以覆盖范围最大的归约子串为输入结果级联式有限状态句法分析示例分析结果示例本章小结•本章以PCFG为重点介绍了近年来句法分析技术的基本原理与方法•句法分析是当前语言处理技术的瓶颈问题之一•句法分析是语义分析（更深层次的语言