隐马尔可夫模型（HMM）的维特比算法原理与计算过程
字数 2241 2025-10-28 08:36:45

隐马尔可夫模型（HMM）的维特比算法原理与计算过程

题目描述
隐马尔可夫模型（HMM）的维特比算法用于解决解码问题：给定观测序列 \(O = (o_1, o_2, ..., o_T)\) 和HMM的参数 \(\lambda = (A, B, \pi)\)（其中 \(A\) 是状态转移矩阵，\(B\) 是观测概率矩阵，\(\pi\) 是初始状态概率分布），如何找到最可能产生该观测序列的隐藏状态序列 \(Q = (q_1, q_2, ..., q_T)\)？维特比算法通过动态规划高效求解最优路径。

解题过程

  1. 问题定义

    • 假设隐藏状态集合为 \(\{s_1, s_2, ..., s_N\}\)，观测集合为 \(\{v_1, v_2, ..., v_M\}\)。
    • 目标：计算 \(\arg\max_{Q} P(Q \mid O, \lambda)\)，即最大化 \(P(Q, O \mid \lambda)\)（因 \(P(O)\) 固定）。

  2. 动态规划表初始化

    • 定义两个表：
      • 概率表 \(\delta_t(i)\)：在时刻 \(t\)，隐藏状态为 \(s_i\) 的所有路径中的最大概率。
      • 路径回溯表 \(\psi_t(i)\)：记录达到 \(\delta_t(i)\) 时前一个时刻的状态。
    • 初始化（\(t=1\)）：

\[ \delta_1(i) = \pi_i \cdot b_i(o_1), \quad \psi_1(i) = 0 \quad (1 \leq i \leq N) \]

 其中 $ b_i(o_1) $ 是状态 $ s_i $ 生成观测 $ o_1 $ 的概率。
  1. 递推计算（\(t=2\) 到 \( T \）
    • 对每个时刻 \(t\) 和每个状态 \(s_j\)：

\[ \delta_t(j) = \max_{1 \leq i \leq N} \left[ \delta_{t-1}(i) \cdot a_{ij} \right] \cdot b_j(o_t) \]

\[ \psi_t(j) = \arg\max_{1 \leq i \leq N} \left[ \delta_{t-1}(i) \cdot a_{ij} \right] \]

 这里 $ a_{ij} $ 是从状态 $ s_i $ 转移到 $ s_j $ 的概率。
  1. 终止与路径回溯
    • 最终时刻 \(T\) 的最优概率和状态：

\[ P^* = \max_{1 \leq i \leq N} \delta_T(i), \quad q_T^* = \arg\max_{1 \leq i \leq N} \delta_T(i) \]

  • 逆序回溯最优路径（\(t=T-1\) 到 \(1\)）：

\[ q_t^* = \psi_{t+1}(q_{t+1}^*) \]

  1. 示例说明
    • 假设HMM有2个状态 \(\{s_1, s_2\}\)，观测序列为 \(O = (o_1, o_2)\)。
    • 已知参数：

\[ \pi = [0.6, 0.4], \quad A = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}, \quad B = \begin{bmatrix} 0.5 & 0.5 \\ 0.3 & 0.7 \end{bmatrix} \]

 观测索引：$ o_1 $ 对应 $ v_1 $，$ o_2 $ 对应 $ v_2 $。
  • 计算步骤：
    • \(t=1\)：
      \(\delta_1(1) = 0.6 \times 0.5 = 0.3\)，\(\delta_1(2) = 0.4 \times 0.3 = 0.12\)
    • \(t=2\)：
      • 对 \(s_1\)：
        \(\delta_2(1) = \max(0.3 \times 0.7, 0.12 \times 0.4) \times 0.5 = \max(0.21, 0.048) \times 0.5 = 0.105\)
        \(\psi_2(1) = \arg\max(0.21, 0.048) = s_1\)
      • 对 \(s_2\)：
        \(\delta_2(2) = \max(0.3 \times 0.3, 0.12 \times 0.6) \times 0.7 = \max(0.09, 0.072) \times 0.7 = 0.063\)
        \(\psi_2(2) = s_1\)
    • 回溯：
      \(q_2^* = \arg\max(0.105, 0.063) = s_1\)，\(q_1^* = \psi_2(s_1) = s_1\)
  • 最优路径：\((s_1, s_1)\)。

关键点

  • 维特比算法通过动态规划避免穷举所有路径（复杂度从 \(O(N^T)\) 降至 \(O(T \cdot N^2)\)）。
  • \(\delta_t(j)\) 始终记录当前最优路径概率，\(\psi_t(j)\) 确保路径可回溯。
