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

句法歧义消解上海交通大学陈玉泉内容提要基于特征的消歧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合理的解释了一个句子可以对应多个分析树但解释地并不理想健壮性，对于不符合语法规范的句子，仍然可以给出它的分析树，只是概率小从实验结果来看，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整合概率模型和特征模型对特征进行抽象：F1(NP,MPNP)=1当且仅当NPMPNP1符合量词和名词搭配的条件。F2(x)=1当且仅当X是树，在X中出现一次VPVPNP…熵的定义描述系统混乱度，越大，系统越混乱P(x)的熵：H(p)xxpxpxpE)(log)())((log最大熵在满足约束条件的情况下，概率密度函数的熵尽可能大。用于在约束条件下求分布函数I={A,B,C}约束条件P(A)+P(B)+P(C)=1P(A)=P(B)=P(C)=1/3时系统熵最大约束条件P(A)+P(B)+P(C)=1andP(A)+P(B)=1/6P(A)=1/12P(B)=1/12P(C)=5/6时熵最大求条件概率的熵H(P(y|x))=H(p(x,y))-H(p(x))xxypxypxp)|(log)|()(我们的任务已知各特征函数，已知P(x)的观测值，已知P(x,y)的观测值，求P(y|x)约束条件(记为C)Foreachf),()|()(ˆ),(),(ˆ,,yxfxypxpyxfyxpyxyx)()(ˆfpfp所要的结果找到下面的p可以知道,这样的p必然存在)(maxargpHpCpr求解过程1，引入LagrangeMultiplier2，写出Lagrangefunction3，对p求导，使其为0，这样可以求出p（为LagrangeMultipliers的函数）4，将p代回Lagrangefunction5，通过迭代求解LagrangeMultiplier求解过程1，2引入LagrangeMultiplier3，对p求导后，得到p的解)),(exp()(1)|(iiiyxfxZxypiyxiiyxpxypxpyxfpHp))),()|()()(,(()(),(,yiiiyxfxZ)),(exp()(求解过程4代入前式最大化)(ˆ)(log)(),()(iiixfpxZxppReranking在概率模型中引入特征的问题特征的出现，使算法复杂度上升。甚至于无法在多项式时间内完成。使用Reranking模式1,GenerativeParse,比如pcfg2,取出前k个解3,抽取特征，对k个解重排序PCFGParseN-bestRerankingModel可以通过多种策略实现MaximumEntropyCharniak2000，89.6/89.5(penntreebank)AMaximum-Entropy-InspiredParserCollins2000，89.6/89.9(penntreebank)DiscriminativeRerankingforNaturalLanguageParsingSVMANN评测体系PARSEVALLabeledPrecision=numberofcorrectconstituentsinproposedparsenumberofconstituentsinproposedparseLabeledRecall=numberofcorrectconstituentsinproposedparsenumberofconstituentsintreebankparseCrossBrackets=Numberofconsituentswhichviolateconstituentboundarieswithaconstituentinthetreebankparse.例子ProposedParse:[[[一/m张/q]MP火车/n]NP票/n]NPTreebankParse:[[一/m张/q]MP[火车/n票/n]NP]NPCorrectconstituents=2Crossbracket=1BracketNumberinproposedParse=3BracketNumberintreebankParse=3So,LabeledPrecision=2/3=66.7%LabeledRecall=2/3=66.7%Crossbracket=1扩展F-score:2*LR*LP/(LR+LP)BatchMeasureCompletematch:theratioofcorrectsentence(alltheconstituentsmatch).Averagecrossing:theAverageCrossBracketofallthesentences.Nocrossing:theratioofsentencesthathavenocrossbrackets2orlesscrossing:therationofsentenceswhosecrossbracketsnumberislessthan2.