五、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