HMM中的前向法(Forward Agorithm)

普通方法(Normal Approach)：

各位应该不难想象，最普通最直接的计算的方法就是枚举所有可能的隐状态序列(S)，然后用Transition Matrix与Emission Matrix的数据，对每一个隐状态序列S求我们的目标观察序列O的一个概率。普通方法的推导如下：

根据对HMM的理解，不难写出以下的表达式：

式中，r就是枚举出来的可能隐状态序列的编号，假设一共会有N个状态出现，序列的长度为T，那么就一共会有个可能的隐状态序列S。右边第一项是在当前隐状态序列S下，目标观察序列O的发生概率（由Emission Matrix影响）。而第二项即为当前隐状态序列S的发生概率（由Transition Matrix影响）。

注意到HMM的Markov特性，即当前事件只与前一时刻时间有关，于是上式第二项可以变为：

意思即：此种隐状态组合的出现概率是由Transition Matrix里面的相应概率相乘得到。

又注意到，我们之前已经假设每个时刻(假设这个时刻为t)产生的观察符号只依赖于这个时刻所处的隐状态，因此总表达式的右边第一项可以改写为：

至此，联立上面三式可以得到：

别看上面的公式好像很长很臭，其实意思是十分明确的，这里不作过多的解释。通过这么长的一个式子，我们至少已经可以直观地看出一个问题，就是这个式子的计算复杂度的问题。显然，如果要计算上式，复杂度将会为：

它意味着，假如我们有10种可能的隐状态，序列长度为20，那么计算量将会是：(10^20) * 20 = 2.0 × 10²¹

普通方法(穷举法)：示意图