后向算法

    对于HMM的评估识别问题，利用动态规划可以用前向算法，从前到后算出前向变量；也可以采用后向算法，从后到前算出后向变量。

先介绍后向变量βt(i):给定模型μ=（A,B,π），并且在时间 时刻t状态为si 的前提下，输出序列为Ot+1Ot+2...OT的概率，即

             βt(i)=P(Ot+1Ot+2...OT|qt=si,μ)

归纳过程

   假设仍然有3个状态

   当t=T时，按照定义：时间t时刻状态qT输出为OT+1......的概率，从T+1开始的输出是不存在的（因为T时刻是终止终止状态），即T之后是空，是个必然事件，因此βt(i)=1,1≤1≤N

    当t=T-1时，

       βT-1(i)=P(OT|qT-1=si,μ) = ai1*b1（OT)*βT(1)+ai2*b2（OT)*βT(2)  + ai3*b3（OT)*βT(3)

 ......

     当t=1时，

   β1(1)=P(O2O3...OT|q2=s1,μ)= a11*b1（O2)*β2(1) + a12*b2（O2)*β2(2)+ a13*b3（O2)*β2(3)

   β1(2)=P(O2O3...OT|q2=s1,μ)= a21*b1（O2)*β2(1) + a22*b2（O2)*β2(2)+ a23*b3（O2)*β2(3)

    β1(3)=P(O2O3...OT|q2=s1,μ) = a31*b1（O2)*β2(1)+ a32*b2（O2)*β2(2) + a33*b3（O2)*β2(3)

   P(O1O2...OT|μ)=  

                          = 

                          =

后向算法

    step1 初始化：

              βT(i)=1,1≤1≤N

    step2 归纳计算：

                  1≤t≤T-1, 1≤i≤N

    step3 求终结和：

            P(O|μ）=

时间复杂度

    计算某时刻在某个状态下的后向变量需要看后一时刻的N个状态，此时时间复杂度为O(N),每个时刻有N个状态，此时时间复杂度为N*O(N)=O(N2),又有T个时刻，所以时间复杂度为T*O(N2)=O(N2T)。

程序例证

              

后向算法计算P(O|M)：

    step1：

              β4(1) = 1

             β4(2) =1        

             β4(3) = 1

    step2：

              β3(1) = β4(1)*a11*b1(white) + β4(2)*a12*b2(white)+ β4(3)*a13*b3(white)

                  .......

    step3:

              P(O|M) = π1*β1(1)*b1(O1) +π2*β1(2)*b2(O1) + π3*β1(3)*b3(O1)

 

程序代码

#include<stdio.h>

#include<stdlib.h>

#include <string.h>

int main()

{

   float a[3][3] = {{0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}};

   float b[3][2] = {{0.5,0.5},{0.4,0.6},{0.7,0.3}};

   float result[4][3];

   int list[4] = {0,1,0,1};

   result[3][0] = 1;

   result[3][1] = 1;

   result[3][2] = 1;

   int i,j,k, count = 3;

   for (i=2; i>=0; i--)

   {

      for(j=0; j<=2; j++)

       {

          result[i][j] = 0;

          for(k=0; k<=2; k++)

          {

               result[i][j] += result[i+1][k] * a[j][k] * b[k][list[count]];

           }

        }

        count -= 1;

    }

    for (i=0; i<=3; i++)

    {

       for(j=0; j<=2; j++)

       {

               printf("b[%d][%d] = %f\n",i+1,j+1,result[i][j])

        }

     }

     printf("backward:%f\n",      

     result[0][0]*0.2*0.5+result[0][1]*0.4*0.4+result[0][2]*0.4*0.7);

     return0;

}

前后向概率的关系

具体推倒就不给出了，总之：

拥有所有观测时，第t时刻有第i个状态的概率 = t时刻的前向概率 * t时刻的后向概率，即：

P(i_t =q_i, Y | λ ) = α_i(t) * β_i(t)