改进的迭代尺度法

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)