欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

IIS(Improved Iterative Scaling)改进的迭代尺度法

改进的迭代尺度法,在很多模型求解中用到,比如最大熵、CRFs等,对模型是对数线性模型的似然都适用。这个算法的思想也很简单,通俗的理解就是通过两个不等式变形优化下界,从而迭代到收敛的算法。

用到两个不等式,对 \(\alpha \gt 0 \)

\(-\log{\alpha} \ge 1 - \alpha \)

\(p(x)\) 是一个概率密度函数

\(e^{\sum_x p(x) q(x)} \le \sum_x{ p(x) e^{q(x)}}\)

为了阅读方便,可以先记住上面两个不等式,至于为什么用这两个不等式变换,文章末尾有我个人简单的思考。

假设模型为:

\(P_{\lambda} (y|x) = \frac{1}{Z_{\lambda}(x)} exp(\sum_{1}^{n}{\lambda_i f_i(x,y) })\)

其中 \(\lambda\) 是参数, \(Z(x)\) 是归一化因子。

似然函数可以写成:

\( L(\lambda) = \sum_{x,y} \tilde{p}(x,y) \log {p(y|x)}\)

其中 \( \tilde{p}(x,y) \) 是样本(x,y)出现的频率。

接下来我们就是要找到合适的 \(\lambda\) ,找 \(\lambda\) 的过程可以看做是下面迭代过程:

\( \lambda' = \lambda + \Delta \lambda\)

所以问题可以看做每次寻找一个 \(\lambda\) 的移动向量,然后不断迭代,接下来就是确定每一步如何找到 \(\Delta \lambda \) .一种容易想到的做法就是通过最大化两次迭代的差值,从而实现每一步得到最优的 \(\Delta \lambda \)

\(\begin{align} L( \lambda') - L(\lambda) &= \sum_{x,y} \tilde{p}(x,y) \log {p_{\lambda'}(y|x)} -\sum_{x,y} \tilde{p}(x,y) \log {p_{\lambda}(y|x)} \\ &= \sum_{x,y} \tilde{p}(x,y) \sum_i {\Delta_i f_i(x,y)} - \sum_x{ \tilde{p}(x) \log{ \frac{Z_{\lambda'} (x) }{Z_\lambda(x) } }} \end{align}\)

对上面式子通过不等式 \(-\log{\alpha} \ge 1 - \alpha \) 可以改写为:

\(\begin{align} L( \lambda') - L(\lambda)&\ge\sum_{x,y}\tilde{p}(x,y) \sum_i {\Delta_i f_i(x,y)}+ 1 - \sum_x{ \tilde{p}(x)\frac{Z_{\lambda'} (x) }{Z_\lambda(x) } }\\ &=\sum_{x,y} \tilde{p}(x,y) \sum_i {\Delta_i f_i(x,y)} + 1 - \sum_x{ \tilde{p}(x,y) } \sum_{y}p_{\lambda}(y|x) exp(\sum_{i}{\Delta_i f_i(x,y)}) \end{align}\)

定义:

\(f^{\#}(x,y) = \sum_i {f_i(x,y)}\)

可以将上式修改为:

\(L( \lambda') - L(\lambda)=\sum_{x,y} \tilde{p}(x,y) \sum_i {\Delta_i f_i(x,y)} + 1 - \sum_x{ \tilde{p}(x,y) } \sum_{y}p_{\lambda}(y|x) exp\left(f^{\#}(x,y)\sum_{i} {\frac{\Delta_i f_i(x,y))}{ f^\#(x,y) }} \right)\)

对上面等式通过不等式: \(e^{\sum_x p(x) q(x)} \le \sum_x{ p(x) e^{q(x)} }\) 可以改写为:

\(L( \lambda') - L(\lambda)\ge\sum_{x,y} \tilde{p}(x,y) \sum_i {\Delta_i f_i(x,y)} + 1 - \sum_x{ \tilde{p}(x,y) } \sum_{y}p_{\lambda}(y|x) \sum_i\left({\frac{ f_i(x,y))}{ f^\#(x,y) }} e^{\Delta_i f^{\#}(x,y)} \right)\)

上式直接对 \(\Delta \lambda\) 求导数,令导函数为0可以直接解出来 \(\Delta \lambda\) , 从而不断迭代达到收敛。

一些思考

不等式的选择问题,对于第一个不等式 \(-\log{\alpha} \ge 1 - \alpha \) 画图之后的效果:

8B29F34A-8979-4021-9B55-2DA3B2C33929

在坐标逼近(1,0)处,他们两个的值是无限接近,当迭代收敛的时候 \(\frac{Z_{\lambda'}(x)}{Z_{\lambda}(x)}\rightarrow 1\) ,刚好是在这个点。

第二个不等式以前没有接触过,但是容易想到的是凸函数的期望不等式,『期望的函数』小于等于『函数的期望』:

\(f(E(x)) \le E(f(x))\)

 

参考资料

berger-iis

未经允许不得转载:大数据算法 » IIS(Improved Iterative Scaling)改进的迭代尺度法

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站