Генерация автоматов на основе рекуррентный нейросетей и автоматического выбора кластеризации

Аннотация

Введение: задача индуцирования регулярной грамматики состоит в построении детерминированных конечных ав-
томатов по списку слов-примеров и слов-контрпримеров из неизвестного регулярного языка. Эта задача является од-
ной из центральных в теории формальных языков и сопряженных с ней областях. Одним из наиболее успешных ее
решений является обучение рекуррентной нейронной сети классификации слов и последующая кластеризация векторов
в пространстве весов. Однако результат кластеризации не всегда позволяет построить непротиворечивый автомат.
Более сложные модели для индуцирования грамматики требовательны к памяти, времени обучения и числу трениро-
вочных примеров. Цель: построение модели для индуцирования грамматики, использующей новые методы машинного
обучения. Методы: в качестве классификатора применена рекуррентная нейронная сеть, использующая предложенную
авторами функцию ошибки. Для кластеризации реализован метод совместного выбора и настройки гиперпараметров
алгоритма кластеризации для различных мер оценки. Результаты: проведено тестирование на наборах данных, соот-
ветствующих десяти различным регулярным грамматикам и, соответственно, десяти различным детерминированным
автоматам. По результатам тестирования разработанная модель корректно синтезирует автоматы с числом состояний
и с числом входных символов не более пяти. Для четырех из семи успешно индуцированных грамматик построенный
автомат получился минимальным. Для трех наборов данных Tech. автомат построить не удалось — либо из-за недо-
статочности числа кластеров в предложенном разбиении, либо из-за невозможности построить из этого разбиения не-
противоречивый автомат. Обсуждение: применение алгоритма поиска наибольшего правдоподобия между кластерами
векторов и соответствующими состояниями автомата для принятия решений в случае нахождения противоречий могло
бы расширить область применимости модели.