三、最大熵的学习

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算法：

   • 输入：

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

   • 输出：

     • 最优参数值
     • 最优模型

   • 算法步骤：

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

     • 计算 ：

       • 若 ，停止计算，得到

       • 若 ：

         • 由 求得

         • 一维搜索：求出 ：

         • 置

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

         • 否则计算 ：

           

           其中： 。

         • 置 ，继续迭代。