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

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 43-55.

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

叶飞^1,2,*, 王翼飞³

1. 铜陵学院数学与计算机学院, 安徽铜陵 244000; 2. 南京大学社会科学计算实验中心, 南京 210093; 3. 上海大学数学系, 上海~200444

出版日期:2013-12-15 发布日期:2013-12-15
通讯作者: 叶飞 E-mail:postyf@163.com
基金资助:
国家自然科学基金 (No. 30871341), 上海市重点学科基金 (No. S30104), 上海市教委重点学科建设项目基金 (No. J50101)

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

YE Fei^1,2,*, WANG Yifei³

1. School of Mathematics and Computer, Tongling University, Tongling 244000, Anhui, China; 2. Computational Experiment Center for Social Science, Nanjing University, Nanjing 210093, China; 3. Department of Mathematics, Shanghai University, Shanghai 200444, China

Online:2013-12-15 Published:2013-12-15

摘要/Abstract

摘要： 首先通过Hadar等价变换方法将高阶隐马氏模型转换为与之等价的一阶向量值隐马氏模型，然后利用动态规划原理建立了一阶向量值隐马氏模型的Viterbi算法，最后通过高阶隐马氏模型和一阶向量值隐马氏模型之间的等价关系建立了高阶隐马氏模型基于动态规划推广的Viterbi算法. 研究结果在一定程度上推广了几乎所有隐马氏模型文献中所涉及到的解码问题的Viterbi算法，从而进一步丰富和发展了高阶隐马氏模型的算法理论.

关键词: 高阶隐马氏模型, 动态规划原理, Viterbi算法

Abstract: 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.

Key words: high-order hidden Markov model, dynamic programming principle, Viterbi algorithm

中图分类号:

O211.62

叶飞, 王翼飞. 基于动态规划的高阶隐马氏模型推广的Viterbi算法[J]. 运筹学学报, 2013, 17(4): 43-55.

YE Fei, WANG Yifei. Extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model[J]. Operations Research Transactions, 2013, 17(4): 43-55.

参考文献

Smith D R. The design of divide and conquer algorithms [J]. Science of Computer Programming, 1985, 5: 37-58.

王海源. 分治算法的两种思路和形式 [J]. 上海师范大学学报(自然科学版), 2003, 32(1): 39-43.

Dreyfus S. Richard Bellman on the birth of dynamic programming [J]. Operations Research, 2002, 50(1): 48-51.

Eddy S R. What is dynamic programming? [J]. Nature Biotechnology, 2004, 22(7): 909-910.

Viterbi A J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm [J]. IEEE Transactions on Information Theory, 1967, 13(2): 260-269.

Omura J K. On the Viterbi decoding algorithm [J]. IEEE Transactions on Information Theory, 1969, 15(1): 177-179.

Viterbi A J. Convolutional codes and their performance in communication systems [J]. IEEE Transactions on Communications Technology, 1971, 19(5): 751-772.

Forney G D. Convolutional codes II. Maximum-likelihood decoding [J]. Information and Control, 1974, 25(3): 222-266.

Levinson S E, Rabiner L R, Sondhi M M. An introduction to the application of the theory of probabilistic functions of Markov process to automatic speech recognition [J]. The Bell System Technical Journal, 1983, 62(4): 1035-1074.

Rabiner L R. A tutorial on hidden Markov models and selected applications in speech recognition [J]. {Proceedings of the IEEE, 1989, 77(2): 257-286.

史笑兴, 王太君, 何振亚. 二阶隐马尔科夫模型的学习算法及其与一阶隐马尔科夫模型的关系 [J]. 应用科学学报, 2001, 19(1): 29-32.

叶飞, 衣娜, 王翼飞. 三阶隐马氏模型算法及其与一阶隐马氏模型的关系 [J]. 应用科学学报, 2011, 29(5): 500-507.

Du Preeze J A. Efficient training of high-order hidden Markov models using first-order representations [J]. Computer Speech and Language, 1998, 12(1): 23-29.

Ching W K, Fung E S, Ng M K. High-order hidden Markov models with applications to DNA sequences [M]//Lecture Notes in Computer Science, Berlin: Springer, 2003, 535-539.

Lee L M, Lee J C. A study on high-order hidden Markov models and applications to speech recognition[M]//Lecture Notes in Computer Science, Berlin: Springer, 2006, 682-690.

Lee L M. High-order hidden Markov model and application to continuous mandarin digit recognition [J]. Journal of Information Science and Engineering, 2011, 27(6): 1919-1930.

Hadar U, Messer H. High-order hidden Markov models---estimation and implementation[C]// Proceedings of the IEEE/SP 15the Workshop on Statistical Signal Processing, 2009, 249-252.

Ye F, Yi N, Wang Y F. EM algorithm for training high-order hidden Markov model with multiple observation sequences [J]. Journal of Information and Computational Science, 2011, 8(10): 1761-1777.

谢锦辉. 隐马尔科夫模型及其在语音处理中的应用 [M]. 武汉: 华中理工大学出版社, 1995, 8.

Ye F, Yi N, Wang Y F. EM algorithm for training high-order hidden Markov model with multiple observation sequences [J]. Journal of Information and Computational Science, 2011, 8(10): 1761-1777.

王翼飞, 史定华. 生物信息学---智能化算法及其应用 [M]. 北京: 化学工业出版社, 2006, 71-104.

胡运权. 运筹学基础及其应用(第五版) [M]. 北京：高等教育出版社, 2008, 198-219.

张鹏. 连续型动态规划的新算法研究 [J]. 运筹学学报, 2012, 16(1): 97-105.