HMM 完整推导：前向算法、维特比解码与 Baum-Welch EM

📐 隐马尔可夫模型（HMM）——序列标注的数学基础

HMM 是这个时代词性标注（POS tagging）的主力模型。一个 HMM 由五元组 $\lambda = (S, V, \pi, A, B)$ 定义：

• $S = \{s_1, \ldots, s_K\}$：隐状态集合（如词性标签：N, V, Det, Adj, …）
• $V = \{v_1, \ldots, v_M\}$：观测符号集合（词汇表）
• $\pi_i = P(t_1 = s_i)$：初始状态概率
• $A_{ij} = P(t_{n+1} = s_j | t_n = s_i)$：转移概率矩阵（$K \times K$）
• $B_j(w) = P(w | t = s_j)$：发射概率（每个状态对词汇表的分布）

联合概率（一阶马尔可夫假设 + 输出独立假设）： $P(\mathbf{w}, \mathbf{t}) = \pi_{t_1} \cdot \prod_{i=1}^{T} B_{t_i}(w_i) \cdot \prod_{i=2}^{T} A_{t_{i-1}, t_i}$

HMM 的三个核心问题：

📐 前向算法——高效计算观测序列概率

问题：直接枚举所有 $K^T$ 条路径求 $P(\mathbf{w})$ 是不可行的。前向算法用动态规划将复杂度降到 $O(TK^2)$。

定义前向变量：$\alpha_t(j) = P(w_1, w_2, \ldots, w_t, t_t = s_j | \lambda)$

第 1 步：初始化（$t=1$） $\alpha_1(j) = \pi_j \cdot B_j(w_1), \quad j = 1, \ldots, K$

直觉：时刻 1 处于状态 $j$ 并发射 $w_1$ 的联合概率

第 2 步：递推（$t = 2, \ldots, T$） $\alpha_t(j) = \left[\sum_{i=1}^{K} \alpha_{t-1}(i) \cdot A_{ij}\right] \cdot B_j(w_t)$

把所有可能的前驱状态 $i$ 的概率累加后，乘以当前发射概率

第 3 步：终止 $P(\mathbf{w} | \lambda) = \sum_{j=1}^{K} \alpha_T(j)$

后向算法类似，定义 $\beta_t(i) = P(w_{t+1}, \ldots, w_T | t_t = s_i, \lambda)$，从 $T$ 向 $1$ 递推。前向和后向变量共同用于 Baum-Welch 参数学习。

📐 维特比算法——最优路径解码

目标：找到使 $P(\mathbf{t} | \mathbf{w})$ 最大的标注序列。

定义维特比变量：$\delta_t(j) = \max_{t_1, \ldots, t_{t-1}} P(t_1, \ldots, t_{t-1}, t_t = s_j, w_1, \ldots, w_t)$

第 1 步：初始化 $\delta_1(j) = \pi_j \cdot B_j(w_1), \quad \psi_1(j) = 0$

第 2 步：递推（与前向唯一区别：$\sum \to \max$） $\delta_t(j) = \max_{1 \le i \le K} \left[\delta_{t-1}(i) \cdot A_{ij}\right] \cdot B_j(w_t)$ $\psi_t(j) = \arg\max_{1 \le i \le K} \left[\delta_{t-1}(i) \cdot A_{ij}\right]$

$\psi_t(j)$ 记录回溯指针：状态 $j$ 在时刻 $t$ 的最优前驱

第 3 步：终止 + 回溯 $t_T^* = \arg\max_j \delta_T(j), \quad t_t^* = \psi_{t+1}(t_{t+1}^*) \quad (t = T{-}1, \ldots, 1)$

实践注意：实际实现中使用 log 概率避免浮点下溢：$\log\delta_t(j) = \max_i[\log\delta_{t-1}(i) + \log A_{ij}] + \log B_j(w_t)$

📐 Baum-Welch 算法（EM）——无监督参数学习

当没有标注数据时（只有句子，没有词性标签），用 EM 算法迭代估计 HMM 参数。

定义辅助变量：

$\xi_t(i,j) = P(t_t = s_i, t_{t+1} = s_j | \mathbf{w}, \lambda) = \frac{\alpha_t(i) \cdot A_{ij} \cdot B_j(w_{t+1}) \cdot \beta_{t+1}(j)}{P(\mathbf{w}|\lambda)}$

$\gamma_t(i) = P(t_t = s_i | \mathbf{w}, \lambda) = \sum_{j=1}^{K} \xi_t(i,j) = \frac{\alpha_t(i) \cdot \beta_t(i)}{P(\mathbf{w}|\lambda)}$

E 步：用当前参数计算 $\xi_t(i,j)$ 和 $\gamma_t(i)$

M 步：重估参数（最大化期望似然）

$\hat{\pi}_i = \gamma_1(i) \qquad \text{（初始状态概率）}$

$\hat{A}_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)} \qquad \text{（转移概率：从 $i$ 转到 $j$ 的期望次数 / 从 $i$ 出发的总次数）}$

$\hat{B}_j(v_k) = \frac{\sum_{t=1, w_t=v_k}^{T} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)} \qquad \text{（发射概率：在状态 $j$ 发射 $v_k$ 的期望次数 / 处于 $j$ 的总次数）}$

收敛保证：EM 保证每次迭代 $P(\mathbf{w}|\lambda)$ 单调不减，但只收敛到局部最优——初始化很重要。