预测问题 - 维特比算法

输入： 模型$\lambda=(A, B, \pi)$ 观测O 输出： 最优状态序列I*

定义： $\sigma_t(i)$：t时刻状态为i的所有路径的概率中的的最大值

$$\sigma_t(i) = \max_{i=1}^NP(i_t=q_i|\lambda)$$

$\psi_t(i)$：t时刻状态为i时，当$\sigma_t(i)$取得最大值时记录一下t-1的状态

过程： 1. 初始化

$$\begin{aligned} \sigma_1(i) = \pi_ib_i(o_1) \\ \psi_1(i) = 0 \end{aligned}$$

1. 递推

   $$\sigma_t(i) = \max_{1\le j\le N}[\sigma_{t-1}(j)a_{ji}b_i(o_t)]$$

   保存导致$\sigma_t(i)$最大的$i_{t-1}$

2. 终止

   $$P* = \max \sigma_T$$

   根据保存的$\psi$向前追溯最优路径。