自然语言理解-句法歧义消解(0)..

句法歧义消解上海交通大学陈玉泉内容提要基于特征的消歧PCFGMEReranking评测体系基于特征的消歧基本框架基本规则：校验传递VerificationReductionTransferEndNY组成部分文法上下文无关文法特征操作（合一也可以是其他）校验，传递词典特征的来源例子文法及其特征操作NPnT:NP.head=nNPNP1NP2T:NP.head=NP2.headNPMPNP1V:MP.quaninNP1.head.QsetT:NP.MPmqT:MP.quan=q词典火车.Qset={列、种、节…}票.Qset={张、种、沓、堆…}例子（cont）MP(一张)+NP(火车)“V:MP.quaninNP1.head.Qset”willfail,since“张”isnotin{列、种、节…}MP(一张)+NP(火车票)issuccessful.例子（cont）PCFGProbabilisticContextFreeGrammar一般统计模型的原型P(x|w,G)=P(w|x,G)*P(x|G)/P(w|G)这里x是我们的分析树，w是句子，G是文法Xres=argmaxxP(x|w,G)由于P(w|x,G)=1,P(w|G)对所有输入都一样所以，Xres=argmaxxP(x|G)PCFG基本概念每一条产生式都有一个概率P(r)句法树中每个节点都有一个概率可以把叶结点的概率定为1树的概率P(x|G)等于根节点的概率概率从叶节点开始往上计算，可以用递归表示。计算方法Forleafnodes,assigntheprobabilityas1.Fornon-leafnodes,Forasubtreegeneratedbyproduction:r：Au1u2…un,theProbabilityis:WhereS(A),S(ui)istheprobabilityofAandui,P(r)istheprobabilityofproductionr.niiuSrPAS1)()()(图示统计计数+正则化Eg.1.每个产生式出现的次数（子树）(20)NPNPNP(18)NPn(18)VPVPNP(14)VPv2.对左部进行正则化.P(NPNPNP)=20/(20+18)=0.526P(NPn)=18/(20+18)=0.474P(VPVPNP)=18/(18+14)=0.562P(VPv)=14/(18+14)=0.438Best-first的实现把概率结合进图算法：活动弧（规则概率*识别节点的概率），弧扩展时，两弧概率相称，弧触发时，规则概率*原弧概率改变图算法中agenda的排序策略：概率最高的弧最先处理，这样可以保证所有弧的概率递减。这样保证了最先出来的结果是概率最大的结果PCFG的特点PCFG合理的解释了一个句子可以对应多个分析树但解释地并不理想CFG不能只通过正例学习（必须有反例），但PCFG可以健壮性，对于不符合语法规范的句子，仍然可以给出它的分析树，只是概率小从实验结果来看，PCFG是比较差的语言模型如果加入上下文信息，词汇信息，父节点子节点信息，效果可以更好PCFG的概率大小并不代表该分析树在实际情况下出现的次数。（概率和长度有关）扩展—加入简单上下文信息共现概率Co-occurrenceProbability(COP)PrecedingCOPPA(v,C),probthatCisaheadofv.（C在V后面）SucceedingCOPPF(v,C),probthatCfollowsv.（C在V前面）这里v必须是词汇范畴，即叶结点PA(v,C)=P(Cv|v)；PF(v,C)=P(vC|v)COP(C)=PA*PF图示统计计数+正则化1.计数(v,C).如果C出现在句首，应该算到NF(e,C).如果在句尾，NF(v,e)+12.同理计算(C,v),即NA(v,C)3.PF(v,C)=NF(v,C)/N(v);PA(v,C)=NA(v,C)/N(v);与PCFG结合ForaParsingTreeS;PCFG:P(S)=P(SAB)*P(A)*P(B).RecursivelycomputeP(A)andP(B).COP:P(S)=PF(v1,S)*PA(v2,S)v1isthelexiconbeforeS,andv2,afterS.Donotneedrecursivecomputation.PCFG+COP:P(S)=P(SAB)*P(A)*P(B)*PF(v1,S)*PA(v2,S)上下文相关信息的好处“学习/v文件/n”有两个解释：用于学习的文件[学习/v文件/n]NP指学习的动作，学习的对象是文件[学习/v文件/n]VP观察下面两句1。大家/n一起/d学习/v文件/n2。我们/r的/u学习/v文件/n掉/v了/u1中学习文件出现在d（一起）后面，所以作为VP的概率比较大2中学习文件出现在u（的）后面，所以作为NP的概率比较大MEMaximumEntropy熵的提出德国物理学家克劳修斯（RudolphJ.Eclausius）于1865提出熵的概念其经典意义定义为：R表示可逆过程，即体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度。RTdQds)(熵原理的形象比喻一滴墨水滴入一杯清水中，墨水扩散后均匀地分布在清水中比喻热力体系的自发过程总是趋于温度均匀分布，反之不行。微观世界中熵的含义热力学定律都是对物质宏观性质进行考察得到的经验定律宏观物体是大量微观粒子构成的1872年，波尔兹曼（L．Boltzmann）指出熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数熵值高意味着无序性强!熵增原理一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发地产生新的有序结构。当熵处于最小值,即能量集中程度最高、有效能量处于最大值时,那么整个系统也处于最有序的状态,相反为最无序状态。熵增原理预示着自然界越变越无序熵与信息1948年电气工程师香农(Shannon)创立了信息论，将信息量与熵联系起来。他用非常简洁的数学公式定义了信息时代的基本概念：熵H(p)=-p(x)logp(x)单位：bits随机事件的熵熵定量的描述事件的不确定性设随机变量，它有A1，A2，…，An共n个可能的结局，每个结局出现的机率分别为p1,p2，...，pn，则的不确定程度，即信息熵为:熵越大，越不确定熵等于0，事件是确定的niippH1log)(例子抛硬币掷色子（32个面）不公平的硬币最大熵理论熵增原理在无外力作用下，事物总是朝着最混乱的方向发展事物是约束和自由的统一体事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则。在已知条件下，熵最大的事物，最可能接近它的真实状态最大熵原则下点的分布对一随机过程，如果没有任何观测量，既没有任何约束，则解为均匀分布最大熵原则下点的分布最大熵原则下点的分布最大熵原则下点的分布选择最好的模型研究某个随机事件，根据已知信息，预测其未来行为。当无法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。满足已知信息要求的模型可能有多个。基于最大熵原理选择模型选择熵最大的模型Jaynes证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势Tribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况基于最大熵的统计建模特征空间的确定特征选择建立统计模型基于最大熵的统计建模即发现满足已知条件的熵最大的模型整合概率模型和特征模型对特征进行抽象：F1(NP,MPNP)=1当且仅当NPMPNP1符合量词和名词搭配的条件。F2(x)=1当且仅当X是树，在X中出现一次VPVPNP…我们的任务已知各特征函数，已知P(x)的观测值，已知P(x,y)的观测值，求P(y|x)基于最大熵的统计建模已有特征f1(x,y),f2(x,y)…,fn(x,y)特征的经验概率：特征的期望概率：如果样本足够多，可信度高的特征的经验概率与真实概率一致的由训练样本习得的模型,对可信度高的特征的估计应满足约束等式:yxyxfyxpfp,),(),(~)(~yxyxfxypxpfp,),()|()(~)()(~)(fpfp基于最大熵的统计建模事件的熵计算模型的最大熵得其中yxxypxypxppH,)|(log)|()(~)(iiiifpfppHp))(~)(()(),()),(exp()|()(1iiixZyxfxypyiiiyxfxZ)),(exp()(最大熵模型求解参数估计GIS算法(GeneralizedIterativescaling)DarrochandRatcliff,1972IIS算法(ImprovedIterativeScaling)DellaPietra1995Input:特征函数特征分布Output:最优参数值最优模型模型的建立特征选择在所有的特征中，选择最有代表性的特征，构造约束集合参数估计应用IIS算法，计算出每个特征对应的参数值i特征选择最简单的方法：选择出现次数大于n的特征Forexample:(AdwaitRatnaparkhi1999)Discardfeaturesthatoccurlessthan5times代价最小Head-DrivenLexicalizedParserMichaelCollins1999当今最流行的句法分析器Head-DrivenLexicalizedPCFGs动机“saw,man,with,telescope”=NounorVerb-attachLexicalization将词汇信息和每一个非终结符相联系XX(w,t)-w:headword-t:POStagofw-Head:决定句法性质的中心成分-Isawaman.-Withalargetelescope方法准确率NormalPCFGDependsPOStagdistributionsAlwaysnoun-attach59%P(noun-attach|saw,man,with,telescope)84.1%Head-DrivenLexicalizedPCFGs:例子内部规则:VP(bought,VBD)-VBD(bought,VBD)NP(Lotus,NNP)词汇规则:VBD(bought,VBD)-boughtProbabilityofS(bought,VBD)-NP(week,NN)NP(IBM,NNP)VP(bought,VBD):Count(VP(bought,VBD)-VBD(bought,VBD)NP(lotus,NNP))Count(VP(bought,VBD))(continue)问题数据稀疏可能的解决方法将规则的右部拆分成一些小步骤对于每一步有独立性假设Model1内部规则:P(h)-Ln(ln)…L1(l1)H(h)R1(r1)…Rm(rm)Example:S(bought,VBD)-NP(week,NN)NP(IBM,NNP)VP(bought,VBD)n=2m=0P=SH=VPL1=NPL2=NPL3=STOPR1=STOPh=bought,VBDl1=IBM,NNPl2=week,NN词汇规则:P(h)-w独立性假设P(Ln(ln)…L1(l1)H(h)R1(r1)…Rm(rm)|P,h)=Ph(H|P,h)*Pl(Li(li)|P,h,H)*Pr(Rj(rj)|P,h,H)1...1ni1...1mjDistance现实:修饰语之间并不是完全