作者信息

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按

算法工程师必备系列更新啦！继上次推出了算法工程师必备的数学基础后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题！

最大熵算法

一、最大熵模型MEM

设随机变量 X 的概率分布为 P(X)，熵为：。
可以证明：，其中为 X 的取值的个数。当且仅当 X 的分布为均匀分布时有。即时熵最大。

1.1 最大熵原理

最大熵Max Entropy原理：学习概率模型时，在所有可能的概率模型（即概率分布）中，熵最大的模型是最好的模型。

通常还有其他已知条件来确定概率模型的集合，因此最大熵原理为：在满足已知条件的情况下，选取熵最大的模型。
在满足已知条件前提下，如果没有更多的信息，则那些不确定部分都是“等可能的”。而等可能性通过熵最大化来刻画。

最大熵原理选取熵最大的模型，而决策树的划分目标选取熵最小的划分。原因在于：

最大熵原理认为在满足已知条件之后，选择不确定性最大（即：不确定的部分是等可能的）的模型。也就是不应该再施加任何额外的约束。
因此这是一个求最大不确定性的过程，所以选择熵最大的模型。
决策树的划分目标是为了通过不断的划分从而不断的降低实例所属的类的不确定性，最终给实例一个合适的分类。因此这是一个不确定性不断减小的过程，所以选取熵最小的划分。

1.2 期望的约束

一种常见的约束为期望的约束：，其中代表随机变量 X 的某个函数（其结果是另一个随机变量）。

其物理意义为：随机变量的期望是一个常数。
示例：当时，约束条件为：，即随机变量 X 的期望为常数。

如果有多个这样的约束条件：

则需要求解约束最优化问题：
给出拉格朗日函数：
可以求得：

将 P(X) 代入，有：

则可以求解出各个。
该式子并没有解析解，而且数值求解也相当困难。

当只有一个约束时，表示约束了变量的期望，即。此时有：
代入，解得：。即：约束了随机变量期望的分布为指数分布。
当有两个约束时，表示约束了变量的期望和方差。即：
此时有：
代入约束可以解得：
它是均值为，方差为的正态分布。即：约束了随机变量期望、方差的分布为正态分布。

二、分类任务最大熵模型

设分类模型是一个条件概率分布为输出。给定一个训练数据集，学习的目标是用最大熵原理选取最好的分类模型。

2.1 最大熵模型

根据训练集，可以得到联合分布的经验分布和的经验分布：
其中 N 为样本数量，为频数。
用特征函数描述输入和输出之间的某个事实：

特征函数是一个二值函数，但是理论上它也可以取任意值。
特征函数关于经验分布的期望定义为。这个期望其实就是约束在训练集上的统计结果的均值（也就是约束出现的期望的估计量）。
a. 如果取值为二值0,1，则表示约束 f 在训练集上出现的次数的均值。
b. 如果取值为任意值，则表示约束 f 在训练集上累计的结果的均值。
特征函数关于模型与经验分布的期望用表示：
理论上，这里使用作为的估计。
可以假设这两个期望相等，即：。
a. 时为 0，在才有可能非 0 。因此上累加。
b. 时为 0，在才有可能非 0 。因此上累加。

理论上，由于，看起来可以使用作为的一个估计。但是这个估计只考虑某个点上的估计，并未考虑任何约束。所以这里通过特征函数的两种期望相等来构建在数据集整体上的最优估计。
最大熵模型：假设有 n 个约束条件，满足所有约束条件的模型集合为：。定义在条件概率分布上的条件熵为：
则模型集合中条件熵最大的模型称为最大熵模型。

2.2 词性标注约束案例

在词性标注任务中，给定单词序列，需要给出每个单词对应的词性。如：{他们吃苹果} 对应的标注序列为 {代词动词名词} 。
假设标注仅仅与当前单词有关，与前面、后面的单词无关，也无前面、后面的标注有关。即：标注由单词唯一决定。则统计文本中所有单词及其词性，得到训练集，其中为单词数量。
假设没有任何约束，则每个单词取得任何词性的概率都是等可能的。现在发现：苹果这个单词的词性标记结果中，大部分都是名词，因此可以定义特征函数：

统计满足特征函数的样本的个数，除以样本总数。则可以认为：当数据足够多时，这个商就是统计意义下的结果：
其中：

，为二元对出现的次数。
满足特征函数的样本出现总数为：。

事实上对于任意单词，其中为所有单词的词汇表，为词汇表大小；以及对任意词性，其中为词性集合（如名词、动词、形容词….)，为词性表大小。可以任意选择搭配从而构造非常庞大的特征函数：

以及约束条件：。其中为满足特征函数的样本个数。

如果较大，则说明该约束指定的单词,词性搭配的可能性很高。
如果较小，则说明该约束指定的单词,词性搭配的可能性很低。
如果为 0，则说明该约束指定的单词,词性搭配几乎不可能出现。

待求的模型为。以矩阵的形式描述为：
其中，即单词的词性为的概率。

设单词中出现的次数为，则有：。则有：
考虑到，则根据有：

