【概述】

改进的迭代尺度法（Improve Iterative Scaling，IIS）是一种专用于最大熵模型学习的最优化算法，其是在通用迭代尺度法（Generalized Iterative Scaling，GIS）的基础上改进得来的

关于最大熵模型，详见：最大熵模型

已知最大熵模型为：

$p_{\boldsymbol{\omega}}(y|x)=\frac{1}{Z_{\boldsymbol{\omega}}(x)}\exp\bigl[\sum_{j=1}^m \omega^{(j)}f_j(x,y)\bigr]$

其中，规范化因子 $Z_{\boldsymbol{\omega}}(x)$ 为：

$Z_{\boldsymbol{\omega}}(x)=\sum_{y\in Y} \exp \Big[\sum_{j=1}^m \omega^{(j)}f_j(x,y)\Big]$

对数似然函数为：

$L_{\tilde{p}}(p_{\boldsymbol{\omega}}) = \sum_{x\in X,y\in Y}\tilde{p}(x,y)\sum_{j=1}^m\omega^{(j)}f_j(x,y)-\sum_{x\in X}\tilde{p}(x)\log Z_{\boldsymbol{\omega}}(x)$

目标是通过极大似然估计学习模型参数，求对数似然函数的极大值 $\hat{\boldsymbol{\omega}}$

【基本思想】

IIS 的基本思想是假设最大熵模型当前的参数向量是 $\mathbf{\omega}=(\omega^{(1)},\omega^{(2)},…,\omega^{(m)})^T$，希望找到一个新的参数向量 $\boldsymbol{\omega}+\boldsymbol{\delta}=(\omega^{(1)}+\delta^{(1)},\omega^{(2)}+\delta^{(2)},…,\omega^{(m)}+\delta^{(m)})^T$，使得模型的对数似然函数值增大

若存在一种参数向量更新的方法：$\tau : \boldsymbol{\omega} \rightarrow \boldsymbol{\omega}+\boldsymbol{\delta}$，那么就可以重复使用这一方法，直到寻找到对数似然函数的最大值

【对数似然函数改变量】

对于给定的经验分布 $\tilde{p}(x,y)$，参数模型从 $\boldsymbol{\omega}$ 到 $\boldsymbol{\omega}+\boldsymbol{\delta}$，对数似然函数的改变量为：

$\begin{align*} L(\boldsymbol{\omega}+\boldsymbol{\delta})-L(\boldsymbol{\omega}) &= \sum_{x,y}\tilde{p}(x,y)\log p_{\boldsymbol{\omega}+\boldsymbol{\delta}}(y|x)-\sum_{x,y}\tilde{p}(x,y)\log p_{\boldsymbol{\omega}}(y|x) \\\ &= \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y) - \sum_x \tilde{p}(x)\log \frac{Z_{\boldsymbol{\omega}+\boldsymbol{\delta}}(x)}{Z_{\boldsymbol{\omega}}(x)} \end{align*}$

利用对数不等式：

$-\log \alpha\geq 1-\alpha,\quad \alpha >0$

可以求出对数似然函数改变量的下界：

$\begin{align*} & L(\boldsymbol{\omega}+\boldsymbol{\delta})-L(\boldsymbol{\omega}) \\ \geq& \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y) +1 - \sum_x \tilde{p}(x)\log \frac{Z_{\boldsymbol{\omega}+\boldsymbol{\delta}}(x)}{Z_{\boldsymbol{\omega}}(x)} \\ =& \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y) +1 - \sum_x \tilde{p}(x)\sum_yp_{\boldsymbol{\omega}}(y|x) \exp \sum_{j=1}^m \delta^{(j)} f_j(x,y) \\ \end{align*}$

将右端记为 $A(\boldsymbol{\delta}|\boldsymbol{\omega})$，有：

$A(\boldsymbol{\delta}|\boldsymbol{\omega}) =\sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y) +1 - \sum_x \tilde{p}(x)\sum_yp_\boldsymbol{\omega}(y|x) \exp \sum_{j=1}^m \delta^{(j)} f_j(x,y)$

则：

