Ewolucyjne metody uczenia ukrytych modeli Markowa

• Autorzy: Figielska E.

Warianty tytułu

EN

Evolutionary methods for training hidden Markov models

• Języki publikacji: PL

Abstrakty

PL

Ukryte modele Markowa stanowią narzędzie modelowania statystycznego wykorzystywane do analizy i przewidywania zjawisk o charakterze sekwencji zdarzeń występujących na przykład w rozpoznawaniu mowy i gestów oraz modelowaniu sekwencji biologicznych. Aby ukryty model Markowa mógł z powodzeniem zostać zastosowany w praktyce, konieczne jest określenie jego topologii i wyznaczenie wartości jego parametrów. Istniejące metody klasyczne nie zawsze są zdolne do dostarczenia wystarczająco dobrych modeli. Dlatego też, w ostatnich latach obserwuje się wzrost zainteresowania możliwością stosowania innych technik, zwłaszcza opartych na mechanizmach stochastycznych. W artykule przedstawione są sposoby wykorzystania w procesie budowy ukrytych modeli Markowa metod ewolucyjnych. Przeprowadzona jest również ocena jakości otrzymywanych w ten sposób modeli.

EN

Hidden Markov models (HMMs) are a statistical tool for analyzing and modeling time-series data. They have been successfully used in many areas requiring time-series analysis for example in speech recognition, DNA sequence analysis or forecasts of stock prices. To use a HMM in practice, the topology and the values of its parameters have to be determined. The existing classical methods for HMM training are not always able to provide sufficiently good models. Therefore, in recent years, we observe an increasing interest in developing other methods for HMM training, especially ones involving evolutionary mechanisms. This paper presents how evolutionary methods can be used to build HMMs. The quality of the obtained in this way HMMs is also discussed.

Słowa kluczowe

PL

ukryte modele Markowa; modelowanie statystyczne; metody uczenia

EN

infrastructure subsystem; statistical modeling; methods for training

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2011
• Tom: nr 5
• Strony: 63--74
• Opis fizyczny: Bibliogr. 31 poz., rys., wykr.

Twórcy

autor

Figielska E.

• Warszawska Wyższa Szkoła Informatyki

Bibliografia

• 1. Baker, J.K., 1975. The Dragon system - an overview. IEEE Trans. Acoust., Speech Signal Process 23 (11), 23-29.
• 2. Bakis, R, 1976. Continuous speech word recognition via centisecond acoustic states, Proceedings ASA Meeting, Washington, DC.
• 3. Baum L.E., J.A. Egon, 1967. An inequality with applications to statistical estimation for probabilistic functions of a Markov process and to a model for ecology. Bull. Amer. Meteorol. Soc. 73, 360-363.
• 4. Baum, L.E., T. Petrie, 1966. Statistical inference for probabilistic functions of finite state Markov chains. Ann. Math. Statist. 37, 1554-1563.
• 5. Baum, L.E., T. Petrie, G. Soules, N. Weiss, 1970. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains, Ann. Math. Statistics, 41 (1), 164-171.
• 6. Baum, L.E., 1972. An inequality and associated maximization technique occurring in statistical estimation for probabilistic functions of Markov process. Inequalities III, 1-8.
• 7. Bladi, P., S. Brunak, 1998. Bioinformatics, the Machine Learning Approach. MIT Press.
• 8. Cai, J., Z.-O. Liu, 2001. Hidden Markov models with spectral features for 2D shape recognition. IEEE Trans. PAMI 23 (12), 703-713.
• 9. Chau, C.W., S. Kwong, C.K. Diu, W.R. Fahrner, 1997. Optimisation of HMM by a genetic algorithm, Proceedings ICASSP, 1727-1730.
• 10. Cheung, L.W.K., 2004. Use of runs statistics for pattern recognition in genomic DNA sequences, Journal of Computational Biology 11 (1), 107-124.
• 11. Coast, D.A., R.M. Stern, G.G. Cano, S.A. Briller, 1990. An approach to cardiac arrhythmia analysis using hidden Markov models, IEEE Transactions on Biomedical Egineering 37 (9), 826-836.
• 12. El-Yacoubi, A., M. Gilloux, R. Sabourin, C.Y. Suen, 1999. An HMM based approach for off-line unconstrained handwritten word modeling and recognition. IEEE Trans. PAMI 21 (8), 752-760.
• 13. Goldberg, D.E., 1995. Algorytmy genetyczne i ich zastosowania, WNT.
• 14. Figielska, E., 2006. Algorytmy ewolucyjne i ich zastosowania, Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki, 81-92.
• 15. Figielska, E., W. Kasprzak, 2008. An evolutionary programming based algorithm for HMM training, in: Computational Intelligence: Methods and Applications, L. Rutkowski, R. Tadeusiewicz, L. A. Zadeh, J. Zurada (eds), in series: Challenging problems of Science - Computer Science, L. Bolc (series editor), Academic Publishing House EXIT, 166-175
• 16. Hassan, Md. R., B. Nath, M. Kirley, 2007. A fusion model of HMM, ANN and GA for stock market forecasting. Expert Systems and Applications 33, 171-180.
• 17. Holland, J. H., 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
• 18. Jelinek, F., 1976. Continuous speech recognition by statistical methods. Proc. IEEE 64, 532-556.
• 19. Kim, I., S. Chien, 2001. Analysis of 3D hand trajectory gestures using stroke-based composite hidden Markov models. Appl. Intell. 15, 131-143.
• 20. Karplus, K., K. Sjolander, C. Barrett, M. Cline, D. Haussler, R. Hughey, L. Holm, C. Sander, 1997.
• 21. Predicting protein structure using hidden Markov models. Proteins: Struct., Funct. Genet. 1 (1), 134-139.
• 22. Kwong, S., C.W. Chau, K.F. Man, K.S. Tang. 2001. Optimisation of HMM topology and its model parameters by genetic algorithms. Pattern Recognition 34, 509-522.
• 23. Kwong, S., Q.H. Heb, K.W. Kua, T.M. Chana, K.F. Mana, K.S. Tanga Kwong S., C.W. Chau, K.F. Man, K.S. Tang. 2002, A genetic classi_cation error methodfor speech recognition. Signal Processing 82, 737 - 748.
• 24. Levinson, S.E., L.R. Rabiner, M.M. Sondhi, 1983. An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition, The Bell System Tech. J., 1035-1074.
• 25. Rabiner, L., 1989. A Tutorial on Hidden Markov Models and selected Applications in Speec Recognition, Proceedings of the IEEE 77 (2), 257-286.
• 26. Rabiner, L., Juang B., 1993. Fundamentals of Speech Recognition, Prentice Hall.
• 27. Thomsen, R., 2002. Evolving the topology of hidden Markov models using evolutionary algorithms. LNCS 2439, 861-870.
• 28. Won, K.-J.; T. Hamelryck, A. Prugel-Bennett, A. Krogh, 2005. Evolving hidden Markov models for protein secondary structure prediction. IEEE Congress on evolutionary computation 1, 33-40
• 29. Won, K.-J.; T. Hamelryck, A. Prugel-Bennett, A. Krogh, 2007. An evolutionary method for learning HMM structure: prediction of protein secondary structure. BMC Bioinformatics 8, 357.
• 30. Yada, T., M. Ishikawa, H. Tanaka, K. Asai, 1994. DNA sequence analysis using hidden Markov model and genetic algorithm. Genome Informatics 5, 178-179.
• 31. Yada, T., 1995. Generation of hidden Markov model describing complex motif in DNA sequences. IPSJ Trans. 40, 750-767.