线性链CRF-推导和实现以及应用

隐马尔可夫模型(Hidden Markov Model,HMM),最大熵马尔可夫模型(Maximum Entropy Markov Model,MEMM)以及条件随机场(Conditional Random Field,CRF)是序列标注中最常用也是最基本的三个模型。HMM首先出现,MEMM其次,CRF最[1] 。三个算法主要思想如下[1]:
1. HMM模型是对转移概率和表现概率直接建模,统计共现概率。
2. MEMM模型是对转移概率和表现概率建立联合概率,统计时统计的是条件概率,但MEMM容易陷入局部最优,是因为MEMM只在局部做归一化。
3. CRF模型中,统计了全局概率,在做归一化时,考虑了数据在全局的分布,而不是仅仅在局部归一化,这样就解决了MEMM中的标记偏置(label bias)的问题(注:标注偏置指的是在进行序列标注的时候,由于是局部归一,导致转移分支数量不等,会造成较少的分支更容易转移)

  1. CRF推导

和HMM不同,CRF是一种判别模型,建立的是随机变量x和y之间的条件概率模型,在图模型中是一种无向图模型。与MEMM不同的是,CRF考虑了全局的状态,而不像MEMM仅仅考虑局部。前面提到CRF建立的是条件概率模型,也即p(y|x), 其公式如下(此时只考虑了边函数):

$$
\begin{align}
p(y|x) & = \frac{\prod_{t=1}^T exp(\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))} {Z(x)} \\
& = \frac{ exp(\sum_{t=1}^T\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))} {Z(x)}
\end{align}
$$

其中,z(x)为归一化因子,也即p(x), $\phi(y_t,y_{t-1},x_t) = exp(\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))$
$$
Z(x) = \sum_y {exp(\sum_{t=1}^T\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))}
$$

利用极大似然估计,可得(为了方便,去掉了x,y的上标i):
$$
\begin{align}
L(\theta) & = \prod_{i=1}^N p(y|x) \\
& = \prod_{i=1}^N \frac{exp(\sum_{t=1}^T\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))} {Z(x)} \\
\end{align}
$$

$$
\begin{align}
ln(L(\theta)) & = \sum_{i=1}^N p(y|x) \\
& = \sum_{i=1}^N (\sum_{t=1}^T \sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t) – ln({Z(x)})) \\
\end{align}
$$

1.1 参数学习

CRF优化的参数只有$\lambda$, f(x)为特征函数,一般是根据特征模板去遍历训练数据得到。对$\lambda$求导可得:

$$
\begin{align}
\frac{\partial {ln(L(\theta))}} {\partial {\lambda_k}} = \sum_{i=1}^N (\sum_{t=1}^T f_k(y_t, y_{t-1}, x_t)- \frac{1}{Z(x)} \frac { \partial {Z(x)}} {\partial {\lambda_k}})
\end{align}
$$

对$\frac { \partial {Z(x)}} {\partial {\lambda_k}}$单独求导可得:
$$
\begin{align}
\frac { \partial {Z(x)}} {\partial {\lambda_k}} = \sum_y [exp(\sum_{t=1}^T\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t)) * \sum_{t=1}^T f_k(y_t, y_{t-1}, x_t)]
\end{align}
$$

则:
$$
\begin{align}
\frac{1}{Z(x)} \frac { \partial {Z(x)}} {\partial {\lambda_k}} & = \sum_y [\frac{ exp(\sum_{t=1}^T\sum_{k=1}^K \lambda_k f_k(y_t, y_{t-1}, x_t))} {Z(x)} * \sum_{t=1}^T f_k(y_t, y_{t-1}, x_t)] \\
& = \sum_y [ p(y|x) * \sum_{t=1}^T f_k(y_t, y_{t-1}, x_t) ]
\end{align}
$$

所以求导结果为:
$$
\begin{align}
\frac{\partial {ln(L(\theta))}} {\partial {\lambda_k}} = \sum_{i=1}^N (\sum_{t=1}^T f_k(y_t, y_{t-1}, x_t)- \sum_y [ p(y|x) * \sum_{t=1}^T f_k(y_t, y_{t-1}, x_t) ] )
\end{align}
$$

从中可以推知,对于每一个$p(y_1,y_2,..,y_{t-1},y_{t},..y_T|x)$,会乘以$\sum_{t=1}^T f_k(y_t=s, y_{t-1}=s’, x_t)$ ,

那么,对于每一个$f_k(y_t=s, y_{t-1}=s’, x_t)$也会乘以$\sum_{y_1,y_2,…,y_{t-2},y_{t+1},..,y_T} p(y_1,y_2,..,y_{t-1},y_{t},..y_T|x)$, 所以有:
$$
\begin{align}
\frac{\partial {ln(L(\theta))}} {\partial {\lambda_k}} = \sum_{i=1}^N (\sum_{t=1}^T f_k(y_t, y_{t-1}, x_t)- \sum_{y_{t-1},y_{t}} \sum_{t=1}^T [ p(y_{t-1}=s’,y_t=s|x) * f_k(y_t=s, y_{t-1}=s’, x_t) ] )
\end{align}
$$

