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

《自然语言处理中的最大熵方法幻灯片.ppt》由会员分享，可在线阅读，更多相关《自然语言处理中的最大熵方法幻灯片.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自然语言处理中的最大熵方法第1页，共38页，编辑于2022年，星期二纲纲 要要熵理论的发展熵理论的发展信息熵信息熵最大熵理论最大熵理论最大熵理论的应用最大熵理论的应用第2页，共38页，编辑于2022年，星期二什么是熵什么是熵什么是熵？什么是熵？没有什么问题在科学史的进没有什么问题在科学史的进程中曾被更为频繁地讨论过程中曾被更为频繁地讨论过 普里高津普里高津熵定律是自然界一切定律中的最高定律熵定律是自然界一切定律中的最高定律 里夫金里夫金&霍华德霍华德第3页，共38页，编辑于2022年，星期二熵的提出熵的提出德国物理学家克劳修斯（德国物理学家克劳修斯（Rudolph J.E clausius）于

2、于1865提出熵的概念提出熵的概念 其经典意义定义为：其经典意义定义为：R表表示示可可逆逆过过程程，即即体体系系的的熵熵变变等等于于可可逆逆过过程程吸吸收收或或耗耗散的热量除以它的绝对温度。散的热量除以它的绝对温度。第4页，共38页，编辑于2022年，星期二熵原理的形象比喻一一滴滴墨墨水水滴滴入入一一杯杯清清水水中中，墨墨水水扩扩散散后后均匀地分布在清水中均匀地分布在清水中比比喻喻热热力力体体系系的的自自发发过过程程总总是是趋趋于于温温度度均匀分布，均匀分布，反之不行反之不行。第5页，共38页，编辑于2022年，星期二微观世界中熵的含义微观世界中熵的含义热力学定律都是对物质宏观性质进行考察得到

3、的经验定热力学定律都是对物质宏观性质进行考察得到的经验定热力学定律都是对物质宏观性质进行考察得到的经验定热力学定律都是对物质宏观性质进行考察得到的经验定律律律律宏观物体是大量微观粒子构成的宏观物体是大量微观粒子构成的1872年，波尔兹曼（年，波尔兹曼（年，波尔兹曼（年，波尔兹曼（L LBoltzmann）指出熵是大）指出熵是大量微观粒子的位置和速度的分布概率的函数，是量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数描述系统中大量微观粒子的无序性的宏观参数熵值高意味着无序性强熵值高意味着无序性强!第6页，共38页，编辑于2022年，星期二熵增原理熵增原理一个孤立

4、系统的熵，自发性地趋于极大，随着熵一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状的增加，有序状态逐步变为混沌状态，不可能自逐步变为混沌状态，不可能自发地产生新的有序结构。发地产生新的有序结构。当熵处于最小值当熵处于最小值,即能量集中程度最高、有效能量即能量集中程度最高、有效能量即能量集中程度最高、有效能量即能量集中程度最高、有效能量处于最大值时处于最大值时处于最大值时处于最大值时,那么整个系统也处于最有序的状态那么整个系统也处于最有序的状态那么整个系统也处于最有序的状态那么整个系统也处于最有序的状态,相反为最无序状态。相反为最无序状态。相反为最无序状态。相反为最无序状态。熵增原理预示

5、着自然界越变越无序熵增原理预示着自然界越变越无序熵增原理预示着自然界越变越无序熵增原理预示着自然界越变越无序第7页，共38页，编辑于2022年，星期二熵的普遍性熵概念的泛化熵概念的泛化 熵理论是存在问题的，熵理论是存在问题的，需要发展和完善需要发展和完善第8页，共38页，编辑于2022年，星期二熵与信息熵与信息1948年电气工程师香农年电气工程师香农(Shannon)创立了信息论，创立了信息论，将信息量与熵联系起来将信息量与熵联系起来。他用非常简洁的数学公式定义了信息时代的基他用非常简洁的数学公式定义了信息时代的基本概念：熵本概念：熵 H(p)=-p(x)logp(x)单位：单位：bits第9

