Intro
IIS和EM一样，也是一种构造下界计算近似MLE的优化算法。事实上IIS算法就是对GIS（Generalized Iterative Scaling，通用迭代法，本质也是一种EM算法）算法进行改进而来的。
IIS利用$\log$函数的性质，以及指数函数的凸性，对目标函数进行了两次缩放，来求解下界函数。 对于MEM和CRF，使用IIS比GIS收敛快很多。
在EM算法中，每次迭代获取到新的边界$B(\theta,\theta^i)$后，需要求$\theta^{i+1}=\arg\max_\theta B(\theta,\theta^i)$，简化$B$成$Q$函数后，即是要求$\frac{\partial Q}{\partial \theta}=0$，然后$\theta^i\to\theta^{i+1}$。在这种方法下，如果$\theta$维度很高又不独立的话（即模型参数很多，含有多个变量）的话，就不能对各参数分别求0偏导，需要全局优化。于是IIS另辟蹊径，采用了一次只优化$\theta$中的一个变量$\delta_i$，而固定其他变量$\delta_j$的方法。
IIS可以用在CRF，MEM等模型中（HMM属于一种特殊的CRF，也可以用，但效果没EM好）
Improved Iterative Scaling
IIS，改进迭代尺度法（本文求的是MEM模型的IIS）
首先已知MEM：$P_w(y|x)=\frac{1}{Z_w(x)}e^{\sum^n_{i=1}w_if_i(x,y)}$，$Z_w(x)=\sum_ye^{\sum_{i=1}^nw_if_i(x,y)}$
则对数似然函数为：$L(w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\hat P(x)\log Z_w(x)$
求：$\arg_w\max L(w)$
思想：对MEM模型参数向量$w=(w_1,w_2,\cdots,w_n)^T$，寻找一个新的参数向量$w\to w+\delta$：
$w+\delta=(w_1+\delta_1,w_2+\delta_2,\cdots,w_n++\delta_n)^T$，使得$L(w+\delta)>L(w)$，以此迭代
推导：前面思想和EM基本一样，先算出$\Delta L$
$\Delta=L(w+\delta)-L(w)=\sum_{x,y}\hat P(x,y)\log P_{w+\delta}(y|x)-\sum_{x,y}\hat P(x,y)\log P_{w}(y|x)$
$=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)-\sum_{x}\hat P(x)\log\frac{Z_{w+\delta}(x)}{Z_{w}(x)}$
$\because -\log\alpha≥1-\alpha,\alpha>0$（这一步就把麻烦的$\log$给干掉了，使得原式可以计算，代价是要构造下界做近似MLE，同EM的思想）
$\therefore \Delta≥\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_{x}\hat P(x)\frac{Z_{w+\delta}(x)}{Z_{w}(x)}$
$=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_{x}\hat P(x)\sum_yP_w(y|x)e^{\sum_{i=1}^n\delta_if_i(x,y)}$ （下界）
这个时候已经可以对$\Delta$求0导数来获取最大值以获取$\delta^{(n+1)}$了（这样就和EM一样，只是用了不同的下界不等式）。但是对目前的$\Delta$求$\frac{\partial \Delta}{\partial \delta_i}=0$会发现仍然存在$\sum_i\delta_i$形式（对负项中的$e^{\sum_{i=1}^n\delta_if_i(x,y)}$求导后根据链式法则显然无法消去$\sum_i\delta_i$部分），导致0导数式包含多个不同$i$的$\delta_i$变量，很难同时优化。（注意对求和函数求导，见EM算法专题中）
(想想为什么HMM中使用EM算法中对每个变量参数求0偏导就可行？因为在HMM中，$(A,B,\pi)$三个变量参数是独立的且求得的$Q$函数已经将三个变量放在三个子式中独立分开，满足
$\max_{A,B,\pi}Q=\{\max_A ④,\max_B ⑤,\max_ \pi ③\}$，每个子式子中只包含本要优化的变量）而本式中，各参数变量$\delta_i$之间根本不独立（求导式中就存在$\sum_i\delta_i$），不能分别求0偏导，传统做法只能让求一组$\delta_i$使得整体满足最大。
于是我们想只将其中一个变量$\delta_i$作为变量，其它$\delta_j$作为固定常数$i≠j$，如何做到呢？那就要在求导中干掉$\sum_i\delta_i$形式，于是下面开始整骚操作：
构造Jensen不等式，以创造第二个下界。Jensen不等式可以将函数的作用范围缩小，这样就可以将$\sum$抛出$e$的指数部分，避免求导的时候链式法则再产生$\sum_i\delta_i$。
令$f^o(x,y)=\sum_if(x,y)$，MEM中$f_i(x,y)∈\{0,1\}$，是一个二值函数，于是$f^o(x,y)$表示所有特征在$(x,y)$出现的次数，这样就可以拼凑出一个求和等于1的分式并满足Jensen不等式形式。这里很需要技巧。
下面就是拼凑出的Jensen不等式形式（Jensen不等式见下面大标题）：
$\lambda_i=\frac{f_i(x,y)}{f^o(x,y)},x_i=\delta_if^o(x,y),f(\sum_i\lambda_ix_i)=e^{\sum_i\lambda_ix_i}$
其中$\lambda_i>0,\sum_i\lambda_i=1,f(X)=e^X$为凸函数，则$e^{\sum_i\lambda_ix_i}≤\sum_i\lambda_ie^{x_i}$
$\therefore \Delta=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_{x}\hat P(x)\sum_yP_w(y|x)e^{\sum_{i=1}^n \frac{f_i(x,y)}{f^o(x,y)}\delta_if^o(x,y)}$
$≥\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_{x}\hat P(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^o(x,y)}e^{ \delta_if^o(x,y)}$（新下界）
（注意前面有个负号！$-e^{\sum_i\lambda_ix_i}≥-\sum_i\lambda_ie^{x_i}$）
记右式为$B(\delta|w),\therefore L(w+\delta)-L(w)≥B(\delta|w)$
$\therefore \frac{\partial B(\delta|w)}{\partial \delta_i}=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nf_i(x,y)-\sum_{x}\hat P(x)\sum_yP_w(y|x)\sum_{i=1}^nf_i(x,y)e^{ \delta_if^o(x,y)}$
于是该式中只有指定$i$的$\delta_i$是变量，达到目的。令$\frac{\partial B(\delta|w)}{\partial \delta_i}=0$即可求得$\delta_i$
其中$\sum_{x,y}\hat P(x,y)\sum_{i=1}^nf_i(x,y)=\mathbb E_{\hat P}(f_i)$
于是计算每一大步迭代，$\delta$中的每一个参数$\delta_i$的公式为：
$\sum_{x}\hat P(x)\sum_yP_w(y|x)\sum_{i=1}^nf_i(x,y)e^{ \delta_if^o(x,y)}=\mathbb E_{\hat P}(f_i)$，其中$f^o(x,y)=\sum_if(x,y)$
一个公式计算一个$\delta_i$，依次计算$\delta_i$就可以求得$\delta$
Improved Iterative Scaling Algorithm
对于MEM
输入：特征函数$f_1,f_2,\cdots,f_n$；经验分布$\hat P(X,Y)$，模型$P_w(y|x)$
输出：最优参数$w_i^o$；最优模型$P_{w^o}$
（1）对所有$i∈\{1,2,\cdots,n\}$，取初值$w_i=0$
（2）对每一$i∈\{1,2,\cdots,n\}$
（a）令$\delta_i$是方差
的解，其中
（b）更新$w_i$的值：$w_i \leftarrow w_i+\delta_i$
（3）如果不是所有$w_i$都收敛，重复（2）
在（a）中计算$\delta_i$的时候，若$f^o(x,y)$是常数（即对所有的$(x,y)$，$f^o(x,y)$都相等。一般都不会是常数），那么
若$f^o(x,y)$不是常数，那就必须直接计算$\delta_i$，可以使用牛顿法计算。
以$g(\delta_i)=0$表示原方程，牛顿法通过迭代求得$\delta_i^o$，使得$g(\delta_i^o)=0$，迭代公式为
只要适当选取初始值$\delta_i^o$，由于原方程有单根，因此牛顿法恒收敛，且收敛速度很快
Jensen不等式
由凸函数性质可得：$\lambda f(x_1)+(1-\lambda)f(x_2)≥f(\lambda x_1+ (1-\lambda)x_2)$
$\therefore$ 对于任意点集$\{x_i\}$，若$\lambda_i≥0$，且$\sum_i\lambda_i=1$
通过数学归纳法可以证明凸函数$f(x)$满足$f(\sum_{i=1}^M\lambda_ix_i)≤\sum_{i=1}^M\lambda_if(x_i)$
对于凹函数，$\lambda f(x_1)+(1-\lambda)f(x_2)≤f(\lambda x_1+ (1-\lambda)x_2)$则相反
即：
若$\lambda_i$看成取值为$x_i$的离散变量$x$的概率分布，则可以写成：
若凸函数：$f(\mathbb E[x])≤\mathbb E[f(x)]$，若为凹函数：$f(\mathbb E[x])≥\mathbb E[f(x)]$
凸则大作用域≤小作用域，凹则大作用域≥小作用域
构造Jensen不等式经常用拼凑法（IIS和EM）
