Extensional Properties of Recurrent Neural Networks

• URL: http://arxiv.org/abs/2410.22730v1
• Date: Wed, 30 Oct 2024 06:29:02 GMT
• Title: Extensional Properties of Recurrent Neural Networks
• Authors: Evgeny Dantsin, Alexander Wolpert,
• Abstract summary: A property of a recurrent neural network (RNN) is called emphextensional if, loosely speaking, it is a property of the function computed by the RNN rather than a property of the RNN algorithm. We prove a version of Rice's theorem for RNNs: any nontrivial extensional property of RNNs is undecidable.
• Score: 49.30491917300904
• License:
• Abstract: A property of a recurrent neural network (RNN) is called \emph{extensional} if, loosely speaking, it is a property of the function computed by the RNN rather than a property of the RNN algorithm. Many properties of interest in RNNs are extensional, for example, robustness against small changes of input or good clustering of inputs. Given an RNN, it is natural to ask whether it has such a property. We give a negative answer to the general question about testing extensional properties of RNNs. Namely, we prove a version of Rice's theorem for RNNs: any nontrivial extensional property of RNNs is undecidable.

Related papers

• Investigating Sparsity in Recurrent Neural Networks [0.0]
  This thesis focuses on investigating the effects of pruning and Sparse Recurrent Neural Networks on the performance of RNNs. We first describe the pruning of RNNs, its impact on the performance of RNNs, and the number of training epochs required to regain accuracy after the pruning is performed. Next, we continue with the creation and training of Sparse Recurrent Neural Networks and identify the relation between the performance and the graph properties of its underlying arbitrary structure.
  arXiv  Detail & Related papers  (2024-07-30T07:24:58Z)
• A Tensor Decomposition Perspective on Second-order RNNs [5.922280687190788]
  We study the model resulting from parameterizing 2RNNs using the CP decomposition, which we call CPRNN. We analyze how rank and hidden size affect model capacity and show the relationships between RNNs, 2RNNs, MIRNNs, and CPRNNs based on these parameters. We support these results empirically with experiments on the Penn Treebank dataset which demonstrate that, with a fixed parameter budget, CPRNNs outperforms RNNs, 2RNNs, and MIRNNs with the right choice of rank and hidden size.
  arXiv  Detail & Related papers  (2024-06-07T16:18:32Z)
• Learning Useful Representations of Recurrent Neural Network Weight Matrices [30.583752432727326]
  Recurrent Neural Networks (RNNs) are general-purpose parallel-sequential computers. How to learn useful representations of RNN weights that facilitate RNN analysis as well as downstream tasks? We consider several mechanistic approaches for RNN weights and adapt the permutation equivariant Deep Weight Space layer for RNNs. Our two novel functionalist approaches extract information from RNN weights by 'interrogating' the RNN through probing inputs.
  arXiv  Detail & Related papers  (2024-03-18T17:32:23Z)
• On Efficiently Representing Regular Languages as RNNs [49.88310438099143]
  We show that RNNs can efficiently represent bounded hierarchical structures that are prevalent in human language. This suggests that RNNs' success might be linked to their ability to model hierarchy. We show that RNNs can efficiently represent a larger class of LMs than previously claimed.
  arXiv  Detail & Related papers  (2024-02-24T13:42:06Z)
• On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks [59.85314067235965]
  We extend the theoretical foundation for the $2nd$-order recurrent network ($2nd$ RNN) We prove there exists a class of a $2nd$ RNN that is Turing-complete with bounded time. We also demonstrate that $2$nd order RNNs, without memory, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars.
  arXiv  Detail & Related papers  (2023-09-26T06:06:47Z)
• Exploiting Low-Rank Tensor-Train Deep Neural Networks Based on Riemannian Gradient Descent With Illustrations of Speech Processing [74.31472195046099]
  We exploit a low-rank tensor-train deep neural network (TT-DNN) to build an end-to-end deep learning pipeline, namely LR-TT-DNN. A hybrid model combining LR-TT-DNN with a convolutional neural network (CNN) is set up to boost the performance. Our empirical evidence demonstrates that the LR-TT-DNN and CNN+(LR-TT-DNN) models with fewer model parameters can outperform the TT-DNN and CNN+(LR-TT-DNN) counterparts.
  arXiv  Detail & Related papers  (2022-03-11T15:55:34Z)
• Recurrent Neural Network from Adder's Perspective: Carry-lookahead RNN [9.20540910698296]
  We discuss the similarities between recurrent neural network (RNN) and serial adder. Inspired by carry-lookahead adder, we introduce carry-lookahead module to RNN, which makes it possible for RNN to run in parallel.
  arXiv  Detail & Related papers  (2021-06-22T12:28:33Z)
• SyReNN: A Tool for Analyzing Deep Neural Networks [8.55884254206878]
  Deep Neural Networks (DNNs) are rapidly gaining popularity in a variety of important domains. This paper introduces SyReNN, a tool for understanding and analyzing a DNN by computing its symbolic representation.
  arXiv  Detail & Related papers  (2021-01-09T00:27:23Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• A Formal Hierarchy of RNN Architectures [88.38859874233944]
  hierarchy is based on two formal properties: space, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We show how these models' expressive capacity is expanded by stacking multiple layers or composing them with different pooling functions. We hypothesize that the practical learnable capacity of unsaturated RNNs obeys a similar hierarchy.
  arXiv  Detail & Related papers  (2020-04-18T00:57:54Z)

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.