6、页，共38页，编辑于2022年，星期二通信中的熵通信中的熵表示表示“是是”和和 “否否”1=是是 0=否否表示表示“是是”、“否否”和和“可能是可能是”11=是是 00=否否 10(01)=可能是可能是一条消息的熵就是编码这条消息所需二一条消息的熵就是编码这条消息所需二进制位即比特的个数。进制位即比特的个数。第10页，共38页，编辑于2022年，星期二随机事件的熵随机事件的熵熵定量的描述熵定量的描述事件事件的不确定性的不确定性设随机变量设随机变量 ，它有，它有A1，A2，An共共n n个可能个可能的结局，每个结局出现的机率分别为的结局，每个结局出现的机率分别为p1,p2，.，pn，则，则 的不

7、确定程度，即信息熵为的不确定程度，即信息熵为:熵越大，越不确定熵越大，越不确定熵等于熵等于0，事件事件是确定的是确定的第11页，共38页，编辑于2022年，星期二例子例子抛硬币抛硬币掷色子（掷色子（32个面）个面）不公平的硬币不公平的硬币第12页，共38页，编辑于2022年，星期二熵的图形第13页，共38页，编辑于2022年，星期二信息熵的意义信息熵的意义信息熵概念为测试信息的多少找到了一信息熵概念为测试信息的多少找到了一个统一的科学定量计量方法，是信息论个统一的科学定量计量方法，是信息论的基础。的基础。信息熵将数学方法和语言学相结合信息熵将数学方法和语言学相结合第14页，共38页，编辑于20

8、22年，星期二最大熵理论最大熵理论熵增原理熵增原理在无外力作用下，事物总是朝着最混乱在无外力作用下，事物总是朝着最混乱的方向发展的方向发展事物是约束和自由的统一体事物是约束和自由的统一体事物总是在约束下争取最大的自由权，事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则这其实也是自然界的根本原则。在已知条件下，熵最大的事物，最可能在已知条件下，熵最大的事物，最可能接近它的真实状态接近它的真实状态第15页，共38页，编辑于2022年，星期二最大熵原则下点的分布对一随机过程，如果没有任何观测量，对一随机过程，如果没有任何观测量，既没有任何约束，则解为均匀分布既没有任何约束，则解为均匀分布

9、第16页，共38页，编辑于2022年，星期二最大熵原则下点的分布第17页，共38页，编辑于2022年，星期二最大熵原则下点的分布第18页，共38页，编辑于2022年，星期二最大熵原则下点的分布第19页，共38页，编辑于2022年，星期二选择最好的模型选择最好的模型研究某个随机事件，根据已知信息，预研究某个随机事件，根据已知信息，预测其未来行为。测其未来行为。当无法获得随机事件的真实分布时，构当无法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。造统计模型对随机事件进行模拟。满足已知信息要求的模型可能有多个。满足已知信息要求的模型可能有多个。第20页，共38页，编辑于2022年，星期二

10、基于最大熵原理选择模型基于最大熵原理选择模型选择熵最大的模型选择熵最大的模型Jaynes证明：对随机事件的所有相容证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占的预测中，熵最大的预测出现的概率占绝对优势绝对优势Tribus证明，正态分布、伽玛分布、指证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况数分布等，都是最大熵原理的特殊情况第21页，共38页，编辑于2022年，星期二基于最大熵的统计建模基于最大熵的统计建模特征空间的确定特征空间的确定特征选择特征选择 建立统计模型建立统计模型 基于最大熵的统计建模即发现满足已知条基于最大熵的统计建模即发现满足已知条件的熵最大的

11、模型件的熵最大的模型第22页，共38页，编辑于2022年，星期二基于最大熵的统计建模基于最大熵的统计建模已有特征已有特征 f1(x,y),f2(x,y),fn(x,y)特征的经验概率：特征的经验概率：特征的期望概率特征的期望概率：如果样本足够多，可信度高的特征的经验概率与真实概率一如果样本足够多，可信度高的特征的经验概率与真实概率一致的致的由训练样本习得的模型由训练样本习得的模型,对可信度高的特征的估计应满足对可信度高的特征的估计应满足约束等式约束等式:第23页，共38页，编辑于2022年，星期二基于最大熵的统计建模基于最大熵的统计建模事件的熵计算模型的最大熵得其中第24页，共38页，编辑于2

