前向算法（），在隐马尔可夫模型（HMM）中，是用于计算“置信状态”的。置信状态指根据既往证据推算出的当前状态的概率分布。这个过程也被叫做“滤波”。前向算法和维特比算法紧密相关但又互不相同。
发展历史
前向算法是用来解决解码问题的算法之一。自从语音识别技术和模式识别技术发展以来，它也越来越普遍地被用在像计算生物学这样的使用HMM的领域内。
算法
整个算法的目标是计算联合概率分布 p(x_t,y_{1:t})。为了方便，我们把 x(t) 简写做 x_t，将 (y(1), y(2), ..., y(t)) 简写做 y_{1:t}。直接计算p(x_t,y_{1:t})则需要计算所有状态序列 \{x_{1:t-1}\} 的边缘分布，而它的数量和 t 成指数相关。使用这一算法，我们可以利用HMM的条件独立性质，递归地进行计算。
我们令
::\alpha_t(x_t) = p(x_t,y_{1:t}) = \sum_{x_{t-1}}p(x_t,x_{t-1},y_{1:t}).
利用链式法则来展开p(x_t,x_{t-1},y_{1:t})，我们可以得到
::\alpha_t(x_t) = \sum_{x_{t-1}}p(y_t|x_t,x_{t-1},y_{1:t-1})p(x_t|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1}).
由于 y_t 和除了 x_t 之外的一切都条件独立，而 x_t 又和 x_{t-1} 之外的一切都条件独立，因此
::\alpha_t(x_t) = p(y_t|x_t)\sum_{x_{t-1}}p(x_t|x_{t-1})\alpha_{t-1}(x_{t-1}).
这样，由于 p(y_t|x_t) 和 p(x_t|x_{t-1}) 由HMM的输出概率和状态转移概率我们可以很快计算用 \alpha_{t-1}(x_{t-1}) 计算出\alpha_t(x_t)，并且可以避免递归计算。
前向算法可以很容易地被修改来适应其他的HMM变种，比如马尔可夫跳跃线性系统。
平滑处理
为了能够使用“未来的历史”（比如我们在试图预测过去的某个时点的状态），我们可以运行后向算法，它是前向算法的一个补充。这一操作被称为平滑。 前向-后向算法对 1 计算 P(x_k | y_{1:t} )，因此使用了过去和未来的全部信息。
解码算法
为了解码最可能的序列，需要使用维特比算法。它会从过去的观测中试图推测最可能的状态序列，也即使 P(x_{0:t}|y_{0:t}) 最大化的状态序列。
参考文献
评论 (0)