最大熵模型+最大似然估计

前言

最近在回顾李航的统计学习方法[1], 看到这一章, 准备好好梳理一下, 更加深入地理解原理以及背后的思想. 作者在这一章介绍了最大熵模型并且推导了对偶函数的极大化等价于最大熵模型的极大似然估计, 面对一大堆的概念, 我重新回顾了一遍其中相关的内容.

1 最大熵模型

最大熵原理是在 1957 年由 E.T.Jaynes 提出的，其主要思想是，在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。吴军数学之美[2]第十六章中通俗地描述其为, 当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。他举了一个某次去AT&T做关于最大熵模型的报告时的栗子:

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

下面是一些概念的定义

熵: 这里指的是信息论里的熵, 是接收的每条消息中包含的信息的平均量. 也可以理解为信息的不确定度, 越随机的信源的熵越大. 就像我们平时说话, 出现少的词往往包含更大的信息量, 比如我中午要去吃肯德基的炸鸡, 在这句话里, "的"字平时非常常用, 但是几乎没什么意义, 但是肯德基跟炸鸡平时出现的相对少, 却包含了更大的信息量. 数学上的定义如下

假设离散随机变量X的概率分布是P(X), 则其熵是

公式1 (P80-6.9)

熵满足以下不等式:

公式2

其中|X|是X的取值个数.当且仅当X的分布是均匀分布时右边等号成立, 也就是说, 当X服从均匀分布时, 熵最大.

最大熵原理: 概率模型学习的一个准则, 最大熵原理认为, 学习概率模型时, 在所有可能的概率模型中, 熵最大的模型是最好的模型. 通常用约束条件来确定概率模型的集合, 所以, 最大熵原理也可以表述为在满足约束条件的模型集合中选择熵最大的模型. 话说李宁的广告语叫一切皆有可能, 字面上的意思不就是最大熵模型么.

那么问题来了, 最大熵模型里的熵是怎么定义的.

准确地说, 是模型P(Y | X)与经验分布P(X)的条件熵. 也就是:

可以理解为模型在当前样本的特征分布下预测结果的熵, 熵越大, 预测结果在各个类之间分布越均匀.

公式3 模型的条件熵

那上文提到的约束条件又是什么?

我们用特征函数f(x, y)描述输入x和输出y之间的某个事实, 定义为

公式4 p82

所以特征函数关于经验分布P(X,Y)的期望值:

公式5 p82

特征函数关于模型P(Y|X)与经验分布P(X)的期望值:

公式6 p83

如果模型能够学习到训练数据中的信息, 那么就可以假设这两个期望值相等.

公式7 p83 6.11

这就形成了我们模型学习的约束条件, 假定满足条件的模型集合为

公式8 p83 6.12

所以 最大熵模型的学习, 等价于学习以下最优化问题.

学习过程就是对偶问题的求解.

公式9 p83

学习方法:

最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：

1. 假定第零次迭代的初始模型为等概率的均匀分布。

2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。

3. 重复步骤 2 直到收敛。

GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定.

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

最大似然估计

似然函数: 

公式10 似然函数

从字面上来看, 似然(likelihood)与概率(probability)没有太大区别, 都代表可能性. 下面是一些我对这两个概念的直观理解.

概率, 表示在所有观测样本中, 样本x出现的可能性. 在这里, 模型的分布以及参数都是确定的.

似然, 标识在模型或者说分布确定的情况下, 对应不同的参数, 样本x出现的可能性.

最大似然估计, 就是在选定模型的前提下, 学习最符合当前观测样本的参数, 本质上是一种典型的经验风险最小化方法. 在样本量比较小的时候, 观测并不能代表整体, 因此, 这种学习方法并不会太好, 容易产生过拟合. 

下一篇关于最似然估计以及最大后验概率将详细描述最大似然法.

其他

首先是一点个人的理解: 二者都属于经验风险最小化的参数学习方法, 最大熵模型追求的目标是, 在对当前样本预测尽可能与观测值一致的前提下, 是的各分类之间尽可能均匀, 也就是模型在当前样本上面预测的条件熵尽可能的大; 最大似然估计则是在确定模型的前提下, 尽可能使各个样本点在预测时发生的概率大. 在[3]中, 大佬证明了最大熵模型的对偶问题求解方法, 等价于最大熵模型的极大似然估计. 

最大熵原理的实质就是，在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，这是我们可以作出的唯一不偏不倚的选择，任何其它的选择都意味着我们增加了其它的约束和假设，这些约束和假设根据我们掌握的信息无法作出。

参考文献

[1]李航著.统计学习方法[M].清华大学出版社,2012.

[2]吴军.数学之美[M].人民邮电出版社,2014.

[3]常宝宝.自然语言处理的最大熵模型[D].北京大学,1999.