Пофонемное распознавание как задача классификации рядов на множестве последовательностей элементов сложных объектов с применением усовершенствованного trie-дерева

Обложка

Цитировать

Полный текст

Аннотация

Последовательности, в том числе последовательности векторов, применимы в любых предметных областях. Последовательности скалярных значений или векторов (ряды) могут быть порождены последовательностями более высокого порядка, например: последовательностями состояний, элементов сложных объектов. Работа посвящена применению усовершенствованного trie-дерева в задаче классификации ряда на множестве последовательностей элементов сложных объектов методом динамического программирования. Рассмотрены сферы применения динамического программирования. Показано, что динамическое программирование приспособлено к многошаговым операциям вычисления аддитивных (мультипликативных) мер подобия / различия. Утверждается, что усовершенствованное trie-дерево применимо в задаче классификации ряда на множестве последовательностей элементов сложных объектов методом динамического программирования при использовании таких мер подобия / различия. Выполнен анализ иерархических представлений множеств последовательностей. Описаны преимущества, которые обеспечивает усовершенствованное trie-дерево по сравнению с традиционными представлениями других сильноветвящихся деревьев. Разработано формальное описание усовершенствованного trie-дерева. Дано пояснение ранее полученным данным о существенном приросте скорости операций добавления и удаления последовательностей в усовершенствованном trie-дереве относительно использования массива с индексной таблицей (24 и 380 раз, соответственно). Выполнена постановка задачи пофонемного распознавания речевых команд как задачи классификации ряда на множестве последовательностей элементов сложных объектов и изложен метод её решения. Разработан метод классификации ряда на множестве последовательностей элементов сложных объектов с применением усовершенствованного trie-дерева. Он исследован на примере пофонемного распознавания с иерархическим представлением словаря классов речевых команд. В этом методе распознавание речевых команд выполняют в процессе обхода усовершенствованного trie-дерева, хранящего множество транскрипций речевых команд – последовательностей транскрипционных символов, которые обозначают классы звуков. Численные исследования показали, что классификация ряда как последовательности элементов сложных объектов повышает частоту правильной классификации по сравнению с классификацией ряда на множестве рядов, а применение усовершенствованного trie-дерева сокращает затраты времени на классификацию.

Об авторах

Г. В Дорохина

ФГБНУ "Институт проблем искусственного интеллекта"

Email: sgv_iai@mail.ru
улица Артёма 118b

