HMM 前向算法 (评估)

评估问题是给定 HMM 参数 $\lambda = (A, B, \pi)$ 与观测序列 $O = o_1 o_2 \dots o_T$,求观测概率 $P(O \mid \lambda)$。直接对状态序列求和共有 $N^T$ 条路径,不可行;前向算法用动态规划定义前向变量 $\alpha_t(j) = P(o_1 \dots o_t, q_t = j \mid \lambda)$(到 t 时刻处于状态 j 且已输出前 t 个观测的联合概率),递推

初始 $\alpha_1(j) = \pi_j b_j(o_1)$,终止 $P(O \mid \lambda) = \sum_j \alpha_T(j)$。每个时刻对 $N$ 个状态各做 $N$ 次转移求和,复杂度由枚举路径的 $O(N^T)$ 降为 $O(N^2 T)$。

语音识别、生物序列分析中的序列打分,也是 Baum-Welch E 步的组成部分;面试常考前向变量定义、与前向/维特比“求和 vs 取 max”的区别。

状态不可观测导致直接求是指数级爆炸,前向算法通过缓存子问题将似然计算降到多项式时间;代价是每步 $O(N^2)$ 的转移求和与 $O(NT)$ 存储(可滚动优化为 $O(N)$)。

写出前向算法递推 $\alpha_t(j) = [\sum_i \alpha_{t-1}(i)a_{ij}]b_j(o_t)$,并说明初值 $\alpha_1(j)$ 与终止条件 $P(O \mid \lambda)$?

为什么直接计算 $P(O \mid \lambda)$ 是指数级 $O(N^T)$?前向算法如何把复杂度降到 $O(N^2T)$?

前向算法与维特比算法有什么区别(求和 vs 取 max、各自输出什么)?

前向变量 $\alpha_t(j)$ 的概率含义是什么?它如何与后向变量 $\beta_t(j)$ 组合得到 $P(q_t = j \mid O, \lambda)$?

给定具体 HMM(如 $N=2$、$T=3$),手算 $P(O \mid \lambda)$ 的完整数值过程?