最大熵算法

一、最大熵模型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 。在 时,解得: