最大熵模型

1.熵

决策树中已经说明。

2.最大熵模型

2.1熵的定义

假设随机变量 的概率分布为 ， 取值为 , ，则由上节我们可知息熵的计算公式如下：

用 来表示事件 的信息量，则 即为随机变量 的平均信息量(期望)。熵满足下列不等式：

由Jensen不等式： 为凸函数，若 为凹函数，则有 ， 为凹函数可得：

其中 是 的取值个数，当随机变量退化为定值时（概率为1），那么此时的熵值为0。另一个极限就是：当随机变量服从均匀分布的时候，此时的熵值最大 。

联合熵

对于服从 的两个随机变量 ，可以形成联合熵Joint Entropy，用 表示:

条件熵

在随机变量 发生的前提下，随机变量 发生所新带来的熵定义为 的条件熵，用 表示，用来衡量在已知随机变量 的条件下随机变量 的不确定性。

若 ，条件熵为：

联合熵等于其中一个随机变量的熵加上另一个随机变量的条件熵，即： 。证明如下：

相对熵

又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。 是 中取值的两个概率分布，则 对 的相对熵是：

并约定 ， 。因此，如果存在 ，使得 ，则有 。

在一定程度上，相对熵可以度量两个随机变量的“距离”，且有 ，可以通过证明知道相对熵总是非负的，而且，当且仅当 时为零。

互信息

两个随机变量 的互信息定义为 的联合分布 和各自独立分布乘积的 相对熵，用 表示：

互信息是一个随机变量包含另一个随机变量信息量的度量。互信息也是在给定另一个随机变量知识的条件下，原随机变量不确定度的缩减量。通过查看表达式，即可知道互信息具有对称性，同样可以简单证明得互信息的非负性。

互信息与熵的关系

由此可见，互信息 是在给定另一个随机变量 知识的条件下， 不确定度的缩减量。

由于互信息的对称性，可得：

将 | 代入上式得：

一些重要表达式:

韦恩图可以很好地表示以上各变量之间的关系，对着上面的公式，应该可以很好理解下面的图表达的含义。

2.2最大熵模型

最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”(无偏性)。“最大熵模型”的核心两点：1.承认已知事物（或知识）；2.对未知事物不做任何假设，没有任何偏见。 ### 2.2.1无偏原则 例如，一篇文章中出现了“学习”这个词，那这个词可以作主语、谓语、宾语。换言之，已知“学习”可能是动词，也可能是名词，故“学习”可以被标为主语、谓语、宾语、定语等等。令 表示“学习”被标为名词， 表示“学习”被标为动词。令 表示“学习”被标为主语， 表示被标为谓语， 表示宾语， 表示定语。则有：

如果没有其他的知识，根据信息熵的理论，概率趋向于均匀。所以有：

若我们已知“学习”被标为定语的可能性很小，只有0.05。引入这个新的知识：在满足了这个约束的情况下，其他的事件我们尽可能的让他们符合均匀分布（无偏原则）：

再加入另一个约束条件：当“学习”被标作名词的时候，它被标作谓语的概率为0.95。即：

此时我们仍然坚持无偏见原则，但随着已知的知识点越来越多，其实也就是约束越来越多，求解的过程会变得越来越复杂。我们可以通过使得熵尽可能的大来保持无偏性。将上述优化及约束转化为数学公式：

且满足以下4个约束条件：

以上表达中，一般用 | ，和用 效果一样，由于 | , 为训练集集合，分布已知，即 是一个定值，因此 最大等价于 | 最大。

2.2.2最大熵模型表示

最大熵模型的一般表达式：

其中， | 是 上满足条件的概率分布,此处对数为自然对数。

假设分类模型是一个条件概率分布 | 表示输入， 表示输出。这个模型表示对于给定输入 ,以条件概率 输出 。给定训练集，学习的目标是用最大熵原理选择最好的分类模型。

