学习笔记|最大熵模型学习的IIS法
Logistic回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化的观点看，这时的目标函数具有很好的性质。它是光滑的凸函数，因此多种最优化方法适用，保证能找到全局最优解。
IIS，全称improved iterative scaling，中文名改进的迭代尺度法，是适用于求解以似然函数为目标的最优化问题（如最大熵模型学习）的方法之一。
已知最大熵模型为
对数似然函数为
（上述结果的推导过程可参见学习笔记|最大熵模型与极大似然估计）
目标是通过极大似然估计学习模型参数，即求对数似然函数的极大值。
IIS的想法是：假设最大熵模型当前的参数向量是，我们希望找到一个新的参数向量ω+δ=，使得模型的对数似然函数值增大。如果能有这样一种参数向量更新方法τ:ω→ω+δ，那么就可以重复使用这一方法，直至找到对数似然函数的最大值。
对于给定的经验分布，模型参数从ω到ω+δ，对数似然函数的改变量是
f(x)=-logx-1+x对∀x>0有。所以f(x)是严格凸函数，它在，即x=1时取到最小值0。（推导过程可参见学习笔记|凸函数的定义与性质）
所以，对∀x>0，有f(x)≥0，即-logx≥1-x。
因此，
将上式记为A(δ|ω)。
于是有
即A(δ|ω)是对数似然函数改变量的一个下界。
如果能找到适当的δ使下界A(δ|ω)提高，那么对数似然函数也会提高。然而，函数A(δ|ω)中的δ是一个向量，含有多个变量，不易同时优化。IIS试图一次只优化其中一个变量，而固定其他变量。
为了达到这一目的，IIS进一步降低下界A(δ|ω)。具体地，IIS引进一个量，
因为是二值函数，所以表示所有 特征在(x,y)出现的次数。这样，A(δ|ω)$可以改写为
因此指数函数是凸函数，对∀i有，且，所以有
（推导依据可参见学习笔记|凸函数的定义与性质）
因此
将上式记为B(δ|ω)。
于是得到
这里，B(δ|ω)是对数似然函数改变量的一个新的（相对不紧的）下界。
求B(δ|ω)对的偏导数：
上式中只有一个变量，令上式为0可得到
于是，依次对求解上式可以求出δ。
IIS算法：
输入：特征函数，经验分布，模型；
输出：最优参数值；最优模型。
（1）对所有i∈{1,2,...,n}，取初值。
（2）对每一i∈{1,2,...,n}
（a）令是方程
的解，这里，
（b）更新值：。
（3）如果不是所有都收敛，重复步（2）。
这一算法关键的一步是（a），即求解方程中的。如果是常数，即对任何x,y，有，那么可以显式地表示成
如果不是常数，那么必须通过数值计算求。简单有效的方法是牛顿法。以表示方程，牛顿法通过迭代求得，使得。迭代公式是
只要适当选取初始值，由于方程有单根，因此牛顿法恒收敛，而且收敛速度很快。
参考文献
【1】统计学习方法（第2版），李航著，清华大学出版社