基于动态规划的高阶隐马氏模型推广的Viterbi算法  

Extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model

作　　者：叶飞[1,2] 王翼飞[3] 

机构地区：[1]铜陵学院数学与计算机学院,安徽铜陵244000 [2]南京大学社会科学计算实验中心,南京210093 [3]上海大学数学系,上海200444

出　　处：《运筹学学报》2013年第4期43-55,共13页Operations Research Transactions

基　　金：国家自然科学基金(No.30871341);上海市重点学科基金(No.S30104);上海市教委重点学科建设项目基金(No.J50101)

摘　　要：首先通过Hadar等价变换方法将高阶隐马氏模型转换为与之等价的一阶向量值隐马氏模型,然后利用动态规划原理建立了一阶向量值隐马氏模型的Viterbi算法,最后通过高阶隐马氏模型和一阶向量值隐马氏模型之间的等价关系建立了高阶隐马氏模型基于动态规划推广的Viterbi算法.研究结果在一定程度上推广了几乎所有隐马氏模型文献中所涉及到的解码问题的Viterbi算法,从而进一步丰富和发展了高阶隐马氏模型的算法理论.Firstly, high-order hidden Markov model is transformed into an equivalent first-order vector-valued hidden Markov model by using Hadar＇s equivalent transformation method. Secondly, the Viterbi algorithm for the first-order vector-valued hidden Markov model is established according to the dynamic programming principle. Finally, the extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model is established by using the equivalence relation between high-order hidden Markov and the first-order vector-valued hidden Markov model. This study extends the related Viterbi algorithms discussed in almost all literatures of hidden Markov model, and then contributes to the algorithmic theory of high-order hidden Markov model.

关 键 词：高阶隐马氏模型 动态规划原理 VITERBI算法 

分 类 号：O211.62[理学—概率论与数理统计]