条件随机场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=1Kwkfk(yi−1,yi,x,i)) 这个式子定义了在给定yi−1时，从yi−1转移到yi的非规范化概率。 这样，我们很容易得到序列位置i+1的标记是yi+1时，在位置i+1之前的部分标记序列的非规范化概率αi+1(yi+1|x)的递推公式： αTi+1(yi+1|x)=αTi(yi|x)Mi+1(yi+1,yi|x) 在起点处，我们定义： α0(y0|x)={10y0=startelse 假设我们可能的标记总数是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+1(x) 同样的。我们定义βi(yi|x)表示序列位置i的标记是yi时，在位置i之后的从i+1到n的部分标记序列的非规范化概率。 这样，我们很容易得到序列位置i+1的标记是yi+1时，在位置i之后的部分标记序列的非规范化概率βi(yi|x)的递推公式： βi(yi|x)=Mi+1(yi,yi+1|x)βi+1(yi+1|x) 在终点处，我们定义： βn+1(yn+1|x)={10yn+1=stopelse 如果用向量表示，则有： βi(x)=Mi+1(x)βi+1(x) 由于规范化因子Z(x)的表达式是： Z(x)=∑c=1mαn(yc|x)=∑c=1mβ1(yc|x) 也可以用向量来表示Z(x): Z(x)=αTn(x)∙1=1T∙β1(x) 其中，1是m维全1向量。
3. linear-CRF的前向后向概率计算
4. linear-CRF的期望计算
5. linear-CRF前向后向算法总结
以上就是linear-CRF的前向后向算法，个人觉得比HMM简单的多，因此大家如果理解了HMM的前向后向算法，这一篇是很容易理解的。
注意到我们上面的非规范化概率$M_{i+1}(y_{i+1},y_i|x)$起的作用和HMM中的隐藏状态转移概率很像。但是这儿的概率是非规范化的，也就是不强制要求所有的状态的概率和为1。而HMM中的隐藏状态转移概率也规范化的。从这一点看，linear-CRF对序列状态转移的处理要比HMM灵活。
（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）