$L(\boldsymbol{\omega}+\boldsymbol{\delta})-L(\boldsymbol{\omega})\geq A(\boldsymbol{\delta}|\boldsymbol{\omega})$

即 $A(\boldsymbol{\delta}|\boldsymbol{\omega})$ 是对数似然函数改变量的一个下界

【下界的提高】

若能找到适当的 $\boldsymbol{\delta}$ 使得下界 $A(\boldsymbol{\delta}|\boldsymbol{\omega})$ 增大，那么对数似然函数也会增大

但 $\boldsymbol{\delta}$ 是一个含有 $m$ 个分量的向量，不易同时优化，IIS 每次只优化其中的一个变量 $\delta^{(j)}$，固定其他变量 $\delta^{(t)},t\neq j$

为达到这一目的，IIS 进一步降低下界 $A(\boldsymbol{\delta}|\boldsymbol{\omega})$ ，即引进一个函数量 $F(x,y)$，其是一个二值函数，表示所有特征在 $(x,y)$ 中出现的次数，即：

$F(x,y) = \sum_{j=1}^mf_j(x,y)$

这样一来，$A(\boldsymbol{\delta}|\boldsymbol{\omega})$ 可以改写为：

$\begin{align*} A(\boldsymbol{\delta}|\boldsymbol{\omega}) =& \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y) +1 \\ &- \sum_x \tilde{p}(x)\sum_yp_\boldsymbol{\omega}(y|x) \exp \Big[F(x,y) \sum_{i=j}^m \frac{\delta^{(j)} f_j(x,y)}{F(x,y)} \Big] \end{align*}$

利用指数函数的凸性，对任意 $j$，有：

$\frac{f_j(x,y)}{F(x,y)}\geq 0$

且满足：

$\sum_{j=1}^m \frac{f_j(x,y)}{F(x,y)}=1$

根据凸函数性质的 Jensen 不等式，有：

$\exp\Big[\sum_{j=1}^m\frac{f_j(x,y)}{F(x,y)}\delta^{(j)}F(x,y)\Big] \leq \sum_{j=1}^m\frac{f_i(x,y)}{F(x,y)}\exp\Big[\delta^{(j)}F(x,y)\Big]$

PS：关于 Jensen 不等式，见：附：关于 Jensen 不等式

此时，$A(\boldsymbol{\delta}|\boldsymbol{\omega})$ 可以改写为：

$\begin{align*} A(\boldsymbol{\delta}|\boldsymbol{\omega}) \geq& \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y)+1 \\ &-\sum_x\tilde{p}(x)\sum_yp_{\boldsymbol{\omega}}(y|x)\sum_{j=1}^m\frac{f_j(x,y)}{F(x,y)}\exp\big[\delta^{(j)}F(x,y)\big] \end{align*}$

记不等式右端为 $B(\boldsymbol{\delta}|\boldsymbol{\omega})$，其是对数似然函数改变量的一个新的下界，其相较于 $A(\boldsymbol{\delta}|\boldsymbol{\omega})$ 更加的宽松，即：

$\begin{align*} B(\boldsymbol{\delta}|\boldsymbol{\omega}) =& \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\delta^{(j)}f_j(x,y)+1 \\ &- \sum_x\tilde{p}(x)\sum_yp_{\boldsymbol{\omega}}(y|x)\sum_{j=1}^m\frac{f_j(x,y)}{F(x,y)}\exp\big[\delta^{(j)}F(x,y)\big] \end{align*}$

于是得到：

$L(\boldsymbol{\omega}+\boldsymbol{\delta})-L(\boldsymbol{\omega})\geq A(\boldsymbol{\delta}|\boldsymbol{\omega}) \geq B(\boldsymbol{\delta}|\boldsymbol{\omega})$

对 $B(\boldsymbol{\delta}|\boldsymbol{\omega})$ 求关于 $\delta^{(j)}$ 的偏导数：

