1. 改进的迭代尺度法

IIS，improved iterative scaling
最大熵模型学习的最优化算法

1.1. 背景

在根据最大熵的学习过程推导最大熵模型中已经求出了最大熵模型。想要解出最大熵模型就要先解出“最大熵模型的对偶函数的极大化”。
在证明：对偶函数的极大化=模型的极大似然估计中已证明”最大熵模型的对偶函数的极大化=最大熵模型的对数似然函数的极大似然估”。这个问题又进一步转化为求“最大熵模型的对数似然函数的极大似然估”。

即找到一个w使得L(w)最大 $L(w) = \sum_{x,y} \tilde P(x, y) \sum_{i=1}^n w_if_i(x, y) - \sum_x \tilde P(x) \log Z_w(x)$

1.2. 算法过程

算法6.1 改进的迭代尺度算法 IIS

输入：
特征函数$f_1,f_2,\cdots,f_n$
经验分布：$\tilde P(X, Y)$
模型：$P_w(Y|X)$

输出：
最优模型参数$w_i^*$
最优模型$P_{w*}$

过程：

1. 对所有$i \in {1,2,\cdots,n}$，取初值$w_i=0$
2. 选择一个$i \in {1,2,\cdots,n}$，令$\delta_i$满足方程：
   $\begin{aligned} \sum_{x,y}\tilde P(x)P_w(y|x)f_i(x, y)\exp(\delta_i)f^\#(x,y))=E_{\tilde P}(f_i) \\ f^\# = \sum_if_i(x,y) && {1} \end{aligned}$ 求解$\delta_i$
3. $w_i = w_i + \delta_i$
4. 如果不是所有$w_i$都收敛，迭代进行2，3