12、022年，星期二最大熵模型求解 参数估计GIS算法(Generalized Iterative scaling)Darroch and Ratcliff,1972 IIS算法(Improved Iterative Scaling)Della Pietra 1995Input:特征函数 特征分布Output:最优参数值 最优模型 第25页，共38页，编辑于2022年，星期二IIS算法1 Start with for all 2 Do for each a Let be the solution tob Update the value of 3 Go to step 2 if not all h

13、ave converged 第26页，共38页，编辑于2022年，星期二词义消歧的例子词义消歧确定多义词在一个句子中所表达的词义“打”的语义：S1,S2,S3,S4S1打人S2打酱油S3打球S4打电话他打完篮球后给我打了个电话?第27页，共38页，编辑于2022年，星期二确定“打”的语义没有任何先验知识概率分布：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熵值最大，最合理第28页，共38页，编辑于2022年，星期二确定“打”的语义先验知识先验知识:取S1或S3的概率：0.6取S2或S4的概率：0.4

14、概率分布：概率分布：P(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)符合约束的分布中，该分布熵值最大，最合理第29页，共38页，编辑于2022年，星期二不存在没有约束的自由他了那个坏人 打=S1他打了二两酒 打=S2他喜欢打篮球 打=S3他喜欢打电话 打=S4他用手机打我 打=S1他酒后打人 打=S1一些人在打球 打=S3第30页，共38页，编辑于2022年，星期二知识的获取统计这些先验知识（约束）(人，S1)(狗，S1)(酱油，S2)(酒，S2)(篮球，S3)(冰球，S3)(电话，S

15、4)(手机，S4)(手机，S1)(酒，S1)(人，S3)第31页，共38页，编辑于2022年，星期二知识的形式化表示在这些约束下，计算P(打=Si)，并满足模型的熵最大引入特征函数 1 if y=S3 and x=篮球 0 otherwise第32页，共38页，编辑于2022年，星期二模型的建立特征选择特征选择在所有的特征中，选择最有代表性的特征，在所有的特征中，选择最有代表性的特征，构造约束集合构造约束集合参数估计参数估计应用应用IIS算法，计算出每个特征对应的参数算法，计算出每个特征对应的参数值值第33页，共38页，编辑于2022年，星期二特征选择(1)最简单的方法：选择出现次数大于n的特

16、征For example:(Adwait Ratnaparkhi 1999)Discard features that occur less than 5 times 代价最小第34页，共38页，编辑于2022年，星期二特征选择特征选择(2)原子特征算法原子特征算法(Basic Feature Selection)1 特征集合特征集合S=02 任取一特征任取一特征 加入集合中加入集合中3 调用调用IIS，确定，确定4 在该约束集合下，计算熵的增量在该约束集合下，计算熵的增量5 选择使熵值增加最大的特征加到选择使熵值增加最大的特征加到S中中6 调用调用IIS，计算在此特征集下的，计算在此特征集下

17、的7 执行执行2第35页，共38页，编辑于2022年，星期二特征选择（特征选择（3）近似增益算法近似增益算法(Approximate Gains)已有特征已有特征对应参数对应参数增加特征增加特征 对应的参数对应的参数则增加的特征只影响当前参数则增加的特征只影响当前参数 ，不变不变模型的形式模型的形式:第36页，共38页，编辑于2022年，星期二ReferenceA.Berger S.D.Pietra V.D.Pietra A maximum entropy approach to natural language processing Computational linguistics 199

18、6,V22(1):39-71S.D.Pietra,V.D.Pietra and J.Lafferty Inducing features of random fields IEEE Transactions on Pattern Analysis and Machine Intelligence 1997,V19(4):380-393 R.Rosenfeld Adaptive statistical language modeling:A Maximum Entropy Approach Phd thesis CMU-CS-94,1994第37页，共38页，编辑于2022年，星期二ThanksThanks第38页，共38页，编辑于2022年，星期二