维特比算法

Verterbi Algorithm

一个动态规划算法，求解HMM模型在特定观测序列下的内部状态。

一般应用于通信的信号解码的领域

公式

目标： $Q\ast =\arg {\max }_{Q}P(Q|O,\lambda )$

• 目标为最大化 Q （内部状态）的概率，建立在 O 指定观测和 $\lambda$ 模型参数之下

动态规划的递推公式：

$${\delta }_t(j)=\underset{i}{\max }[{\delta }_{t-1}(i)\cdot A[i][j]]\cdot B[j][o_t]$$

解释：

• ${\delta }_t(i)$ ： t 时刻到达状态 i 的最大概率
• ${\psi }_t(i)$ ：记录路径
• 取最大值：在当前步骤下，取前一个状态的最大概率，最后形成一条路径
• A 和 B 分别为 HMM 中的状态转移矩阵和观测矩阵

例子

source: 如何通俗地讲解 viterbi 算法？ - Kiwee的回答 - 知乎

要点：

• 内部状态：健康还是发烧
• 观测状态：正常、冷、头晕

路径示意图：

在计算概率的过程中，每一个节点上的概率均可以在途中标记。概率计算完成后，前向过程结束，反向过程开始，寻找一个最大化的最优路径。