Поиск оптимальной последовательности событий автоматной модели с использованием искусственных нейронных сетей

Содержание

Конечные автоматы активно применяются в различных областях науки и техники, особенно в области информатики. Одной из областей применения автоматов является моделирование [1]. Описание процессов в виде конечных автоматов удобно для человека. В случае сложных процессов допустимо описание процесса в виде композиции автоматов [2]. Композиция автоматов все также понятна для человека и может быть заменена одним большим автоматом.

Одной из задач, которую можно решать над автоматными моделями – это поиск кратчайших последовательностей входных символов (событий) из начального состояния в одно из конечных состояний. Так как одним из возможных представлений функции переходов является диаграмма состояний или граф переходов, то задача поиска оптимальной последовательности событий сводится к поиску кратчайшего расстояния от вершины начального состояния до вершины одного из конечных состояний.

Есть множество эффективных алгоритмов поиска пути в графе, однако, сложность алгоритмов зависит от количества вершин и ребер графа. Также задача усложняется необходимостью проверки каждой конечной вершины. В связи с этим ставится задача построения функции $f:Q arrow X$, выбирающей следующий входной символ таким образом, чтобы за минимальное количество символов автомат достиг одного из конечных состояний.

Для построения данной функции создадим искусственную нейронную сеть прямого распространения, которая принимает состояние автомата (представленное в One-Hot кодировке), а на выходе выдает вектор размерности $| X |$, представляющий меру близости до конечного состояния.

Рассмотрим процедуру обучения данной нейронной сети.

Инициализация. Конечный автомат $A$ переводится в состояние $q_{0}$. Искусственная нейронная сеть $N$ инициализируется случайными малыми весами. Список $D$ пуст. Стек $S$ пуст.

Шаг 1. Искусственная нейронная сеть N по текущему состоянию $q_{i}$ вычисляет меру близости. По мере близости выбирается следующий входной символ $x_{i}$. При $(q_{i},x_{i}) \in D$, $x_{i}$ заменяется на случайно выбранный другой элемент множества $X$. Кортеж $(q_{i},x_{i})$ добавляется в стек $S$. Автомат $A$ получает на вход символ $x_{i}$ и переходит в следующее состояние $q_{i + 1}$.

Шаг 2. Если $q_{i + 1} \in F$ переходим к шагу 3, в противном случае – переходим к шагу 1.

Шаг 3. Из стека $S$ по очереди извлекаются кортежи $( q_{i},x_{i})$, дополнятся порядковым номером в стеке и записываются в список $\text{D}$. Если $( q_{i},x_{i},\ n_{i} )$ уже был записан в списке $D$, то номер обновляется минимальным значением.

Шаг 4. Нейронная сеть $N$ обучается методом обратного распространения ошибки. Для каждого $q_{i}\ $формируется вектор размерности $| X |$. Если для $( q_{i},x_{j}, n_{j} )$, есть значения в $D$, то $j$-ый компонент вектора будет равен $$1 - \frac{n_{j}}{\sum_{( q_{i},x_{k} ) \in D}n_{k}}$$ В противном случае – $j$-ый компонент вектора равен $0$.

Шаг 5. При необходимости продолжить обучение. Конечный автомат $A$ переводится в состояние $q_{0}$. Переходим к шагу 1.

Данный алгоритм был реализован с помощью фреймворка машинного обучения TensorFlow. Результаты тестирования на различных случайно сгенерированных графах (количество вершин от 10 до 10000) подтверждают работоспособность данного подхода.

Литература #

Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб., Питер, 2009. — 176 с.
Гуренко В. В. Введение в теорию автоматов: Электронное учебное издание / В. В. Гуренко. — Москва: МГТУ им. Н.Э. Баумана, 2013. - 62 с.