НАУЧНЫЙ ВЕСТНИК


НОВОСИБИРСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

ISSN (печатн.): 1814-1196          ISSN (онлайн): 2658-3275
English | Русский

Последний выпуск
№3(72) Июль - Сентябрь 2018

Распознавание, декодирование и восстановление последовательностей с пропусками, описываемых скрытой марковской моделью с дискретным распределением наблюдений

Выпуск № 1 (66) Январь - Март 2017
Авторы:

А.А. Попов,
Т.А. Гультяева,
В.Е. Уваров
DOI: http://dx.doi.org/10.17212/1814-1196-2017-1-99-119
Аннотация
В работе рассматриваются различные подходы к использованию аппарата скрытых марковских моделей (СММ) для анализа последовательностей с пропусками. Были рассмотрены задачи обучения СММ по последовательностям с пропусками, а также задачи распознавания, декодирования и восстановления последовательностей с пропусками. В ходе выполнения работы был разработан алгоритм для обучения СММ по последовательностям с пропусками, основанный на маргинализации пропущенных наблюдений, а также алгоритм, основанный на восстановлении последовательностей с пропусками с помощью модифицированного алгоритма Витерби. Также были разработаны алгоритмы для восстановления и декодирования последовательностей с пропусками с помощью модифицированного алгоритма Витерби. Кроме того, были разработаны алгоритмы для распознавания последовательностей с пропусками с помощью маргинализации пропущенных наблюдений, а также с помощью модифицированного алгоритма Витерби. Для оценки эффективности разработанных алгоритмов были реализованы методы, основанные на стандартных подходах к работе с последовательностями, содержащими пропуски: склеивание последовательностей с пропусками, а также восстановление пропусков в последовательностях по моде соседних наблюдений. С помощью вычислительных экспериментов было показано, что алгоритмы обучения СММ по последовательностям с пропусками, а также распознавания последовательностей с пропусками, основанные на маргинализации пропущенных наблюдений, показали наилучшие результаты по сравнению с другими подходами. Также было продемонстрировано экспериментально, что при восстановлении и декодировании последовательностей с пропусками алгоритм, использующий модифицированный алгоритм Витерби, оказался эффективнее других подходов. Таким образом, на основе результатов вычислительных экспериментов нами предлагается алгоритм обучения СММ по последовательностям с пропусками и алгоритм распознавания последовательностей с пропусками, основанные на маргинализации пропущенных наблюдений. Для декодирования и восстановления последовательностей с пропусками нами предлагаются алгоритмы на основе модификации алгоритма Витерби для случая пропущенных наблюдений.
Ключевые слова: скрытые марковские модели, машинное обучение, последовательности, алгоритм Баума–Велша, пропущенные наблюдения, неполные данные, алгоритм Витерби, классификация

Список литературы
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.
Просмотров: 729