DOI: https://doi.org/10.18523/2617-7080i2018p15-20

Метод дискретної регуляризацiї для прихованих марковських моделей, занурених у гiльбертiв простiр iз вiдтворюючим ядром

Galyna Kriukova

Анотація


Прихованi марковськi моделi — добре вiдомi ймовiрнiснi графiчнi моделi для часових рядiв дискретних, частково спостережуваних стохастичних процесiв. Ми розглядаємо спосiб розширити застосування прихованих марковських моделей до негаусових неперервних розподiлiв за допомогою занурення апрiорного ймовiрнiсного розподiлу простору станiв у гiльбертiв простiр iз вiдтворюючим ядром. Вiдповiднi методи регуляризацiї запропоновано для зменшення схильностi до перенавчання та обчислювальної складностi алгоритму, наприклад, метод пiдвибiрки Нiстрома та узагальнене сiмейство регуляризацiйних функцiй застосовуються пiд час побудови обернених ядерної та ознакової матриць. Цей метод може бути використаний у рiзних задачах статистичного виведення, зокрема класифiкацiї, передбачення, iдентифiкацiї, сегментацiї, а також як онлайн-алгоритм — для динамiчної обробки даних та обробки потоку даних. Далi ми наводимо приклад застосування методу до прикладних задач, порiвнюємо запропонований пiдхiд iз сучасними алгоритмами.

Метою дослiдження є розробка методiв регуляризацiї обернених задач, що виникають на стадiї навчання ймовiрнiсних графiчних моделей, в яких уявлення про розподiл занурено в гiльбертiв простiр iз вiдтворюючим ядром. Основною методикою реалiзацiї є застосування узагальненого сiмейства регуляризацiйних функцiй та дискретної регуляризацiї, зокрема метод Нiстрома, до вiдповiдних обернених задач обертання матриць ядра та ознак. Задачу вибору вiдповiдних регуляризацiйних змiнних та параметрiв ядра, що визначає гiльбертiв простiр, розв’язано за допомогою методу лiнiйної функцiональної стратегiї, тобто ансамблю рiшень, побудованих iз рiзними значеннями параметрiв. У результатi дослiдження отримано теоретичнi апроксимацiйнi оцiнки та оцiнки складностi алгоритму, а також у процесi чисельного експерименту запропонований пiдхiд було порiвняно з продуктивнiстю iнших алгоритмiв.


Ключові слова


прихована марковська модель; обробка потоку даних; гiльбертiв простiр iз вiдтворюючим ядром; онлайн-алгоритм; регуляризацiя

Повний текст:

PDF (English)

Посилання


Bargi, A., Xu, R. Y. D., & Piccardi, M. (2018). AdOn HDP-HMM: An adaptive online model for segmentation and classification of sequential data. IEEE Transactions on Neural Networks and Learning Systems, PP, 1–16. https://doi.org/10.1109/tnnls.2017.2742058

Kohlmorgen, J., & Lemm, S. (2001). A dynamic HMM for on-line segmentation of sequential data. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic NIPS'01 (pp. 793–800). Cambridge, MA, USA: MIT Press.

Harchaoui, Z., Vallet, F., Lung-Yut-Fong, A., & Cappe, O. (2009). A regularized kernel-based approach to unsupervised audio segmentation. In 2009 IEEE International Conference on Acoustics, Speech and Signal Processing (pp. 1665–1668). https://doi.org/10.1109/icassp.2009.4959921

Muandet, K., Fukumizu, K., Sriperumbudur, B., & Schölkopf, B. (2017). Kernel mean embedding of distributions: A review and beyond. Foundations and Trends® in Machine Learning, 10, 1–141. https://doi.org/10.1561/2200000060

Smola, A., Gretton, A., Song, L., & Schölkopf, B. (2007). A Hilbert space embedding for distributions. In M. Hutter, R. A. Servedio, & E. Takimoto (Eds.), Algorithmic Learning Theory (pp. 13–31). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-75225-7_5

Song, L., Boots, B., Siddiqi, S. M., Gordon, G., & Smola, A. (2010a). Hilbert space embeddings of hidden Markov models. In Proceedings of the 27th International Conference on International Conference on Machine Learning ICML'10 (pp. 991–998). USA: Omnipress.

