最大熵算法

一、最大熵模型MEM

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

   可以证明： ，其中 为 X 的取值的个数。当且仅当 X 的分布为均匀分布时有 。即 时熵最大。

1.1 最大熵原理

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

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

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

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

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

1.2 期望的约束

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

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

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

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

   
   

3. 给出拉格朗日函数：

   可以求得：

   
   

• 将 P(X) 代入 ，有：

   

  则可以求解出各个 。

  
  

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

二、分类任务最大熵模型

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

2.1 最大熵模型

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

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

   
   

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

   
   

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

• 特征函数 关于经验分布 的期望定义为 。这个期望其实就是约束 在训练集上的统计结果的均值（也就是约束 出现的期望的估计量）。

  a. 如果 取值为二值0,1，则表示约束 f 在训练集上出现的次数的均值。

  b. 如果 取值为任意值，则表示约束 f 在训练集上累计的结果的均值。

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

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

  
  

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

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

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

2.2 词性标注约束案例

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

   假设标注仅仅与当前单词有关，与前面、后面的单词无关，也无前面、后面的标注有关。即：标注 由单词 唯一决定。则统计文本中所有单词及其词性，得到训练集 ，其中 为单词数量。

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

   
   

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

   其中：

   
   

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

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

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

  
  

• 考虑到 ，则根据 有：

  
  

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

  b. 由于 ，因此可以发现有： 因此在这个特殊的情形下， 是 的估计。

2.3 模型求解

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

   
   

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

   其中：

   
   

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

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

• 先用 对 求偏导数：

  
  

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

  
  

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

  
  

• 定义 为规范因子，则：

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

  
  

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

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

2.4 最大熵与逻辑回归

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

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

   
   

   以及：

   
   

• 当 y=1 时有：

  
  

• 当 y=0 时有：

  
  

  最终得到：

  
  

  这就是逻辑回归模型。

三、最大熵的学习

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

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

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

3.1 改进的迭代尺度法

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

2. 已知最大熵模型为：

   其中

   对数似然函数为：

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

   
   

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

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

• 利用不等式：当 时 , 有：

  
  

• 考虑到 ，以及：

  
  

  根据 有：

  则有：

  
  

  令

  则 。

  
  

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

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

  以及Jensen 不等式有：

  
  

  于是：

  
  

• 令

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

  
  

• 输入：

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

• 输出：

• 最优参数
• 最优模型

• 算法步骤：

• 初始化：取 。

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

  a. 求解 ，求解方法为：对每一个 ：

  (1) 求解 。其中 是方程：的解，其中： 。

  (2) 。

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

3.2 拟牛顿法

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

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

   
   

   计算梯度:

   
   

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

• 输入：

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

• 输出：

• 最优参数值
• 最优模型

• 算法步骤：

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

• 计算 ：

  a. 若 ，停止计算，得到

  b. 若 ：

  (1) 由

  (2) 一维搜索：求出

  (3) 置

  (4) 计算 。

  (5) 否则计算 ：

  其中： 。

  
  

  (6) 置 ，继续迭代。

—— 完 ——