条件随机场 (CRF 入门)——训练算法

四、CRF学习问题

这一篇是使用CRF的核心。

还是那句话,不能求解的模型没有任何意义,CRF的优点在于,它在较好地模拟现实的同时,能够比较轻松地进行学习,而且还是凸优化问题,可以直接使用万能的梯度下降法求解。

CRF的求解方法有很多种,这里我只介绍一下梯度下降算法。

梯度下降法

身为概率图模型,自然有迭代算法EM可以适用,嫌弃计算量大收敛慢的话还可以试试Gibbs采样。

不过说起最通用最广泛的算法还是梯度下降法,作为一个凸优化模型,可以很轻松地与其他凸优化模型融合,从而得到更广泛的应用。可以说,学会了这一个算法,其他的会不会都无所谓

这里同样采用线性链条件随机场作为例子。

线性链CRF,给定x 求某一y序列的概率为:

$$ P\left( y|x \right) = \frac{1}{Z}\prod_{t = 1}^{T}{\exp\left( \sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right)} \right)}(1) $$

其中分母Z(x)是归一因子: $$ Z\left( x \right) = \sum_{y}^{}{\prod_{t = 1}^{T}{\exp\left( \sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right)} \right)}}(2) $$ 它在较好地模拟现实的同时,能够比较轻松地求解

公式(2) 中的y就是所有可能的序列,计算开销很大。

给出似然函数的对数表达式:

$$ \ln\left( L\left( \theta \right) \right) = \sum_{i = 1}^{N}{(\sum_{t = 1}^{T}{\sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right) -}}ln(Z(x)))} (3) $$

其中N是训练序列的个数,现在我们要用随机梯度下降法(SGD)来极大似然函数(准确地说应该是梯度上升法),因此每次只用处理一个训练序列,于是有:

$$ \ln\left( p(y|x) \right) = \sum_{t = 1}^{T}{\sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right) -}}\ln\left( Z\left( x \right) \right)(4) $$

参数更新:

$$ \lambda_{k} = \lambda_{k} + \alpha \frac{{\partial ln}\left( p(y|x) \right)}{\partial\lambda_{k}}(5) $$

到这里,大家可以停一下,先试着自己求一下梯度,如果遇到困难了再接着往下看。

对第k个特征函数求偏导,得到:

$$ \frac{{\partial ln}\left( p(y|x) \right)}{\partial\lambda_{k}} = \sum_{t = 1}^{T}{f_{k}\left( x,y_{t - 1},y_{t} \right)} - \frac{1}{Z\left( x \right)}\frac{\partial Z\left( x \right)}{\partial\lambda_{k}} (6) $$

第一项非常简单,现在我们来对第二项进行求解。

$$ \frac{1}{Z\left( x \right)}\frac{\partial Z\left( x \right)}{\partial\lambda_{k}} = \frac{1}{Z\left( x \right)}\sum_{y}{}{\left( \exp{\left( \sum_{t = 1}^{T}{\sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right)}} \right) \sum_{t = 1}^{T}{f_{k}\left( x,y_{t - 1},y_{t} \right)}} \right)(7)} $$

注意到 $$ P\left( y|x \right) = \frac{1}{Z}\exp\left( \sum_{t = 1}^{T}{\sum_{k = 1}^{K}{\lambda_{k}f_{k}\left( x,y_{t - 1},y_{t} \right)}} \right) $$ 而 Z(x)对于一个训练序列来讲是常数,所以可以拿到括号里面,化简得到:

$$ \frac{1}{Z\left( x \right)}\frac{\partial Z\left( x \right)}{\partial\lambda_{k}} = \sum_{y}{}{\left( {p(y|x)}{\sum_{t = 1}^{T}{f_{k}\left( x,y_{t - 1},y_{t} \right)}} \right)(8)} $$

这一步很漂亮,接着:

$$ \frac{{\partial ln}\left( p(y|x) \right)}{\partial\lambda_{k}} = \sum_{t = 1}^{T}{f_{k}\left( x,y_{t - 1},y_{t} \right)} - \sum_{y}^{}{\left( {p(y|x)}{\sum_{t = 1}^{T}{f_{k}\left( x,y_{t - 1},y_{t} \right)}} \right)(9)} $$

推导完毕,这个式第一项是真实值,第二项是期望值,当两者相等时,梯度为0,迭代停止。

而之前在介绍前向-后向算法的时候,已经指出特征函数的期望可以用

$$E_{P(Y|X)}(f_k)=\sum_{y}P(y|x){f_k}(y,x)={\sum_{i=1}^{n+1}} \sum_{y_{I-1},y_i} f_k(y_{i-1},y_i,x,i)\bullet{\frac{{\alpha_i}^T(y_{i-1}|x)M_i (y_{i-1},{y_i}|x){\beta_i}(y_i|x)}{Z(x)}}$$

来求解,于是这个问题就解决了。

Reference:

《统计学习方法》李航

https://www.zhihu.com/question/20380549/answer/45066785 宁远成梁 https://zhuanlan.zhihu.com/p/26696451

展开全文
相关主题
Top
微信扫码咨询专知VIP会员