【概述】
对于线性链条件随机场的预测问题，即：已知线性链条件随机场 $P(Y|X)$ 和输入序列 $x$，求条件概率最大的输出序列 $y^{*}$，即对输入序列进行标注
条件随机场的预测算法与隐马尔可夫模型的预测算法相似，采用 Viterbi 算法，即采用动态规划求概率最大路径，一条路径对应一条状态
关于 Viterbi 算法，详见：隐马尔可夫模型的预测
【基本思想】
由线性链条件随机场的内积形式
可得：
故线性链条件随机场的预测问题，可转化为求非规范化概率最大的最优路径问题：
其中，用路径表示标记序列，即有：
为求解最优路径，可将 $\max\limits_y \big[ \mathbf{w}\cdot F(y,x) \big]$ 写为如下形式：
其中，对于局部特征向量 $F_i(y_{i-1},y_i,x)$ ，有：
下面，定义在位置 $1$ 的各标记 $j=1,2,\cdots,m$ 的非规范化概率：
根据定义，可得到 $\delta$ 的递推公式：
即可求出到位置 $i$ 的各标记 $l=1,2,\cdots,m$ 的非规范化概率的最大值
同时，可记录非规范化概率最大值的路径，即：
直到 $i=n$ 时终止，此时求得非规范化概率的最大值为：
以及最优路径的终点：
由此最优路径返回，有：
求得最优路径为：
【算法流程】
综上所属，对于线性链条件随机场预测的 Viterbi 算法流程如下
输入：模型特征向量 $F(y,x)$，权值向量 $\mathbf{w}$，观测序列 $x=(x_1,x_2,\cdots,x_n)$
输出：最优路径 $y^{*} = (y_1^{*},y_2^{*},\cdots,y_n^{*})$
算法流程：
Step 1：算法初始化
Step 2：对 $i=2,3,\cdots,n$ 递推
Step 3：终止
Step 4：返回路径
求得最优路径为：
