8、概率句法分析

概率句法分析徐志明哈工大语言技术中心语言的描述语言的描述统计学的方法：语言是个概率分布。构造概率模型，描述语言句子的概率分布。例如：n-gram模型、HMM。代数学的方法语言是一个句子集合。定义一种文法，它可推导出该语言的所有句子。通过能否推导出完整的句法分析树，判断句子的合法性。上述两种方法结合概率文法：将概率引入到语言文法中，分析句子的句法结构。用概率指导句法结构歧义的消解。语言文法语言文法：四元组：G=(VN,VT,R,S)VN：非终结符的集合，表示句子结构分析的中间成分VT：终结符的集合，相当于词汇表。R：规则集：基本形式：。其中：，。S：初始符号，代表语言的句子。例如：句子：Themanatetheapple.TNVVVV*VSàNPVPNPàDETNVPàVNPNàappleNàmanVàateDETàtheVN={S,NP,VP,DET,N,V}VT={the,man,ate,apple}文法的类型0型短语文法1型上下文有关文法2型上下文无关文法3型正则文法文法类型逐渐增加限制如果文法是正规文法一定也是上下文无关文法语言学家Chomsky把文法分成以下四种类型：逐次兼容文法的类型0-型（无约束文法）–无限制1-型（上下文相关文法）αAβàαγβ2-型（上下文无关文法）Aàγ3-型（正则文法）AàaBAàa上下文无关文法上下文无关文法(ContextFreeGrammar，CFG)四元组：G=(VN,VT,R,S)VN：非终结符的集合VT：终结符的集合。R：规则集。基本形式：。其中：，。S：初始符号。概率上下文无关文法(ProbabilisticContextFreeGrammar，PCFG)将概率引入到CFG文法中。每条规则，附带一个概率值。约束：1)(APAA*VNVA)()()|()(AcAcAPAPPCFG：例子句法分析句法分析(Parsing)和句法分析器(Parser)任务：词序列句法分析树。本质：线性序列非线性序列。动机：自然语言是一种非线性的符号序列。句子结构表现为复杂的嵌套性，而N-gram和HMM只能处理线性序列。句法分析例子：输入句子：Isawthedogwiththetelescope.输出该句子的句法分析树Isawthedogwiththetelescope.ParsingCFG：句法分析树表示(S(NP(ProI))(VP(VP(Vsaw)(NP(Detthe)(Ndog)))(PP(Pwith)(NP(Detthe)(Ntelescope)))))句法分析模型ParserModel计算句法分析树概率：。计算句子概率：句法歧义消解：选择概率最大的句法分析树：),|(GSTP),|(GSTargmaxPTTbest})(:{)(),()(STyieldTTTPTSPSP句子概率=各种句法分析树的概率之和句法分析树概率计算句法分析树概率=该分析树上的所有规则概率之积。句子概率=该句子的各种句法分析树的概率之和。句法分析树：假设位置无关子树的概率与构成子树所在的位置无关。类似于HMM中的时间无关。上下文无关子树的概率与子树以外的词无关。祖先无关子树的概率与子树以外的节点无关。PCFG规则概率估计语言学文法构造CFG。编写语言规则。语料库建设建立基于CFG的句法树库(TreeBank)：带有句法标注的语料库。句法分析树的集合。如PenTreeBank文法训练：规则概率对于规则，在树库上统计该规则及其非终结符A的频度。然后可估计规则概率应用：应用概率Parser进行句法分析。)()()|()(AcAcAPAPAPCFG规则概率估计—例子S→NPVP3261312NP→ProNP→DetNNP→NPPPVP→VNPVP→VPPPPP→PNPPCFG：规则的频度统计S→NPVP3261312NP→ProNP→DetNNP→NPPPVP→VNPVP→VPPPPP→PNP/3=1.0/9=0.22/9=0.67/9=0.11/4=0.75/4=0.25/2=1.0PCFG：规则的概率估计句法分析的难点句法分析的难点：句法歧义：一个句子对应着几种可能的句法分析结果（多颗句法分析树）句法分析的核心任务是消解句子在句法结构上的歧义。SVPVPPPNPNPNPPronVDetNPrepDetNIsawagirlwithatelescopeSVPNPPPNPNPNPPronVDetNPrepDetNIsawagirlwithatelescope符号注释一些符号的注释句子句法分析树：T文法G=(VN,VT,R,S)假设文法G的规则形式只有两种形式：可以通过范式化处理，使CFG规则满足上述形式。nwwS1APCFG的三个基本问题与HMM相似，PCFG也有三个基本问题。问题1：给定文法G，计算由G生成句子S的概率？问题2：寻找句子S最优句法分析树?问题3：如何从语料库W中训练G的概率参数,使得P(W|G)最大模型参数训练问题),|(GSTargmaxPTTbest)|(GSP问题1&2思路采用动态规划算法，将句法分析树的概率计算转换成句法分析树的子树的概率计算。问题1：向内算法向内变量非终结符A的内部概率（Insideprobability）（可理解成子树概率）。根据文法G从A推出词串的概率。SABC11...iww1...jnwwkiwwjkww1...ijwwij)|()()(AwwPwwAPAjijiij问题1：向内概率公式)()(),()|()(),(),|(),(),(),|(),(),()|()()(,1,,1,,1,,1,,,,1CBCBAPCwwPB|wwPA|CBPCBA,,|wwPA|CBPCBA,,|CB,wwPA|C,wwB,wwPAwwPwwAPAjkikkCBjkkikCBkijkkikCBkijkkCBkikCBjkkijijiij独立性假设XXB,PBP)()(P(A,B|C)=P(A|B,C)P(B|C))()(iiiwAPA问题1：向内算法（自下向上）输入：文法G，句子输出：算法：1、初始化：2、归纳计算：j从1到n，i从1到n-j，重复下面计算3、结束：)()(iiiwAPA)()|()|(,11SGwwSPGSPnnnwwS1ni1)()(),()(,1,,CBCBAPAjikikkCBjii,)|(GSP词性概率句法子树概率句子生成概率问题1：向内算法计算示例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问题1：向内算法计算示例1234567初始化891011ij问题2：Viterbi算法输入：文法G，句子输出：t*(S在G下最优句法分析树)算法：1、初始化2、动态规划：j从1到n,i从1到n-j,重复如下步骤3、结束t*的根节点为S（文法开始符号）；从开始回溯，得到S的最优树结构记录了非终结符及其统摄的起止位置1,(*)()nPtS,()()iiiAPAw1,()nS,()iijAnwwS1ni1)()(),()()()(),()(,1,,,1,,CBCBAPargmaxACBCBAPmaxAjikikkCBjii,jikikkCBjii,Viterbi算法示例问题3：参数训练问题从树库直接统计——TreebankGrammar最大似然估计依赖于艰巨的工程：树库建设向内向外算法无监督学习迭代过程与初始参数相关问题3：向外算法向外变量非终结符A的外部概率（Outsideprobability）根据文法G从A推出词串的上下文的概率，记为：...ijww,()ijA...ijwwij)|()()(1111SwA问题3：向外算法（自下向上）输入：文法G，句子输出：算法：1、初始化：2、归纳计算：j从n-1到0，i从1到n-j，重复下面计算nwwS1nji1,()ijA1,1,()0,nASAASihCBihijkjCBkjijnj-inj-iijBBACPCBABCPCSwA)()()()()()()|()()(计算外部概率示例（自顶向下）问题3：向内向外算法规则使用次数的数学期望统计经过三点规则概率重估公式向内向外算法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为基础基于CFG规则的分析方法基于CFG规则的分析方法：1.CYK算法；2.移进－归约算法；3.Marcus确定性分析算法；4.Earley算法；5.Tomita算法（GLR算法、富田算法）；6.Chart算法（图分析算法、线图分析算法）；句法分析策略句法分析通常采用的策略有：自顶向下分析法；自底向上分析法；左角分析法；其他策略。1线图分析算法(1)SàNPVP(2)NPàN(3)NPàCS的(4)VPàVNP(5)CSàNPV'(6)V'àVV我是县长派来的苍蝇是瞎子打死的主意是董永想出来的……NVNVV的线图结构图示1234560NNVVV的我是县长派来的苍蝇是瞎子打死的主意是董永想出来的……V'CSNPVPS线图ChartNPNP基本概念：线图/chart线图是一组节点(node)和边(edge)的集合节点：对应着输入字符串中的字符间隔边：起点,终点,标记其中标记为非终结符或终结符问题：如何从输入串开始，一步步形成chart，使得存在一条边可以覆盖全部节点，并且边上标记为S？Chart的另一种表示形式“边”的起始位置边的终止位置“边”上的标记6SVPNP的5CSV'V4V3N,NP2V1N,NP00123456Chart算法的基本数据结构1)chart{edge[i]}i=1,2,…edge:=P1,P2,Label2)agenda栈（stack）结构，存放等待加入到chart中的边（edge）3)activearc存放当前分析状态，状态由三部分组成P1,P2,点规则Chart算法的过程描述1)将待分析字符串w置入输入缓冲区，agenda清为空栈；2)循环，反复执行下面步骤，直至输入缓冲区和agenda均为空a)若agenda为空，则从输入缓冲区取一个字符，并把该字符及其起止位置(P1,P2)推入agenda栈；b)从agenda中弹出栈顶的边，该边的起止位置为(P1,P2),边上标记为L；c)检查规则集中的规则，对所有形如AàL这样的规则，在activ