最大熵算法

一、最大熵模型MEM

  1. 设随机变量 的概率分布为 ，熵为： 。

    可以证明： ，其中 为 的取值的个数。

    当且仅当 的分布为均匀分布时有 。即 时熵最大。

1.1 最大熵原理

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

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

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

    • 最大熵原理认为在满足已知条件之后，选择不确定性最大（即：不确定的部分是等可能的）的模型。也就是不应该再施加任何额外的约束。

      因此这是一个求最大不确定性的过程，所以选择熵最大的模型。

    • 决策树的划分目标是为了通过不断的划分从而不断的降低实例所属的类的不确定性，最终给实例一个合适的分类。因此这是一个不确定性不断减小的过程，所以选取熵最小的划分。

1.2 期望的约束

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

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

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

    则需要求解约束最优化问题：

  3. 给出拉格朗日函数：

    可以求得：

    • 将 代入 ，有：

      则可以求解出各个 。

    • 该式子并没有解析解，而且数值求解也相当困难。

  4. 当只有一个约束 时，表示约束了变量的期望，即 。此时有：

    代入 ，解得： 。

    即：约束了随机变量期望的分布为指数分布。

  5. 当有两个约束 时，表示约束了变量的期望和方差。即：

    此时有：

    代入约束可以解得：

    它是均值为 ，方差为 的正态分布。即：约束了随机变量期望、方差的分布为正态分布。

二、分类任务最大熵模型

  1. 设分类模型是一个条件概率分布 为输入， 为输出。

    给定一个训练数据集 ，学习的目标是用最大熵原理选取最好的分类模型。

2.1 最大熵模型

  1. 根据训练集 ，可以得到联合分布 的经验分布 和 的经验分布 ：

    其中 为样本数量， 为频数。

  2. 用特征函数 描述输入 和输出 之间的某个事实：

    • 特征函数是一个二值函数，但是理论上它也可以取任意值。

    • 特征函数 关于经验分布 的期望定义为 ： 。

      这个期望其实就是约束 在训练集上的统计结果的均值（也就是约束 出现的期望的估计量）。

      • 如果 取值为二值0,1，则表示约束 在训练集上出现的次数的均值。
      • 如果 取值为任意值，则表示约束 在训练集上累计的结果的均值。

    • 特征函数 关于模型 与经验分布 的期望用 表示：

      理论上 ，这里使用 作为 的估计。

    • 可以假设这两个期望相等，即：。

      • 在 时为 0，在 才有可能非 0 。因此 仅仅在 上累加。
      • 在 时为 0，在 才有可能非 0 。因此 仅在 上累加。

  3. 理论上，由于 ，看起来可以使用 作为 的一个估计。

    但是这个估计只考虑某个点 上的估计，并未考虑任何约束。所以这里通过特征函数的两种期望相等来构建在数据集整体上的最优估计。

  4. 最大熵模型：假设有 个约束条件 ，满足所有约束条件的模型集合为： 。

    定义在条件概率分布 上的条件熵为：

    则模型集合 中条件熵最大的模型称为最大熵模型。

2.2 词性标注约束案例

  1. 在词性标注任务中，给定单词序列 ，需要给出每个单词对应的词性 。如 ：{他们 吃 苹果} 对应的标注序列为 {代词 动词 名词} 。

    假设标注仅仅与当前单词有关，与前面、后面的单词无关，也无前面、后面的标注有关。即：标注 由单词 唯一决定。

    则统计文本中所有单词及其词性，得到训练集 ，其中 为单词数量。

  2. 假设没有任何约束，则每个单词取得任何词性的概率都是等可能的。现在发现：苹果 这个单词的词性标记结果中，大部分都是名词，因此可以定义特征函数：

    当为苹果且为名词时其他情况

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

    其中：

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

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

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

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

  4. 待求的模型为 。以矩阵的形式描述为：

    其中 ，即单词 的词性为 的概率。

    • 设单词 在 中出现的次数为 ，则有： 。则有：

    • 考虑到 ，则根据 有：

      • 其物理意义为：单词 的词性为 的概率 = 数据集 中单词 的词性为 出现的次数 / 数据集 中单词 出现的次数。

      • 由于 ， ，因此可以发现有：

        因此在这个特殊的情形下， 是 的估计。

  5. 事实上，真实的词性标注还需要考虑前后单词的词性的影响。比如：不可能出现连续的三个动词，也不可能出现连续的五个代词。

    当需要考虑前后文影响时，需要使用 HMM 模型 或者 CRF 模型。

