On the Representational Capacity of Recurrent Neural Language Models

• URL: http://arxiv.org/abs/2310.12942v5
• Date: Thu, 30 May 2024 14:49:25 GMT
• Title: On the Representational Capacity of Recurrent Neural Language Models
• Authors: Franz Nowak, Anej Svete, Li Du, Ryan Cotterell,
• Abstract summary: We show that a rationally weighted RLM with computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
• Score: 56.19166912044362
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.

Related papers

• Large Language Models and the Extended Church-Turing Thesis [0.0]
  We investigate the computational power of large language models (LLMs) by the classical means of computability and computational complexity theory. We show that any fixed (non-adaptive) LLM is computationally equivalent to a, possibly very large, deterministic finite-state transducer. We discuss the merits of our findings in the broader context of several related disciplines and philosophies.
  arXiv  Detail & Related papers  (2024-09-11T03:09:55Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs) We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
  arXiv  Detail & Related papers  (2024-06-20T10:59:02Z)
• What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages [78.1866280652834]
  Large language models (LM) are distributions over strings. We investigate the learnability of regular LMs (RLMs) by RNN and Transformer LMs. We find that the complexity of the RLM rank is strong and significant predictors of learnability for both RNNs and Transformers.
  arXiv  Detail & Related papers  (2024-06-06T17:34:24Z)
• Lower Bounds on the Expressivity of Recurrent Neural Language Models [47.537525313391164]
  Investigation into the representational capacity of neural LMs has predominantly focused on their ability to emphrecognize formal languages. We take a fresh look at the representational capacity of RNN LMs by connecting them to emphprobabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.
  arXiv  Detail & Related papers  (2024-05-29T16:02:09Z)
• Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
  We study what classes of probability distributions RNN LMs can represent. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata. These results present a first step towards characterizing the classes of distributions RNN LMs can represent.
  arXiv  Detail & Related papers  (2023-10-08T13:36:05Z)
• Advancing Regular Language Reasoning in Linear Recurrent Neural Networks [56.11830645258106]
  We study whether linear recurrent neural networks (LRNNs) can learn the hidden rules in training sequences. We propose a new LRNN equipped with a block-diagonal and input-dependent transition matrix. Experiments suggest that the proposed model is the only LRNN capable of performing length extrapolation on regular language tasks.
  arXiv  Detail & Related papers  (2023-09-14T03:36:01Z)
• Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results [0.348097307252416]
  We show some results related to the problem of extracting Finite State Machine based models from trained RNN Language models. Our reduction technique from 3-SAT makes this latter fact easily generalizable to other RNN architectures.
  arXiv  Detail & Related papers  (2020-04-01T14:48:59Z)

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.