条件随机场 (CRF 入门)——预测算法

五、CRF预测算法

目标:已知模型参数和输入序列,求出最大概率的输出序列。

对于线性链条件随机场,通常采用Viterbi算法进行求解,这是一个非常常见的动态规划算法,思想也很简单。如果之前没有学过可以看一下,如果很熟可以直接跳过。

线性链条件随机场的Viterbi算法:

输入: 模型的特征向量F(y,x),权值向量w,观测序列$x = (x_{1},x_{2},\ldots,x_{n})$

输出: 最优路径$y{*} = (y_{1}{\ast},y_{n}{\ast},\ldots,y_{n}{\ast})$

(1)初始化:

$$ \delta_{1}\left( j \right) = w F_{1}(y_{0} = \text{start},y_{1} = j,x) $$

其中j=1,2,…,m代表y的所有可能取值

(2)递推:对i=2,3,…,n, l=1,2,…,m

$$ \delta_{i}\left( l \right) = {\delta_{i - 1}\left( j \right) + w F_{i}(y_{i - 1} = j,y_{i} = l,x)} $$

$$ \Psi_{i}\left( l \right) = {\delta_{i - 1}\left( j \right) + w F_{i}(y_{i - 1} = j,y_{i} = l,x)} $$

(3)终止:

$$ \max_{y}\{{wF(y,x)}\} = \{\delta_{n}{(j)}\} $$

$$ y_{n}{*} = {\delta_{n}\left( j \right)} $$

(4)返回路径: $y_{i}^{\ast}=\Psi_{i+1}( y_{i + 1}^{\ast})$

最终得到$y^{\ast} = (y_{1}^{\ast},y_{n}^{\ast},\ldots,y_{n}^{\ast})$

一般的CRF的预测算法和普通的概率图模型一样,采用和积算法即可得到,这里就不赘述了。

Reference:

《统计学习方法》李航

https://www.zhihu.com/question/20380549/answer/45066785 宁远成梁

https://zhuanlan.zhihu.com/p/26696451

展开全文
相关主题
Top
微信扫码咨询专知VIP会员