РАСПОЗНАВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ИСПОЛЬЗОВАНИЕМ КОНЕЧНЫХ АВТОМАТОВ И МАШИННОГО ОБУЧЕНИЯ

Распознавание последовательностей является критически важной задачей во многих дисциплинах. Традиционные методы, основанные на конечных автоматах (КА), обеспечивают структурированное представление данных и высокую интерпретируемость, однако их гибкость ограничена. Современные алгоритмы машинного обучения (ML) демонстрируют высокую точность, но требуют значительных вычислительных ресурсов. Объединение этих парадигм может повысить эффективность распознавания сложных последовательностей. Данное исследование посвящено интеграции КА с методами ML для решения задач анализа последовательностей. Рассматриваются три различные области применения: классификация текстов (определение спама), распознавание генетических последовательностей, связанных с болезнью Альцгеймера, и идентификация жестов на основе изображений.

Для каждой области были разработаны и протестированы гибридные модели, объединяющие детерминированные конечные автоматы (DFA), недетерминированные конечные автоматы (NFA) и алгоритмы машинного обучения, такие как Random Forest, Gradient Boosting и многослойные перцептроны (MLP). Экспериментальные результаты свидетельствуют о том, что данные гибридные модели достигают производительности, сопоставимой с традиционными методами ML, а в некоторых случаях обеспечивают более точные прогнозы. 

При классификации спама нейронные сети показали наилучшие результаты, при этом комбинации КА с нейронными сетями продемонстрировали схожую эффективность.

В анализе генетических последовательностей модели на основе градиентного бустинга показали наивысшую точность, а интеграция КА позволила сохранить высокий уровень производительности при повышении интерпретируемости. 

В задаче распознавания жестов наиболее эффективными оказались подходы, основанные на нейронных сетях, однако интеграция КА с ансамблевыми методами позволила добиться высоких прогностических показателей, превосходящих традиционные ML-модели.

В заключение, интеграция конечных автоматов и машинного обучения представляет собой перспективное направление в анализе последовательностей. Будущие исследования могут быть направлены на оптимизацию архитектур моделей и их применение в других областях, требующих высокой точности распознавания сложных структур.

1. Determinism and Nondeterminism in Finite Automata with Advice / Р. Ďuriš et al // In Lecture notes in computer science. – 2018. – Р. 3-16. https://doi.org/10.1007/978-3-319-98355-4_1.

2. Veanes M. Applications of symbolic finite automata / M. Veanes // In Lecture notes in computer science. – 2013. – Р. 16-23. https://doi.org/10.1007/978-3-642-39274-0_3.

3. An introduction to learning automata and Optimization / J.K. Kordestani et al // In Intelligent systems reference library. – 2021. Р. 1-50. https://doi.org/10.1007/978-3-030-76291-9_1.

4. Hong P. Gesture modeling and recognition using finite state machines / P. Hong, M. Turk, T.S. Huang // IEEE. – 2002. https://doi.org/10.1109/afgr.2000.840667.

5. Decombinator: a tool for fast, efficient gene assignment in T-cell receptor sequences using a finite state machine / N. Thomas et al // Bioinformatics. – 2013. – № 29(5). – Р. 542-550. https://doi.org/10.1093/bioinformatics/btt004.

6. Road network extraction: a neural-dynamic framework based on deep learning and a finite state machine / J. Wang et al // International Journal of Remote Sensing. – 2015. – № 36(12). – Р. 31443169. https://doi.org/10.1080/01431161.2015.1054049.

7. Constrained training of recurrent neural networks for automata learning / В.К. Aichernig et al // In Lecture notes in computer science. – 2022. – Р. 155-172. https://doi.org/10.1007/978-3-03117108-6_10.

8. Privacy attacks to the 4G and 5G cellular paging protocols using side channel information / S.R. Hussain et al // in Proc. Netw. Distrib. Syst. Security Symp. (NDSS). – 2019. – Р. 1-15.

9. Baray E. WLAN security protocols and WPA3 security approach measurement through aircrackng technique / E. Baray, N.K. Ojha // in Proc. 5th Int. Conf. Comput. Methodologies Commun. (ICCMC). – 2021. – Р. 23-30.

10. Vanhoef M. Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd / M. Vanhoef, E. Ronen // 2020 IEEE Symposium on Security and Privacy (SP). – IEEE, 2020. – P. 517533.