隐马尔可夫模型（HMM）的维特比算法解码最优状态序列
字数 3086 2025-12-10 06:00:19

隐马尔可夫模型（HMM）的维特比算法解码最优状态序列

题目描述

假设我们已经有一个完全定义的隐马尔可夫模型（HMM），包括初始状态概率分布 π，状态转移概率矩阵 A，以及观测概率矩阵 B。现在给定一个观测序列 O = (o₁, o₂, ..., o_T)，我们的任务是：找到最有可能产生这个观测序列的隐藏状态序列 Q* = (q₁*, q₂*, ..., q_T*)。这个过程称为解码，而维特比（Viterbi）算法是解决这一问题的动态规划算法。

解题过程（循序渐进讲解）

1. 问题形式化与目标

一个HMM由以下参数定义：

  • 隐藏状态集合：S = {s₁, s₂, ..., s_N}
  • 观测符号集合：V = {v₁, v₂, ..., v_M}
  • 初始状态概率：πᵢ = P(q₁ = sᵢ), 1 ≤ i ≤ N
  • 状态转移概率：aᵢⱼ = P(qₜ₊₁ = sⱼ | qₜ = sᵢ), 1 ≤ i, j ≤ N
  • 观测概率：bᵢ(k) = P(oₜ = vₖ | qₜ = sᵢ), 1 ≤ i ≤ N, 1 ≤ k ≤ M

给定观测序列 O = (o₁, o₂, ..., o_T)，我们希望找到：
Q* = arg max_{Q} P(Q | O, λ)
其中 λ = (π, A, B) 代表模型参数。根据贝叶斯定理，P(Q|O) ∝ P(Q, O)，因此问题等价于寻找能最大化联合概率 P(Q, O) 的状态序列 Q。

2. 动态规划的核心思想

如果我们直接枚举所有可能的隐藏状态序列（共有 N^T 种），计算量是不可接受的。维特比算法的核心是利用动态规划，将“寻找全局最优路径”分解为一系列子问题。

我们定义两个关键变量：

  • δₜ(i)：在时刻 t，到达状态 sᵢ 的所有可能状态路径（q₁, q₂, ..., qₜ）中，能产生观测序列 (o₁, ..., oₜ) 的最大概率值。
    即：δₜ(i) = max_{q₁, ..., qₜ₋₁} P(q₁, ..., qₜ = sᵢ, o₁, ..., oₜ | λ)
  • ψₜ(i)：一个回溯指针，用于记录在时刻 t 达到状态 sᵢ 时，其前一个时刻（t-1）的最优状态是哪个。它存储的是状态索引。

算法思想：从第一个观测开始，逐步向后递推计算每个时刻、每个状态的最大概率路径的概率值（δ）和回溯指针（ψ）。当到达最后一个观测时，选择概率最大的状态，然后通过回溯指针向前追溯，即可得到整个最优状态序列。

3. 算法步骤详解

步骤一：初始化（t = 1）
对于每个状态 i (1 ≤ i ≤ N)：

  • δ₁(i) = πᵢ * bᵢ(o₁)
    （解释：从初始状态 i 开始，并生成第一个观测 o₁ 的概率。）
  • ψ₁(i) = 0
    （解释：因为第一帧没有前驱状态，所以指针设为0或None。）

步骤二：递推（t = 2, 3, ..., T）
对于每个时刻 t 和每个状态 j (1 ≤ j ≤ N)，我们需要计算：

  1. 计算候选概率：对于每一个可能的前一个状态 i (1 ≤ i ≤ N)，计算从前一状态 i 转移到当前状态 j，并生成当前观测 oₜ 的概率。
    候选值 = δₜ₋₁(i) * aᵢⱼ * bⱼ(oₜ)
    （解释：δₜ₋₁(i) 是到 t-1 时刻为止，以状态 i 结尾的最优路径的概率。乘以 aᵢⱼ 是转移到状态 j，再乘以 bⱼ(oₜ) 是在状态 j 下生成观测 oₜ 的概率。）
  2. 最大化：找出所有候选值中的最大值，将其赋予 δₜ(j)。
    δₜ(j) = max_{1≤i≤N} [δₜ₋₁(i) * aᵢⱼ] * bⱼ(oₜ)
  3. 记录回溯指针：记录下使得上式取得最大值的那个前一个状态 i 的索引。
    ψₜ(j) = argmax_{1≤i≤N} [δₜ₋₁(i) * aᵢⱼ]

步骤三：终止
在所有观测处理完毕后，我们在最后一个时刻 T，找到概率最大的状态。

  • P* = max_{1≤i≤N} δ_T(i)
    （P* 是最优路径的概率。）
  • q_T* = argmax_{1≤i≤N} δ_T(i)
    （q_T* 是最后一个时刻最优的状态。）

步骤四：回溯（Path Backtracking）
从最后一个时刻的最优状态开始，利用之前存储的回溯指针 ψ，向前追溯，得到完整的最优状态序列。
对于 t = T-1, T-2, ..., 1：
qₜ* = ψ_{t+1}(q*_{t+1})
最终得到的序列 (q₁*, q₂*, ..., q_T*) 就是我们要求的、最可能产生观测序列 O 的隐藏状态序列。

