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))$$