The Learning Algorithms of Coupled Discrete Hidden Markov Models

Abstract:

A hidden Markov model (HMM) encompasses a large class of stochastic process models and has been successfully applied to a number of scientific and engineering problems, including speech and other pattern recognition problems, and biological sequence analysis. A major restriction is found, however, in conventional HMM, i.e., it is ill-suited to capture the interactions among different models. A variety of coupled hidden Markov models (CHMMs) have recently been proposed as extensions of HMM to better characterize multiple interdependent sequences. The resulting models have multiple state variables that are temporally coupled via matrices of conditional probabilities. This paper study is focused on the coupled discrete HMM, there are two state variables in the network. By generalizing forward-backward algorithm, Viterbi algorithm and Baum-Welch algorithm commonly used in conventional HMM to accommodate two state variables, several new formulae solving the 2-chain coupled discrete HMM probability evaluation, decoding and training problem are theoretically derived.

• Periodical: Applied Mechanics and Materials (Volumes 411-414)
• Pages: 2106-2110
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.411-414.2106
• Online since: September 2013
• Authors: Shi Ping Du, Jian Wang, Yu Ming Wei
• Keywords: Baum-Welch Algorithm, Coupled Hidden Markov Model, Forward-Backward Procedure, Hidden Markov Model (HMM), Lagrange Multipliers, Viterbi Algorithm

References

[1] R. Cole,L. Hirschman,L. Atlas,M. Beckman, et al., The challenge of spoken language systems: Research directions for the nineties, IEEE Trans. Speech Audio Process. 1995, 3(1): 1-21.

DOI: 10.1109/89.365385

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

DOI: 10.1109/5.18626

[3] L.R. Rabiner, B.H. Juang, Fundamentals of speech recognition, Prentice-Hall, (1993).

[4] Matthew Brand, Nuria Oliver, and Alex Pentland. Coupled hidden Markov models for complex action recognition. In Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition. 1997, pp.994-999.

DOI: 10.1109/cvpr.1997.609450

[5] S.R. Eddy. Profile hidden Markov models. Bioinformatics. 1998, 14(9): 755–763.

DOI: 10.1093/bioinformatics/14.9.755

[6] R. Durbin,S. Eddy,A. Krogh, G. Mitchison, Biological sequence analysis. Cambridge University Press, (1998).

[7] K. Asai, S. Hayamizu ,K. Handa, Prediction of protein secondary structure by the hidden Markov model, Comput. Appl. Biosci. 1993, 9(2): 141-146.

DOI: 10.1093/bioinformatics/9.2.141

[8] J. Kwon and K. Murphy. Modeling freeway traffic with coupled HMMs. Technical report, University of California at Berkeley, May (2000).

[9] I. Rezek and S. J. Roberts. Estimation of coupled hidden Markov models with application to biosignal interaction modelling. In Proc. IEEE Int. Conf. on Neural Network for Signal Processing. 2000, volume 2, p.804–813.

DOI: 10.1109/nnsp.2000.890160

[10] I. Rezek, M. Gibbs and S. J. Roberts. Maximum a posteriori estimation of coupled hidden Markov models. Journal of VLSI Signal Processing. 2002, 32(1-2): 55-66.

[11] Matthew Brand. Coupled hidden Markov models for modeling interactive processes. Technical Report 405, MIT Media Lab, (1997).

[12] T.T. Kristjansson B.J. Frey, and T. Huang. Event-coupled hidden Markov models. In Proc. IEEE Int. Conf. on Multimedia and Exposition. 2000, volume 1, p.385–388.

[13] Z. Ghahramani and M. I. Jordan. Factorial hidden Markov models. Machine Learning. 1997, 29(2-3): 245–275.

[14] Y. Bengio and P. Frasconi. Input-Output HMMs for sequence processing. IEEE Trans. Neural Networks. 1996, 7(5): 1231–1249.

DOI: 10.1109/72.536317

[15] G.D. Forney. The Viterbi Algorithm. IEEE Transactions. 1973, 61(3): 268–278.

[16] A.P. Dempster, N. M. Laird, D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. 1997, 39(1) : 1-38.

DOI: 10.1111/j.2517-6161.1977.tb01600.x