A provably stable neural network Turing Machine

• URL: http://arxiv.org/abs/2006.03651v4
• Date: Sun, 18 Sep 2022 16:20:48 GMT
• Title: A provably stable neural network Turing Machine
• Authors: John Stogin, Ankur Mali and C Lee Giles
• Abstract summary: We introduce a neural stack architecture, including a differentiable parametrized stack operator that approximates stack push and pop operations. Using the neural stack with a recurrent neural network, we introduce a neural network Pushdown Automaton (nnPDA) and prove that nnPDA with finite/bounded neurons and time can simulate any PDA. We prove that differentiable nnTM with bounded neurons can simulate Turing Machine (TM) in real-time.
• Score: 13.615420026818038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a neural stack architecture, including a differentiable parametrized stack operator that approximates stack push and pop operations for suitable choices of parameters that explicitly represents a stack. We prove the stability of this stack architecture: after arbitrarily many stack operations, the state of the neural stack still closely resembles the state of the discrete stack. Using the neural stack with a recurrent neural network, we introduce a neural network Pushdown Automaton (nnPDA) and prove that nnPDA with finite/bounded neurons and time can simulate any PDA. Furthermore, we extend our construction and propose new architecture neural state Turing Machine (nnTM). We prove that differentiable nnTM with bounded neurons can simulate Turing Machine (TM) in real-time. Just like the neural stack, these architectures are also stable. Finally, we extend our construction to show that differentiable nnTM is equivalent to Universal Turing Machine (UTM) and can simulate any TM with only \textbf{seven finite/bounded precision} neurons. This work provides a new theoretical bound for the computational capability of bounded precision RNNs augmented with memory.

Related papers

• Multi-layer random features and the approximation power of neural networks [4.178980693837599]
  We prove that a reproducing kernel Hilbert space contains only functions that can be approximated by the architecture. We show that if eigenvalues of the integral operator of the NNGP decay slower than $k-n-frac23$ where $k$ is an order of an eigenvalue, our theorem guarantees a more succinct neural network approximation than Barron's theorem.
  arXiv  Detail & Related papers  (2024-04-26T14:57:56Z)
• The Expressive Leaky Memory Neuron: an Efficient and Expressive Phenomenological Neuron Model Can Solve Long-Horizon Tasks [64.08042492426992]
  We introduce the Expressive Memory (ELM) neuron model, a biologically inspired model of a cortical neuron. Our ELM neuron can accurately match the aforementioned input-output relationship with under ten thousand trainable parameters. We evaluate it on various tasks with demanding temporal structures, including the Long Range Arena (LRA) datasets.
  arXiv  Detail & Related papers  (2023-06-14T13:34:13Z)
• Token Turing Machines [53.22971546637947]
  Token Turing Machines (TTM) is a sequential, autoregressive Transformer model with memory for real-world sequential visual understanding. Our model is inspired by the seminal Neural Turing Machine, and has an external memory consisting of a set of tokens which summarise the previous history.
  arXiv  Detail & Related papers  (2022-11-16T18:59:18Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Neuromorphic Computing is Turing-Complete [0.0]
  Neuromorphic computing is a non-von Neumann computing paradigm that performs computation by emulating the human brain. Neuromorphic systems are extremely energy-efficient and known to consume thousands of times less power than CPU and GPU. We devise neuromorphic circuits for computing all the mu-recursive functions and all the mu-recursive operators.
  arXiv  Detail & Related papers  (2021-04-28T19:25:01Z)
• Continual Learning with Deep Artificial Neurons [0.0]
  We introduce Deep Artificial Neurons (DANs), which are themselves realized as deep neural networks. We demonstrate that it is possible to meta-learn a single parameter vector, which we dub a neuronal phenotype, shared by all DANs in the network. We show that a suitable neuronal phenotype can endow a single network with an innate ability to update its synapses with minimal forgetting.
  arXiv  Detail & Related papers  (2020-11-13T17:50:10Z)
• Reservoir Memory Machines as Neural Computers [70.5993855765376]
  Differentiable neural computers extend artificial neural networks with an explicit memory without interference. We achieve some of the computational capabilities of differentiable neural computers with a model that can be trained very efficiently.
  arXiv  Detail & Related papers  (2020-09-14T12:01:30Z)
• Reservoir memory machines [79.79659145328856]
  We propose reservoir memory machines, which are able to solve some of the benchmark tests for Neural Turing Machines. Our model can also be seen as an extension of echo state networks with an external memory, enabling arbitrarily long storage without interference.
  arXiv  Detail & Related papers  (2020-02-12T01:45:00Z)
• Non-linear Neurons with Human-like Apical Dendrite Activations [81.18416067005538]
  We show that a standard neuron followed by our novel apical dendrite activation (ADA) can learn the XOR logical function with 100% accuracy. We conduct experiments on six benchmark data sets from computer vision, signal processing and natural language processing.
  arXiv  Detail & Related papers  (2020-02-02T21:09:39Z)
• On the computational power and complexity of Spiking Neural Networks [0.0]
  We introduce spiking neural networks as a machine model where---in contrast to the familiar Turing machine---information and the manipulation thereof are co-located in the machine. We introduce canonical problems, define hierarchies of complexity classes and provide some first completeness results.
  arXiv  Detail & Related papers  (2020-01-23T10:40:16Z)

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.