特征： 其中 为这个特征中的上下文信息， 为这个特征中需要确定的信息。样本：即 特征对的训练数据集。

对于一个特征 ，定义特征函数：

则特征函数关于经验分布 在样本中的期望：

其中 为 在样本中出现的概率。

特征函数关于模型 | 与经验分布 的期望值为：

其中 为 在样本中出现的概率。

换言之，如果能够获取训练数据中的信息，那么上述这两个期望值相等，即：

上面这个等式就是最大熵模型中的限制条件，那么最大熵模型的完整提法是：

2.2.3求解最大熵模型

针对原问题，首先引入拉格朗日乘子 定义拉格朗日函数，转换为对偶问题求其极大化：

其中参数 表示 | , 表示 的向量形式，即：

按照Lagrange乘子法的思路，对参数 求偏导，可得：

求得：

由于 | ，得

这里 起到了归一化的作用。

现将求得的最优解 | 带回之前建立的拉格朗日函数L,可得到关于 的函数：

从 可以看出，最大熵模型模型属于对数线性模型，因为其包含指数函数，所以几乎不可能有解析解。我们需要使用其他方式进行逼近。

2.2.4极大似然估计

极大似然估计的MLE一般形式表示为：

其中 是对模型进行估计的概率分布， 是实验结果得到的概率分布。两边取对数，得到对数似然估计:

则对于 的对数似然估计为：

上述式子最后结果的第二项是常数项,所以最终结果等价于：

将之前得到的最大熵的解带入MLE:

上述结果跟之前得到的对偶问题的极大化解

只差一个“-”号，所以只要把原对偶问题的极大化解也加个负号，等价转换为对偶问题的极小化解,则与极大似然估计的结果具有完全相同的目标函数。因此，最大熵模型的对偶问题的极小化等价于最大熵模型的极大似然估计。

熵是表示不确定性的度量，似然表示的是与知识的吻合程度，进一步，最大熵模型是对不确定度的无偏分配，最大似然估计则是对知识的无偏理解。 且根据MLE的正确性，可以断定：最大熵的解（无偏的对待不确定性）同时是最符合样本数据分布的解，进一步证明了最大熵模型的合理性。

2.3改进的迭代尺度法(IIS)

最大熵模型为：

对数似然函数为：

通过极大似然函数求解最大熵模型的参数，即求上述对数似然函数参数 的极大值。此时，通常通过迭代算法求解，比如改进的迭代尺度法IIS、梯度下降法、牛顿法或拟牛顿法。这里主要介绍下其中的改进的迭代尺度法IIS。

改进的迭代尺度法IIS的核心思想是：假设最大熵模型当前的参数向量是 ，希望找到一个新的参数向量，使得当前模型的对数似然函数值L增加。重复这一过程，直至找到对数似然函数的最大值。

下面，计算参数 变到 的过程中，对数似然函数的增加量，用 表示，同时利用不等式： ，可得到对数似然函数增加量的下界，如下：

将上述求得的下界结果记为 ,并引入 ,f是一个二值函数，故 表示的是所有特征 出现的次数，然后利用Jensen不等式：

把上述式子求得的 的下界记为 ：

则 ,对 求偏导：

令偏导为0,若 为常数：

若 不是常数，那么无法直接求得令偏导为0时候 的值，令偏导表示为：

转为 的根，用牛顿法：

计算 的根而不是求 的极小值,所以牛顿法中是函数值除以一阶导，而不是一阶导除以二阶导。实践中，可采用拟牛顿法BFGS解决。

将上述求解过程中得到的参数 ，回代到下式中，即可得到最大熵模型的最优估计:

参考

1. 周志华 《机器学习》
2. 最大熵模型中的数学推导
3. 3月机器学习在线班第六课笔记–信息熵与最大熵模型
4. Entropy (information theory)
5. The Improved Iterative Scaling Algorithm: A Gentle Introuduction
6. Shannon entropy
7. A Mathematical Theory of Communication