Список литературы

  1. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона + CD // М.: ДМК Пресс. 2010. 272 с.
  2. Кнут Д.Э. Искусство программирования. Т.3: Сортировка и поиск // М.: Вильямс. 2000. 832 с.
  3. Briandais R. File searching using variable-length keys // Proc. Western Joint Computer Conf. 1959. pp. 295–298.
  4. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология // СПб.: Невский Диалект; БХВ-Петербург. 2003. 654 с.
  5. Liao T.F., Bolano D., Brzinsky-Fay C., Cornwell B., Fasang A.E., Helske S., Piccarreta R., Raab M., Ritschard G., Struffolino E., Studer M. Sequence analysis: Its past, present, and future. Social science research. 2022. vol. 107. doi: 10.1016/j.ssresearch.2022.102772.
  6. Mathew S., Peat G., Parry E., Sokhal B.S., Yu D. Applying sequence analysis to uncover 'real-world' clinical pathways from routinely collected data: a systematic review. Journal of Clinical Epidemiology. 2024. vol. 166. doi: 10.1016/j.jclinepi.2023.111226.
  7. Громов В.А., Мазайшвили К.В., Заикин П.В., Николаев Е.Н., Бесчастнов Ю.Н., Зворыкина Е.И., Паринов А.А., Незнанов А.А. Различение хаотических и регулярных временных рядов для идентификации состояния артериовенозной фистулы // Вестник кибернетики. 2022. № 1(45). С. 72–82.
  8. Ковалева К.А., Яхонтова И.М. Теория исследования и разработки методов и моделей прогнозирования временных рядов с приращением в страховании // Новые технологии. 2019. № 4. С. 239–248.
  9. Зюсько К.Д. Прогноз спроса на товар с помощью нейронных сетей в условиях меняющейся размерности входных данных // Экономика и качество систем связи. 2020. № 1 (15). С. 36–41.
  10. Луценко Е.В. Применение автоматизированного системно-когнитивного анализа банковских баз данных по операциям с кредитными картами для количественной оценки риска мошенничества // Научный журнал КубГАУ. 2021. № 172. С. 82–172.
  11. Кузьмин В.Н., Менисов А.Б. Исследование путей и способов повышения результативности выявления компьютерных атак на объекты критической информационной инфраструктуры // Информационно-управляющие системы. 2022. № 4. С. 29–43.
  12. Leichtnam L., Totel E., Prigent N., Me L. Sec2graph: Network attack detection based on novelty detection on graph structured data // Detection of Intrusions and Malware, and Vulnerability Assessment: 17th International Conference, DIMVA. Springer International Publishing, 2020. pp. 238–258.
  13. Жукова Н.А. Онтологические модели трансформации данных о состоянии технических объектов // Онтология проектирования. 2019. Т. 9. № 3(33). С. 345–360.
  14. Nguyen D., Luo W., Nguyen T., Venkatesh S., Phung D. Sqn2Vec: Learning Sequence Representation via Sequential Patterns with a Gap Constraint. Machine Learning and Knowledge Discovery in Databases. Proceedings of the European Conference, ECML PKDD (Part II). 2019. pp. 569–584.
  15. Fradkin D., Morchen F. Mining sequential patterns for classification. Knowledge and Information Systems. 2015. № 45 (3). pp. 731–749.
  16. Привалов А.Н., Смирнов В.А. Метод нечеткого сравнения строк для обнаружения фейковых сайтов // Известия ТулГУ. Технические науки. 2022. № 2. С. 184–191.
  17. Blanchard P. Sequence Analysis. Encyclopedia of Research Methods. London: Sage Publications Ltd. 2020. URL: https://www.researchgate.net/publication/342232021_Sequence_Analysis (дата обращения: 15.05.2024).
  18. Vanasse A., Courteau J., Courteau M., Benigeri M., Chiu Y.M., Dufour I., Couillard S., Larivée P., Hudon C. Healthcare utilization after a first hospitalization for COPD: a new approach of State Sequence Analysis based on the '6W' multidimensional model of care trajectories. BMC Health Serv. Res. 2020. vol. 20(1). doi: 10.1186/s12913-020-5030-0.
  19. Su H., Liu S., Zheng B., Zhou X., Zheng K. A survey of trajectory distance measures and performance evaluation. The VLDB Journal. 2020. № 29. pp. 3–32.
  20. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах: Учеб. Пособие. М.: Высш. школа, 1979. 125 с.
  21. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учебное пособие. Нижний Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.
  22. Баширзаде Л.И., Алиев Г.С. Применение динамического программирования для моделирования процессов принятия решений // Архивариус. 2022. № 3 (66). С. 51–55.
  23. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. К.: Наук. думка, 1987. 262 с.
  24. Шелепов В.Ю., Дорохин О.А., Засыпкин А.В., Червин Н.А. О некоторых подходах к проблеме компьютерного распознавания устной русской речи // Труды Междунар. конф. «Знание – Диалог – Решение». 1997. Т. 1. С. 234–240.
  25. Alshehri M., Coenen F., Dures K. Sub-sequence-based dynamic time warping. Proceedings of the 11th International Conference on Knowledge Discovery and Information Retrieval. 2019. pp. 274–281.
  26. Deriso D., Boyd S. A general optimization framework for dynamic time warping // Optimization and Engineering. 2023. vol. 24. pp. 1411–1432.
  27. Wang L., Koniusz P. Uncertainty-DTW for Time Series and Sequences. European Conference on Computer Vision (ECCV 2022). Cham: Springer Nature Switzerland. 2022. vol. 13681. pp. 176–195.
  28. Bringmann K., Fischer N., Hoog I., Kipouridis E., Kociumaka T., Rotenberg E. Dynamic Time Warping // Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Publisher Society for Industrial and Applied Mathematics. 2024. pp. 208–242.
  29. Jain V., Fokow V., Wicht J., Wetzker U. A Dynamic Time Warping Based Method to Synchronize Spectral and Protocol Domains for Troubleshooting Wireless Communication // IEEE Access. 2023. vol. 11. pp. 64668–64678.
  30. Козлов А.В., Саввина Г.В., Шелепов В.Ю. Система пофонемного распознавания отдельно произносимых слов // Искусственный интеллект. 2003. № 1. С. 156–165.
  31. Дорохина Г.В. Модификация алгоритма DTW для пофонемного распознавания слов // Проблемы искусственного интеллекта. 2015. № 0(1). С. 38–49.
  32. Дорохина Г.В. Анализ методов распознавания речевых команд на основе алгоритма DTW // Труды шестого междисциплинарного семинара «Анализ разговорной русской речи» (АР3-2012) (27-28 августа 2012. г. Санкт-Петербург). 2012. С. 29–34.
  33. Васильев В.И., Шевченко А.И., Эш С.Н. Принцип редукции в задачах обнаружения закономерностей: Монография. Донецк, 2009. 340 с.
  34. Бурибаева А.К., Дорохина Г.В., Ниценко А.В., Шелепов В.Ю. Сегментация и дифонное распознавание речевых сигналов // Труды СПИИРАН. 2014. Т. 31. № 8. С. 20–42.
  35. Дорохина Г.В., Павлюкова А.П. Модуль морфологического анализа слов русского языка // Искусственный интеллект. 2004. № 3. С. 636–642.
  36. Дорохина Г.В. Патент на изобретение № UA 78806 «Устройство для хранения и поиска строковых величин и способ хранения и поиска строковых величин». собственник: Институт проблем искусственного интеллекта. Промышленная собственность. 2007. опубл. 25.04.2007.
  37. Дорохина Г.В., Павлыш В.Н. Способ представления множеств последовательностей // Информатика и кибернетика. 2016. № 1(3). С. 56–64.
  38. Дорохина Г.В. Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования // Искусственный интеллект. 2009. № 4. C. 338–343.
  39. Финаев В.И., Дорохина Г.В. Применения усовершенствованных деревьев цифрового поиска // Проблемы искусственного интеллекта. 2019. № 4 (15). С. 62–77.
  40. Bantay L., Abonyi J. Frequent pattern mining-based log file partition for process mining // Engineering Applications of Artificial Intelligence. 2023. vol. 123. doi: 10.1016/j.engappai.2023.106221.
  41. Xing Z., Pei J., Keogh J. A brief survey on sequence classification // SIGKDD Explor. 2010. vol. 12(1). pp. 40–48.
  42. Atar R.H., Bhosale D.S. Pattern Based Sequence Classification // International Journal of Advanced Research in Science, Communication and Technology (IJARSCT). 2023. vol. 3. № 1. pp. 390–396.
  43. Lazzari N., Poltronieri A., Presutti V. Classifying sequences by combining context-free grammars and OWL ontologies // European Semantic Web Conference. Cham: Springer Nature Switzerland, 2023. С. 156–173.
  44. Crochemore M., Lecroq T, Liu L., Ozsu T. Encyclopedia of Database Systems. Verlag: Springer. 2009. pp. 3179–3182.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».