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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,自然语言处理中的最大熵方法,马金山,信息检索研究室,,ir,.hit.,edu,.,cn,纲 要,熵理论的发展,信息熵,最大熵理论,最大熵理论的应用,什么是熵,什么是熵？没有什么问题在科学史的进程中曾被更为频繁地讨论过,普里高津,熵定律是自然界一切定律中的最高定律,里夫金&霍华德,熵的提出,德国物理学家克劳修斯（,Rudolph J.E,clausius,）,于1865提出熵的概念,其经典意义定义为：,R,表示可逆过程，即体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度。,熵原理的形象比喻,一滴墨水滴入一杯清水中,，,墨水扩散后均匀地分布在清水中,比喻热力体系的自发过程总是趋于温度均匀分布，,反之不行,。,微观世界中熵的含义,热力学定律都是对物质宏观性质进行考察得到的经验定律,宏观物体是大量微观粒子构成的,1872年，波尔兹曼（,L,Boltzmann,）,指出熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数,熵值高意味着无序性强!,熵增原理,一个孤立系统的熵，自发性地趋于极大，随着熵的增加，有序状,态,逐步变为混沌状态，不可能自发地产生新的有序结构。,当熵处于最小值,即能量集中程度最高、有效能量处于最大值时,那么整个系统也处于最有序的状态,相反为最无序状态。,熵增原理预示着自然界越变越无序,熵的普遍性,熵概念的泛化,熵理论是存在问题的，需要发展和完善,熵与信息,1948,年电气工程师香农,(,Shannon),创立了信息论，将信息量与熵联系起来,。,他用非常简洁的数学公式定义了信息时代的基本概念：熵,H(p)=-p(x),logp,(x),单位：,bits,通信中的熵,表示“是”,和 “否”,1=,是,0=,否,表示“是”,、,“否”和“可能是”,11=是00=否 10(01)=可能是,一条消息的熵就是编码这条消息所需二进制位即比特的个数。,随机事件的熵,熵定量的描述,事件,的不确定性,设随机变量,，它有,A,1,，,A,2,，A,n,共,n,个可能的结局，每个结局出现的机率分别为,p,1,p,2,，,.,，,p,n,，,则 的不确定程度，即信息熵为:,熵越大，越不确定,熵等于0，,事件,是确定的,例子,抛硬币,掷色子（32个面）,不公平的硬币,熵的图形,信息熵的意义,信息熵概念为测试信息的多少找到了一个统一的科学定量计量方法，是信息论的基础。,信息熵将数学方法和语言学相结合,最大熵理论,熵增原理,在无外力作用下，事物总是朝着最混乱的方向发展,事物是约束和自由的统一体,事物总是在约束下争取最大的自由权，这其实也是自然界的根本原则,。,在已知条件下，熵最大的事物，最可能接近它的真实状态,最大熵原则下点的分布,对一随机过程，如果没有任何观测量，,既没有任何约束，则解为均匀分布,最大熵原则下点的分布,最大熵原则下点的分布,最大熵原则下点的分布,选择最好的模型,研究某个随机事件，根据已知信息，预测其未来行为。,当无法获得随机事件的真实分布时，构造统计模型对随机事件进行模拟。,满足已知信息要求的模型可能有多个。,基于最大熵原理选择模型,选择熵最大的模型,Jaynes,证明：对随机事件的所有相容的预测中，熵最大的预测出现的概率占绝对优势,Tribus,证明，正态分布、伽玛分布、指数分布等，都是最大熵原理的特殊情况,基于最大熵的统计建模,特征空间的确定,特征选择,建立统计模型,基于最大熵的统计建模即发现满足已知条件的熵最大的模型,基于最大熵的统计建模,已有特征,f,1,(x,y),f,2,(x,y),f,n,(x,y),特征的经验概率：,特征的期望概率,：,如果样本足够多，可信度高的特征的经验概率与真实概率一致的,由训练样本习得的模型,对可信度高的特征的估计应满足约束等式:,基于最大熵的统计建模,事件的熵,计算模型的最大熵,得,其中,最大熵模型求解,参数估计,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 value of,3,Go to step 2 if not all have converged,词义消歧的例子,词义消歧,确定多义词在一个句子中所表达的词义,“打”的语义：,S1,S2,S3,S4,S1,打人,S2,打酱油,S3,打球,S4,打电话,他,打,完篮球后给我,打,了个电话,?,确定“打”的语义,没有任何先验知识,概率分布：,P(S,1,)=0.25 P(S,2,)=0.25,P(S,3,)=0.25 P(S,4,)=0.25,H(p)=-4 X(0.25 log,2,0.25)=2,熵值最大，最合理,确定“打”的语义,先验知识:,取,S,1,或,S,3,的概率：0.6,取,S,2,或,S,4,的概率：0.4,概率分布：,P(S,1,)=0.3 P(S,2,)=0.2,P(S,3,)=0.3 P(S,4,)=0.2,H(p)=-2 X(0.2 log,2,0.2)-2 X(0.3 log,2,0.3),符合约束的分布中，该分布熵值最大，最合理,不存在没有约束的自由,他了那个坏人 打=,S1,他打了二两酒 打=,S2,他喜欢打篮球 打=,S3,他喜欢打电话 打=,S4,他用,手机打,我 打=,S1,他,酒,后,打,人 打=,S1,一些,人,在,打,球 打=,S3,知识的获取,统计这些先验知识（约束）,(人，,S1),(狗,，S1),(酱油，,S2),(酒，,S2),(篮球，,S3),(冰球，,S3),(电话，,S4),(手机，,S4),(手机，,S1),(酒，,S1),(人，,S3),知识的形式化表示,在这些约束下，计算,P(,打=,S,i,)，,并满足模型的熵最大,引入特征函数,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),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 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,Thanks,