# 改进的迭代尺度法（IIS）

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

## 背景

在[根据最大熵的学习过程推导最大熵模型](https://windmising.gitbook.io/lihang-tongjixuexifangfa/3/6)中已经求出了最大熵模型。想要解出最大熵模型就要先解出“最大熵模型的对偶函数的极大化”。\
在[证明：对偶函数的极大化=模型的极大似然估计](https://windmising.gitbook.io/lihang-tongjixuexifangfa/3/7)中已证明”最大熵模型的对偶函数的极大化=最大熵模型的对数似然函数的极大似然估”。这个问题又进一步转化为求“最大熵模型的对数似然函数的极大似然估”。

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