前向-后向算法在隐马尔可夫模型（HMM）前向概率与后向概率递推计算中的应用

字数 3150 2025-12-06 05:59:01

前向-后向算法在隐马尔可夫模型（HMM）前向概率与后向概率递推计算中的应用

1. 问题背景

隐马尔可夫模型（HMM）常用于序列建模，比如语音识别、自然语言处理中的词性标注。HMM 的参数为：

状态集合 \(Q = \{1,2,\dots,N\}\)，观测集合 \(V = \{v_1,\dots,v_M\}\)
初始状态概率 \(\pi_i = P(z_1 = i)\)
状态转移概率 \(a_{ij} = P(z_{t+1}=j \mid z_t=i)\)
观测发射概率 \(b_j(k) = P(o_t = v_k \mid z_t = j)\)

已知模型参数 \(\lambda = (\pi, A, B)\) 和观测序列 \(O = (o_1, o_2, \dots, o_T)\)，我们要计算 观测序列的概率 \(P(O \mid \lambda)\)。
直接计算需对所有状态路径求和，复杂度 \(O(N^T)\) 不可行。前向-后向算法通过动态规划，在 \(O(N^2 T)\) 时间内计算。

2. 前向概率计算

定义：前向概率

\[\alpha_t(i) = P(o_1, o_2, \dots, o_t, z_t = i \mid \lambda) \]

即到时刻 \(t\) 为止的观测序列，且 \(t\) 时刻状态为 \(i\) 的联合概率。

递推步骤：

步骤 1：初始化（\(t=1\)）

\[\alpha_1(i) = \pi_i \cdot b_i(o_1), \quad i=1,\dots,N \]

\(\pi_i\) 是初始状态概率
\(b_i(o_1)\) 是状态 \(i\) 下观测到 \(o_1\) 的概率

步骤 2：递推（\(t=1,2,\dots,T-1\)）

从 \(t\) 到 \(t+1\) 时，考虑 \(t\) 时刻的所有可能状态 \(j\) 转移到 \(t+1\) 时刻的状态 \(i\)，并观测到 \(o_{t+1}\)：

\[\alpha_{t+1}(i) = \left[ \sum_{j=1}^N \alpha_t(j) a_{ji} \right] b_i(o_{t+1}), \quad i=1,\dots,N \]

括号内：对 \(t\) 时刻状态 \(j\) 的前向概率 \(\alpha_t(j)\) 乘转移概率 \(a_{ji}\)，求和得到 \(t+1\) 时刻状态 \(i\) 的“预测概率”
再乘发射概率 \(b_i(o_{t+1})\) 得到 \(\alpha_{t+1}(i)\)

步骤 3：终止

观测序列概率为：

\[P(O \mid \lambda) = \sum_{i=1}^N \alpha_T(i) \]

因为 \(T\) 时刻状态为任意 \(i\) 且已完成所有观测。

3. 后向概率计算

定义：后向概率

\[\beta_t(i) = P(o_{t+1}, o_{t+2}, \dots, o_T \mid z_t = i, \lambda) \]

即已知 \(t\) 时刻状态为 \(i\) 的条件下，从 \(t+1\) 到 \(T\) 的观测序列的条件概率。

递推步骤：

步骤 1：初始化（\(t=T\)）

定义边界条件：

\[\beta_T(i) = 1, \quad i=1,\dots,N \]

（因为 \(T\) 时刻之后没有观测，概率为 1）

步骤 2：递推（\(t=T-1,\dots,1\)）

从 \(t+1\) 到 \(t\) 反向递推：

\[\beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j), \quad i=1,\dots,N \]

解释：在 \(t\) 时刻状态 \(i\) 下，转移到 \(t+1\) 时刻状态 \(j\) 的概率为 \(a_{ij}\)，且在 \(j\) 下观测到 \(o_{t+1}\) 的概率为 \(b_j(o_{t+1})\)，之后（从 \(t+1\) 到 \(T\) ）的后向概率为 \(\beta_{t+1}(j)\)
对所有可能的 \(j\) 求和

步骤 3：用后向概率计算 \(P(O \mid \lambda)\)

在 \(t=1\) 时：

\[P(O \mid \lambda) = \sum_{i=1}^N \pi_i b_i(o_1) \beta_1(i) \]

这个结果应与前向算法一致。

4. 统一表示观测序列概率

用前向和后向概率组合可得：

