CRF模型的学习问题和预测问题

CRF的learning问题

如通常的分类问题，x属于分类y的概率模型为：
$p(y|x) = \frac{\exp{(score(y,x))}}{\sum_{\forall \ y^{'} }\exp{(score(y^{'}, x))}}$

名词解释

术语	含义
$x$	样本特征，可以包括文本序列、词性序列、实体指示词序列等，如果是LSTM+CRF，则x是embedding序列
$y$	样本label，是一个长度与输入文本相同的序列
$y_t$	在位置t上的label
$f_k(y,x)$	样本(y,x)在特征模板k上的取值

对数似然函数为：
$L = score(y,x) - log{\sum_{\forall \ y^{'}}\exp({score(y^{'}, x)})}$
损失函数为在样本集上的对数似然的负数：
$Loss = -\sum_{x,y\in samples}{[score(y,x) - log{\sum_{\forall \ y^{'}}\exp({score(y^{'}, x)})}]}$
求解等式右侧 $log{\sum_{\forall \ y^{'}}\exp({score(y^{'}, x)})}$ 的值需要穷举所有的路径，是指数复杂度的，是不可解的。那怎么办？这里列举两个思路（对应2个序列标注模型）。

退而求其次，不在整体上拟合全序列label，而是在每个局部位置上拟合状态转移概率，将学习到的概率转移矩阵放到隐马尔可夫模型的框架中，计算全序列概率。这就是MEMM（Maximum Entropy Markov Model）方法，相比于隐马模型，其概率转移矩阵是与x相关的（用最大熵模型求解的），其表达能力有了很大的提升,但其仍然是一个Markov Model，状态转移概率归一化是在每一步独立进行的，而不是在全局上进行的，导致一个重大的缺陷即“Label Bias Problem”。
如果可以把打分函数 $score(y,x)$ 拆解为局部特征（unigramt特征 $f(y_t,x)$ 和bigram特征 $f(y_{t-1}, t_t,x)$ ）的加权和，这时候 $log{\sum_{\forall \ y^{'}}\exp({score(y^{'}, x)})}$ 是可解的（这个设定，和 $p(y,x) = \prod_{t=1}^{n}{p(y_{t-1},y_t,x)}$ 这个设定是等价的。而 $p(y,x) = \prod_{t=1}^{n}{p(y_{t-1},y_t,x)}$ 这个设定，又和概率图模型 $p(y,x)$ 满足马尔可夫性即 $p(y_{t}|x,y)=p(y_{t}|x,y_{t-1},y_{t+1})$ 是等价的。有兴趣的可以自己推导一下）。这就是CRF方法。

以下讨论CRF方法对特征权重的求解方法。

定义 $f_k(y,x)$ 是样本 $(y,x)$ 在特征模板K上的取值， $w_k$ 是特征 $k$ 的权重：
$score(y,x) = \sum_k{w_kf_k(y,x)}$

$f_k(y,x)=\sum_t{f_k(y_{t-1},y_t,x)}$

$Loss = -\sum_{x,y\in samples} log\frac{exp(\sum_k{w_kf_k(y,x)})}{\sum_{\forall \ y^{'}}{\sum_kexp({w_kf_k(y^{'},x)})}}$

$\frac{\partial Loss }{\partial w_k} = \sum_{x,y\in samples}{f_k(y,x)} - \sum_{x\in samples}{\sum_{\forall \ y^{'}}{p(y^{'}|x)f_k(y^{'},x)}}$

注：等式右边，第一部分是特征在样本中的计数，也就是特征在经验分布中的期望。(the data feature counts)

第二部分是特征在model分布中的期望（the model expectet feature counts)

问题的关键，是第二部分的求解。

为简化问题，对上式，去掉外层的求和，即对单个样本进行求解：
$\sum_{y^{'}\in all\ path}{P(y^{'}|x)f_k(y^{'},x)}$

$=\sum_{y^{'}\in all\ path}{\{P(y^{'}|x)\sum_t{f_k(y_{t-1},y_t,x)}\}}$

$= \sum_{t}{\sum_{y^{'}\in all\ path}{P(y^{'}|x)f_k(y_{t-1},y_t,x)}}$

$= \sum_{t}\sum_{\forall a,b\in y}{\{f_k(y_{t-1}=a,y_t=b,x){\sum_{\forall \ y^{'}\ s.t.\ y_{t-1}=a,y_t=b }{P(y^{'}|x)}}\}}$

$= \sum_{t}\sum_{\forall a,b\in y}{f_k(y_{t-1}=a,y_t=b,x)P(y_{t-1}=a,y_t=b | x)}$

Forword-Backword算法

记
$W_t(y_{t-1},y_t|x)=\sum_{k}w_kf_k(y_{t-1},y_t,x)$

$M_t(y_{t-1},y_t|x)=exp(W_t(y_{t-1},y_t,x))$

则：
$P_w(y|x) = \frac{1}{Z_w(x)}\prod_{t=1}^{n+1}{M_t(y_{i-1}|y_t,x)}$

定义前向向量和后向向量：
$\alpha_1(y_1) = M(start, y_1)$

$\alpha_t(y_t) = \sum_{y_{t-1}}\alpha(y_{t-1})M(y_{t-1}, y_t)$

$\beta_n(y_n) = M(y_n,stop)$

$\beta_{t-1}(y_{t-1}) = \sum_{y_{t}}\beta(y_{t})M(y_{t-1}, y_t)$

则有：

全路径概率总和：
$Z(x) = \alpha(y_{n+1})=\sum_{y_n}{M(y_n,stop)\alpha(y_n)} = \beta(y_0) = \sum_{y_1}{M(start,y_1)\beta(y_1)}$
求解unigram特征权重时需要的：
$P(y_t=a|x)=\frac{\alpha(y_t=a)\beta(y_t=a)}{Z(x)}$
求解bigram特征权重时需要的：
$P(y_{t-1}=a,y_t=b|x) = \frac{\alpha(y_{t-1}=a)M(y_{t-1}=a,y_t=b)\beta(y_t=b)}{Z(x)}$

预测问题

$\arg \max_y{p(y|x)}$

$= \arg\max_y\frac{\exp{(score(y,x))}}{\sum_{\forall \ y^{'}}\exp{(score(y^{'}, x))}}$

$= \arg\max_yscore(y,x)$

$=\arg\max_y{\sum_k{w_kf_k(y,x)}}$

$=\arg\max_y{\sum_k{w_k\sum_t{f_k(y_{t-1},y_t,x)}}}$

$=\arg\max_y{\sum_t{\sum_kw_k{f_k(y_{t-1},y_t,x)}}}$

$=\arg\max_y{\sum_t{W_t(y_{t-1},y_t|x)}}$

转化为最大路径求解的问题，计算好 $W_t$ 矩阵后，用verterbi算法求解即可。

工程实践

传统方法，比如基于CRF++，基于特征模板：参考用CRF做命名实体识别(三)

特征	F1值	精度	召回率
字	0.8399	0.8472	0.8327
字+词性+边界	0.8711	0.8839	0.8589
字+词性+边界+实体指示词	0.8856	0.9076	0.8649
字+词性+边界+特征词	0.8847	0.8990	0.8709
字+词性+边界+实体指示词 +特征词	0.8853	0.8994	0.8718
字+词性+边界+常用词	0.928	0.9382	0.9182
字+词性+边界+特征词+常用词	0.9293	0.9381	0.9207
字+词性+边界+实体指示词+特征词+常用词	0.9261	0.9334	0.9191