On Computability, Learnability and Extractability of Finite State Machines from Recurrent Neural Networks

• URL: http://arxiv.org/abs/2009.06398v1
• Date: Thu, 10 Sep 2020 15:55:30 GMT
• Title: On Computability, Learnability and Extractability of Finite State Machines from Recurrent Neural Networks
• Authors: Reda Marzouk
• Abstract summary: This work aims at shedding some light on connections between finite state machines (FSMs), and recurrent neural networks (RNNs) Examined connections in this master's thesis is threefold: the extractability of finite state machines from recurrent neural networks, learnability aspects and computationnal links.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work aims at shedding some light on connections between finite state machines (FSMs), and recurrent neural networks (RNNs). Examined connections in this master's thesis is threefold: the extractability of finite state machines from recurrent neural networks, learnability aspects and computationnal links. With respect to the former, the long-standing clustering hypothesis of RNN hidden state space when trained to recognize regular languages was explored, and new insights into this hypothesis through the lens of recent advances of the generalization theory of Deep Learning are provided. As for learnability, an extension of the active learning framework better suited to the problem of approximating RNNs with FSMs is proposed, with the aim of better formalizing the problem of RNN approximation by FSMs. Theoretical analysis of two possible scenarions in this framework were performed. With regard to computability, new computational results on the distance and the equivalence problem between RNNs trained as language models and different types of weighted finite state machines were given.

Related papers

• Rethinking Spiking Neural Networks as State Space Models [1.9775291915550175]
  Spiking neural networks (SNNs) are posited as a biologically plausible alternative to conventional neural architectures. We present a novel class of spiking neuronal model grounded in state space models. Our models attain state-of-the-art performance among SNN models across diverse long-range dependency tasks.
  arXiv  Detail & Related papers  (2024-06-05T04:23:11Z)
• Reasoning Algorithmically in Graph Neural Networks [1.8130068086063336]
  We aim to integrate the structured and rule-based reasoning of algorithms with adaptive learning capabilities of neural networks. This dissertation provides theoretical and practical contributions to this area of research.
  arXiv  Detail & Related papers  (2024-02-21T12:16:51Z)
• Neural Network with Local Converging Input (NNLCI) for Supersonic Flow Problems with Unstructured Grids [0.9152133607343995]
  We develop a neural network with local converging input (NNLCI) for high-fidelity prediction using unstructured data. As a validation case, the NNLCI method is applied to study inviscid supersonic flows in channels with bumps.
  arXiv  Detail & Related papers  (2023-10-23T19:03:37Z)
• Linear Leaky-Integrate-and-Fire Neuron Model Based Spiking Neural Networks and Its Mapping Relationship to Deep Neural Networks [7.840247953745616]
  Spiking neural networks (SNNs) are brain-inspired machine learning algorithms with merits such as biological plausibility and unsupervised learning capability. This paper establishes a precise mathematical mapping between the biological parameters of the Linear Leaky-Integrate-and-Fire model (LIF)/SNNs and the parameters of ReLU-AN/Deep Neural Networks (DNNs)
  arXiv  Detail & Related papers  (2022-05-31T17:02:26Z)
• Knowledge Enhanced Neural Networks for relational domains [83.9217787335878]
  We focus on a specific method, KENN, a Neural-Symbolic architecture that injects prior logical knowledge into a neural network. In this paper, we propose an extension of KENN for relational data.
  arXiv  Detail & Related papers  (2022-05-31T13:00:34Z)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• Quasi-orthogonality and intrinsic dimensions as measures of learning and generalisation [55.80128181112308]
  We show that dimensionality and quasi-orthogonality of neural networks' feature space may jointly serve as network's performance discriminants. Our findings suggest important relationships between the networks' final performance and properties of their randomly initialised feature spaces.
  arXiv  Detail & Related papers  (2022-03-30T21:47:32Z)
• Fusing the Old with the New: Learning Relative Camera Pose with Geometry-Guided Uncertainty [91.0564497403256]
  We present a novel framework that involves probabilistic fusion between the two families of predictions during network training. Our network features a self-attention graph neural network, which drives the learning by enforcing strong interactions between different correspondences. We propose motion parmeterizations suitable for learning and show that our method achieves state-of-the-art performance on the challenging DeMoN and ScanNet datasets.
  arXiv  Detail & Related papers  (2021-04-16T17:59:06Z)
• Progressive Tandem Learning for Pattern Recognition with Deep Spiking Neural Networks [80.15411508088522]
  Spiking neural networks (SNNs) have shown advantages over traditional artificial neural networks (ANNs) for low latency and high computational efficiency. We propose a novel ANN-to-SNN conversion and layer-wise learning framework for rapid and efficient pattern recognition.
  arXiv  Detail & Related papers  (2020-07-02T15:38:44Z)
• A Chain Graph Interpretation of Real-World Neural Networks [58.78692706974121]
  We propose an alternative interpretation that identifies NNs as chain graphs (CGs) and feed-forward as an approximate inference procedure. The CG interpretation specifies the nature of each NN component within the rich theoretical framework of probabilistic graphical models. We demonstrate with concrete examples that the CG interpretation can provide novel theoretical support and insights for various NN techniques.
  arXiv  Detail & Related papers  (2020-06-30T14:46:08Z)
• Going in circles is the way forward: the role of recurrence in visual inference [0.0]
  State-of-the-art neural network models for visual recognition rely heavily or exclusively on feedforward computation. This important insight suggests that computational neuroscientists may not need to engage recurrent computation. We argue that FNNs are a special case of RNNs and that computational neuroscientists and engineers should engage recurrence to understand how brains and machines can achieve greater and more flexible computational depth.
  arXiv  Detail & Related papers  (2020-03-26T19:53:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.