# 预测问题 - 维特比算法

**输入：**\
模型$$\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.  递推 &#x20;

    $$
    \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.  终止 &#x20;

    $$
    P* = \max \sigma_T
    $$

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