4 linear chain CRF Viterbi

超找给定$x$序列最大概率输出序列$y^\ast$。

与HMM/MEMM viterbi类似的搜索方法，但在CRF中并不用计算规范化概率。
$$\begin{align} y^\ast &= \arg\max_y p(y|x) \\ &= \arg\max_y \frac{ \exp( w \cdot F(y,x) ) }{Z_w(x)} \\ &= \arg\max_y \exp( w \cdot F(y,x) ) \\ &= \arg\max_y w \cdot F(y,x) \\ &= \arg\max_y \sum_k w_k f_k(y, x) \\ &= \arg\max_y \sum_k w_k \sum_i f_k(y_{i-1}, y_i, x_i) \\ &= \arg\max_y \sum_i \sum_k w_k f_k(y_{i-1}, y_i, x_i) \\ &= \arg\max_y \sum_i f^\prime(y_{i-1}, y_i, x_i) \end{align}$$

$$f^\prime(y_{i-1}, y_i, x_i)=\sum_k w_k f_k(y_{i-1}, y_i, x_i)$$

也就是说只需计算连续最大特征函数求和路径。

可看到线行链中只有前后两个$y_{i-1}, y_i$是互相依赖的，因此这里和HMM类似，只是把求积换成求和。

1. 初始化:
   $$\begin{align} \delta_1(s_j) &= f^\prime(y_0=start, y_1=s_j, x_1) \\ \psi_1(s_j) &= 0 \end{align}$$

2. 递归:
   $$\begin{align} \delta_i(s_l) &= \max_{s_j} \delta_{i-1}(s_j) + f^\prime(y_{i-1}=s_j, y_i=s_l, x_i) \\ \psi_i(s_l) &= \arg\max_{s_j} \delta_{i-1}(s_j) + f^\prime(y_{i-1}=s_j, y_i=s_l, x_i) \end{align}$$

3. 结束：

$$\begin{align} \delta_{n+1}(s_l) &= \max_{s_j} \delta_{n}(s_j) + f^\prime(y_{n}=s_j, y_{n+1}=stop, x_{n+1}) \\ \psi_{n+1}(s_l) &= \arg\max_{s_j} \delta_{n}(s_j) + f^\prime(y_{n}=s_j, y_{n+1}=stop, x_{n+1}) \\ p^\ast &= \max_{s_j} \delta_{n+1}(s_j) \\ y_n^\ast &= \max_{s_j} \delta_{n+1}(s_j) \\ y_i^\ast &= \psi_{i+1}(y_{i+1}^\ast) \quad, i = n-1, n-2, \cdots, 1 \end{align}$$

参考资料：
[1] 李航; 统计机器学习
[2] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models
[3] Lafferty, J., McCallum, A., Pereira, F. (2001). “Conditional random fields: Probabilistic models for segmenting and labeling sequence data”. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289.
[4] An Introduction to Conditional Random Fields Charles Sutton1 and Andrew McCallum2