条件随机场CRF(二) 前向后向算法评估标记序列概率

　　　　条件随机场CRF(一)从随机场到线性链条件随机场

　　　　条件随机场CRF(二) 前向后向算法评估标记序列概率

　　　　条件随机场CRF(三) 模型学习与维特比算法解码

　　　　在条件随机场CRF(一)中我们总结了CRF的模型，主要是linear-CRF的模型原理。本文就继续讨论linear-CRF需要解决的三个问题：评估，学习和解码。这三个问题和HMM是非常类似的，本文关注于第一个问题：评估。第二个和第三个问题会在下一篇总结。

1. linear-CRF的三个基本问题

　　　　在隐马尔科夫模型HMM中，我们讲到了HMM的三个基本问题，而linear-CRF也有三个类似的的基本问题。不过和HMM不同，在linear-CRF中，我们对于给出的观测序列x是一直作为一个整体看待的，也就是不会拆开看(x1,x2,...)，因此linear-CRF的问题模型要比HMM简单一些，如果你很熟悉HMM，那么CRF的这三个问题的求解就不难了。

　　　　 linear-CRF第一个问题是评估，即给定 linear-CRF的条件概率分布P(y|x), 在给定输入序列x和输出序列y时，计算条件概率P(yi|x)和P(yi−1，yi|x)以及对应的期望. 本文接下来会详细讨论问题一。

　　　　 linear-CRF第二个问题是学习，即给定训练数据集X和Y，学习linear-CRF的模型参数wk和条件概率Pw(y|x)，这个问题的求解比HMM的学习算法简单的多，普通的梯度下降法，拟牛顿法都可以解决。

　　　　 linear-CRF第三个问题是解码，即给定 linear-CRF的条件概率分布P(y|x),和输入序列x, 计算使条件概率最大的输出序列y。类似于HMM，使用维特比算法可以很方便的解决这个问题。　

2.linear-CRF的前向后向概率概述

　　　　要计算条件概率P(yi|x)和P(yi−1，yi|x)，我们也可以使用和HMM类似的方法，使用前向后向算法来完成。首先我们来看前向概率的计算。

　　　　我们定义αi(yi|x)表示序列位置i的标记是yi时，在位置i之前的部分标记序列的非规范化概率。之所以是非规范化概率是因为我们不想加入一个不影响结果计算的规范化因子Z(x)在分母里面。

　　　　在条件随机场CRF(一)第八节中，我们定义了下式：Mi(yi−1,yi|x)=exp(K∑k=1wkfk(yi−1,yi,x,i))

　　　　这个式子定义了在给定yi−1时，从yi−1转移到yi的非规范化概率。

　　　　这样，我们很容易得到序列位置i+1的标记是yi+1时，在位置i+1之前的部分标记序列的非规范化概率αi+1(yi+1|x)的递推公式：αi+1(yi+1|x)=αi(yi|x)Mi+1(yi+1,yi|x)

　　　　在起点处，我们定义：α0(y0|x)={1y0=start0else

　　　　假设我们可能的标记总数是m, 则yi的取值就有m个，我们用αi(x)表示这m个值组成的前向向量如下：αi(x)=(αi(yi=1|x),αi(yi=2|x),...αi(yi=m|x))T

　　　　同时用矩阵Mi(x)表示由Mi(yi−1,yi|x)形成的m×m阶矩阵：Mi(x)=[Mi(yi−1,yi|x)]

　　　　这样递推公式可以用矩阵乘积表示：αTi+1(x)=αTi(x)Mi(x)

　　　　同样的。我们定义βi(yi|x)表示序列位置i的标记是yi时，在位置i之后的从i+1到n的部分标记序列的非规范化概率。

　　　　这样，我们很容易得到序列位置i+1的标记是yi+1时，在位置i之后的部分标记序列的非规范化概率βi(yi|x)的递推公式：βi(yi|x)=Mi(yi,yi+1|x)βi+1(yi+1|x)

　　　　在终点处，我们定义：βn+1(yn+1|x)={1yn+1=stop0else

　　　　如果用向量表示，则有：βi(x)=Mi(x)βi+1(x)

　　　　由于规范化因子Z(x)的表达式是：Z(x)=m∑c=1αn(yc|x)=m∑c=1β1(yc|x)

　　　　也可以用向量来表示Z(x):Z(x)=αTn(x)∙1=1T∙β1(x)

　　　　其中，1是m维全1向量。

3. linear-CRF的前向后向概率计算

　　　　有了前向后向概率的定义和计算方法，我们就很容易计算序列位置i的标记是yi时的条件概率P(yi|x):P(yi|x)=αTi(yi|x)βi(yi|x)Z(x)=αTi(yi|x)βi(yi|x)αTn(x)∙1

　　　　也容易计算序列位置i的标记是yi，位置i−1的标记是yi−1 时的条件概率P(yi−1,yi|x):P(yi−1,yi|x)=αTi−1(yi−1|x)Mi(yi−1,yi|x)βi(yi|x)Z(x)=αTi−1(yi−1|x)Mi(yi−1,yi|x)βi(yi|x)αTn(x)∙1

4. linear-CRF的期望计算

　　　　有了上一节计算的条件概率，我们也可以很方便的计算联合分布P(x,y)与条件分布P(y|x)的期望。

　　　　特征函数fk(x,y)关于条件分布P(y|x)的期望表达式是：EP(y|x)[fk]=EP(y|x)[fk(y,x)]=n+1∑i=1∑yi−1yiP(yi−1,yi|x)fk(yi−1,yi,x,i)=n+1∑i=1∑yi−1yifk(yi−1,yi,x,i)αTi−1(yi−1|x)Mi(yi−1,yi|x)βi(yi|x)αTn(x)∙1

　　　　同样可以计算联合分布P(x,y)的期望：EP(x,y)[fk]=∑x,yP(x,y)n+1∑i=1fk(yi−1,yi,x,i)=∑x¯P(x)∑yP(y|x)n+1∑i=1fk(yi−1,yi,x,i)=∑x¯P(x)n+1∑i=1∑yi−1yifk(yi−1,yi,x,i)αTi−1(yi−1|x)Mi(yi−1,yi|x)βi(yi|x)αTn(x)∙1

　　　　假设一共有K个特征函数，则k=1,2,...K

5. linear-CRF前向后向算法总结

　　　　以上就是linear-CRF的前向后向算法，个人觉得比HMM简单的多，因此大家如果理解了HMM的前向后向算法，这一篇是很容易理解的。

　　　　注意到我们上面的非规范化概率Mi+1(yi+1,yi|x)起的作用和HMM中的隐藏状态转移概率很像。但是这儿的概率是非规范化的，也就是不强制要求所有的状态的概率和为1。而HMM中的隐藏状态转移概率也规范化的。从这一点看，linear-CRF对序列状态转移的处理要比HMM灵活。