IIS算法公式（1）推导

$$\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) \end{aligned}$$

算法原理

假设最大熵模型当前的参数向量是$w=(w_1,w_2,\cdots,w_n)^T$， 我们希望找到一个新的参数向量$w+\delta = (w_1+\delta_1,w_2+\delta_2,\cdots,w_n+\delta_n)^T$使得L(w)增大。 如果有这样一种参数向量更新的方法$\tau(w):w \rightarrow w+\delta$, 那么就可以重复使用这一方法，直至找到L(w)的最大值。

令$A(\delta|w)$是$L(w+\delta) - L(w)$的下界，即满足$L(w+\delta) - L(w) \ge A(\delta|w)$，那么 找到适当的$\delta$使下界$A(\delta|w)$提高，那么L(w)也会提高。

推导

1. 计算$L(w+\delta) - L(w)$的下界$A(\delta|w)$，得：

   $$A(\delta|w) = \sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_x\tilde P(x)\sum_yP_w(y|x)\exp \sum_{i=1}^n\delta_if_i(x,y)$$
2. 需要找到适当的$\delta$使下界$A(\delta|w)$提高。但$A(\delta|w)$中的$\delta$是一个向量，含有多个变量，不易同时优化。因此，一次只优化其中一个变量$\delta_i$，而固定其它变量$\delta_j,i \neq j$。基于此得到新的下界$B(\delta|w)$。

   $$\begin{aligned} B(\delta|w) = \sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x, y) + 1 - \sum_x\tilde P(x)\sum_yP_w(y|x)\sum_{i=1}^n(\frac{f_i(x,y)}{f^\#(x,y)})\exp(\delta_if^\#(x,y)) \\ f^\# = \sum_if_i(x,y) && {3} \end{aligned}$$
3. $B(\delta|w)$对$\delta_i$求偏导，并令偏导=0，得到等式：

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

   即算法中要解的公式

依次解出$\delta_i$，进一步求出$\delta$，再通过$\delta$更新w 迭代进行以上步骤，直至找到最优的w