最大熵模型简介课件

Generative Model vs.Discriminative ModelvGenerative Model(GM):P(Y|X)=P(X|Y)P(Y)/P(X)，通过求解P(X|Y)和P(Y)来求解P(Y|X)vDiscriminative Model(DM):对P(Y|X)直接建模GMDMGaussiansMixtures of GaussiansHMMNave BayesBayesian NetworkMRF(马尔科夫随机场)Logistic RegressionSVMskNNMaxEnt(最大熵模型)MEMM(最大熵马尔科夫模型)CRF(条件随机场模型)Voted PerceptronNeural Network纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题最大熵原理(Maximum Entropy Principle)v信息熵：信息熵：熵的概念最先在1864年首先由克劳修斯提出，1948年美国电器工程师香农(Shannon,C.E)在通信的数学理论中，把“熵”用来表示一个随机事件的“不确定性”或信息量的量度。随机事件的不确定性信息量概率分布消除熵(Entropy)v一个离散随机变量X，其概率分布函数为p(x)，则X的熵定义为：v由于H只与p(x)有关，所以有时也写成H(p)v通常对数以2为底，H代表了X的信息量，也可以认为是对X进行二进制编码所需要的平均编码长度v性质：X只取某个确定值的时左边等号成立X为均匀分布时右边等号成立 联合熵、条件熵、互信息v随机变量X、Y的联合分布是p(x,y)，它们的联合熵(Joint Entropy)为v条件熵(Conditional Entropy)v互信息(Mutual Information)有人称红色方框内式子为互信息I(x,y)或者点互信息，将I(X,Y)称为平均互信息。一个是对变量的具体值求值，一个是对随机变量求值，请注意区分一个例子v一个6面的骰子，各面的点数分别为1,2,6，令X表示抛出后朝上的点数。分布一p1：p(X=1)=p(X=2)=p(X=6)=1/6分布二p2：p(X=1)=p(X=2)=1/4,p(X=3)=p(X=4)=p(X=5)=p(X=6)=1/8分布三p3:只有已知条件p(X=1)+p(X=2)=0.6H(p1)=1/6*log6*6=log62.58H(p2)=2*1/4*log4+4*1/8*log8=2.5p1vs p2:分布一具有更大的熵(信息量)，即具有更大的不确定性。p3*=argmax(H(p3),此时 p(X=1)=p(X=2)=0.3,p(X=3)=p(X=4)=p(X=5)=p(X=6)=0.1最大熵原理v最大熵原理：1957 年由E.T.Jaynes 提出。v主要思想：在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。v原理的实质：前提：已知部分知识 关于未知分布最合理的推断符合已知知识最不确定或最随机的推断。这是我们可以作出的唯一不偏不倚的选择，任何其它的选择都意味着我们增加了其它的约束和假设，这些约束和假设根据我们掌握的信息无法作出。一些现象v热力学：热学中一个重要的基本现象是趋向平衡态，这是一个不可逆过程，即朝熵增加的方向转变。v社会学：共产主义v经济学：消除垄断v哲学：中庸v家庭：婆家、娘家v最大熵原理v一个正确的概率分布p应该满足下面两个条件：（1）服从样本数据中的已知统计证据。（2）使熵最大化。其中，P表示所有可能的概率分布。最大熵原理v特征特征：用来表示从样本中获得的统计证据。也就是使得熵最大的概率分布p必须受到特征的限制。通常为一个二值函数。v例如：在词性标注中，可定义特征如下：纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题最大熵模型(Maximum Entropy Model)v假设有一个样本集合 ，我们给出k个特征 ，特征j对p的制约可以表示为 ,表示在概率分布为p时特征 的期望。表示特征 的样本期望值。最大熵模型v无任何先验知识：v存在先验知识：(求满足一组条件的最优解问题)最大熵模型v例如：给定一个词假定已知存在四种词性：名词、动词、介词、指代词v如果该词在语料库中出现过，并且属于名词的概率为70%，则判断该词属于名词的概率为0.7，属于其他三种词性的概率均为0.1v如果该词没有在语料库中出现，则属于四种词性的概率为0.25在符合已知情况的前提下，使未知事件的概率分布尽可能均匀最大熵模型条件分布v假设有一个样本集合 ，表示一个上下文，表示对应的结果。假设我们给出k个特征 ，对每个特征给出条件限制：期望概率值等于经验概率值其中：最大熵模型条件分布 是模型参数，可以看成是特征函数的权重。带约束非线性规划问题:拉格朗日乘子算法模型训练：即求 的值。纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题最大熵模型中的一些算法vGIS(Generalized Iterative Scaling)算法、IIS(Improved Iterative Scaling)算法或者Quasi Newton算法参数估计算法：用来得到具有最大熵分布的参数 的值。vFI 算法(特征引入算法，Feature Induction)解决如何选择特征的问题：通常采用一个逐步增加特征的办法进行，每一次要增加哪个特征取决于样本数据。AlgorithmsvGeneralized Iterative Scaling(GIS):(Darroch and Ratcliff,1972)vImproved Iterative Scaling(IIS):(Della Pietra et al.,1995)GIS:setupRequirements for running GIS:vObey form of model and constraints:vAn additional constraint:LetAdd a new feature fk+1:GIS algorithmvCompute dj,j=1,k+1vInitialize (any values,e.g.,0)vRepeat until convergeFor each jvCompute vUpdatewhereApproximation for calculating feature expectationProperties of GISvL(p(n+1)=L(p(n)vThe sequence is guaranteed to converge to p*.vThe converge can be very slow.vThe running time of each iteration is O(NPA):N:the training set sizeP:the number of classesA:the average number of features that are active for a given event(a,b).IIS algorithmvCompute dj,j=1,k+1 andvInitialize (any values,e.g.,0)vRepeat until convergeFor each jvLet be the solution to vUpdateCalculating IfThenGIS is the same as IISElsemust be calculated numerically.FI算法特征引入v特征选取的衡量标准：信息增益v一个特征对所处理问题带来的信息越多，越适合引入到模型中。v首先形式化一个特征空间，所有可能的特征都为候补特征。然后从候补特征集合中选取对模型最为有用的特征集合。FI算法(续)v输入：候补特征集合F，经验分布v输出：模型选用的特征集合S，结合这些特征的模型Ps1.初始化：特征集合S为空，它所对应的模型Ps均匀分布，n02.对于候补特征集合F中的每一个特征f，计算该特征加入模型后为模型带来的增益值Gf。3.选择具有最大增益值的G(S,f)的特征fn。4.把特征fn加入到集合S中，S=(f1,f2,fn);5.重新调整参数值，使用GIS算法计算模型Ps.6.n=n+1,返回步骤2。FI算法(续)v计算增益量：Kullback-Leibler(KL)距离(也叫相对熵)v两个概率p、q的KL距离：v基本思想：距离越小，分布越接近。FI算法(续)v引入第i个特征fi后的增益值：v选择的特征：纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题最大熵模型的应用词性标注v任务：根据上下文 ，求词 的词性v利用最大熵模型求v特征定义：v 即为语料库中词性为DET的that出现次数除以语料库中总词数纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题总结v最大熵模型用途：进行概率估计。在已知条件下，如何选择一个合适的分布来预测事件。v优点：1.只需集中精力选择特征，不需考虑如何使用这些特征。2.特征选择灵活，容易更换。各个特征之间可以毫不相关。便于从多个角度来描述问题。3.无需做独立性假设。纲要v最大熵原理v最大熵模型定义v最大熵模型中的一些算法v最大熵模型的应用v总结v思考题思考v如何利用最大熵模型来进行中文文本分类？v参看：李荣陆等，使用最大熵模型进行中文文本分类，计算机研究与发展，2005，42(1):94-101参考文献1.A maximum entropy approach to natural language processing(Adam Berger)2.A Brief MaxEnt Tutorial(Adam Berger)3.Learning to parse natural language with maximum entropy models(Adwait Ratnaparkhi)4.A simple Introduction to Maximum Entropy Models for Natural Language Processing(Adwait Ratnaparkhi)网上资源vhttp:/homepages.inf.ed.ac.uk/s0450736/maxent_toolkit.html，一个用Python和C+写的ME工具包。vhttp:/www.cs.cmu.edu/aberger/maxent.html，一个学习ME的链接