4. 一个简单的示例（帮助理解）

假设一个天气（隐藏状态）和活动（观测）的HMM：

  • 状态：{雨天（R），晴天（S）}
  • 观测：{散步（W），购物（S），打扫（C）}
  • 模型参数（假设已知）：
    π = [0.6, 0.4] （初始更可能是雨天）
    A = [[0.7, 0.3], [0.4, 0.6]] （行：R,S；列：R,S）
    B = [[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]] （行：R,S；列：W,S,C）

给定观测序列：O = (W, S, C) （散步，购物，打扫）

计算过程：

  1. 初始化 (t=1, o₁=W):
    δ₁(R) = 0.6 * 0.1 = 0.06
    δ₁(S) = 0.4 * 0.6 = 0.24
    ψ₁(R)=0， ψ₁(S)=0

  2. 递推 (t=2, o₂=S):
    对于状态 R：
    从 R 来：0.06 * 0.7 * 0.4 = 0.0168
    从 S 来：0.24 * 0.4 * 0.4 = 0.0384
    max = 0.0384，来自 S -> δ₂(R) = 0.0384， ψ₂(R) = S
    对于状态 S：
    从 R 来：0.06 * 0.3 * 0.3 = 0.0054
    从 S 来：0.24 * 0.6 * 0.3 = 0.0432
    max = 0.0432，来自 S -> δ₂(S) = 0.0432， ψ₂(S) = S

  3. 递推 (t=3, o₃=C):
    对于状态 R：
    从 R 来：0.0384 * 0.7 * 0.5 = 0.01344
    从 S 来：0.0432 * 0.4 * 0.5 = 0.00864
    max = 0.01344，来自 R -> δ₃(R) = 0.01344， ψ₃(R) = R
    对于状态 S：
    从 R 来：0.0384 * 0.3 * 0.1 = 0.001152
    从 S 来：0.0432 * 0.6 * 0.1 = 0.002592
    max = 0.002592，来自 S -> δ₃(S) = 0.002592， ψ₃(S) = S

  4. 终止：
    P* = max(0.01344， 0.002592) = 0.01344
    q₃* = argmax = R

  5. 回溯：
    t=3: q₃* = R
    t=2: q₂* = ψ₃(R) = R
    t=1: q₁* = ψ₂(R) = S
    最终最优状态序列为：(S, R, R) -> 晴天，雨天，雨天。

这个例子展示了维特比算法如何一步步地、高效地找到全局最优的隐藏状态序列，而不必穷举所有 2^3 = 8 种可能。其时间复杂度为 O(T * N²)，远小于穷举法的指数级复杂度。

