本文共 2101 字，大约阅读时间需要 7 分钟。
HMM（隐藏马尔可夫链模型）是一种常用的概率模型，广泛应用于语音识别、机器翻译等领域。模型的核心参数包括初始状态概率向量 π、状态转移概率矩阵 A 和发射概率矩阵 B。通过 EM 算法，我们可以在已知观测数据 X 的情况下，最大化似然函数，求解 HMM 模型的参数 θ = (π, A, B)。
在上篇文章中，我们讨论了在上帝视角下（即已知隐变量 Z）如何通过简单的词频统计和归一化来求解 HMM 模型参数。这是因为当隐变量 Z 已知时，参数 θ 可以直接通过统计 X 和 Z 的联合概率来计算。
然而，现实中我们只能通过观测数据 X 来估计隐变量 Z。为了解决这一问题，我们引入了 F/B 算法（Forward/Backward 算法），其核心思想是通过动态规划来计算 Z 的后向概率和前向概率，从而实现模型参数的求解。
Forward 算法的目标是计算在已知观测数据 X 的情况下，隐变量 Z 的条件概率 p(z_k | x_{1..k})。具体来说，Forward 算法通过动态规划的思想，将大的求解问题拆解为更小的问题来处理。
假设观测数据 X 由 n 个样本组成，每个样本可以表示为 x_1, x_2, ..., x_n。而隐变量 Z 则由 z_1, z_2, ..., z_n 组成。根据 HMM 模型的定义，Z 发射到 X 的概率矩阵为 B，状态转移概率矩阵为 A。
Forward 算法的核心公式为：[ p(z_k, x_{1..k}) = p(z_k, x_{1..k}) ]其中，X_{1..k} 表示前 k 个观测值。
为了简化计算，我们可以将上述公式拆解为：[ p(z_k, x_{1..k}) = \sum_{z_{k-1}} p(z_{k-1}, x_{1..k-1}) p(z_k | z_{k-1}, x_{1..k-1}) p(x_k | z_k, z_{k-1}, x_{1..k-1}) ]
在动态规划的框架下，我们可以将问题拆解为：[ p(z_k, x_{1..k}) = \sum_{z_{k-1}} p(z_{k-1}, x_{1..k-1}) p(z_k | z_{k-1}) p(x_k | z_k) ]
这里，p(z_k | z_{k-1}) 是状态转移矩阵 A，p(x_k | z_k) 是发射概率矩阵 B。通过动态规划，我们可以逐步计算 p(z_k, x_{1..k})，并将其保存下来以便后续计算使用。
Backward 算法则是用于计算隐变量 Z 的后向概率 p(x_{k+1..n} | z_k)。其核心思想与 Forward 算法类似，但计算方向相反。
Backward 算法的核心公式为：[ p(x_{k+1..n} | z_k) = \sum_{z_{k+1}} p(z_{k+1} | z_k) p(x_{k+1} | z_{k+1}, z_k) p(x_{k+2..n} | z_{k+1}, z_k, x_{k+1}) ]
同样地，我们可以将上述公式拆解为：[ p(x_{k+1..n} | z_k) = \sum_{z_{k+1}} p(z_{k+1} | z_k) p(x_{k+1} | z_{k+1}) p(x_{k+2..n} | z_{k+1}) ]
这里，p(z_{k+1} | z_k) 是状态转移矩阵 A，p(x_{k+1} | z_{k+1}) 是发射概率矩阵 B，而 p(x_{k+2..n} | z_{k+1}) 则是动态规划的结果。
通过 Forward 和 Backward 算法，我们可以逐步计算隐变量 Z 的后向概率和前向概率。具体来说：
通过对 Forward 和 Backward Pass 的结合，我们可以计算出隐变量 Z 的后验概率 p(z_k | x)，从而完成 HMM 模型参数的求解。
动态规划的核心思想是将大的问题拆解为更小的问题来处理。通过保存子问题的解，我们可以避免重复计算，从而显著降低计算复杂度。具体来说，Forward 和 Backward 算法的时间复杂度均为 O(n * m^2)，其中 n 是观测数据的长度，m 是隐变量的数量。
通过 EM 算法，我们可以在已知观测数据 X 的情况下，最大化似然函数，求解 HMM 模型的参数 θ = (π, A, B)。而核心的实现工具是 F/B 算法，其通过 Forward 和 Backward Pass 的结合，利用动态规划的思想，有效地解决了隐变量 Z 的求解问题。这一算法不仅适用于 HMM 模型，还可以扩展到更广泛的马尔可夫模型中。
转载地址：http://btokz.baihongyu.com/