$\begin{align*} \frac{\partial B(\boldsymbol{\delta}|\boldsymbol{\omega})}{\partial \delta^{(j)}} =& \sum_{x,y}\tilde{p}(x,y)f_j(x,y)-\sum_x\tilde{p}(x)\sum_{y}p_{\boldsymbol{\omega}}(y|x)f_j(x,y) \exp\big[\delta^{(j)}F(x,y)\big] \\ \end{align*}$

此时，该式除 $\delta^{(j)}$ 外不含任何其他变量，令偏导为 $0$ 可得：

$\sum_{x,y}\tilde{p}(x)p_{\boldsymbol{\omega}}(y|x)f_j(x,y) \exp\big[\delta^{(j)}F(x,y)\big] = E_{\tilde{p}}(f_j)$

最后，依次对 $\delta^{(j)}$ 求解方程即可得到 $\boldsymbol{\delta}$

【算法流程】

输入：特征函数 $f_1,f_2,…,f_n$；经验分布 $\tilde{P}(X,Y)$；最大熵模型 $p_{\boldsymbol{\omega}}(y|x)$

输出：最优参数值 $\boldsymbol{\omega}^{*}$；最优模型 $p_{\boldsymbol{\omega}^{*}}(y|x)$

算法流程：

Step1.对所有的 $j\in\{1,2,…,m\}$，取初值 $\omega^{(j)}=0$

Step2.对每一 $j\in\{1,2,…,m\}$：

1）令 $\delta^{(j)}$ 为下列方程的解

$\sum_{x,y}\tilde{p}(x)p(y|x)f_j(x,y) \exp\big[\delta^{(j)}F(x,y)\big]=E_{\tilde{p}}(f_j)$

其中， $F(x,y)=\sum\limits_{j=1}^mf_j(x,y)$

2）更新 $\omega^{(j)}$ 的值：$\omega^{(j)}=\omega^{(j)}+\delta^{(j)}$

Step3.若存在未收敛的 $\omega^{(j)}$，重复步骤 2

可以发现，上述算法的关键步骤是 Step2 的步骤 1），即求解 $\delta^{(j)}$ 的过程

若 $F(x,y)$ 是一个常数，即对任意的 $x$ 与 $y$，满足：

$F(x,y)=M$

则解 $\delta^{(j)}$ 可表示为：

$\delta^{(j)}=\frac{1}{M}\log \frac{E_{\tilde{p}}(f_j)}{E_{p}(f_j)}$

此时，对于 $M$ 来说，可将其视为梯度下降法中的学习速率，同时，IIS 等同于通用迭代尺度法 GIS

若 $F(x,y)$ 不是一个常数，则必须通过数值计算的方法来求 $\delta^{(j)}$，此时，通常选用牛顿迭代法来求 $\delta^{(j)}$

即用 $g(\delta^{(j)})=0$ 来表示方程 $\sum\limits_{x,y}\tilde{p}(x)p(y|x)f_j(x,y)\exp\big[\delta^{(j)}F(x,y)\big]=E_{\tilde{p}}(f_j)$ 的解，利用牛顿迭代法对下列公式进行迭代：

$\delta_{k+1}^{(j)}=\delta_k^{(j)}-\frac{g(\delta_{k}^{(j)})}{g'(\delta_{k}^{(j)})}$

通过迭代可得到 $(\delta^{(j)})^*$，使得 $g((\delta^{(j)})^*)=0$

【附：关于 Jensen 不等式】

基本形式

若 $f(x)$ 是区间 $[a,b]$ 上的下凸函数，对任意的 $x_1,x_2,…,x_n\in [a,b]$，有：

$\frac{1}{n}\sum_{i=1}^nf(x_i)\geq f(\frac{1}{n}\sum\limits_{i=1}^nx_i)$

仅当 $x_1=x_2=…=x_n$ 时，等号成立

注：若为上凸函数，不等号反向

加权形式

若 $f(x)$ 是区间 $[a,b]$ 上的下凸函数，对任意的 $x_1,x_2,…,x_n\in [a,b]$，且对任意 $a_i>0$，满足 $\lambda_1+\lambda_2+…+\lambda_n=1$，有：

$\sum_{i=1}^n\lambda_if(x_i)\geq f(\sum\limits_{i=1}^n\lambda_ix_i)$