Song, L., Huang, J., Smola, A., & Fukumizu, K. (2009a). Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning ICML 09 (pp. 961–968). New York, NY, USA: ACM. https://doi.org/10.1145/1553374.1553497

Bauer, F., Pereverzev, S., & Rosasco, L. (2007). On regularization algorithms in learning theory. Journal of Complexity, 23, 52–72. https://doi.org/10.1016/j.jco.2006.07.001

Nair, M. T. (2017). A discrete regularization method for ill-posed operator equations. The Journal of Analysis, 25, 253–266. https://doi.org/10.1007/s41478-017-0047-4

Kriukova, G., Pereverzyev, S., Jr, & Tkachenko, P. (2017a). Nyström type subsampling analyzed as a regularized projection. Inverse Problems, 33, 074001. https://doi.org/10.1088/1361-6420/33/7/074001

Song, L., Huang, J., Smola, A., & Fukumizu, K. (2009b). Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning ICML '09 (pp. 961–968). New York, NY, USA: ACM. https://doi.org/10.1145/1553374.1553497

Song, L., Boots, B., Siddiqi, S. M., Gordon, G., & Smola, A. (2010b). Hilbert space embeddings of hidden Markov models. In Proceedings of the 27th International Conference on International Conference on Machine Learning ICML'10 (pp. 991–998). USA: Omnipress.

Kimeldorf, G., & Wahba, G. (1971). Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis and Applications, 33, 82–95. https://doi.org/10.1016/0022-247x(71)90184-3

Kriukova, G., Panasiuk, O., Pereverzyev, S. V., & Tkachenko, P. (2016). A linear functional strategy for regularized ranking. Neural Networks, 73, 26–35. https://doi.org/10.1016/j.neunet.2015.08.012

Lu, S., & Pereverzev, S. V. (2013). Regularization theory for ill-posed problems: selected topics. Inverse and Ill-Posed Problems Series. Berlin: De Gruyter. https://doi.org/10.1515/9783110286496

Smola, A. J., & Schökopf, B. (2000). Sparse greedy matrix approximation for machine learning. In Proceedings of the Seventeenth International Conference on Machine Learning ICML '00 (pp. 911–918). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Williams, C., & Seeger, M. (2001). Using the Nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems 13 (pp. 682–688). MIT Press.

Kriukova, G., Shvai, N., & Pereverzyev, S. V. (2017b). Application of regularized ranking and collaborative filtering in predictive alarm algorithm for nocturnal hypoglycemia prevention. In 2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS) (pp. 634–638). volume 2. https://doi.org/10.1109/idaacs.2017.8095169

Fong, S., Fiaidhi, J., Mohammed, S., & Moutinho, L. (2017). Real-time decision rules for diabetes therapy management by data stream mining. IT Professional, PP, 1. https://doi.org/10.1109/mitp.2017.265104658

Goh, C. Y., Dauwels, J., Mitrovic, N., Asif, M. T., Oran, A., & Jaillet, P. (2012). Online map-matching based on hidden Markov model for real-time traffic sensing applications. In 2012 15th International IEEE Conference on Intelligent Transportation Systems (pp. 776–781). https://doi.org/10.1109/itsc.2012.6338627

Krajzewicz, D., Erdmann, J., Behrisch, M., & Bieker, L. (2012). Recent development and applications of SUMO — Simulation of Urban MObility. International Journal On Advances in Systems and Measurements, 5, 128–138.

OpenStreetMap contributors (2017). Planet dump retrieved from https://planet.osm.org. URL: https://www.openstreetmap.org.

Newson, P., & Krumm, J. (2009). Hidden Markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems GIS '09 (pp. 336–343). New York, NY, USA: ACM. https://doi.org/10.1145/1653771.1653818

Sudakov, O., Kriukova, G., Natarov, R., Gaidar, V., Maximyuk, O., Radchenko, S., & Isaev, D. (2017). Distributed system for sampling and analysis of electroencephalograms. In 2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS) (pp. 306–310). volume 1. https://doi.org/10.1109/idaacs.2017.8095095






Copyright (c) 2018 Galyna Kriukova

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.