Аннотация
Скрытые марковские модели – это популярный и эффективный инструмент, используемый в задачах машинного обучения. Однако продвижение данной методологии для решения прикладных задач сдерживается высокими вычислительными затратами. В данной работе рассматривается метод оптимизации вычислений при распознавании многомерных последовательностей, описываемых скрытыми марковскими моделями. Оптимизация вычислений осуществляется как на этапе обучения скрытой марковской модели, так и на этапе распознавания многомерных числовых последовательностей. Обучение моделей производилось с использованием алгоритма Баума-Велша, который является модификацией EM алгоритма применительно к скрытым марковским моделям. Классификация производилась на основе значения логарифма функции правдоподобия того, что последовательность была сгенерирована данной скрытой марковской моделью. Для его вычисления применялся традиционный алгоритм forward-backward. В качестве классификатора применялся также метод опорных векторов в пространстве первых производных от логарифма функции правдоподобия по параметрам скрытых марковских моделей.Для оптимизации применялись параллельные гибридные вычисления с использованием графического процессора. В качестве фреймворка для программирования параллельных гибридных вычислений использовался фреймворкOpenCL, который является кроссплатформенным и эффективным. В работе представлены результаты проведенной оптимизации: время исполнения для задач различной размерности и сравнение с временем исполнения последовательного метода. Оптимизация вычислений позволила значительно ускорить процесс распознавания.
Ключевые слова: машинное обучение, скрытая марковская модель, гибридные вычисления, GPU, оптимизация вычислений, алгоритм Баума–Велша, forward-backwardалгоритм,EM алгоритм, классификация, распознавание, параллелизм, метод максимального правдоподобия, скрытые переменные
Список литературы
1. 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.
2. Ковалевский В.А. Оптимальный алгоритм распознавания некоторых последовательностей изображений // Кибернетика. – 1967. – № 4. – C. 75–80.
3. Гультяева Т.А. Исследование подхода к решению задачи классификации последовательностей, представленных скрытыми марковскими моделями, с использованием инициированных этими моделями признаков: дис. ... канд. техн. наук: 05.13.17. – Новосибирск, 2013. – 242 с.
4. Гультяева Т.А., Попов А.А. Классификация смоделированных скрытыми марковскими моделями последовательностей в многоклассовом случае // Научный вестник НГТУ. – 2013. – № 3 (52). – С. 40–45.
5. Popov A.A., Gultyaeva T.A. The classification of noisy sequences generated by similar HMMs // Lecture Notes in Computer Science. – 2011. – Vol. 6744. – P. 30–35.
6. 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.
7. Гультяева Т.А., Попов А.А. Классификация последовательностей с использованием скрытых марковских моделей в условиях неточного задания их структуры // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2013. – № 3 (24). – С. 57–63.
8. Гультяева Т.А., Попов А.А. Классификация зашумленных последовательностей, порожденных близкими скрытыми марковскими моделями // Научный вестник НГТУ. – 2011. – № 3. – С. 3–16.
9. Neal R.M., Beal M.J., Roweis S.T. Inferring state sequences for non-linear systems with embedded hidden Markov models // Advances in Neural Information Processing Systems 16 / ed. by S. Thrun, L.K. Saul, B. Schölkopf. – Cambridge: MIT Press, 2003. – P. 401–408.
10. Dempster A.P., Laird N.M., Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society. Series B. – 1977. – Vol. 39. – P. 1–38.
11. Гультяева Т.А. Особенности вычисления первых производных от логарифма функции правдоподобия для скрытых марковских моделей при длинных сигналах // Сборник научных трудов НГТУ. – 2010. – № 2 (60). – C. 39–46.
12. Robust ASR using support vector machines / R. Solera-Urena, D. Martin-Iglesias, A. Gallardo-Antolini, C. Peláez-Moreno, F. Díaz-de-María // Speech Communication. – 2007. – Vol. 49. – P. 253–267.
13. Гультяева Т.А., Попов А.А. Классификация последовательностей, порожденных близкими скрытыми марковскими моделями, при наличии шума, распределенного по закону Коши // Информатика и проблемы телекоммуникаций: материалы российской научно-технической конференции. – Новосибирск, 2011. – С. 60–62.
14. Гультяева Т.А., Попов А.А. Классификация последовательностей, смоделированных скрытыми марковскими моделями при наличии аддитивного шума // Научный вестник НГТУ. – 2012. – № 3. – С. 16–24.
15. Гультяева Т.А., Попов А.А. Классификация последовательностей, подверженных действию помех с характеристиками, зависящими от скрытых состояний // Сборник научных трудов НГТУ. – 2011. – № 1 (63). – С. 59–68.
16. Baum L.E. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains // The Annals of Mathematical Statistics. – 1970. – Vol. 41. – P. 164–171.
17. Luebke D., Humphreys G. How GPUs work // Computer. – 2007. – Vol. 40. – P. 96–100.
18. Официальный сайт фреймворка OpenCL [Электронный ресурс]. – URL: https://www.khronos.org/opencl/ (дата обращения: 23.10.2015).
19. Munshi A., Gaster B.R., Mattson T.G. OpenCL programming guide. – Boston: Addison-Wesley Professional, 2011. – 603 p.
20. OpenCL user guide [Electronic resource]. – URL: http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2013/12/AMD_OpenCL_Programming_User_Guide.pdf (accessed: 23.10.2015).
21. Liu C. cuHMM: a CUDA implementation of hidden Markov model: training and classification [Electronic resource]. – 2009. – URL: https://liuchuan.org/pub/cuHMM.pdf (accessed: 23.10.2015).
22. Gultyaeva T.A., Sautin A.S., Uvarov V.E. Graphics processing unit implementation of Hidden Markov models // 12th International Conference on Actual Problems of Electronic Instrument Engineering, APEIE–2014: proceedings: in 7 vol., Novosibirsk, Russia, 2–4 October 2014. – Novosibirsk, 2014. – Vol. 1. – P. 571–573.
23. Гультяева Т.А., Уваров В.Е. Решение на GPU задачи обучения и классификации многомерных числовых последовательностей с помощью скрытых марковских моделей // Материалы 53-й международной научной студенческой конференции МНСК–2015. Математика, Новосибирск, 11–17 апреля 2015 г. – Новосибирск, 2015. – C. 196.
