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

2017-11-22 2574

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

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(一)第八节中，我们定义了下式：

M i (y i - 1, y i | x) = e x p (\sum k = 1 K w k f k (y i - 1, y i, x, i))

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

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

α i + 1 (y i + 1 | x) = α i (y i | x) M i + 1 (y i + 1, y i | x)

　　　　在起点处，我们定义：

α 0 (y 0 | x) = {10 y 0 = s t a r t e l s e

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

α i (x) = (α i (y i = 1 | x), α i (y i = 2 | x), . . . α i (y i = m | x)) T

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

M i (x) = [M i (y i - 1, y i | x)]

　　　　这样递推公式可以用矩阵乘积表示：

α T i + 1 (x) = α T i (x) M i (x)

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

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

β i (y i | x) = M i + 1 (y i, y i + 1 | x) β i + 1 (y i + 1 | x)

　　　　在终点处，我们定义：

β n + 1 (y n + 1 | x) = {10 y n + 1 = s t o p e l s e

　　　　如果用向量表示，则有：

β i (x) = M i + 1 (x) β i + 1 (x)

　　　　由于规范化因子Z(x)的表达式是：

Z (x) = \sum c = 1 m α n (y c | x) = \sum c = 1 m β 1 (y c | x)

　　　　也可以用向量来表示Z(x):

Z (x) = α T n (x) ∙ 1 = 1 T ∙ β 1 (x)

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

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

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

P (y i | x) = α T i ( y i | x ) β i ( y i | x ) Z ( x ) = α T i ( y i | x ) β i ( y i | x ) α T n ( x ) ∙ 1

　　　　也容易计算序列位置i的标记是yi，位置i−1的标记是yi−1 时的条件概率P(yi−1,yi|x):

P (y i - 1, y i | x) = α T i - 1 ( y i - 1 | x ) M i ( y i - 1 , y i | x ) β i ( y i | x ) Z ( x ) = α T i - 1 ( y i - 1 | x ) M i ( y i - 1 , y i | x ) β i ( y i | x ) α T n ( x ) ∙ 1

4. linear-CRF的期望计算

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

　　　　特征函数fk(x,y)关于条件分布P(y|x)的期望表达式是：

E P (y | x) [f k] = E P (y | x) [f k (y, x)] = \sum i = 1 n + 1 \sum y i - 1 y i P (y i - 1, y i | x) f k (y i - 1, y i, x, i) = \sum i = 1 n + 1 \sum y i - 1 y i f k (y i - 1, y i, x, i) α T i - 1 ( y i - 1 | x ) M i ( y i - 1 , y i | x ) β i ( y i | x ) α T n ( x ) ∙ 1 (1) (2) (3)

　　　　同样可以计算联合分布P(x,y)的期望：

E P (x, y) [f k] = \sum x, y P (x, y) \sum i = 1 n + 1 f k (y i - 1, y i, x, i) = \sum x P ¯ ¯ ¯ ¯ (x) \sum y P (y | x) \sum i = 1 n + 1 f k (y i - 1, y i, x, i) = \sum x P ¯ ¯ ¯ ¯ (x) \sum i = 1 n + 1 \sum y i - 1 y i f k (y i - 1, y i, x, i) α T i - 1 ( y i - 1 | x ) M i ( y i - 1 , y i | x ) β i ( y i | x ) α T n ( x ) ∙ 1 (4) (5) (6)

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

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

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

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

本文转自刘建平Pinard博客园博客，原文链接：http://www.cnblogs.com/pinard/p/7055072.html，如需转载请自行联系原作者

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

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

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

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

4. linear-CRF的期望计算

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

热门文章

最新文章

相关课程

相关电子书

相关实验场景