谈谈最大熵模型

http://hanycn.spaces.live.com/blog/cns!9BBB4846B30BBCB0!384.entry




Google （谷歌）中国的博客网志，走近我们的产品、技术和文化

数学之美 系列十六（上） 不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型
2006年10月8日 上午 07:27:00






发表者：Google 研究员，吴军

[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为最大熵原理(the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]

前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。

让我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo"，利用语言模型，根据有限的上下文(比如前两个词)，我们能给出两个最常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了，即使利用较长的上下文也做不到。当然，我们知道如果通篇文章是介绍文学的，作家王小波的可能性就较大；而在讨论两岸关系时，台湾学者王晓波的可能性会较大。在上面的例子中，我们只需要综合两类不同的信息，即主题信息和上下文信息。虽然有不少凑合的办法，比如：分成成千上万种的不同的主题单独处理，或者对每种信息的作用加权平均等等，但都不能准确而圆满地解决问题，这样好比以前我们谈到的行星运动模型中的小圆套大圆打补丁的方法。在很多应用中，我们需要综合几十甚至上百种不同的信息，这种小圆套大圆的方法显然行不通。

数学上最漂亮的办法是最大熵(maximum entropy)模型，它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥，但是它的原理很简单，我们每天都在用。说白了，就是要保留全部的不确定性，将风险降到最小。让我们来看一个实际例子。

有一次，我去 AT&T 实验室作关于最大熵模型的报告，我带去了一个色子。我问听众“每个面朝上的概率分别是多少”，所有人都说是等概率，即各点的概率均为1/6。这种猜测当然是对的。我问听众们为什么，得到的回答是一致的：对这个“一无所知”的色子，假定它每一个朝上概率均等是最安全的做法。（你不应该主观假设它象韦小宝的色子一样灌了铅。）从投资的角度看，就是风险最小的做法。从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。接着，我又告诉听众，我的这个色子被我特殊处理过，已知四点朝上的概率是三分之一，在这种情况下，每个面朝上的概率是多少？这次，大部分人认为除去四点的概率是 1/3，其余的均是 2/15，也就是说已知的条件（四点概率为 1/3）必须满足，而对其余各点的概率因为仍然无从知道，因此只好认为它们均等。注意，在猜测这两种不同情况下的概率分布时，大家都没有添加任何主观的假设，诸如四点的反面一定是三点等等。（事实上，有的色子四点反面不是三点而是一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。

最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。

回到我们刚才谈到的拼音转汉字的例子，我们已知两种信息，第一，根据语言模型，wang-xiao-bo 可以被转换成王晓波和王小波；第二，根据主题，王小波是作家，《黄金时代》的作者等等，而王晓波是台湾研究两岸关系的学者。因此，我们就可以建立一个最大熵模型，同时满足这两种信息。现在的问题是，这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文（前两个词）和主题预测下一个词的最大熵模型，其中 w3 是要预测的词（王晓波或者王小波）w1 和 w2 是它的前两个字（比如说它们分别是“出版”，和“”），也就是其上下文的一个大致估计，subject 表示主题。



我们看到，在上面的公式中，有几个参数 lambda 和 Z ，他们需要通过观测数据训练出来。

最大熵模型在形式上是最漂亮的统计模型，而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型的诸多参数，以及最大熵模型在自然语言处理和金融方面很多有趣的应用。
固定链接 |



第一次看见“熵”是在高中物理，是热力学吧。
大概有这么个例子：
容器中有冷空气和热容器，中间绝热隔离，如果把绝热隔离的东西拿掉，冷热空气会混合，最终完全混合。宏观上看来就是：温度中和了。
微观看来：
1.在隔离还存在前，冷热空气分子都是随机超四面八方运动的；（无序状态：随机运动）
2.隔离拿掉后，大量冷空气分子向热空气运动，同时更多热空气分子向冷空气运动；（有序状态：定向运动）
3.经过冷热空气的中和，最终整体达到一个新的温度，此时空气分子运动与开始状态一样：四面八方；（无序状态）

分析下：
状态一 把冷热空气分别看作两个不同的系统，他们的状态一样，都是无序的。
状态二 冷热空气混合的过程，他们相互混合，此过程状态是有序的。（定向运动）
状态三 混合完毕的空气看作一个系统，此时的状态是无序的。（朝各个方向的随机运动）

可以看到，同一个系统中的物质状态是趋于无序的。

由此德国物理学家克劳伊士于1865年引入了一个新的概念：熵(entropy)
熵表示系统的无序程度。越无序，熵越大。
所有系统的最终状态必然是熵增加至最大值的状态。

宇宙大爆炸，就是由原来的一个小点向四周空间扩散的过程，也就是说熵越来越大。
熵在生态学中是表示生物多样性的指标。从单细胞生物进化到现在的形形色色哦生物，熵也是越来越大。
熵的概念在1948年由克劳德·艾尔伍德·香农第一次引入到信息论中来，成为信息熵(information entropy)。

熵在信息论的定义如下：
如果有一个系统S内存在多个事件S = {E1,...,En}, 每个事件的概率分布 P = {p1, ..., pn}，则每个事件本身的信息为
I_e = -\log_2 {p_i} （对数以2为底，单位是比特） I_e = -\ln {p_i} （对数以e为底，单位是纳特/nats）
如英语有26个字母，假如每个字母在文章中出现次数平均的话，每个字母的信息量为
I_e = -\log_2 {1\over 26} = 4.7
；而汉字常用的有2500个，假如每个汉字在文章中出现次数平均的话，每个汉字的信息量为
I_e = -\log_2 {1\over 2500} = 11.3
整个系统的平均信息量为
H_s = \sum_{i=1}^n p_i I_e = -\sum_{i=1}^n p_i \log_2 p_i
这个平均信息量就是信息熵。因为和热力学中描述热力学熵的玻耳兹曼公式形式一样，所以也称为“熵”。
如果两个系统具有同样大的信息量，如一篇用不同文字写的同一文章，由于是所有元素信息量的加和，使用汉字的应用的汉字就比使用英文字母的使用的字母要少。所以汉字印刷的文章要比其他应用总体数量少的字母印刷的文章要短。即使一个汉字占用两个字母的空间，汉字印刷的文章也要比英文字母印刷的用纸少。
实际上每个字母和每个汉字在文章中出现的次数并不平均，因此实际数值并不如同上述，但上述计算是一个总体概念。使用书写单元越多的文字，每个单元所包含的信息量越大。

所有跟帖： 

• 对数及其运算法则 -marketreflections- ♂ (10911 bytes) () 07/12/2008 postreply 14:58:26

• 什么时候才需要对数据进行自然对数处理？ 人大经济论坛 -marketreflections- ♂ (583 bytes) () 08/19/2008 postreply 12:49:39

• 数字不具有实质性的意义（忽略矢量性），累积等变换处理 -marketreflections- ♂ (5421 bytes) () 08/19/2008 postreply 12:54:54

• 时间序列数据回归分析时,会犯谬误回归的错误, -marketreflections- ♂ (7723 bytes) () 08/19/2008 postreply 13:02:47

• 异方差 -marketreflections- ♂ (18369 bytes) () 08/19/2008 postreply 13:08:42

• “S”曲线的增长率是先增后减还是一直减少 图 (图) -marketreflections- ♂ (3031 bytes) () 08/20/2008 postreply 09:25:46

• “增长率”和“增长速率” -marketreflections- ♂ (2348 bytes) () 08/20/2008 postreply 09:29:41

• 增长速率是单位时间增长率的变化量 -marketreflections- ♂ (1649 bytes) () 08/20/2008 postreply 09:32:17

• 种群无限环境中的指数增长 种群有限环境中的逻辑斯谛增长 -marketreflections- ♂ (4153 bytes) () 08/20/2008 postreply 09:42:48

• 技术扩散的逻辑曲线----逻辑斯蒂增长模型 -marketreflections- ♂ (1140 bytes) () 08/20/2008 postreply 09:45:27

• 逻辑斯蒂增长模型(Logistic growth model) (图) -marketreflections- ♂ (1279 bytes) () 08/20/2008 postreply 09:49:18

• 逻辑斯蒂增长模型: K代表环境容量,(K－N)/K代表环境阻力 -marketreflections- ♂ (1292 bytes) () 10/05/2008 postreply 17:00:07

• 种群数量增长和数学曲线 -marketreflections- ♂ (4222 bytes) () 10/05/2008 postreply 17:07:02

• 几种反应 体系平衡 突然改变一个条件，扰动，偏离原平衡 -marketreflections- ♂ (6314 bytes) () 11/17/2008 postreply 08:03:05

• 种群数量增长和数学曲线 -marketreflections- ♂ (4222 bytes) () 10/05/2008 postreply 17:07:53

• 金融均衡理论的基础是一价原理，或无套利原理 -marketreflections- ♂ (5869 bytes) () 08/20/2008 postreply 09:56:30

• 指数增长期 逻辑斯蒂期 衰退期 -marketreflections- ♂ (22480 bytes) () 08/20/2008 postreply 10:10:17

• 最大信息熵原理 -marketreflections- ♂ (2080 bytes) () 10/04/2008 postreply 18:42:32

• 最小作用量原理 SimWe仿真论坛 » J03：其他网络资源交流 -marketreflections- ♂ (9147 bytes) () 10/04/2008 postreply 19:46:58