Maximum Entropy Model 最大熵模型

最大熵模型的思想是:数据集没有约束(或满足了已知约束之后)的情况下,认为数据的概率分布是均匀的,没有偏向说哪些数据是概率更大的,这种情况也代表整个数据集是熵最大的。这是在缺乏信息的情况下能够做到的最合理的“认为”,此时通过求熵最大,来求得模型参数。这样求得的模型在进行预测时,尽管精度不保证更高,但它能覆盖到更多的情况,因为它在训练时候没有“偏见”。

举个例子,一个六面色子,在没有任何信息的情况下,假定所有数字被掷到的概率相等,为,这个假设是最合理的,也是使得熵最大的。

最大熵模型

设有样本集,其中类别是(不一定是N个类别,里面可以有相等值),需要求解合理分类器。

选择使用最大熵模型,也就是选择了软分类器。软分类器的意思是通过求解不同类别的概率并从中挑选出概率最大的那个,来决定最终分类的类别。所以这里我们的目标是写出函数的表达式。而最大熵的思想是:通过最大化训练集的条件熵,可以获得最优的表达式——

也就是找到合适的P也就是,使得上面的条件熵最大。其中为来自数据样本的经验分布,计算方法是:即在样本集中,x出现的频次在样本总数N里的占比。因为我们没法得到,所以用经验分布代替。

注:这里的表示遍历样本集的去重后的数据,而非遍历变量取值范围。比如变量取值范围是而样本集为,则表示的遍历

到目前为止,只有还不足以计算出P,我们还应该从数据中探索约束条件。

特征函数及约束条件

首先第一点,样本集里的数据一定是符合某种数据规则的,也就是之间是有某种关系的,不然任何组合都可以成为样本数据,那么求模型就没有任何意义了。我们把之间的关系定义为特征函数:

我们可能需要很多个不同特征的组合,因为x和y的关系可能不止一种。举个例子,基于下面的数据集判断“resume”的在句子里的意思是“简历”(设为0)还是“继续”(设为1):

定义2个它的函数:

1)当resume后面是名词,则resume为“继续”:

2)当resume后面是动词,则resume为“简历”:

则特征函数可以表示数据的特性:

特征函数在数据集上关于经验分布的期望为:

特征函数在数据集上关于分布的期望为:

由于我们得不到,所以只好通过替换:,所以有:

如果我们通过训练数据能训练出模型,那么两个特征函数期望相等:

于是我们得到了第一个约束条件

此外容易得到另一个约束条件,对所有可能,概率和为1:

于是我们得到了第二个约束条件

求解法(一):拉格朗日对偶化

综上,我们的问题表述为:

将最大问题改写为最小问题:

使用拉格朗日法,引进乘子,得到拉格朗日函数:

问题被转换为:

因为上面为P的凸函数,则可以进一步转化为对偶问题:

  ①

先求内部的min,通过对P的偏导数为0求得:

其中

上面的式子中,还是未知数,接下来继续对外部的max求解,可以得到最优的解,再代入上式,就可以得到的表达式了。

求解法(二):极大对数似然估计

除了上面的方法,还有一种更简单的方法可以转换最大熵问题,即转换为对数极大似然估计。
条件概率的极大似然函数,就是希望样本中各个概率乘积最大:

N个样本中可能有重复的,合并重复样本,一共有n个不重复的值,则上式可以写作:

其中C为每个值在数据集里出现的次数。

我们只要最大化上式,就可以求得的表达式。

不过此处还可以再转换一次:最大化上式跟最大化它的开N次根,是等效的,所以我们将它开N次根:

为了便于计算,再对它取log,就得到对数似然函数:

最大化上式,即就是最大熵模型的最优解。为什么?证明如下:

已知上面拉格朗日对偶化问题①为,我们只要证明等于这里的对数似然函数就好了。

通过代数计算(过程略)可以求得:

至此,证明了最大熵模型求解可以转换为极大对数似然估计。

最大熵模型和逻辑回归

最大熵模型可以推导成为逻辑回归,逻辑回归只是最大熵模型的一种特殊情况。

最大熵模型为:

其中

如果分类类别只有两种

只定义一个特征函数:

将特征函数代入到最大熵模型,求时的结果:

时的结果:

于是得到了逻辑回归模型

以上。