\[P(O \mid \lambda) = \sum_{i=1}^N \alpha_t(i) \beta_t(i), \quad \text{对任意 } t \]

验证：取 \(t=1\) 得到后向公式，取 \(t=T\) 得到前向公式。

5. 前向-后向算法的其他用途

这个算法不仅计算 \(P(O \mid \lambda)\)，还用于：

（1）计算状态概率

给定观测序列，\(t\) 时刻状态为 \(i\) 的概率：

\[\gamma_t(i) = P(z_t=i \mid O, \lambda) = \frac{\alpha_t(i) \beta_t(i)}{P(O \mid \lambda)} \]

分子：通过 \(i\) 的所有路径概率（前向后向结合）
分母：所有路径概率（用前向算法求出或 \(\sum_i \alpha_t(i)\beta_t(i)\)）

（2）计算转移概率

\(t\) 时刻状态 \(i\)，\(t+1\) 时刻状态 \(j\) 的概率：

\[\xi_t(i,j) = \frac{\alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)}{P(O \mid \lambda)} \]

解释：

\(\alpha_t(i)\)：到 \(t\) 时刻状态 \(i\) 的概率
乘 \(a_{ij}\) 转移到 \(j\)，乘 \(b_j(o_{t+1})\) 得到 \(t+1\) 时刻观测
乘 \(\beta_{t+1}(j)\) 得到后面观测的概率
除以 \(P(O \mid \lambda)\) 得条件概率

这些 \(\gamma_t(i)\) 和 \(\xi_t(i,j)\) 是 Baum-Welch（EM）算法 中 E 步的核心，用于重新估计 HMM 参数。

6. 总结

前向算法：从前向后动态规划，计算观测序列概率
后向算法：从后向前动态规划，与前向对称
结合前向后向：可计算任意时刻状态分布、状态转移分布
复杂度：每个时刻对 \(N\) 个状态，每个状态考虑 \(N\) 个转移，复杂度 \(O(N^2 T)\)，远优于直接枚举 \(O(N^T)\)

这个算法是 HMM 三大基本问题（评估、解码、学习）中评估问题的核心解法，也是学习问题中 EM 算法的基础。

