2020/09/10 by Reda Marzouk, Marzouk, Reda
Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2009.06398
openalex publication_date 2020/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work aims at shedding some light on connections between finite state\nmachines (FSMs), and recurrent neural networks (RNNs). Examined connections in\nthis master's thesis is threefold: the extractability of finite state machines\nfrom recurrent neural networks, learnability aspects and computationnal links.\nWith respect to the former, the long-standing clustering hypothesis of RNN\nhidden state space when trained to recognize regular languages was explored,\nand new insights into this hypothesis through the lens of recent advances of\nthe generalization theory of Deep Learning are provided. As for learnability,\nan extension of the active learning framework better suited to the problem of\napproximating RNNs with FSMs is proposed, with the aim of better formalizing\nthe problem of RNN approximation by FSMs. Theoretical analysis of two possible\nscenarions in this framework were performed. With regard to computability, new\ncomputational results on the distance and the equivalence problem between RNNs\ntrained as language models and different types of weighted finite state\nmachines were given.\n