a. 其物理意义为：单词的词性为的概率 = 数据集中单词的词性为出现的次数数据集中单词出现的次数。
b. 由于，因此可以发现有：因此在这个特殊的情形下，是的估计。

事实上，真实的词性标注还需要考虑前后单词的词性的影响。比如：不可能出现连续的三个动词，也不可能出现连续的五个代词。当需要考虑前后文影响时，需要使用 HMM 模型或者 CRF 模型。

2.3 模型求解

对给定的训练数据集，以及特征函数，最大熵模型的学习等价于约束最优化问题：
将其转化为最小化问题：
其中：

是已知的。
是未知的。

将约束最优化的原始问题转换为无约束最优化的对偶问题，通过求解对偶问题来求解原始问题。
引入拉格朗日乘子 w_0,w_1,\cdots,w_n，定义拉格朗日函数：

最优化的原始问题是：，对偶问题是。
由于拉格朗日函数是凸函数，因此原始问题的解与对偶问题的解是等价的。
求解对偶问题：先求解内部的极小化问题，之后求解对偶问题外部的极大化问题。

先求解内部的极小化问题：。
它是一个的函数，将其记作：。

先用对求偏导数：

令偏导数为 0 。在时，解得：
由于，则有：。因此有：
定义为规范因子，则：
由该式表示的模型就是最大熵模型。

再求解对偶问题外部的极大化问题：。

将其解记作，即：。
求得之后，用它来表示，得到，即得到最大熵模型。

上述过程总结为：

先求对偶问题的内部极小化，得到函数，以及极值点。
再求函数的极大值，得到。
最后将得到最终模型。

可以证明：函数的最大化，等价于最大熵模型的极大似然估计。
证明如下：已知训练数据中，出现的频次为。则条件概率分布的对数似然函数为：

将对数似然函数除以常数，考虑到，其中为经验概率分布。则的对数似然函数为：

再利用：
代入，最后化简合并，最终发现它就是。

2.4 最大熵与逻辑回归

设为维变量，对于二类分类问题，定义个约束：

根据最大熵的结论，有：

以及：

当 y=1 时有：
当 y=0 时有：

最终得到：

这就是逻辑回归模型。

三、最大熵的学习

最大熵模型的学习就是在给定训练数据集时，对模型进行极大似然估计或者正则化的极大似然估计。
最大熵模型与 logistic 回归模型有类似的形式，它们又称为对数线性模型。

它们的目标函数具有很好的性质：光滑的凸函数。因此有多种最优化方法可用，且保证能得到全局最优解。
最常用的方法有：改进的迭代尺度法、梯度下降法、牛顿法、拟牛顿法。

3.1 改进的迭代尺度法

改进的迭代尺度法Improved Iterative Scaling:IIS是一种最大熵模型学习的最优化算法。
已知最大熵模型为：
其中
对数似然函数为：
最大熵模型的目标是：通过极大化似然函数学习模型参数，求出使得对数似然函数最大的参数。
IIS 原理：假设最大熵模型当前的参数向量是，希望找到一个新的参数向量，使得模型的对数似然函数值增大。

若能找到这样的新参数向量，则更新。
重复这一过程，直到找到对数似然函数的最大值。

对于给定的经验分布，模型参数从之间，对数似然函数的改变量为：

利用不等式：当时 , 有：
考虑到，以及：

根据有：
则有：

令
则。

如果能找到合适的使得提高，则对数似然函数也会提高。但是是个向量，不容易同时优化。

一个解决方案是：每次只优化一个变量。
为达到这个目的，引入一个变量 ,y)。

改写为：

利用指数函数的凸性，根据
以及Jensen 不等式有：

于是：
令
则：。这里是对数似然函数改变量的一个新的（相对不那么紧）的下界。

求对的偏导数：
令偏导数为 0 即可得到：
最终根据可以得到。
IIS 算法：

输入：

特征函数
经验分布
模型

输出：

最优参数
最优模型

算法步骤：

初始化：取。
迭代，迭代停止条件为：所有均收敛。迭代步骤为：
a. 求解，求解方法为：对每一个：
(1) 求解。其中是方程：的解，其中：。
(2) 。
b. 判定迭代停止条件。若不满足停止条件，则继续迭代。

3.2 拟牛顿法

若对数似然函数最大，则最小。
令，则最优化目标修改为：

计算梯度:
最大熵模型学习的 BFGS算法：

输入：

特征函数
经验分布
目标函数
梯度
精度要求

输出：

最优参数值
最优模型

算法步骤：

选定初始点，取为正定对阵矩阵，迭代计数器。
计算：
a. 若，停止计算，得到
b. 若：
(1) 由
(2) 一维搜索：求出
(3) 置
(4) 计算。
(5) 否则计算：
其中：。

(6) 置，继续迭代。

✄------------------------------------------------

看到这里了，说明您也喜欢这篇文章，您可以点击「分享」与朋友们交流，点击「在看」使我们的新文章及时出现在您的订阅列表中，或顺手「点赞」给我们一个支持，让我们做的更好哦。

欢迎微信搜索并关注「目标检测与深度学习」，不被垃圾信息干扰，只分享有价值知识！

算法工程师必备的机器学习--最大熵