HMM 维特比解码

解码问题是给定 $\lambda = (A, B, \pi)$ 与观测 $O$,求最可能的隐藏状态序列 $q^* = \arg\max_q P(q \mid O, \lambda)$。维特比算法用动态规划维护 $\delta_t(j)$ — 到时刻 t 处于状态 j 且输出前 t 个观测的所有路径中的最大概率,递推

同时用前驱表 $\psi_t(j) = \arg\max_i \delta_{t-1}(i) a_{ij}$ 记录最优路径中 t−1 时刻的状态;初值 $\delta_1(j) = \pi_j b_j(o_1)$,终止取 $P^* = \max_j \delta_T(j)$,再从 $\psi_T$ 沿表回溯(backtracking)得到整条最优状态序列。复杂度 $O(N^2 T)$,与前向算法同阶。

词性标注、命名实体识别、语音与手写识别中的最优路径搜索;面试常考维特比与前向算法对比、与贪心/束搜索的区别。

穷举 $N^T$ 条路径不可行;维特比与前向算法同样用 DP 缓存,但把“求和”换成“取 max”并保存前驱以重建轨迹,保证全局最优而非贪心逐点最优;代价是每步 $O(N^2)$ 比较,且必须保留完整 $\psi$ 表用于回溯(不能像评估那样滚动丢弃)。

检验攻克程度：针对「HMM 维特比解码」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。