Аннотация
В работе рассматриваются различные подходы к использованию аппарата скрытых марковских моделей (СММ) для анализа последовательностей с пропусками. Были рассмотрены задачи обучения СММ по последовательностям с пропусками, а также задачи распознавания, декодирования и восстановления последовательностей с пропусками. В ходе выполнения работы был разработан алгоритм для обучения СММ по последовательностям с пропусками, основанный на маргинализации пропущенных наблюдений, а также алгоритм, основанный на восстановлении последовательностей с пропусками с помощью модифицированного алгоритма Витерби. Также были разработаны алгоритмы для восстановления и декодирования последовательностей с пропусками с помощью модифицированного алгоритма Витерби. Кроме того, были разработаны алгоритмы для распознавания последовательностей с пропусками с помощью маргинализации пропущенных наблюдений, а также с помощью модифицированного алгоритма Витерби. Для оценки эффективности разработанных алгоритмов были реализованы методы, основанные на стандартных подходах к работе с последовательностями, содержащими пропуски: склеивание последовательностей с пропусками, а также восстановление пропусков в последовательностях по моде соседних наблюдений. С помощью вычислительных экспериментов было показано, что алгоритмы обучения СММ по последовательностям с пропусками, а также распознавания последовательностей с пропусками, основанные на маргинализации пропущенных наблюдений, показали наилучшие результаты по сравнению с другими подходами. Также было продемонстрировано экспериментально, что при восстановлении и декодировании последовательностей с пропусками алгоритм, использующий модифицированный алгоритм Витерби, оказался эффективнее других подходов. Таким образом, на основе результатов вычислительных экспериментов нами предлагается алгоритм обучения СММ по последовательностям с пропусками и алгоритм распознавания последовательностей с пропусками, основанные на маргинализации пропущенных наблюдений. Для декодирования и восстановления последовательностей с пропусками нами предлагаются алгоритмы на основе модификации алгоритма Витерби для случая пропущенных наблюдений.
Ключевые слова: скрытые марковские модели, машинное обучение, последовательности, алгоритм Баума–Велша, пропущенные наблюдения, неполные данные, алгоритм Витерби, классификация
Авторы:
А.А. Попов
630073, РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет, доктор технических наук, профессор. Е-mail:alex@fpm.ami.nstu.ru
Т.А. Гультяева
630073, РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет, кандидат технических наук, доцент. Е-mail:t.gultyaeva@corp.nstu.ru
В.Е. Уваров
630073, РФ, г. Новосибирск, пр. Карла Маркса, 20, Новосибирский государственный технический университет, аспирант. Е-mail:vadim.uvarov42@gmail.com
Список литературы
1. Baum L.E., Petrie T. Statistical inference for probabilistic functions of finite state Markov chains // The Annals of Mathematical Statistics. – 1966. – Vol. 37. – P. 1554–1563. 2. Baum L.E., Egon J.A. An inequality with applications to statistical estimation for probabilistic functions of a Markov process and to a model for ecology // Bulletin of the American Meteorological Society. – 1967. – Vol. 73. – P. 360–363. 3. Gales M., Young S. The application of hidden Markov models in speech recognition // Signal Processing. – 2007. – Vol. 1, N 3. – P. 195–304. 4. Rabiner L.R. A tutorial on hidden Markov models and selected applications in speech recognition // Proceedings of the IEEE. – 1989. – Vol. 77. – P. 257–285. 5. Статистика упоминания ключевого слова “hidden Markov models” между 1800 и 2008 годами, полученная с помощью сервиса Google Ngram Viewer [Электронный ресурс]. – URL: https://books.google.com/ngrams/graph?content=hidden+Markov+models&year_start=1800&year_end=2008&corpus=15&smoothing=3&share=&direct_url=t1%3B%2Chidden%20Markov%20models%3B%2Cc0 (дата обращения: 29.03.2017). 6. Robust automatic speech recognition with missing and unreliable acoustic data / M. Cooke, P. Green, L. Josifovski, A. Vizinho // Speech Communication. – 2001. – Vol. 34, N 3. – P. 267–285. 7. Lee D., Kulic D., Nakamura Y. Missing motion data recovery using factorial hidden Markov models // IEEE International Conference on Robotics and Automation. – Pasadena, California, 2008. – P. 1722–1728. 8. Classification of observation sequences described by hidden Markov models / T. Gultyaeva, A. Popov, V. Kokoreva, V. Uvarov // Applied Methods of Statistical Analysis. Nonparametric Approach: Proceedings of the International Workshop, Novosibirsk, Russia, 14–19 September 2015. – Novosibirsk, 2015. – P. 136–144. 9. Training hidden Markov models on incomplete sequences / T. Gultyaeva, A. Popov, V. Kokoreva, V. Uvarov // 13th International Scientific-Technical Conference on Actual problems of Electronic Instrument Engineering (APEIE-2016): proceedings, Novosibirsk, 3–6 October 2016. – Novosibirsk, 2016. – Vol. 1, pt. 2. – P. 317–320. 10. Гультяева Т.А., Попов А.А., Саутин А.С. Методы статистического обучения в задачах регрессии и классификации: монография. – Новосибирск: Изд-во НГТУ, 2016. – 322 с. 11. Попов А.А., Гультяева Т.А., Уваров В.Е. Исследование подходов к обучению скрытых марковских моделей при наличии пропусков в последовательностях // Обработка информации и математическое моделирование: материалы российской научно-технической конференции. – Новосибирск, 2016. – С. 125–139. 12. Popov A., Gultyaeva A., Uvarov V. A comparison of some methods for training hidden Markov models on sequences with missing observations // 11th International Forum on Strategic Technology (IFOST 2016): proceedings, Novosibirsk, 1–3 June 2016. – Novosibirsk, 2016. – Pt. 1. – P. 431–435. 13. Попов А.А., Гультяева Т.А., Уваров В.Е. Исследование методов обучения скрытых марковских моделей при наличии пропусков в последовательностях // Труды XIII международной конференции «Актуальные проблемы электронного приборостроения», Новосибирск, 3–6 октября 2016. – Новосибирск, 2016. – Т. 8. – С. 149–152. 14. Baum L.E., Sell G.R. Growth functions for transformations on manifolds // Pacific Journal of Mathematics. – 1968. – Vol. 27, N 2. – P. 211–227. 15. Dempster A.P., Laird N.M., Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society. – 1977. – Vol. 39. – P. 1–38. 16. Li X. Training hidden Markov models with multiple observations – a combinatorial method // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2000. – Vol. PAMI-22, N 4. – P. 371–377. 17. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains / L.E. Baum, T. Petrie, G. Soules, N. Weiss // The Annals of Mathematical Statistics. – 1970. – Vol. 41. – P. 164–171. 18. Baum L.E. An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes // Inequalities. – 1972. – Vol. 3. – P. 1–8. 19. Viterbi A.J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm // IEEE Transactions on Information Theory. – 1967. – Vol. 13. – P. 260–269. 20. Gelman A., Hill J. Data analysis using regression and multilevel/hierarchical models. – Cambridge: Cambridge University Press, 2006.