隐马尔可夫模型（HMM）的维特比算法解码最优状态序列 题目描述 假设我们已经有一个完全定义的隐马尔可夫模型（HMM），包括初始状态概率分布 π，状态转移概率矩阵 A，以及观测概率矩阵 B。现在给定一个观测序列 O = (o₁, o₂, ..., o_ T)，我们的任务是：找到最有可能产生这个观测序列的隐藏状态序列 Q* = (q₁* , q₂* , ..., q_ T* )。这个过程称为 解码 ，而维特比（Viterbi）算法是解决这一问题的动态规划算法。 解题过程（循序渐进讲解） 1. 问题形式化与目标 一个HMM由以下参数定义： 隐藏状态集合：S = {s₁, s₂, ..., s_ N} 观测符号集合：V = {v₁, v₂, ..., v_ M} 初始状态概率：πᵢ = P(q₁ = sᵢ), 1 ≤ i ≤ N 状态转移概率：aᵢⱼ = P(qₜ₊₁ = sⱼ | qₜ = sᵢ), 1 ≤ i, j ≤ N 观测概率：bᵢ(k) = P(oₜ = vₖ | qₜ = sᵢ), 1 ≤ i ≤ N, 1 ≤ k ≤ M 给定观测序列 O = (o₁, o₂, ..., o_ T)，我们希望找到： Q* = arg max_ {Q} P(Q | O, λ) 其中 λ = (π, A, B) 代表模型参数。根据贝叶斯定理，P(Q|O) ∝ P(Q, O)，因此问题等价于寻找能 最大化联合概率 P(Q, O) 的状态序列 Q。 2. 动态规划的核心思想 如果我们直接枚举所有可能的隐藏状态序列（共有 N^T 种），计算量是不可接受的。维特比算法的核心是利用动态规划，将“寻找全局最优路径”分解为一系列子问题。 我们定义两个关键变量： δₜ(i) ：在时刻 t，到达状态 sᵢ 的所有可能状态路径（q₁, q₂, ..., qₜ）中，能产生观测序列 (o₁, ..., oₜ) 的 最大概率值 。 即：δₜ(i) = max_ {q₁, ..., qₜ₋₁} P(q₁, ..., qₜ = sᵢ, o₁, ..., oₜ | λ) ψₜ(i) ：一个 回溯指针 ，用于记录在时刻 t 达到状态 sᵢ 时，其前一个时刻（t-1）的最优状态是哪个。它存储的是状态索引。 算法思想 ：从第一个观测开始，逐步向后递推计算每个时刻、每个状态的最大概率路径的概率值（δ）和回溯指针（ψ）。当到达最后一个观测时，选择概率最大的状态，然后通过回溯指针向前追溯，即可得到整个最优状态序列。 3. 算法步骤详解 步骤一：初始化（t = 1） 对于每个状态 i (1 ≤ i ≤ N)： δ₁(i) = πᵢ * bᵢ(o₁) （解释：从初始状态 i 开始，并生成第一个观测 o₁ 的概率。） ψ₁(i) = 0 （解释：因为第一帧没有前驱状态，所以指针设为0或None。） 步骤二：递推（t = 2, 3, ..., T） 对于每个时刻 t 和每个状态 j (1 ≤ j ≤ N)，我们需要计算： 计算候选概率 ：对于每一个可能的前一个状态 i (1 ≤ i ≤ N)，计算从前一状态 i 转移到当前状态 j，并生成当前观测 oₜ 的概率。 候选值 = δₜ₋₁(i) * aᵢⱼ * bⱼ(oₜ) （解释：δₜ₋₁(i) 是到 t-1 时刻为止，以状态 i 结尾的最优路径的概率。乘以 aᵢⱼ 是转移到状态 j，再乘以 bⱼ(oₜ) 是在状态 j 下生成观测 oₜ 的概率。） 最大化 ：找出所有候选值中的最大值，将其赋予 δₜ(j)。 δₜ(j) = max_ {1≤i≤N} [ δₜ₋₁(i) * aᵢⱼ] * bⱼ(oₜ) 记录回溯指针 ：记录下使得上式取得最大值的那个前一个状态 i 的索引。 ψₜ(j) = argmax_ {1≤i≤N} [ δₜ₋₁(i) * aᵢⱼ ] 步骤三：终止 在所有观测处理完毕后，我们在最后一个时刻 T，找到概率最大的状态。 P* = max_ {1≤i≤N} δ_ T(i) （P* 是最优路径的概率。） q_ T* = argmax_ {1≤i≤N} δ_ T(i) （q_ T* 是最后一个时刻最优的状态。） 步骤四：回溯（Path Backtracking） 从最后一个时刻的最优状态开始，利用之前存储的回溯指针 ψ，向前追溯，得到完整的最优状态序列。 对于 t = T-1, T-2, ..., 1： qₜ* = ψ_ {t+1}(q*_ {t+1}) 最终得到的序列 (q₁* , q₂* , ..., q_ T* ) 就是我们要求的、最可能产生观测序列 O 的隐藏状态序列。 4. 一个简单的示例（帮助理解） 假设一个天气（隐藏状态）和活动（观测）的HMM： 状态：{雨天（R），晴天（S）} 观测：{散步（W），购物（S），打扫（C）} 模型参数（假设已知）： π = [ 0.6, 0.4 ] （初始更可能是雨天） A = [ [ 0.7, 0.3], [ 0.4, 0.6] ] （行：R,S；列：R,S） B = [ [ 0.1, 0.4, 0.5], [ 0.6, 0.3, 0.1] ] （行：R,S；列：W,S,C） 给定观测序列：O = (W, S, C) （散步，购物，打扫） 计算过程 ： 初始化 (t=1, o₁=W) : δ₁(R) = 0.6 * 0.1 = 0.06 δ₁(S) = 0.4 * 0.6 = 0.24 ψ₁(R)=0， ψ₁(S)=0 递推 (t=2, o₂=S) : 对于状态 R： 从 R 来：0.06 * 0.7 * 0.4 = 0.0168 从 S 来：0.24 * 0.4 * 0.4 = 0.0384 max = 0.0384，来自 S -> δ₂(R) = 0.0384， ψ₂(R) = S 对于状态 S： 从 R 来：0.06 * 0.3 * 0.3 = 0.0054 从 S 来：0.24 * 0.6 * 0.3 = 0.0432 max = 0.0432，来自 S -> δ₂(S) = 0.0432， ψ₂(S) = S 递推 (t=3, o₃=C) : 对于状态 R： 从 R 来：0.0384 * 0.7 * 0.5 = 0.01344 从 S 来：0.0432 * 0.4 * 0.5 = 0.00864 max = 0.01344，来自 R -> δ₃(R) = 0.01344， ψ₃(R) = R 对于状态 S： 从 R 来：0.0384 * 0.3 * 0.1 = 0.001152 从 S 来：0.0432 * 0.6 * 0.1 = 0.002592 max = 0.002592，来自 S -> δ₃(S) = 0.002592， ψ₃(S) = S 终止 ： P* = max(0.01344， 0.002592) = 0.01344 q₃* = argmax = R 回溯 ： t=3: q₃* = R t=2: q₂* = ψ₃(R) = R t=1: q₁* = ψ₂(R) = S 最终最优状态序列为：(S, R, R) -> 晴天，雨天，雨天。 这个例子展示了维特比算法如何一步步地、高效地找到全局最优的隐藏状态序列，而不必穷举所有 2^3 = 8 种可能。其时间复杂度为 O(T * N²)，远小于穷举法的指数级复杂度。