自然语言处理中的最大熵方法.ppt

1、自然语言处理中的最大熵方法,马金山 信息检索研究室 ,纲 要,熵理论的发展 信息熵 最大熵理论 最大熵理论的应用,什么是熵,什么是熵？ 没有什么问题在科学史的进程中曾被更为频繁地讨论过 普里高津 熵定律是自然界一切定律中的最高定律 里夫金&霍华德,熵的提出,德国物理学家克劳修斯（Rudolph J.E clausius） 于1865提出熵的概念 其经典意义定义为： R表示可逆过程，即体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度。,熵原理的形象比喻,一滴墨水滴入一杯清水中，墨水扩散后均匀地分布在清水中 比喻热力体系的自发过程总是趋于温度均匀分布， 反之不行。,微观世界中熵的含义,热力学

2、定律都是对物质宏观性质进行考察得到的经验定律 宏观物体是大量微观粒子构成的 1872年，波尔兹曼（LBoltzmann）指出熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数 熵值高意味着无序性强 !,熵增原理,一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状态逐步变为混沌状态，不可能自发地产生新的有序结构。 当熵处于最小值, 即能量集中程度最高、有效能量处于最大值时, 那么整个系统也处于最有序的状态,相反为最无序状态。 熵增原理预示着自然界越变越无序,熵的普遍性,熵概念的泛化 熵理论是存在问题的， 需要发展和完善,熵与信息,1948年电气工程师香

3、农( Shannon)创立了信息论，将信息量与熵联系起来。 他用非常简洁的数学公式定义了信息时代的基本概念：熵 H(p) = -p(x)logp(x) 单位：bits,通信中的熵,表示“是” 和 “否” 1 = 是 0 =否 表示“是” 、“否”和“可能是” 11 =是00 = 否 10(01) = 可能是 一条消息的熵就是编码这条消息所需二进制位即比特的个数。,随机事件的熵,熵定量的描述事件的不确定性 设随机变量 ，它有A1，A2，An共n个可能的结局，每个结局出现的机率分别为p1,p2 ，.，pn，则 的不确定程度，即信息熵为: 熵越大，越不确定 熵等于0，事件是确定的,例子,抛硬币 掷色

4、子（32个面） 不公平的硬币,熵的图形,信息熵的意义,信息熵概念为测试信息的多少找到了一个统一的科学定量计量方法，是信息论的基础。 信息熵将数学方法和语言学相结合,最大熵理论,熵增原理 在无外力作用下，事物总是朝着最混乱的方向发展 事物是约束和自由的统一体 事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则。 在已知条件下，熵最大的事物，最可能接近它的真实状态,最大熵原则下点的分布,对一随机过程，如果没有任何观测量， 既没有任何约束，则解为均匀分布,最大熵原则下点的分布,最大熵原则下点的分布,最大熵原则下点的分布,选择最好的模型,研究某个随机事件，根据已知信息，预测其未来行为。 当无

5、法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。 满足已知信息要求的模型可能有多个。,基于最大熵原理选择模型,选择熵最大的模型 Jaynes证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势 Tribus证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况,基于最大熵的统计建模,特征空间的确定 特征选择 建立统计模型 基于最大熵的统计建模即发现满足已知条件的熵最大的模型,基于最大熵的统计建模,已有特征 f1(x,y), f2(x,y), fn(x,y) 特征的经验概率： 特征的期望概率： 如果样本足够多，可信度高的特征的经验概率与真实概率一致的 由训练样

6、本习得的模型,对可信度高的特征的估计应满足约束等式:,基于最大熵的统计建模,事件的熵 计算模型的最大熵 得 其中,最大熵模型求解,参数估计 GIS算法(Generalized Iterative scaling) Darroch and Ratcliff,1972 IIS算法(Improved Iterative Scaling) Della Pietra 1995 Input: 特征函数 特征分布 Output: 最优参数值 最优模型,IIS算法,1 Start with for all 2 Do for each a Let be the solution to b Update the

7、value of 3 Go to step 2 if not all have converged,词义消歧的例子,词义消歧 确定多义词在一个句子中所表达的词义 “打”的语义：S1,S2,S3,S4 S1打人 S2打酱油 S3打球 S4打电话 他打完篮球后给我打了个电话 ? ?,确定“打”的语义,没有任何先验知识 概率分布： P(S1)= 0.25 P(S2)= 0.25 P(S3)= 0.25 P(S4)= 0.25 H(p)= -4 X (0.25 log20.25)=2 熵值最大，最合理,确定“打”的语义,先验知识: 取S1或S3的概率：0.6 取S2或S4的概率：0.4 概率分布： P

8、(S1)= 0.3 P(S2)= 0.2 P(S3)= 0.3 P(S4)= 0.2 H(p)= -2 X (0.2 log20.2) -2 X (0.3 log20.3) 符合约束的分布中，该分布熵值最大，最合理,不存在没有约束的自由,他了那个坏人 打=S1 他打了二两酒 打=S2 他喜欢打篮球 打=S3 他喜欢打电话 打=S4 他用手机打我 打=S1 他酒后打人 打=S1 一些人在打球 打=S3,知识的获取,统计这些先验知识（约束） (人，S1) (狗，S1) (酱油，S2) (酒，S2) (篮球，S3) (冰球，S3) (电话，S4) (手机，S4) (手机，S1) (酒，S1) (人，

9、S3),知识的形式化表示,在这些约束下，计算P(打= Si)，并满足模型的熵最大 引入特征函数 1 if y=S3 and x=篮球 0 otherwise,模型的建立,特征选择 在所有的特征中，选择最有代表性的特征，构造约束集合 参数估计 应用IIS算法，计算出每个特征对应的参数值,特征选择(1),最简单的方法： 选择出现次数大于n的特征 For example: (Adwait Ratnaparkhi 1999) Discard features that occur less than 5 times 代价最小,特征选择(2),原子特征算法(Basic Feature Selection

10、 ) 1 特征集合S=0 2 任取一特征 加入集合中 3 调用IIS，确定 4 在该约束集合下，计算熵的增量 5 选择使熵值增加最大的特征加到S中 6 调用IIS，计算在此特征集下的 7 执行2,特征选择（3）,近似增益算法(Approximate Gains) 已有特征 对应参数 增加特征 对应的参数 则增加的特征只影响当前参数 ， 不变 模型的形式:,Reference,A.Berger S.D.Pietra V.D.Pietra A maximum entropy approach to natural language processing Computational linguistics 1996,V22(1):39-71 S.D.Pietra, V.D.Pietra and J.Lafferty Inducing features of random fields IEEE Transactions on Pattern Anal