Viterbi 算法是一种动态规划（Dynamic Programming）算法，主要用于在隐马尔可夫模型（Hidden Markov Model, HMM）中寻找最可能的隐藏状态序列（即最优路径），使得该序列能够生成观测到的输出序列。

一、背景：隐马尔可夫模型（HMM）

HMM 包含以下要素：

  • 状态集合 \(S = \{s_1, s_2, ..., s_N\}\)：隐藏的、不可直接观测的状态。
  • 观测集合 $ O = {o_1, o_2, ..., o_T}$：可以观测到的输出序列（长度为 T）。
  • 初始状态概率 $ \pi = \{\pi_i\} $：系统在时刻 1 处于状态 $ s_i $ 的概率。
  • 状态转移概率矩阵 $ A = [a_{ij}] $：从状态 $ s_i $ 转移到 $ s_j $ 的概率。
  • 观测概率矩阵（发射概率）$ B = [b_j(k)] $：在状态 $ s_j $ 下观测到 $ o_k $ 的概率。

二、Viterbi 算法目标

给定观测序列 $ O = (o_1, o_2, ..., o_T) $ 和 HMM 参数 $ (\pi, A, B) $，求最可能的隐藏状态路径 \[ Q^* = (q_1^*, q_2^*, ..., q_T^*) \]，使得：

\[ Q^* = \arg\max_{Q} P(Q | O; \lambda) \]

其中 $ = (\pi, A, B) $ 是 HMM 的参数。

由于直接枚举所有可能路径（共 $ N^T $ 条）计算量过大，Viterbi 算法通过动态规划在 $ O(N^2 T) $ 时间内高效求解。

三、Viterbi 算法步骤

1. 初始化（t = 1）

对每个状态 $ s_i （ i = 1, ..., N $）：

\[ \delta_1(i) = \pi_i \cdot b_i(o_1) \] \[ \psi_1(i) = 0 \]

  • $ \delta_t(i) $：时刻 t 时，以状态 $ s_i $ 结尾的最大路径概率。
  • $ \psi_t(i) $：记录时刻 t 时，使路径概率最大的前一状态（用于回溯）。

2. 递推（t = 2 到 T）

对每个时刻 $ t = 2, ..., T $，对每个状态 $ s_j $：

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

3. 终止

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

4. 回溯（路径重构）

对 $ t = T-1, T-2, ..., 1 $：

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

最终得到最优状态序列 \[ Q^* = (q_1^*, q_2^*, ..., q_T^*) \]

四、举例说明（简化）

假设：

  • 状态：Rainy (R), Sunny (S)
  • 观测：Walk, Shop, Clean
  • 观测序列：[Walk, Shop, Clean]

给定 HMM 参数后，Viterbi 算法会计算每一步每个状态的最大概率路径，并记录回溯指针，最终输出最可能的天气序列，例如 [Sunny, Rainy, Rainy]。

五、应用场景

  • 语音识别（将声学信号映射到音素序列）
  • 自然语言处理（词性标注、命名实体识别）
  • 生物信息学（基因序列分析）
  • 通信（解卷积、纠错码）

六、注意事项

  • Viterbi 找的是最可能的单一路径，不是所有路径的期望或平均。

  • 若概率值非常小，建议使用对数概率避免浮点下溢：

    将乘法转为加法： \[ \log \delta_t(j) = \max_i \left[ \log \delta_{t-1}(i) + \log a_{ij} \right] + \log b_j(o_t) \]

下面是一个 Python 实现 Viterbi 算法 的完整示例，适用于隐马尔可夫模型（HMM）。

我们将用一个经典的例子：天气预测（隐藏状态）和人的活动（观测值）。

🌦️ 问题设定

  • 隐藏状态（Hidden States）：['Rainy', 'Sunny']
  • 观测值（Observations）：['walk', 'shop', 'clean']
  • 观测序列：['walk', 'shop', 'clean']
  • 目标：找出最可能的天气序列（如 ['Sunny', 'Rainy', 'Rainy']）

🔧 HMM 参数定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 隐藏状态
states = ['Rainy', 'Sunny']

# 观测值
observations = ['walk', 'shop', 'clean']

# 初始概率 π
start_probability = {
    'Rainy': 0.6,
    'Sunny': 0.4
}

# 状态转移概率 A
transition_probability = {
    'Rainy': {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny': {'Rainy': 0.4, 'Sunny': 0.6}
}

# 发射概率（观测概率）B
emission_probability = {
    'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}
}

✅ Viterbi 算法实现（使用对数概率避免下溢）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import math

def viterbi(obs, states, start_p, trans_p, emit_p):
    """
    Viterbi 算法实现
    :param obs: 观测序列，如 ['walk', 'shop', 'clean']
    :param states: 隐藏状态列表
    :param start_p: 初始状态概率字典
    :param trans_p: 状态转移概率字典
    :param emit_p: 发射（观测）概率字典
    :return: 最优状态路径（列表）
    """
    T = len(obs)
    N = len(states)

    # 使用对数概率避免浮点下溢
    # delta[t][state] = log(最大路径概率)
    delta = [{}]
    psi = [{}]

    # 初始化 t=0
    for s in states:
        delta[0][s] = math.log(start_p[s]) + math.log(emit_p[s][obs[0]])
        psi[0][s] = None

    # 递推 t=1 到 T-1
    for t in range(1, T):
        delta.append({})
        psi.append({})
        for s in states:
            max_prob = float('-inf')
            best_prev = None
            for prev_s in states:
                prob = delta[t-1][prev_s] + math.log(trans_p[prev_s][s]) + math.log(emit_p[s][obs[t]])
                if prob > max_prob:
                    max_prob = prob
                    best_prev = prev_s
            delta[t][s] = max_prob
            psi[t][s] = best_prev

    # 终止：找最后一个时刻最可能的状态
    best_path_prob = float('-inf')
    best_last_state = None
    for s in states:
        if delta[T-1][s] > best_path_prob:
            best_path_prob = delta[T-1][s]
            best_last_state = s

    # 回溯路径
    best_path = [best_last_state]
    for t in range(T-1, 0, -1):
        best_last_state = psi[t][best_last_state]
        best_path.insert(0, best_last_state)

    return best_path

🧪 使用示例

1
2
3
4
5
if __name__ == "__main__":
    obs_seq = ['walk', 'shop', 'clean']
    result = viterbi(obs_seq, states, start_probability, transition_probability, emission_probability)
    print("观测序列:", obs_seq)
    print("最可能的隐藏状态序列:", result)

输出示例： 

1
2
观测序列: ['walk', 'shop', 'clean']
最可能的隐藏状态序列: ['Sunny', 'Rainy', 'Rainy']