《自然语言理解-句法歧义消解(0)》由会员分享，可在线阅读，更多相关《自然语言理解-句法歧义消解(0)（60页珍藏版）》请在金锄头文库上搜索。
1、句法歧义消解,上海交通大学 陈玉泉,内容提要,基于特征的消歧 PCFG ME Reranking 评测体系,基于特征的消歧,基本框架,基本规则： 校验 传递,Verification,Reduction,Transfer,End,N,Y,组成部分,文法 上下文无关文法 特征操作（合一也可以是其他） 校验，传递 词典 特征的来源,例子,文法及其特征操作 NP n T: NP.head = n NP NP1 NP2 T: NP.head = NP2.head NP MP NP1 V: MP.quan in NP1.head.Qset T: NP. MP m q T: MP.quan = q 词典
2、火车.Qset = 列、种、节 票.Qset = 张、种、沓、堆,例子（cont）,MP(一张) + NP(火车) “V: MP.quan in NP1.head.Qset” will fail, since “张” is not in 列、种、节 MP(一张) + NP(火车票) is successful.,例子（cont）,PCFG,Probabilistic Context Free Grammar,一般统计模型的原型,P(x | w, G) = P( w | x, G) * P( x | G) / P(w | G) 这里x是我们的分析树，w是句子，G是文法 Xres = argmax
3、x P(x|w,G) 由于P(w | x, G) = 1, P(w | G) 对所有输入都一样 所以， Xres = argmaxx P(x | G),PCFG基本概念,每一条产生式都有一个概率P(r) 句法树中每个节点都有一个概率 可以把叶结点的概率定为1 树的概率P(x|G)等于根节点的概率 概率从叶节点开始往上计算，可以用递归表示。,计算方法,For leaf nodes, assign the probability as 1. For non-leaf nodes, For a subtree generated by production: r：Au1u2un , the Prob
4、ability is: Where S(A), S(ui) is the probability of A and ui, P(r) is the probability of production r.,图示,统计,计数 + 正则化 Eg. 1. 每个产生式出现的次数（子树） (20) NP NP NP (18) NP n (18) VP VP NP (14) VP v 2. 对左部进行正则化. P(NP NP NP) = 20 / (20 + 18) = 0.526 P(NP n) = 18 / (20 +18) = 0.474 P(VP VP NP) = 18 / (18 + 14) =
5、 0.562 P(VP v) = 14 / (18 + 14) = 0.438,Best-first的实现,把概率结合进图算法： 活动弧（规则概率*识别节点的概率）， 弧扩展时，两弧概率相称， 弧触发时，规则概率*原弧概率 改变图算法中agenda的排序策略：概率最高的弧最先处理，这样可以保证所有弧的概率递减。 这样保证了最先出来的结果是概率最大的结果,PCFG的特点,PCFG合理的解释了一个句子可以对应多个分析树 但解释地并不理想 CFG不能只通过正例学习（必须有反例），但PCFG可以 健壮性，对于不符合语法规范的句子，仍然可以给出它的分析树，只是概率小 从实验结果来看，PCFG是比较差的语
6、言模型 如果加入上下文信息，词汇信息，父节点子节点信息，效果可以更好 PCFG的概率大小并不代表该分析树在实际情况下出现的次数。（概率和长度有关）,扩展加入简单上下文信息,共现概率,Co-occurrence Probability (COP) Preceding COP PA(v,C), prob that C is ahead of v. （ C在V后面） Succeeding COP PF(v,C), prob that C follows v. （ C在V前面） 这里v必须是词汇范畴，即叶结点 PA(v, C) = P(Cv | v)；PF(v, C) = P(vC | v) COP(
7、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结合,For a Parsing Tree S; PCFG :P(S) = P(SAB)* P(A) * P(B). Recursively compute P(A) and P(B). COP: P(S) = PF(v1, S) * PA(v2, S)
8、v1 is the lexicon before S, and v2, after S. Do not need recursive computation. PCFG + COP: P(S) = P(SAB)* P(A) * P(B) * PF(v1, S) * PA(v2, S),上下文相关信息的好处,“学习/v 文件/n”有两个解释： 用于学习的文件 学习/v 文件/nNP 指学习的动作，学习的对象是文件 学习/v 文件/nVP 观察下面两句 1。大家/n 一起/d 学习/v 文件/n 2。我们/r 的/u 学习/v 文件/n 掉/v 了/u 1中学习文件出现在d（一起）后面，所以作为V
9、P的概率比较大 2中学习文件出现在u（的）后面，所以作为NP的概率比较大,ME,Maximum Entropy,熵的提出,德国物理学家克劳修斯（Rudolph J.E clausius） 于1865提出熵的概念 其经典意义定义为： R表示可逆过程，即体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度。,熵原理的形象比喻,一滴墨水滴入一杯清水中，墨水扩散后均匀地分布在清水中 比喻热力体系的自发过程总是趋于温度均匀分布， 反之不行。,微观世界中熵的含义,热力学定律都是对物质宏观性质进行考察得到的经验定律 宏观物体是大量微观粒子构成的 1872年，波尔兹曼（LBoltzmann）指出熵是大量微观
10、粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数 熵值高意味着无序性强 !,熵增原理,一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发地产生新的有序结构。 当熵处于最小值, 即能量集中程度最高、有效能量处于最大值时, 那么整个系统也处于最有序的状态,相反为最无序状态。 熵增原理预示着自然界越变越无序,熵与信息,1948年电气工程师香农( Shannon)创立了信息论，将信息量与熵联系起来。 他用非常简洁的数学公式定义了信息时代的基本概念：熵 H(p) = -p(x)logp(x) 单位：bits,随机事件的熵,熵定量的描述事件的
11、不确定性 设随机变量 ，它有A1，A2，An共n个可能的结局，每个结局出现的机率分别为p1,p2 ，.，pn，则 的不确定程度，即信息熵为: 熵越大，越不确定 熵等于0，事件是确定的,例子,抛硬币 掷色子（32个面） 不公平的硬币,最大熵理论,熵增原理 在无外力作用下，事物总是朝着最混乱的方向发展 事物是约束和自由的统一体 事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则。 在已知条件下，熵最大的事物，最可能接近它的真实状态,最大熵原则下点的分布,对一随机过程，如果没有任何观测量， 既没有任何约束，则解为均匀分布,最大熵原则下点的分布,最大熵原则下点的分布,最大熵原则下点的分布,选
12、择最好的模型,研究某个随机事件，根据已知信息，预测其未来行为。 当无法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。 满足已知信息要求的模型可能有多个。,基于最大熵原理选择模型,选择熵最大的模型 Jaynes证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势 Tribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况,基于最大熵的统计建模,特征空间的确定 特征选择 建立统计模型 基于最大熵的统计建模即发现满足已知条件的熵最大的模型,整合概率模型和特征模型,对特征进行抽象： F1(NP, MP NP) = 1 当且仅当 NP MP NP1符合量词和名
13、词搭配的条件。 F2(x) = 1 当且仅当 X是树，在X中出现一次VPVP NP ,我们的任务,已知各特征函数，已知P(x)的观测值，已知P(x,y)的观测值，求P(y|x),基于最大熵的统计建模,已有特征 f1(x,y), f2(x,y), fn(x,y) 特征的经验概率： 特征的期望概率： 如果样本足够多，可信度高的特征的经验概率与真实概率一致的 由训练样本习得的模型,对可信度高的特征的估计应满足约束等式:,基于最大熵的统计建模,事件的熵 计算模型的最大熵 得 其中,最大熵模型求解,参数估计 GIS算法(Generalized Iterative scaling) Darroch and
14、 Ratcliff,1972 IIS算法(Improved Iterative Scaling) Della Pietra 1995 Input: 特征函数 特征分布 Output: 最优参数值 最优模型,模型的建立,特征选择 在所有的特征中，选择最有代表性的特征，构造约束集合 参数估计 应用IIS算法，计算出每个特征对应的参数值,特征选择,最简单的方法： 选择出现次数大于n的特征 For example: (Adwait Ratnaparkhi 1999) Discard features that occur less than 5 times 代价最小,Head-Driven Lexic
15、alized Parser,Michael Collins 1999 当今最流行的句法分析器,Head-Driven Lexicalized PCFGs,动机 “saw, man, with, telescope” = Noun or Verb-attach Lexicalization 将词汇信息和每一个非终结符相联系X X(w, t) -w: head word - t: POS tag of w Head: 决定句法性质的中心成分 I saw a man. With a large telescope,Head-Driven Lexicalized PCFGs: 例子,内部规则: VP(
16、bought, VBD) - VBD(bought, VBD) NP(Lotus, NNP) 词汇规则: VBD(bought, VBD) - bought Probability of S(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),问题 数据稀疏 可能的解决方法 将规则的右部拆分成一些小步骤 对于每一步有独立性假设,Model 1,内部规则: 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 = 2 m = 0 P = S H = VP
