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

Автор(и)

  • Galyna Kriukova Національний університет «Києво-Могилянська академія», Україна

DOI:

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

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

прихована марковська модель, обробка потоку даних, г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в.

Біографія автора

Galyna Kriukova, Національний університет «Києво-Могилянська академія»

Кандидат фiзико-математичних наук, доцент кафедри математики Нацiонального унiверситету «Києво-Могилянська академiя». Сфера наукових iнтересiв - оберненi задачi, машинне навчання, математичне моделювання.

Посилання

  1. 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
  2. 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.
  3. 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
  4. 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
  5. 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
  6. 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.
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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.
  13. 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
  14. 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
  15. 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
  16. 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.
  17. 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.
  18. 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
  19. 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
  20. 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
  21. 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.
  22. OpenStreetMap contributors (2017). Planet dump retrieved from https://planet.osm.org. URL: https://www.openstreetmap.org.
  23. 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
  24. 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

##submission.downloads##

Як цитувати

[1]
Kriukova, G. 2018. Метод дискретної регуляризацiї для прихованих марковських моделей, занурених у гiльбертiв простiр iз вiдтворюючим ядром. Могилянський математичний журнал. 1, (Груд 2018), 15–20. DOI:https://doi.org/10.18523/2617-7080i2018p15-20.

Номер

Том 1 (2018): Могилянський математичний журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2018 Galyna Kriukova

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.

б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.

в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)

г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).