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$ 表用于回溯(不能像评估那样滚动丢弃)。

写出维特比递推 $\delta_t(j) = \max_i[\delta_{t-1}(i)a_{ij}]b_j(o_t)$ 及回溯过程,复杂度是多少?

维特比与前向算法的区别?(求和 vs 取 max、各自输出什么、为什么需要前驱表 $\psi$)

为什么维特比能保证全局最优?与贪心逐点选择、束搜索有何不同?

给定具体例子(如 $N=2$、$T=3$),手推最优状态路径并说明回溯如何工作?

维特比与 CRF/MEMM 推理有何联系(推断阶段共用同一 DP,只是势函数不同)?