前向-后向算法是一种基础的动态规划技术，用于隐马尔可夫模型（HMM）及相关概率序列模型。它计算给定观测序列下每个隐状态的后验边际分布，从而实现高效推断和参数估计。该算法是经典机器学习的基石，并在语音识别、生物信息学和自然语言处理等现代应用中仍具相关性。
该算法于20世纪60年代末至70年代初发展起来，由Leonard Baum及其同事在一系列关于马尔可夫链概率函数统计估计的论文中正式提出。它常与维特比算法一起介绍，后者寻找最可能的隐状态序列，而前向-后向算法则计算每个时间步上每个单独状态的概率。该算法分两次遍历进行：前向遍历计算观测到给定时间点为止的序列并以特定状态结束的概率，后向遍历计算给定起始状态下观测到序列剩余部分的概率。将这两组概率结合即可得到所需的后验边际分布。
数学表述
考虑一个具有隐状态 \( S = \{s_1, s_2, \ldots, s_N\} \)、转移概率 \( a_{ij} = P(s_j | s_i) \)、发射概率 \( b_j(o_t) = P(o_t | s_j) \) 以及初始状态分布 \( \pi_i = P(s_i) \) 的HMM。对于观测序列 \( O = (o_1, o_2, \ldots, o_T) \)，前向变量 \( \alpha_t(i) \) 定义为截至时间 \( t \) 的部分观测序列且在时间 \( t \) 处于状态 \( s_i \) 的概率：\( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \)，其中 \( \lambda \) 表示模型参数。前向遍历初始化 \( \alpha_1(i) = \pi_i b_i(o_1) \)，并递归计算 \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \)。
后向变量 \( \beta_t(i) \) 定义为给定时间 \( t \) 的状态为 \( s_i \) 时，从时间 \( t+1 \) 到 \( T \) 的观测序列的概率：\( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \)。后向遍历初始化 \( \beta_T(i) = 1 \) 对所有 \( i \)，并递归计算 \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \)。在时间 \( t \) 处于状态 \( s_i \) 的后验概率则为 \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \)。
在序列建模中的应用
该算法广泛用于通过Baum-Welch算法训练HMM，这是期望最大化的一种实例。在E步中，前向-后向算法计算期望充分统计量，例如状态间转移的期望次数和每个观测符号发射的期望次数。这些统计量随后在M步中用于更新模型参数。这一迭代过程收敛到似然函数的局部最大值。
在语音识别中，带有前向-后向训练的HMM从20世纪70年代到21世纪初是声学建模的主导方法，之后在很大程度上被深度学习方法所取代。在生物信息学中，该算法用于基因预测和分析蛋白质序列，其中HMM对保守基序进行建模。在自然语言处理中，它出现在词性标注以及使用结构化输出层训练序列到序列模型中。
与现代机器学习的关系
尽管前向-后向算法是一种经典技术，但其原理在现代机器学习中持续存在。前向遍历类似于循环神经网络中的信息传播，后向遍历类似于误差信号的反向传播，尽管数学目标不同。在用于序列标注的神经网络中，例如双向LSTM，前向和后向隐藏状态被结合以捕获两个方向的上下文，这与该算法的前向和后向变量相呼应。此外，该算法对动态规划的高效使用启发了基于transformer的模型中的类似技术，例如某些形式的结构化预测中使用的前向-后向算法，以及训练大型语言模型用于命名实体识别等任务。
该算法还与束搜索的概念相关，两者都管理序列问题中的计算复杂度，但目的不同：束搜索近似最可能的序列，而前向-后向计算精确的边际概率。在概率图模型中，前向-后向算法是链图上和积算法的特例，并通过置信传播推广到树结构模型。
计算复杂度与变体
前向-后向算法的时间复杂度为 \( O(T N^2) \)，空间复杂度为 \( O(T N) \)，其中 \( T \) 是序列长度，\( N \) 是隐状态数量。这种效率使其适用于具有数千个时间步和数百个状态的序列。对于大型状态空间，使用前向滤波后向采样等近似方法用于粒子滤波和蒙特卡洛方法。在在线设置中，仅前向算法可用于滤波，而后向遍历需要整个序列，因此是离线的。变体包括缩放前向-后向算法以避免数值下溢，这在处理长序列和小概率时很常见。
参见
- hidden-markov-model
- 维特比算法
- Baum-Welch算法
- dynamic-programming
- sequence-modeling