最大熵模型：读书笔记三

取自 自然语言处理百科

6. 最大熵原理：一个手工例子

举个例子，一个快餐店提供3种食品：汉堡(B)、鸡肉(C)、鱼(F)。价格分别是1元、2元、3元。已知人们在这家店的平均消费是1.75元，求顾客购买这3种食品的概率。如果你假设一半人买鱼另一半人买鸡肉，那么根据熵公式，这不确定性就是1位（熵等于1）。但是这个假设很不合适，因为它超过了你所知道的事情。我们已知的信息是：

以及关于对概率分布的不确定性度量，熵：

对前两个约束，两个未知概率可以由第三个量来表示，可以得到：

把上式代入熵的表达式中，熵就可以用单个概率来表示： 对这个单变量优化问题，很容易求出时熵最大，有，和。

总结一下。以上，我们根据未知的概率分布表示了约束条件，又用这些约束条件消去了两个变量，用剩下的变量表示熵，最后求出了熵最大时剩余变量的值，结果就求出了一个符合约束条件的概率分布，它有最大不确定性，我们在概率估计中没有引入任何偏差。

7. 最大熵原理：正式表述

假设有一个随机系统，已知一组状态，但不知道其概率，而且我们知道这些状态的概率分布的一些限制条件。这些限制条件或者是已知一定的总体平均值，或者是它们的一些界限。在给定关于模型的先验知识的条件下，问题是选择一个在某种意义下最佳的概率模型。Jaynes(1957)提出了一个最大熵原则：当根据不完整的信息作为依据进行推断时，应该由满足分布限制条件的具有最大熵的概率分布推得。也就是说，熵的概念在概率分布空间定义一种度量，使得具有较高熵的分布比其它的分布具有更大的值。显然，“最大熵问题”是一个带约束的最优化问题。

为方便叙述，考虑最大微分熵

对所有随机变量的概率密度函数，满足以下约束条件：

其中，是的一个函数。约束1和约束2描述的是概率密度函数的基本属性，约束3定义变量的矩，它随函数的表达式不同而发生变化，它综合了随机变量的所有可用的先验知识。为了解这个约束最优化问题，利用拉格朗日乘子法，目标函数为：

其中， 是拉格朗日乘子。对被积函数求的微分，并令其为0，有：

解得：

我们看到这个概率密度函数具有指数形式。匈牙利数学家Csiszar曾经证明，对任何一组不自相矛盾的信息，最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。我们还可以得到，在所有零均值随机向量可达到的微分熵中，多元正态分布具有最大的微分熵。最大熵的解，同时是最吻合样本数据分布的解。

8. 最大熵模型的训练：GIS算法和其他

上节我们得到，一个最大熵模型可以有效地把各种信息综合在一起（无偏见地对待不确定性），而且具有指数函数的形式，下面模型的训练就要确定这个指数函数的各个参数。最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代算法，由 Darroch 和 Ratcliff 在七十年代提出，大致可以概括为以下几个步骤：

1. 假定第零次迭代的初始模型为等概率的均匀分布。 2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际 的，就把相应的模型参数变小；否则，将它们便大。 3. 重复步骤 2 直到收敛。

Darroch 和 Ratcliff没有能对这种算法的物理含义进行很好地解释，后来是由Csiszar解释清楚的，因此，人们在谈到这个算法 时，总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用，大家只是通过它来了解最大熵模型的算法。

八十年代，Della Pietra在IBM对GIS算法进行了两方面的改进，提出了改进迭代算法IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。

由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是原IBM现微软的研究员Adwait Ratnaparkhi。Ratnaparkhi的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。

9. 最大熵模型：金融领域内的应用

最大熵模型在自然语言处理领域内得到了广泛的应用，在金融界，也能见到它的影子。当年最早改进最大熵模型算法的Della Pietra在九十年代初退出了学术界，而到在金融界大显身手。他和很多IBM语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金公司 ----(Renaissance Technologies。我们知道，决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。 Della Pietra等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预测，获得了巨大的成功。从该基金1988 年创立至今，它的净回报率高达平均每年34%。也就是说，如果1988年你在该基金投入一块钱，今天你能得到200块钱。这个业绩，远远超过股神巴菲特的旗舰公司Berkshire Hathaway（同期，Berkshire Hathaway的总回报是16倍）。

参考文献 1. 吴军《数学之美系列十六（上）-不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型》， http://googlechinablog.com/2006/10/blog-post.html

2. 吴军《数学之美系列十六（下）-不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型》，http://googlechinablog.com/2006/11/blog-post.html

3. Jaynes, E.T., 1957. ”Information Theory and Statistical Mechanics”, Physical Review, vol.106, pp.620-630. http://bayes.wustl.edu/etj/articles/theory.1.pdf

4. Haykin, Simon《神经网络原理》（第10章 信息论模型，叶世伟等译，北京：机械工业出版社，2004）

5. 王厚峰. 机器学习课程讲义之六MEM (Maximum Entropy Model).北京大学软件与微电子学院，2007年春季学期

6. Penfield, Paul. Information and Entrop. MIT Open Course, Spring 2003. http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-050JInformation-and-EntropySpring2003/CourseHome/index.htm

7. Wei, Xiaoliang《最大熵模型与自然语言处理》www.cs.caltech.edu/~weixl/research/read/summary/MaxEnt2.ppt

8. 常宝宝《自然语言处理的最大熵模型》www.icl.pku.cn/WebData_http-dir-listable/ICLseminars/2003spring/最大熵模型.pdf

9. 廖先桃《最大熵理论及其应用》http://ir.hit.edu.cn/phpwebsite/index.php?module=documents&JAS_DocumentManager_op=downloadFile&JAS_File_id=196 Technorati Tags: Maximum Entropy, MEM, 最大熵模型, 最大熵, 熵, 信息论

转自：http://johnthu.spaces.live.com/blog/cns!2053CD511E6D5B1E!246.entry

作者：胡江堂，北京大学软件学院