Nondeterministic Stacks in Neural Networks

• URL: http://arxiv.org/abs/2304.12955v2
• Date: Thu, 18 May 2023 01:56:21 GMT
• Title: Nondeterministic Stacks in Neural Networks
• Authors: Brian DuSell
• Abstract summary: We develop a differentiable data structure that efficiently simulates a nondeterministic pushdown automaton. We show that this raises their formal recognition power to arbitrary context-free languages. We also show that an RNN augmented with a nondeterministic stack is capable of surprisingly powerful behavior.
• Score: 0.456877715768796
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Human language is full of compositional syntactic structures, and although neural networks have contributed to groundbreaking improvements in computer systems that process language, widely-used neural network architectures still exhibit limitations in their ability to process syntax. To address this issue, prior work has proposed adding stack data structures to neural networks, drawing inspiration from theoretical connections between syntax and stacks. However, these methods employ deterministic stacks that are designed to track one parse at a time, whereas syntactic ambiguity, which requires a nondeterministic stack to parse, is extremely common in language. In this dissertation, we remedy this discrepancy by proposing a method of incorporating nondeterministic stacks into neural networks. We develop a differentiable data structure that efficiently simulates a nondeterministic pushdown automaton, representing an exponential number of computations with a dynamic programming algorithm. We incorporate this module into two predominant architectures: recurrent neural networks (RNNs) and transformers. We show that this raises their formal recognition power to arbitrary context-free languages, and also aids training, even on deterministic context-free languages. Empirically, neural networks with nondeterministic stacks learn context-free languages much more effectively than prior stack-augmented models, including a language with theoretically maximal parsing difficulty. We also show that an RNN augmented with a nondeterministic stack is capable of surprisingly powerful behavior, such as learning cross-serial dependencies, a well-known non-context-free pattern. We demonstrate improvements on natural language modeling and provide analysis on a syntactic generalization benchmark. This work represents an important step toward building systems that learn to use syntax in more human-like fashion.

Related papers

• pyhgf: A neural network library for predictive coding [0.2150989251218736]
  texttpyhgf is a Python package for creating, manipulating and sampling dynamic networks for predictive coding. We improve over other frameworks by enclosing the network components as transparent, modular and malleable variables in the message-passing steps. The transparency of core variables can also translate into inference processes that leverage self-organisation principles.
  arXiv  Detail & Related papers  (2024-10-11T19:21:38Z)
• Semantic Loss Functions for Neuro-Symbolic Structured Prediction [74.18322585177832]
  We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training. It is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby. It can be combined with both discriminative and generative neural models.
  arXiv  Detail & Related papers  (2024-05-12T22:18:25Z)
• ExAIS: Executable AI Semantics [4.092001692194709]
  Neural networks can be regarded as a new programming paradigm, i.e., instead of building ever-more complex programs through (often informal) logical reasoning in the programmers' mind, complex 'AI' systems are built by optimising generic neural network models with big data. In this new paradigm, AI frameworks such as PyTorch play a key role, which is as essential as the compiler for traditional programs. It is known that the lack of a proper semantics for programming languages (such as C), i.e., a correctness specification for compilers, has contributed to many problematic program behaviours and security issues
  arXiv  Detail & Related papers  (2022-02-20T17:33:34Z)
• Dynamic Inference with Neural Interpreters [72.90231306252007]
  We present Neural Interpreters, an architecture that factorizes inference in a self-attention network as a system of modules. inputs to the model are routed through a sequence of functions in a way that is end-to-end learned. We show that Neural Interpreters perform on par with the vision transformer using fewer parameters, while being transferrable to a new task in a sample efficient manner.
  arXiv  Detail & Related papers  (2021-10-12T23:22:45Z)
• Learning Hierarchical Structures with Differentiable Nondeterministic Stacks [25.064819128982556]
  We present a stack RNN model based on the recently proposed Nondeterministic Stack RNN (NS-RNN) We show that the NS-RNN achieves lower cross-entropy than all previous stack RNNs on five context-free language modeling tasks. We also propose a restricted version of the NS-RNN that makes it practical to use for language modeling on natural language.
  arXiv  Detail & Related papers  (2021-09-05T03:25:23Z)
• Towards Zero-shot Language Modeling [90.80124496312274]
  We construct a neural model that is inductively biased towards learning human languages. We infer this distribution from a sample of typologically diverse training languages. We harness additional language-specific side information as distant supervision for held-out languages.
  arXiv  Detail & Related papers  (2021-08-06T23:49:18Z)
• Low-Dimensional Structure in the Space of Language Representations is Reflected in Brain Responses [62.197912623223964]
  We show a low-dimensional structure where language models and translation models smoothly interpolate between word embeddings, syntactic and semantic tasks, and future word embeddings. We find that this representation embedding can predict how well each individual feature space maps to human brain responses to natural language stimuli recorded using fMRI. This suggests that the embedding captures some part of the brain's natural language representation structure.
  arXiv  Detail & Related papers  (2021-06-09T22:59:12Z)
• Learning Context-Free Languages with Nondeterministic Stack RNNs [20.996069249108224]
  We present a differentiable stack data structure that simultaneously and tractably encodes an exponential number of stack configurations. We call the combination of this data structure with a recurrent neural network (RNN) controller a Nondeterministic Stack RNN.
  arXiv  Detail & Related papers  (2020-10-09T16:48:41Z)
• 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)
• On the Linguistic Capacity of Real-Time Counter Automata [1.8072051868187933]
  We study the abilities of real-time counter machines as formal grammars. We show that counter languages are closed under complement, union, intersection, and many other common set operations. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
  arXiv  Detail & Related papers  (2020-04-15T03:37:47Z)
• Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack [73.48927855855219]
  Recurrent neural networks (RNNs) are a widely used deep architecture for sequence modeling, generation, and prediction. RNNs generalize poorly over very long sequences, which limits their applicability to many important temporal processing and time series forecasting problems. One way to address these shortcomings is to couple an RNN with an external, differentiable memory structure, such as a stack. In this paper, we improve the memory-augmented RNN with important architectural and state updating mechanisms.
  arXiv  Detail & Related papers  (2020-04-04T14:19:15Z)

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.