其中,$f_k(y_t, y_{t-1})$可由模板函数和样本本身统计得到,而p(s,s’|x)可以利用类似于HMM的前向后向算法求解。

令$\alpha_t(s_i)$为t时刻隐含状态为$s_i$的概率,也即$\alpha_t(s_i)=p(x_1,x_2,…,x_t,y_t=s_i)$,

$$
\begin{align}
\alpha_t(s_i) & = p(x_1,x_2,…,x_t,y_t=s_i) \\
& = \sum_{y_1,…,y_{t-1}} p(x_1,x_2,…,x_{t-1},y_{t-1}=s_j, x_t, y_t = s_i) \\
& = \sum_{y_{t-1}=s_j} \sum_{y_1,…,y_{t-2}} p(x_1,x_2,…,x_{t-1},y_1,…y_{t-2}, y_{t-1}=s_j,x_t,y_t=s_i) \\
& = \sum_{s_j} \sum_{y_1,…,y_{t-2}} (\prod_{l=1}^{t-2} \phi(y_{l-1},y_l,x_l)) \phi(y_{t-2},y_{t-1}=s_j,x_{t-1}) \phi(y_{t-1}=s_j,y_t=s_i,x_t) \\
& = \sum_{s_j} \alpha_{t-1}(s_j) \phi(y_{t-1}=s_j,y_t=s_i,x_t)
\end{align}
$$

$p(x_1,x_2,x_3,…x_T) =\sum_{s_i} p(x_1,x_2,…,x_t,y_t=s_i)=\sum_{s_i} \alpha_T(s_i)$

令$\beta_t(s_i)$为t时刻隐含状态为$s_i$,且观测序列为$x_{t+1},..x_T$的概率,有:

$$
\begin{align}
\beta_t(s_i) & = p(x_{t+1},x_{t+2},…,x_T|y_t=s_i) \\
& = \sum_{s_j} p(x_{t+1},x_{t+2}, …,x_T, y_{t+1}=s_j| y_t=s_i, ) \\
& = \sum_{y_{t+1}=s_j} \sum_{y_{t+2},..,y_T} p(x_{t+1},x_{t+2}, …,x_T, y_{t+1}=s_j, y_{t+2},..,y_T| y_t=s_i) \\
& = \sum_{y_{t+1}=s_j} \sum_{y_{t+2},..,y_T} (\prod_{l={t+2}}^{T} \phi(y_{l-1},y_l,x_l)) \phi(y_{t+1}=s_j,y_t=s_i,x_{t+1}) \\
& = \sum_{s_j} \beta_{t+1}(s_j) \phi(y_{t+1}=s_j,y_t=s_i,x_{t+1}) \\
\end{align}
$$

则$p(s,s’|x)$为:
$$
\begin{align}
p(s,s’|x) & = p(y_{t-1}=s’, y_t=s|x_1,x_2,…,x_T) \\
& = \frac{p(x_1,x_2,…,x_T,y_{t-1}=s’, y_t=s)} {p(x_1,x_2,…,x_T)} \\
& = \frac{ a_{t-1}(s’) * \phi(s’, s, x_t) \beta_{t}(s) } { \sum_{s_i} \alpha_T(s_i)}
\end{align}
$$

得到损失函数对$\lambda_k$的求导之后,便可以利用梯度下降的方法对$\lambda$进行更新.

1.2 推断

对于给定的$x$,计算得到最大概率的状态序列y,也即$argmax_{y}(p(y|x))$, 可以用vietebi算法进行求解,令$\delta_t(s_i)$为t时刻隐含状态为${s_i}$的最大概率,则

$$\delta_t(s_i) = max_{s_j}{\delta_{t-1}(s_i) * \phi(s_j, s_i, x_t)}$$.

2.实现

推导出$\lambda$的梯度更新公式,就很容易实现了~ 在实现的时候关注几个变量的求解即可.

2.1 特征函数

假设条件概率建模的时候只考虑边特征函数$f(y_{t-1},y_t,x_t)$,那么在实现的时候可以简单的使用一个三维数组f来表示这个边特征函数, f[ob_state][si][sj]表示的是观测状态为ob_state, 并且上一时刻隐含状态为si,当前时刻隐含状态为sj的特征函数,这个可以通过遍历训练数据得到,我们给个简单的分词的例子来说明,对于我们给定的训练语聊:

今 B
天 E
天 B
气 E
真 S
不 B
错 E

那么,假设特征模板只有边函数,理论上可以得到如下的特征函数,其中s

