Viterbi算法的动态规划原理与路径回溯

Viterbi算法核心思想： 利用动态规划在状态网格中寻找概率最大的路径。

最优子结构： 到达t时刻状态j的最优路径必定包含到达t-1时刻某个状态i的最优路径（否则可以替换得到更优路径，矛盾）。

核心递推：

δ₁(j) = πⱼ · bⱼ(o₁)          // 初始化
δₜ(j) = max_{i=1..N} [δₜ₋₁(i) · aᵢⱼ] · bⱼ(oₜ)  // 递推
ψₜ(j) = argmax_{i=1..N} [δₜ₋₁(i) · aᵢⱼ]       // 回溯指针

• δₜ(j)：t时刻处于状态j且生成前t个观测的最大概率
• ψₜ(j)：到达δₜ(j)的前一时刻最优状态

终止： P* = max_i δ_T(i)，q*_T = argmax_i δ_T(i)

路径回溯（Backtracking）： 从T时刻的最优状态开始，反向回溯：

for t = T-1 down to 1:
    q*_t = ψ_{t+1}(q*_{t+1})

复杂度：

• 时间复杂度：O(T·N²)（每步N²个转移评估）
• 空间复杂度：O(T·N)（存储δ和ψ矩阵）

优化技巧：

• 取对数加法替代乘法（log-Viterbi），避免浮点下溢
• 稀疏矩阵加速（当转移矩阵A很稀疏时）

应用：语音识别（词解码）、基因序列标注、词性标注。