隐马尔可夫模型（HMM）的维特比算法原理与计算过程 题目描述 隐马尔可夫模型（HMM）的维特比算法用于解决 解码问题 ：给定观测序列 \( O = (o_ 1, o_ 2, ..., o_ T) \) 和HMM的参数 \( \lambda = (A, B, \pi) \)（其中 \( A \) 是状态转移矩阵，\( B \) 是观测概率矩阵，\( \pi \) 是初始状态概率分布），如何找到最可能产生该观测序列的隐藏状态序列 \( Q = (q_ 1, q_ 2, ..., q_ T) \)？维特比算法通过动态规划高效求解最优路径。 解题过程 问题定义 假设隐藏状态集合为 \( \{s_ 1, s_ 2, ..., s_ N\} \)，观测集合为 \( \{v_ 1, v_ 2, ..., v_ M\} \)。 目标：计算 \( \arg\max_ {Q} P(Q \mid O, \lambda) \)，即最大化 \( P(Q, O \mid \lambda) \)（因 \( P(O) \) 固定）。 动态规划表初始化 定义两个表： 概率表 \( \delta_ t(i) \) ：在时刻 \( t \)，隐藏状态为 \( s_ i \) 的所有路径中的最大概率。 路径回溯表 \( \psi_ t(i) \) ：记录达到 \( \delta_ t(i) \) 时前一个时刻的状态。 初始化（\( t=1 \)）： \[ \delta_ 1(i) = \pi_ i \cdot b_ i(o_ 1), \quad \psi_ 1(i) = 0 \quad (1 \leq i \leq N) \] 其中 \( b_ i(o_ 1) \) 是状态 \( s_ i \) 生成观测 \( o_ 1 \) 的概率。 递推计算（\( t=2 \) 到 \( T \） 对每个时刻 \( t \) 和每个状态 \( s_ j \)： \[ \delta_ t(j) = \max_ {1 \leq i \leq N} \left[ \delta_ {t-1}(i) \cdot a_ {ij} \right] \cdot b_ j(o_ t) \] \[ \psi_ t(j) = \arg\max_ {1 \leq i \leq N} \left[ \delta_ {t-1}(i) \cdot a_ {ij} \right ] \] 这里 \( a_ {ij} \) 是从状态 \( s_ i \) 转移到 \( s_ j \) 的概率。 终止与路径回溯 最终时刻 \( T \) 的最优概率和状态： \[ P^* = \max_ {1 \leq i \leq N} \delta_ T(i), \quad q_ T^* = \arg\max_ {1 \leq i \leq N} \delta_ T(i) \] 逆序回溯最优路径（\( t=T-1 \) 到 \( 1 \)）： \[ q_ t^* = \psi_ {t+1}(q_ {t+1}^* ) \] 示例说明 假设HMM有2个状态 \( \{s_ 1, s_ 2\} \)，观测序列为 \( O = (o_ 1, o_ 2) \)。 已知参数： \[ \pi = [ 0.6, 0.4 ], \quad A = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}, \quad B = \begin{bmatrix} 0.5 & 0.5 \\ 0.3 & 0.7 \end{bmatrix} \] 观测索引：\( o_ 1 \) 对应 \( v_ 1 \)，\( o_ 2 \) 对应 \( v_ 2 \)。 计算步骤： \( t=1 \)： \( \delta_ 1(1) = 0.6 \times 0.5 = 0.3 \)，\( \delta_ 1(2) = 0.4 \times 0.3 = 0.12 \) \( t=2 \)： 对 \( s_ 1 \)： \( \delta_ 2(1) = \max(0.3 \times 0.7, 0.12 \times 0.4) \times 0.5 = \max(0.21, 0.048) \times 0.5 = 0.105 \) \( \psi_ 2(1) = \arg\max(0.21, 0.048) = s_ 1 \) 对 \( s_ 2 \)： \( \delta_ 2(2) = \max(0.3 \times 0.3, 0.12 \times 0.6) \times 0.7 = \max(0.09, 0.072) \times 0.7 = 0.063 \) \( \psi_ 2(2) = s_ 1 \) 回溯： \( q_ 2^* = \arg\max(0.105, 0.063) = s_ 1 \)，\( q_ 1^* = \psi_ 2(s_ 1) = s_ 1 \) 最优路径：\( (s_ 1, s_ 1) \)。 关键点 维特比算法通过动态规划避免穷举所有路径（复杂度从 \( O(N^T) \) 降至 \( O(T \cdot N^2) \)）。 \( \delta_ t(j) \) 始终记录当前最优路径概率，\( \psi_ t(j) \) 确保路径可回溯。