HMM中的前向法(Forward Agorithm)

可行的替代算法 – 前向法(Forward Algorithm)：

我们在面对一种所谓的可以简化计算、加速计算的方法面前，应该首先考虑到底这种算法是如何简化？在哪一步发生了奇妙的变化？为什么这样可行？

记得在上一页提到的普通穷举算法中，对于所有的可能隐状态路径计算，其实都有很大部分的重复。比如，我要分别算(S1 > S2 > S1 > S3 > S2)这个路径与(S1 > S2 > S1 > S3 > S4)这个路径的概率时候，这两个路径的t<=4的那些状态(S1 > S2 > S1 > S3 >..)其实是相同的。我们的加速算法，切入点就是这里，去掉重复的地方使速度变快，复杂度降低。

定义一个forward变量，表示t时刻之前的所有路径到达t时刻的第i种(i<=N)状态的“局部概率”。

由此定义得，，并根据此定义推出了用Emission/Transition概率表示的forward变量：

需注意，上式出现的变量i与j，其物理意义是相同的，都是代表指向的隐状态的序号，只是为了区分当前时刻t与前一时刻t-1，在t-1中用i表示当时指向的隐状态序号，在t时刻中用j表示当前指向的隐状态序号。当t顺移到t+1时刻后，t时刻的j自然会用i表示，而在t+1用j表示。

还需注意到一点是，表示从状态j“发射”(emission)出我们已得知的当前时刻观察符号O(t)的概率，其实就是存在于Emission Matrix的那些概率。

上式对的定义其实就是一个体现递归运算的过程，除了t=1的特殊初始情况外，都是在不断迭代t>1的时候的那条式子，直到t==T。

而所谓的局部概率，以及定义式中的这一项求和，都体现了不重复运算的思想。因为上一步已经算出了前一时刻的概率，并在当前一步把前一时刻的概率“加入”到了当前的概率运算里面，而前一时刻的概率运算又需要前前一时刻的概率运算。就是这一个递归的、不重复过程，不仅使复杂度降低，也使程序代码变得更加简洁。

最后，我们关注的概率将会是：

由于重复的运算被消除，所以应用了前向法的计算量将明显减少。显然，从前一时刻“跨越”到下一时刻的运算量为，而对于一个长为T的序列，共要“跨越”T次，因此运算量将是。用之前相同的数据，即假设我们有10种可能的隐状态，序列长度为20，那么计算量将会是：(10^2) * 20 = 2000，远比之前的运算量少。

以下图示将会表现出前向法的一个过程以及与普通穷举算法的区别。

Forward_1

◄ Back

Next ►

Picture 1 of 5