改进的迭代尺度法（IIS）

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

背景

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

即找到一个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)$$

算法过程

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