隐马尔可夫模型(五)——隐马尔可夫模型的解码问题(维特比算法)(转载)

标签:ima   space   递归   init   letter   overflow   stdio.h   html   result   

阅读目录

  • HMM解码问题
  • 维特比算法
  • 时间复杂度
  • 程序例证
回到顶部

HMM解码问题

      给定一个观察序列O=O1O2...OT,和模型μ=(A,B,π),如何快速有效地选择在一定意义下“最优”的状态序列Q=q1q2...qT,使该状态最好地解释观察序列。

            技术分享

      一种想法是求出每个状态的概率rt(i)最大(rt(i)=P(qt=si,O|μ)),记q‘t(i)=argQmax(rt(i)),但是这样做,忽略了状态之间的关系,很可能两个状态之间的概率为0,即aq‘t(i)q‘t+1(i)=0,这样求得的“最优”状态序列是不合法的。

      为防止状态之间转移概率为0(断续问题),换一种思路,不是求单个状态求得最大值,而是求得整个状态序列最大值,即求

                                   Q‘= argQmaxP(Q|O,μ)

      此时用维特比算法,先定义下维特比变量δt(i):在时间t,HMM沿着一条路径到达状态si,并输出观察序列O=O1O2...Ot的最大概率:

        δt(i)=max P(q1q2...qt=si,O1O2...Ot|μ)

           技术分享

                            t                      t+1

      上图中,对于从t时刻三个到 t+1时刻的状态1,到底取状态1,2还是3,不是看单独状态1,2还是3的概率,而是看在状态1,2,3各自的维特比变量值乘以相应的状态转换概率,从中选出最大值,假设2时最大,那么记下t+1时刻状态1之前的路径是t时刻的状态2,以此类推。

      δt(i)的递归关系式: δt+1(i)=maxj δt(j)*aji*bi(Ot+1),为了记忆路径,定义路径变量ψt(i),记录该路径上的状态si的前一个状态。

回到顶部

维特比算法

      step1 初始化:

              δt(i) = πi*bi(O1), 1≤i≤N

              ψt(i) = 0

      step2 归纳计算:

      δt(i)=max1≤j≤N δt-1(j)*aji*bi(Ot),2≤t≤T;1≤i≤N

             记忆路径   ψt(i) = arg [max1≤j≤Nδt-1(j)*aji*bi(Ot)]

      step3 终结:

            QT‘ = arg max1≤i≤N T(i)]

            P‘(QT‘) = max1≤i≤N T(i)]

   step4 路径回溯:

             q

隐马尔可夫模型(五)——隐马尔可夫模型的解码问题(维特比算法)(转载)

扫一扫手机访问