2.3 模型求解

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

  2. 将其转化为最小化问题：

    其中：

    • 是已知的。
    • 是未知的。

  3. 将约束最优化的原始问题转换为无约束最优化的对偶问题，通过求解对偶问题来求解原始问题。

    引入拉格朗日乘子 ，定义拉格朗日函数 ：

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

  4. 先求解内部的极小化问题： 。

    它是一个 的函数，将其记作： 。

    • 先用 对 求偏导数：

      令偏导数为 0 。在 时，解得：

    • 由于 ，则有： 。因此有：

    • 定义 为规范因子，则：

      由该式表示的模型 就是最大熵模型。

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

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

  6. 上述过程总结为：

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

  7. 可以证明： 函数的最大化，等价于最大熵模型的极大似然估计。

    证明如下：已知训练数据 中， 出现的频次为 。则条件概率分布 的对数似然函数为：

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

    再利用 ：

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

2.4 最大熵与逻辑回归

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

  2. 根据最大熵的结论，有：

    以及：

    • 当 时有：

    • 当 时有：

    最终得到：

    这就是逻辑回归模型。

三、最大熵的学习

  1. 最大熵模型的学习就是在给定训练数据集 时，对模型进行极大似然估计或者正则化的极大似然估计。

  2. 最大熵模型与 logistic 回归模型有类似的形式，它们又称为对数线性模型。

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

3.1 改进的迭代尺度法

  1. 改进的迭代尺度法Improved Iterative Scaling:IIS是一种最大熵模型学习的最优化算法。

  2. 已知最大熵模型为：

    其中

    对数似然函数为：

    最大熵模型的目标是：通过极大化似然函数学习模型参数，求出使得对数似然函数最大的参数 。

  3. IIS 原理：假设最大熵模型当前的参数向量是 ，希望找到一个新的参数向量 ，使得模型的对数似然函数值增大。

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

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

    • 利用不等式：当 时 有：

    • 考虑到 ，以及：

      根据 有：

      则有：

    • 令

      则 。

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

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

  6. 改写为：

    • 利用指数函数的凸性，根据

      以及Jensen 不等式有：

      于是：

    • 令

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

  7. 求 对 的偏导数：

    令偏导数为 0 即可得到 ：

    最终根据 可以得到 。

  8. IIS 算法：

    • 输入：

      • 特征函数
      • 经验分布
      • 模型

    • 输出：

      • 最优参数
      • 最优模型

    • 算法步骤：

      • 初始化：取 。

      • 迭代，迭代停止条件为：所有 均收敛。迭代步骤为：

        • 求解 ，求解方法为：对每一个 ：

          • 求解 。其中 是方程： 的解，其中： 。
          • 更新 。

        • 判定迭代停止条件。若不满足停止条件，则继续迭代。

3.2 拟牛顿法

  1. 若对数似然函数 最大，则 最小。

    令 ，则最优化目标修改为：

    计算梯度:

  2. 最大熵模型学习的 BFGS算法：

    • 输入：

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

    • 输出：

      • 最优参数值
      • 最优模型

    • 算法步骤：

      • 选定初始点 ，取 为正定对阵矩阵，迭代计数器 。

      • 计算 ：

        • 若 ，停止计算，得到

        • 若 ：

          • 由 求得

          • 一维搜索：求出 ：

          • 置

          • 计算 。 若 ，停止计算，得到 。

          • 否则计算 ：

            其中： 。

          • 置 ，继续迭代。