前向-后向算法在隐马尔可夫模型（HMM）前向概率与后向概率递推计算中的应用 1. 问题背景隐马尔可夫模型（HMM）常用于序列建模，比如语音识别、自然语言处理中的词性标注。HMM 的参数为：状态集合 \( Q = \{1,2,\dots,N\} \)，观测集合 \( V = \{v_ 1,\dots,v_ M\} \) 初始状态概率 \( \pi_ i = P(z_ 1 = i) \) 状态转移概率 \( a_ {ij} = P(z_ {t+1}=j \mid z_ t=i) \) 观测发射概率 \( b_ j(k) = P(o_ t = v_ k \mid z_ t = j) \) 已知模型参数 \( \lambda = (\pi, A, B) \) 和观测序列 \( O = (o_ 1, o_ 2, \dots, o_ T) \)，我们要计算观测序列的概率 \( P(O \mid \lambda) \)。直接计算需对所有状态路径求和，复杂度 \( O(N^T) \) 不可行。前向-后向算法通过动态规划，在 \( O(N^2 T) \) 时间内计算。 2. 前向概率计算定义：前向概率 \[ \alpha_ t(i) = P(o_ 1, o_ 2, \dots, o_ t, z_ t = i \mid \lambda) \] 即到时刻 \( t \) 为止的观测序列，且 \( t \) 时刻状态为 \( i \) 的联合概率。递推步骤：步骤 1：初始化（\( t=1 \)） \[ \alpha_ 1(i) = \pi_ i \cdot b_ i(o_ 1), \quad i=1,\dots,N \] \( \pi_ i \) 是初始状态概率 \( b_ i(o_ 1) \) 是状态 \( i \) 下观测到 \( o_ 1 \) 的概率步骤 2：递推（\( t=1,2,\dots,T-1 \)）从 \( t \) 到 \( t+1 \) 时，考虑 \( t \) 时刻的所有可能状态 \( j \) 转移到 \( t+1 \) 时刻的状态 \( i \)，并观测到 \( o_ {t+1} \)： \[ \alpha_ {t+1}(i) = \left[ \sum_ {j=1}^N \alpha_ t(j) a_ {ji} \right] b_ i(o_ {t+1}), \quad i=1,\dots,N \] 括号内：对 \( t \) 时刻状态 \( j \) 的前向概率 \( \alpha_ t(j) \) 乘转移概率 \( a_ {ji} \)，求和得到 \( t+1 \) 时刻状态 \( i \) 的“预测概率” 再乘发射概率 \( b_ i(o_ {t+1}) \) 得到 \( \alpha_ {t+1}(i) \) 步骤 3：终止观测序列概率为： \[ P(O \mid \lambda) = \sum_ {i=1}^N \alpha_ T(i) \] 因为 \( T \) 时刻状态为任意 \( i \) 且已完成所有观测。 3. 后向概率计算定义：后向概率 \[ \beta_ t(i) = P(o_ {t+1}, o_ {t+2}, \dots, o_ T \mid z_ t = i, \lambda) \] 即已知 \( t \) 时刻状态为 \( i \) 的条件下，从 \( t+1 \) 到 \( T \) 的观测序列的条件概率。递推步骤：步骤 1：初始化（\( t=T \)）定义边界条件： \[ \beta_ T(i) = 1, \quad i=1,\dots,N \] （因为 \( T \) 时刻之后没有观测，概率为 1）步骤 2：递推（\( t=T-1,\dots,1 \)）从 \( t+1 \) 到 \( t \) 反向递推： \[ \beta_ t(i) = \sum_ {j=1}^N a_ {ij} b_ j(o_ {t+1}) \beta_ {t+1}(j), \quad i=1,\dots,N \] 解释：在 \( t \) 时刻状态 \( i \) 下，转移到 \( t+1 \) 时刻状态 \( j \) 的概率为 \( a_ {ij} \)，且在 \( j \) 下观测到 \( o_ {t+1} \) 的概率为 \( b_ j(o_ {t+1}) \)，之后（从 \( t+1 \) 到 \( T \) ）的后向概率为 \( \beta_ {t+1}(j) \) 对所有可能的 \( j \) 求和步骤 3：用后向概率计算 \( P(O \mid \lambda) \) 在 \( t=1 \) 时： \[ P(O \mid \lambda) = \sum_ {i=1}^N \pi_ i b_ i(o_ 1) \beta_ 1(i) \] 这个结果应与前向算法一致。 4. 统一表示观测序列概率用前向和后向概率组合可得： \[ P(O \mid \lambda) = \sum_ {i=1}^N \alpha_ t(i) \beta_ t(i), \quad \text{对任意 } t \] 验证：取 \( t=1 \) 得到后向公式，取 \( t=T \) 得到前向公式。 5. 前向-后向算法的其他用途这个算法不仅计算 \( P(O \mid \lambda) \)，还用于：（1）计算状态概率给定观测序列，\( t \) 时刻状态为 \( i \) 的概率： \[ \gamma_ t(i) = P(z_ t=i \mid O, \lambda) = \frac{\alpha_ t(i) \beta_ t(i)}{P(O \mid \lambda)} \] 分子：通过 \( i \) 的所有路径概率（前向后向结合）分母：所有路径概率（用前向算法求出或 \( \sum_ i \alpha_ t(i)\beta_ t(i) \)）（2）计算转移概率 \( t \) 时刻状态 \( i \)，\( t+1 \) 时刻状态 \( j \) 的概率： \[ \xi_ t(i,j) = \frac{\alpha_ t(i) a_ {ij} b_ j(o_ {t+1}) \beta_ {t+1}(j)}{P(O \mid \lambda)} \] 解释： \( \alpha_ t(i) \)：到 \( t \) 时刻状态 \( i \) 的概率乘 \( a_ {ij} \) 转移到 \( j \)，乘 \( b_ j(o_ {t+1}) \) 得到 \( t+1 \) 时刻观测乘 \( \beta_ {t+1}(j) \) 得到后面观测的概率除以 \( P(O \mid \lambda) \) 得条件概率这些 \( \gamma_ t(i) \) 和 \( \xi_ t(i,j) \) 是 Baum-Welch（EM）算法中 E 步的核心，用于重新估计 HMM 参数。 6. 总结前向算法：从前向后动态规划，计算观测序列概率后向算法：从后向前动态规划，与前向对称结合前向后向：可计算任意时刻状态分布、状态转移分布复杂度：每个时刻对 \( N \) 个状态，每个状态考虑 \( N \) 个转移，复杂度 \( O(N^2 T) \)，远优于直接枚举 \( O(N^T) \) 这个算法是 HMM 三大基本问题（评估、解码、学习）中评估问题的核心解法，也是学习问题中 EM 算法的基础。