《最大熵原理与应用课件.ppt》由会员分享，可在线阅读，更多相关《最大熵原理与应用课件.ppt（138页珍藏版）》请在三一办公上搜索。
1、1,最大熵原理来 最大熵测量 熵集中原理 最小交叉熵原理 最大熵原理应用,最大熵原理与应用,要 点：,2,最大熵原理,3,起源于统计力学 1957年，统计物理学家Jaynes根据信息熵的概念提出了一个利用部分信息确定随机变量集合概率分布的方法，称为最大熵原理。,最大熵原理,4,信息论提供了一个基于部分知识建立概率分布的构造性准则，并导致被称作最大熵估计的一种统计推断方法。这是根据给定信息得到的最小可能偏差的估计。如果把统计力学看成统计推断的一种形式，而不是一种物理学理论，那么就会发现通常的计算原则，从确定分割函数开始，都是最大熵原理的直接结果。,最大熵原理,5,统计力学的所有已知结果，无论是平
2、衡的还是不平衡的，基本上都是最大熵原理推导出的结果。,最大熵原理,6,基本思想:求满足某些约束的信源事件概率分布时，应使得信源的熵最大可以使我们依靠有限的数据达到尽可能客观的效果克服可能引入的偏差。,最大熵原理,7,一般的最大熵原理应用于良好定义的假设空间和无噪情况且不完整的数据的推断问题。,8,最大熵原理应用于多个领域:信号检测与处理 自然语言处理生物医学环境水利 气象学经济学,9,最大熵原理的描述:在寻找满足某些约束的概率分布时，选择满足这些约束具有最大熵的概率分布。,10,约束所提供的信息是不完整的，称作部分信息;部分信息有若干种形式:随机变量矩的约束概率分布形状的约束,11,利用最大熵
3、原理主要有以下两个依据：主观依据客观依据,12,主观依据。“不充分理由原理”，也叫“中性原理”:如果对所求的概率分布无任何先验信息，没有任何依据证明某种事件可能比任何其他事件更优先，只能假定所有可能是等概率的。对“不充分理由原理”进行扩展-最大熵原理。,13,客观依据。Jaynes提出熵集中定理：满足给定约束的概率分布绝大多数集中在使熵最大的区域。具有较大熵的分布具有较高的多样性，所以实现的方法数也更多，这样越有可能被观察到。Max Plank指出:大自然好像对较大熵的情况更偏爱。在满足给定约束的条件下，事物总是力图达到最大熵。,14,最大熵原理（离散情况）,熵 其中，约束,15,离散最大熵分
4、布定理,满足约束达到最大熵的概率分布 其中,16,最大熵:,17,证 求有约束极值 待定常数,18,令,19,20,21,例,随机变量集合X，符号集A=a1,a2,a3,随机变量集合Y，符号集B=b1,b2,b3.满足:,求使H(XY)达到最大值的XY的联合分布.,22,例,解:,23,The Kangaroo Problem,Information:1/3 of kangaroos have blue eyes,and 1/3 of kangaroos are left-handedProblem:On the basis of this information alone,estimate
5、 what proportion of kangaroos are both blue-eyed and left-handed,24,X:眼睛红，不红；Y：左撇子，非左撇子；,解:,25,最大熵条件；,解:,26,Solution uses a single variable,0 x 1/3 but how to choose?Common sense says x=1/9(i.e.no correlation of attributes),Is there some function of the pi which when maximised yields this preferred
6、solution?,The Kangaroo Problem:2 x 2 Truth Table,Normalisation:p1+p2+p3+p4=1Constraints:p1+p2=1/3;p1+p3=1/3,27,例,某学校学生中，30%爱好音乐，60%爱好体育，10%爱好书法，问音乐、体育和书法都爱好的学生所占比例是多少？,28,例1 做1000次抛掷骰子的试验，求抛掷点数的平均值。解 由于抛掷次数很多，所以各点出现的频率近似等于出现的概率。假定在每次抛掷后，骰子6个面中的每一个面朝上的概率都相同，即为1/6。这里我们利用了“不充分理由原理”，因为除知道骰子有6个面外，我们没有其他任
7、何别的信息。抛掷点数的平均值：m=(1+2+3+4+5+6)/6=3.5。#,29,例1(续)做1000次抛掷骰子的试验后得知抛掷点数的平均值为4.5，求骰子各面朝上的概率分布。解 骰子的各面朝上的概率是不均匀的。除概率的归一性外，我们知道的信息仅有平均值，这对于确定6个面的概率是不完整的信息，必须利用最大熵原理。平均值的约束写为,30,计算得,所求分布为计算,31,一快餐店出售4种套餐：、鱼、鸡肉、面条和豆腐，单价分别为8元、3元、2元和1元。在某月通过调查得知，该快餐店套餐的总营业额为25万元，共有10万人次来就餐。试利用最大熵原理求本月4种套餐所占的销售份额。,32,2鱼、鸡肉、面条和豆
8、腐四种销售份额分别记 为：,33,2约束为,34,解得,35,36,连续情况,信源的熵满足,，,37,连续最大熵分布定理,达到最大值的概率密度其中最大熵为,38,最大熵测量,为使试验次数最少，需要每次试验的熵最大,39,最大熵测量例,一般性假币称重鉴别问题：设有n 枚硬币，其中仅有一枚假币，在已知或未知假币与真币之间重量关系两种条件下，通过用无砝码天平称重的方法鉴别假币，求所需的最少称重次数。,40,最大熵测量例,在每次天平称重时，天平的两端应放置相同数目的硬币，会出现3种称重结果：平衡（假币未参与称重），左倾（天平左端重），右倾（天平右端重）；每次天平称重所获得的最大信息量为（称重结果等概率
9、）,41,最大熵测量例,命题1：设有 n（）枚硬币，其中有一假，且知其较轻或较重；那么，发现假币的最少称重次数k满足：,最大熵测量例,命题2：设有n（）枚硬币，其中有一假，且满足：这些硬币分成两组A、B；A有a枚，B有b枚，a+b=n；若假币属于A，则其较轻；若假币属于B，则其较重；那么，发现假币的最少称重次数k满足：,43,最大熵测量例,命题3：设有n（）枚硬币，其中有一假，但不知轻重，还有另外的一枚真币；那么，称k次就能发现假币。,44,最大熵测量例,命题4：设有 n（）枚硬币，其中有一假，但不知轻重；那么，称k次就能发现假币。,45,最大熵测量例,将硬币编号：1，2，3，4，5，6，7，
10、8，9，10，11，12。三次称重安排如下：称重 左盘 右盘 其它 1 1,2,3,4 5,6,7,8 9,10,11,12 2 1,6,7,8 5,10,11,12 9,2,3,4 3 5,6,10,2 9,7,11,3 1,8,12,4 称重结果：0：平衡，1：左倾，-1：右倾，,46,3次称重安排可表示成矩阵形式（矩阵上一行是硬币序号）：其中，每行为称重安排，1：放左盘，-1：放右盘，0：不放。每一列为检测结果，检测结果对应的硬币序号为假币。如果结果与上面符合，则对应重量为重，如果结果不包含在上述表中，则1、-1互换，得到的重量为轻。例如，若称重结果为110则1号为假币，且重量较重；若称
11、重结果为1-1 0，1与-1交换为-110，则8号为假币，且重量较轻。,47,熵集中定理熵集中定理是最大熵原理的依据。可以证明，具有最大熵的概率分布具有最多的实现方法数，因此更容易被观察到，而且是满足某些条件的分布所产生的熵绝大部分在最大熵附近。,48,49,假设做N次随机实验，每次实验有n个结果，每种结果出现的次数为，设每种结果出现的概率为，那么当N足够大时，有。因此，实现某种特殊的概率集合 的方法数为,熵集中定理,50,斯特灵公式：,熵集中定理,51,方法数最多的分布最容易观测到方法数与熵呈指数关系对应最大熵的分布最容易观测到熵的另一种含义：表征某种分布实现方法数的多少，熵大则表明方法数大
12、。当试验次数足够多时，熵等于方法数的对数被试验总数除。,52,满足约束的一组概率所产生的熵在如下范围：其中,熵集中定理,53,当N足够大时，渐近为维数为k（=n-m-1，n为信源符号数，m为约束方程个数），置信度为1-F的 分布。通常，在很高的置信度的条件下，的值很小。,54,55,56,57,许多专家学者从不同的角度和侧面研究和定义信息。据说到目前为止已有上百种信息的定义或说法。例如，“信息是事物之间的差异”，“信息是物质与能量在时间与空间分布的不均匀性”，“信息是收信着事先不知道的东西”等等。,58,求置信度95%和99.99%时信源熵的范围。根据题意，为自由度6-1-1=4的 分布，查表
13、，(1)在置信度95%条件下,得，信源熵的范围：1.609 H 1.614(奈特)。#(2)在置信度99.99%条件下,得，信源熵的范围：1.602 H 1.614(奈特)。#,59,信息与物质、能量相同的特征:信息可以产生、消失、携带、处理和量度。信息与物质、能量不同的特征:信息可共享，可无限制地复制。,60,几种重要的最大熵分布1满足均值约束的分布是指数分布。,61,例2 连续信源X的取值区间为0，），均值E(X)=,求达到最大熵的X的分布密度和相应的最大熵。,62,63,2满足均值和均方值约束的分布是高斯分布。,64,65,3满足几何平均值约束的分布是幂律分布。,66,4,67,5,68
14、,幂律分布,幂律分布,69,幂律分布,泊松分布 个体尺度在特征尺度附近变化很小，平均值能表征整个群体特性分布。幂律分布。个体尺度在很宽的范围内变化，跨越多个数量级。积累概率分布“长尾”,70,幂律分布,泊松分布 幂律分布,71,19世纪的意大利经济学家Pareto研究了个人收入的统计分布,发现少数人的收入要远多于大多数人的收入，80/20 法则个人收入X不小于某个特定值x的概率与x的常数次幂亦存在简单的反比关系，即为Pareto定律。,72,自然界与社会生活中存在很多幂律分布现象。1932年，Zipf在研究英文单词出现的频率时,发现如果把单词出现的频率按由大到小的顺序排列,则每个单词出现的频率
15、与它的名次的常数次幂存在简单的反比关系，这种分布就称为Zipf定律。,73,在生物学和经济学中也有很多例子。企业按交易额排序、大学按科研收入或专利排序也遵循幂律。在定量财政学中，很多经验研究表明，股票波动概率分布函数在截短前服从幂律，后面有一个拖尾),74,Zipf定律与Pareto定律都是简单的幂函数。幂律分布表现为一条斜率为幂指数的负数的直线。这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。,75,双对数坐标幂律分布曲线,76,实际上，幂律分布广泛存在于物理学、天文学、计算机科学、生物学、生态学、人口统计学与社会科学、经济与金融学等众多领域中，且表现形式多种多样。,77,78,逆
16、最大熵问题,对给定熵函数和概率密度求满足最大熵的约束 已知熵：概率分布：求：,79,连续情况,已知 和 求,，,80,逆最大熵问题例,均匀分布 指数分布：高斯分布：,81,逆最大熵问题例,拉普拉斯分布：伽玛分布,82,逆最大熵问题例,Pareto分布 贝塔分布,83,84,.,85,.,86,最小交叉熵原理,87,88,交叉熵法在信息处理中，往往要求一个概率密度接近另一个目标概率密度，而目标概率密度的参数未知的。这样，将（12.3.2）式作为目标概率密度，为含有参数的概率密度，写成，可以通过改变u使交叉熵最小。由于,89,仙农建立了三项基本技术的理论基础信息论是前两项技术的理论基础,90,信息
17、理论方法的应用,最大熵谱分析 信号功率谱的估计通常要通过计算相关函数来实现。常规的谱估计方法要将信号的样值序列进行适当截短，即利用在有限时间内的样值计算相关函数，然后进行功率谱的估计。如果所使用的时间段太长，就不能保证信号的平稳性，而使用的时间段太短，就会降低功率谱的分辨率。,91,92,Burg提出最大熵谱估计:在所计算的自相关函数的约束下，把使信源熵率最大的功率谱作为估计的结果。一个限带高斯连续信源的熵由它的功率谱所决定，而通过计算得到的信号的自相关函数序列就是功率谱的约束。最大熵谱估计就是求在此约束下使熵率达到最大的信号的功率谱。,93,94,伯格最大熵定理,设 对所有i，那么，满足上面
18、约束的最大熵率随机过程 是如下形式的p阶高斯马尔科夫过程：其中，为独立同分布，且 的选择满足上面的约束。注：未假定：零均值，高斯和广义平稳,95,伯格最大熵定理,熵率 Yule-Walker方程,96,最大熵谱估计,熵率:自相关函数序列就是功率谱的约束:令最大熵谱估计就是使J最大的谱，令得,97,98,谱估计方法,经典谱估计（非参数法）相关法:Blackman-Turkey,（间接法)周期图法(periodogram):(直接法）Bartlett提出,Welch 改进现代谱估计(参数法）AR谱估计MA谱估计ARMA谱估计最大熵(maximun entropy)谱估计最大似然(maximum-l
19、ikelihood)谱估计,99,谱估计方法,AR谱估计模型自相关法，Yule-Walker法协方差法Burg 法(最大熵法),100,AR谱估计方法,自相关法，Yule-Walker法保证稳定加窗精度差,101,AR谱估计方法,协方差（Covariance）法 存在稳定性问题不加窗精度高,102,AR谱估计方法,Burg法计算反射系数保证稳定精度高,103,谱估计方法比较,AR谱估计经典方法（BARTLETT）Yule-Walker法ML法Burg 法(最大熵法)（见比较图）,104,105,106,最小交叉熵谱估计,最小交叉熵谱估计可以看成考虑到一个先验估计的 自相关函数另一种延伸方式；在
20、谱估计时，使被估计的过程和先验估计之间的交叉熵最小；如果先验估计是平坦谱，那么最小交叉熵谱估计就归结为最大熵谱估计。,107,最小交叉熵谱估计,设概率密度p属于某概率集合P，该集合是已知的，但p本身未知，q为先验密度，同时还有p满足的约束条件。最小交叉熵谱估计的原理就是：在所有满足约束的密度中，选择与先验密度q交叉熵最小的概率密度p。由于利用了先验信息，最小交叉熵谱估计比最大熵谱估计的性能有改善。,108,最小交叉熵谱估计,109,最小交叉熵谱估计,110,最小交叉熵谱估计,111,最小交叉熵谱估计,112,最大熵建模及其在自然语言处理中应用1.最大熵建模基本原理建模就是构造一个精确表示随机过
21、程行为的随机模型，估计在给定上下文x条件下输出y 的概率p（y|x），其中x为模型的输入，y为输出。为设计一个适合某种过程的模型，需要对该过程的行为进行一段时间的观察，收集样本值作为训练数据。设训练样本集有N对样本值，表示为(x1,y1),(x2,y2),(xN,yN)。,113,定义两种分布，一是经验分布，就是通过训练数据得到的分布；二是模型分布，就是信源实际的分布。训练集合中数据对的分布称为经验分布，定义为 在训练集合中出现的次数通常，一个特殊的数据对要么不出现，要么出现多次。最大熵建模就是以训练数据为依据，用最大熵原理构造一个产生训练样本经验分布 的统计模型，这里估计的是条件概率,114
22、,建模的一个重要步骤就是从训练数据中提取特征。特征或特征函数指的是x与y之间存在的某种特定关系，可以用一个输出为0或1的二值函数（或示性函数）表示。特征实际上是一种映射：其中，。，A为y的符号集，表示一个可能的类集合；B为x的符号集，为上下文集合。,115,对于一个特征(x0,y0)，定义特征函数：,116,实际上，特征函数的定义与所解决的问题有关。以文本分类问题为例。假设有4类文本：政治、经济、体育和文艺。每个词在不同类的文本中出现的概率是不同的，特别是具有代表性的词类。例如，“货币”一词经常出现在经济类的文本中，而“比赛”一词经常出现在体育类的文本中。对于一个特征（“球”，“运动”），其中
23、“球”属于上下文集合，“运动”属于类集合，其特征函数定义为：,117,用经验分布对特征求平均是有用的统计量，表示为用模型 对f 的期望值为其中，为训练样本中x的经验分布。,118,我们令经验分布特征平均值与模型分布特征平均值相同，即要求对每一个特征有，或 称为约束方程或简称约束。当样本数足够多时，可信度高的特征的经验概率与期望概率是一致的。,119,定义P表示所有满足（12.4.15）约束的条件概率分布的集合，即，条件熵表示为,120,121,最大熵建模就是：从满足约束条件的集合P中，选择具有 最大熵的分布，即 这是一个求有约束优极值化问题，,122,123,应用拉格朗日乘子法，引入拉格朗日乘
24、子，得,124,结论：最大熵建模的解p*满足：（1）（2）（3）（4）是惟一的。,125,最大熵建模在简单情况可以求出解析解，例如有一、二个约束情况。但一般情况最大熵问题没有显式解，求参数必须借助数值解法。有些实际问题，有时可能有上千个约束条件，计算量和花费的时间巨大，必须使用有效的算法。一个专门用于最大熵问题的就是由Danroch 和Rateliff于1972年提出了一个称为GIS(Generalized Iterative Scaling Algorithm)的算法，该算法要求特征为非负值，没有解析解，收敛速度较慢。D.Pietra等改进了原有的求解算法，降低了求解的约束条件，提出了IIS
25、(Improved Iterative Scaling Algorithm)算法，增加了算法的适用性，IIS算法是目前最大熵参数求解中的常用算法。,126,最大熵统计模型的优缺点最大熵建模方法有很多优点：（1）与极大似然估计结果同，所建立的模型是唯一的；（2）最大熵统计模型可以灵活地设置约束条件。通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度；（3）通常性能优于其他方法。最大熵统计模型的缺点：（1）运算量大；（2）存在过拟合问题，通常在求极值时需加入先验随机函数进行平滑。,127,1最大熵建模在自然语言处理中的应用最大熵建模已成功应用到自然语言处理的许多方面，其中包括：
26、单词聚类(S.Pietra)机器翻译（A.L.Berger）统计属性-值文法(S.Abney)句子边界检测，词类标注(Ratnaparkli,1998)自适应统计语言建模(Rosenfeld,1996)组块分析(Osborne,2003;Koeling,2003)垃圾邮件过滤(Zhang,2003)名实体识别(A.Borthwick),128,最大熵原理在经济学中的应用前面指出物理学中的波耳兹曼分布是一个指数分布。推导该定律的基本依据是能量守恒定律。因此，我们可以推断，在一个大系统中任何守恒的量都应该具有指数概率分布。在物理学中指数Boltzmann-Gibbs分布和封闭经济系统中的货币的平衡
27、分布具有类似性，与能量类似，在一个封闭经济体中，货币在经济代理商之间的相互作用中在局部是守恒的，所以货币也遵循Boltzmann-Gibbs分布，其等效温度等于平均每个代理商的货币量。,129,财富不但包含货币还包含物质财富，所以不守恒，一个早期的研究者Vilfledo Pareto在19世纪末发现，在一个人口均匀分布的地理范围内，人们之间的财富的分布按一个幂律分布，因此这种分布经常称做Pareto分布。下面利用最大熵原理推导和分析封闭的经济体中货币和财富的分布。,130,131,132,133,在总货币守恒的市场中，货币的分配服从Boltzman-Gibbs分布。,134,135,136,137,138,谢谢大家！,
