# IIS

一般介绍最大熵的文章都会IIS。凸优化中迭代方法有很多，目前收敛速度比较快的是拟牛顿法，常用L-BFGS，没必要用IIS，但是IIS的思想可以学习学习。

$$
\begin{align}
L_{\widetilde p}(P_w) &= \log \prod_{x,y} P(y|x)^{\widetilde P(x,y)} \\
&= \sum_{x,y} \widetilde P(x,y) \log P(y|x) \\
&= \sum_{x,y} \widetilde P(x,y) \log (\exp(\sum_{i=1}^n w_i f_i(x,y)) / Z_w(x)) \\
&= \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n w_i f_i(x,y) -  \sum_x \widetilde P(x) \log Z_w(x) \\
\end{align}
$$

$$
\begin{align}
L(w+\delta) - L(w) &= \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n \delta_i f_i(x,y) - \sum_x \widetilde P(x) \log (Z_{w+\delta}(x)/Z_w(x)) \\
& \ge \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n \delta_i f_i(x,y) + \sum_x \widetilde P(x) (1- Z_{w+\delta}(x)/Z_w(x)) \qquad \because (-log x \ge 1-x )\\
&= \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n \delta_i f_i(x,y) + 1 - \sum_x \widetilde P(x) (Z_{w+\delta}(x)/Z_w(x)) \\
&= \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n \delta_i f_i(x,y) + 1 - \sum_x \widetilde P(x) \sum_y P_w(y|x) \exp(\sum_{i=1}^n \delta_i f_i(x,y)) \\
\end{align}
$$

$$
\text{令} f^{\#} (x,y) = \sum_{i=1}^n f_i(x,y) \\
\exp(\sum_{i=1}^n \delta_i f_i(x,y)) = \exp(\sum_{i=1}^n \frac {f_i(x,y)}{f^{\#} (x,y)} \delta_i f^{\#} (x,y)) \le \sum_{i=1}^n \frac {f_i(x,y)}{f^{\#} (x,y)} \exp(\delta_i f^{\#} (x,y))
$$

$$
L(w+\delta) - L(w) \ge \sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n \delta_i f_i(x,y) + 1 - \sum_x \widetilde P(x) \sum_y P_w(y|x) \sum_{i=1}^n \frac {f_i(x,y)}{f^{\#} (x,y)} \exp(\delta_i f^{\#} (x,y))
$$
