最大熵模型是近年来自然语言处理领域最成功的一种机器学习算法。最大熵模型,通俗地讲就是把可以明确的信息尽量提取出来,不知道的信息(不确定的)保留,将预测风险降到最低。
1 信息量、信息熵的概念
一个例子:假币问题
假设有5个硬币,分别编号为1、2、3、4、5。这5个硬币中,有1个是假的,且假币比真币轻。现在有一架没有砝码的天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一:
(1)左边比右边轻。
(2)右边比左边轻。
(3)两边同样重。
试问:至少要称量几次才能确保找到假币?
一种可能的称量方法如图4所示。
图4
首先,将1号和2号硬币一起放在天平的左边,3号和4号硬币一起放在天平右边。可能的结果有3种,即左边轻、右边轻和相等。如果结果相等则5号硬币是假币,如果出现某一边轻,则说明假币在轻的这一边。接着第二次称量,比较轻的这边的两个硬币的重量,较轻的则为假币。
这个过程至少要称量硬币两次,那么为什么是两次呢?
首先我们把这个问题转化为一个数学问题:令X表示假硬币的序号:X∈X={1,2,3,4,5};令Yi表示第i次使用天平得到的结果:Y∈Y={1,2,3};1表示“左轻”,2表示“平衡”,3表示“右轻”。
用天平称n次,获得的结果是:Y1,Y2…Yn;由于会称n次,结果有3个,那么Y1,Y2…Yn的所有可能排列组合的数量是3n。
根据题意,该问题就是要求通过Y1,Y2…Yn确定X。即影射map(Y1,Y2…Yn)=X;我们知道Y1Y2…Yn的变化数量是大于等于X的变化数量,即3n≥5。
而一般意义上,这类问题中都会产生下面的公式。
能否通过这个公式推导出最小的称量次数n呢?一个自然的想法是对等式两边取对数,这里的Y和X都是非零的,那么去对数后可以变换为如下形式:
可以看到,n是有最小值的,且最小值的大小与可能的假币X的个数以及天平可能的结果Y有关。依据题目,假币可能位于5个硬币之中且机会均等(概率为1/5),X=5,而天平的结果有三种,即Y=3,那么将其带入公式为(log以2为底):
取n大于1.46的最小整数为2,即本题的答案。
在这个题目中,5个硬币中每个硬币是假币的概率其实是均等的,即1/5。那么如果这种概率不是均等的会怎样呢?题目如下。
假设有5个硬币,分别编号为1、2、3、4、5,其中一个是假的,假币比真币轻。已知第1、2号硬币是假硬币的概率都是1/3;第3、4、5号是假硬币的概率都是1/9。现在有一架没有砝码的天平,假设使用天平n次能够找到假币,那么n的期望值至少是多少?
此时,有1/3的概率是假币的硬币有两个,有1/9的概率是假币的硬币有三个,那么n值计算公式如下:
1.事件的信息量
在上面的两个问题中,都使用了如下公式:
h(x)表示事件发生的信息量,表示事件发生的概率。
需要注意以下几点:
(1)当事件发生的概率小时,Px极小,且-log以2为底的函数是单调递减函数,那么计算出的h(x)很大,即事件发生的概率越小,其信息量越大。
(2)假设X1、X2两个事件独立,则有:
那么X1、X2两个事件同时发生的信息量为:
同理,若某随机变量只包含事件X1、X2,该随机变量的信息量期望就可以被定义为:
这个公式就是信息熵的定义公式。
2.随机变量的信息熵
信息熵的定义如下:
X是一个随机变量,H(X)表示X的信息熵,P(X)表示随机变量X中某事件x的发生概率。另外经典信息熵中log以2为底,单位是bit(比特);若log以e为底,单位是nat(奈特)
信息熵是指某随机变量各个事件(或状态)的信息量的期望值,其大小与P(X)有关。期望值代表了随机变量的不确定性程度。在理解信息熵时,需要考虑以下两种情况:
(1)假定随机变量中各个事件是均匀分布的,即每个事件发生概率一样,那么这个随机变量中的事件或状态越多,不确定性也就越大,信息熵值也就大,反之则越小。例如随机变量“性别”,对于“男性”这一个状态,显然P(男性)=1,那么其信息熵值为0,代表不确定性程度最低。
(2)假定随机变量中各个事件与状态个数是确定的,可以证明概率平均分布的随机变量是最不确定的,即信息熵值是最大的,如下所示。
H(X)代表随机变量X的信息熵,|X|表示随机变量X中的事件数。
这里以包含两个事件的随机变量为例,假定某随机变量X包含事件A和B,那么其信息熵为:
P表示事件A发生的概率,1-P表示事件B发生的概率。
此时令P从0~1之间取值,那么相应信息熵值的变化如图5所示。
图5
从图中可以看到,当P=0时,X中只有事件A发生;而当P=1时,X中只有事件B发生,其信息熵最小为0;而当事件A与事件B概率平均分布时,即当P=0.5时,信息熵值达到最大,随机变量X的不确定性程度最高。
2 最大熵模型
1.最大熵模型的原则与理解
之前介绍过信息熵的概念,以及信息熵的理解。我们已经知道均匀分布的随机变量是最不确定的,即信息熵值是最大的:
另外信息熵本质上将随机变量中事件发生的概率P与信息熵H结合在了一起,即定义了一个函数(概率分布函数)到一个值(信息熵)的映射。
P(x)àH (函数à数值)
当信息熵值达到最大时,事件的发生是没有限定条件的(关于假币的第一个问题)。当有条件时,即得知随机变量中某些事件的概率时(关于假币的第二个问题),就是最大熵模型考虑的范畴。
最大熵模型的原则在于,承认已知事件,对未知事物不做任何假设,没有任何意见。在此情况下,随机变量的信息熵是最大的,也就是说随机变量的不确定性程度是最高的。
为什么要关注最大的信息熵呢?因为在一个自封闭系统中,事物的运动总是朝向均匀分布的方向,即熵最大的方向,如图6所示。
图6
那么若已知某随机变量的一些事件的分布,对于未知事件的分布,最合理的假设便是随机变量熵最大时的分布,即平均(均匀)分布。
下面我们来看一个例子:
我们知道词语“学习”既可以表示动词,也可以表示名词。“学习”在句子中还可以被标注为主语、谓语、宾语、定语。令随机变量X表示“学习”的词性,其有两种状态:X1表示“学习”被标注为动词,X2表示名词;令随机变量Y表示“学习”的句子成分,其有四种可能:Y1表示主语,Y2表示谓语,Y3表示宾语,Y4表示定语。
(1)若没有任何的已知信息,那么根据最大熵原则,则有:
(2)若在已知“学习”被标为定语的可能性很小,只有0.05,则有:
根据最大熵原则,随机变量Y的剩下三种事件的分布应是均匀分布,随机变量X不变,则有:
(3)若第(2)条的基础上又已知当“学习”被标为动词时,那它被标为谓语的概率为0.95,这里涉及了条件概率问题,即已知约束条件:
要求计算X和Y的分布,使H(Y|X)达到最大值,则有:
给定约束条件,计算约束条件下熵最大的随机变量分布,这就是一个典型的最大熵模型。
2.最大熵模型的一般形式
给定随机变量与,其特征函数,其中,最大熵模型的一般形式为:
即
P={p | p是X上满足条件的概率分布},log为自然对数,表示边缘分布在训练数据集中的经验分布,代表条件分布。
约束条件为:
分别代表联合分布与其边缘分布在训练数据集中的经验分布。
3.最大熵模型
最大熵模型如何进行学习呢?下面进行介绍。
注意到最大熵求解是一个带有约束的最优化问题,可以构造拉格朗日乘子将有约束最优化问题转换为无约束最优化问题:
将原问题求解转化为其对偶问题求解,因为为凸函数,原问题与对偶问题最优解一致:
求解过程变为
第一步,求对偶问题内部极小化,求对偏导,令其为0:
并令,解得:
由于,所以可得:
代表。
称为规范化因子。
第二步,求对偶问题外部极大化,将第一步解出的带入中,得到函数,
。
问题变为求解函数,
根据上述公式,可知最大熵模型的目标是对的极大化,此时就可以使用数学优化方法求解,如梯度下降、牛顿与拟牛顿法,这里不再介绍。