> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/hmm/10.md).

# 预测问题 - 维特比算法

**输入：**\
模型$$\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$$向前追溯最优路径。