$f_1(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘今’ and $y_{t-1}$ ='<s>’ and $y_{t}$ = ‘B’ else 0
$f_2(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘天’ and $y_{t-1}$ =’B’ and $y_{t}$ = ‘E’ else 0
$f_3(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘天’ and $y_{t-1}$ =’E’ and $y_{t}$ = ‘B’ else 0
$f_4(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘气’ and $y_{t-1}$ =’B’ and $y_{t}$ = ‘E’ else 0
$f_5(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘真’ and $y_{t-1}$ =’E’ and $y_{t}$ = ‘S’ else 0
$f_6(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘不’ and $y_{t-1}$ =’S’ and $y_{t}$ = ‘B’ else 0
$f_7(y_{t-1},y_t,x_t) $ = 1 if $x_t$ = ‘错’ and $y_{t-1}$ =’B’ and $y_{t}$ = ‘E’ else 0

那么在代码里,首先我们对ob_state进行编码,出现过的观测状态’今’、’天’、’气’、’真’、’不’、’错’的编码分别为1、2、3、4、5、6. BEMS分别为1、2、3、4. 起始状态为0. 则上述的的特征函数$f_1,…f_7$分别可以用f[1][0][1]、f[2][1][2]、f[2][2][1]、f[3][2][1]、f[4][2][4]、f[5][4][1]、f[6][1][2] 来表示. 当然这个实现还是很耗内存的.

2.2 特征函数的参数$\lambda$

因为特征函数和参数是一一对应的,为了实现方便,我们也用三维数组来表达$\lambda$. $\lambda[ob\_state][si][sj]$对应的特征函数为f[ob_state][si][sj]. 由三维数组来存储特征函数和参数的好处是在推断的时候,我们能够直接根据给定的观测状态迅速定位需要的特征函数和参数,从而根据vertibi推断最可能的隐含状态序列.

2.3 debug

应用一阶梯度的优化方法一般都比较好debug, 直接用梯度检测即可.

具体实现见:https://github.com/kymo/SUML/blob/master/CRF/crf.h

3. 应用

crf在诸多场景都得到了很好的应用,比如比较常见的命名实体识别、分词、词性标注等,当然在具体的业务场景中也有不少应用,比如地图中的poi识别,语音交互的nlp中的slot filling,多轮对话场景下的指代消解等等,甚至可以用在语音识别中的语句平滑中~

当然,现在RNN越来越多的参与到这种序列建模的工作中,在传统的序列标注任务中取得了state of art的成绩,但是这也不意味着CRF会逐渐的消逝,除了性能因素之外,另外一个很大的原因是在于CRF能够很好的对label整体进行建模,它给出的是整个label的条件概率,而RNN做标注的时候,仅仅是考虑了观测状态之间的信息传递。

所以,就有人综合了两者的性能表现,提出了LSTM-CRF, RNN-CRF, GRU-CRF等诸多解决方案,通过结合RNN系列模型能够结合更多观测状态信息以及CRF的序列整体建模能力,提升标注的准确. 一般的架构是输入层+embedding层+RNN cell+seq softmax+CRF layer. 其中seq softmax层的输出是一个二维矩阵p,p[si][ob_state]可以认为是隐含状态si到观测状态ob_state之间的激发概率.  和通常的crf不同的是,rnn后接crf, 一般需要学习的是转移概率矩阵A,A[i][j]表示的隐含状态i到隐含状态j的转移概率,那么可以得到p(x,y)为:

$$p(x_1,…x_T,y_1,…,y_T) = exp(\sum_{t=1}^T A_{y_{t-1} ,{y_{t}}} + \sum_{t=1}^T p_{y_{t},x_{t}}) $$

那么我们便可以重新得到不同于原始crf的loss, 原始的loss中需要用到特征函数和特征参数,此时我们需要关注的仅仅是转移概率矩阵. 加入crf layer的神经网络的loss仍然用log likelihood,如下:

$$
\begin{align}
L(\theta) & = \prod \frac{p(x,y)} {Z(x)} \\
& = \prod \frac{ exp(\sum_{t=1}^T A_{y_{t-1} ,{y_{t}}} + \sum_{t=1}^T p_{y_{t},x_{t}}) } {Z(x)} \\
log(L(\theta)) & = \sum_{batch}( {\sum_{t=1}^T A_{y_{t-1} ,{y_{t}}} + \sum_{t=1}^T p_{y_{t},x_{t}} – log(Z(x))})
\end{align}
$$

具体实现可以见tensorflow中的crf_log_likelihood: https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/crf/python/ops/crf.py 其中,crf_log_likelihood的loss=crf_sequence_score-crf_log_norm.

参考文献
1. https://www.52ml.net/1709.html
2. https://zhuanlan.zhihu.com/p/26696451

Leave a Reply

Your email address will not be published. Required fields are marked *