HMM学习最佳范例七：前向-后向算法2

七、前向-后向算法(Forward-backward algorithm)

要理解前向-后向算法，首先需要了解两个算法：后向算法和EM算法。后向算法是必须的，因为前向-后向算法就是利用了前向算法与后向算法中的变量因子，其得名也因于此；而EM算法不是必须的，不过由于前向-后向算法是EM算法的一个特例，因此了解一下EM算法也是有好处的，说实话，对于EM算法，我也是云里雾里的。好了，废话少说，我们先谈谈后向算法。

1、后向算法（Backward algorithm）
　　其实如果理解了前向算法，后向算法也是比较好理解的，这里首先重新定义一下前向算法中的局部概率at(i)，称其为前向变量，这也是为前向-后向算法做点准备：

image.png

　　相似地，我们也可以定义一个后向变量Bt(i)（同样可以理解为一个局部概率）：

image.png
　后向变量(局部概率)表示的是已知隐马尔科夫模型lamda及t时刻位于隐藏状态Si这一事实，从t+1时刻到终止时刻的局部观察序列的概率。同样与前向算法相似，我们可以从后向前（故称之为后向算法）递归地计算后向变量：
　　1）初始化，令t=T时刻所有状态的后向变量为1：
image.png

　　2）归纳，递归计算每个时间点，t=T-1,T-2,…,1时的后向变量：

image.png
　　这样就可以计算每个时间点上所有的隐藏状态所对应的后向变量，如果需要利用后向算法计算观察序列的概率，只需将t=1时刻的后向变量（局部概率）相加即可。下图显示的是t+1时刻与t时刻的后向变量之间的关系：
image.png
上述主要参考自HMM经典论文《A tutorial on Hidden Markov Models and selected applications in speech recognition》。下面我们给出利用后向算法计算观察序列概率的程序示例，这个程序仍然来自于UMDHMM。

后向算法程序示例如下（在backward.c中):

void Backward(HMM *phmm, int T, int *O, double **beta, double pprob)
{
　　int i, j; / state indices /
　　int t; / time index */
　　double sum;

/* 1. Initialization */
　　for (i = 1; i <= phmm->N; i++)
　　　　beta[T][i] = 1.0;

/* 2. Induction /
　　for (t = T - 1; t >= 1; t--)
　　{
　　　　for (i = 1; i <= phmm->N; i++)
　　　　{
　　　　　　sum = 0.0;
　　　　　　for (j = 1; j <= phmm->N; j++)
　　　　　　　　sum += phmm->A[i][j] *
　　　　　　　　　　　　　　(phmm->B[j][O[t+1]])beta[t+1][j];
　　　　　　beta[t][i] = sum;
　　　　}
　　}

/* 3. Termination /
　　pprob = 0.0;
　　for (i = 1; i <= phmm->N; i++)
　　　　*pprob += beta[1][i];
}

好了，后向算法就到此为止了，下一节我们粗略的谈谈EM算法。