On the Representational Capacity of Recurrent Neural Language Models

Overview

• This paper investigates the computational capabilities of language models (LMs) based on recurrent neural networks (RNNs).
• It builds on previous work that showed RNNs with rational weights and unbounded computation time are Turing complete.
• However, LMs define weightings over strings, so the authors analyze the computational power of RNN-based LMs (RLMs) in this context.

Plain English Explanation

The researchers wanted to understand how powerful language models built using recurrent neural networks (RNNs) can be. Previous research had shown that RNNs with certain mathematical properties could, in theory, perform any computation that a standard computer can do, given enough time.

However, language models don't just decide whether a string of words is valid or not - they also assign probabilities or "weights" to different sequences of words. So the researchers set out to analyze the computational capabilities of these weighted language models based on RNNs.

Their key finding is that an RNN-based language model with unbounded computation time can simulate any probabilistic Turing machine with rational weights. This means these language models can, in principle, perform a wide range of computations, not just simple language tasks.

But in practice, language models process text in real-time, one symbol at a time. So the researchers also showed that within this real-time constraint, RNN-based language models can at least simulate a certain class of probabilistic Turing machines. This provides a lower bound on their computational expressivity.

Technical Explanation

The authors build on the Turing completeness result for RNNs shown by Siegelmann and Sontag (1992). They extend this to the probabilistic case, proving that a rationally weighted RNN-based language model (RLM) with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions.

Since in practice, RLMs process text in real-time, the authors treat the above result as an upper bound on their computational expressivity. They also provide a lower bound by showing that under the real-time constraint, RLMs can simulate deterministic real-time rational PTMs.

Critical Analysis

The paper provides a rigorous theoretical analysis of the computational capabilities of RNN-based language models. However, the authors acknowledge that their results only establish upper and lower bounds on expressivity, rather than a precise characterization.

Additionally, the assumption of unbounded computation time in the upper bound result may not be realistic for practical language models. The authors note that further work is needed to understand the computational power of RLMs under more realistic resource constraints.

Another potential limitation is that the paper focuses solely on the mathematical properties of RLMs, without considering aspects like the evolution of representations or the role of memory in realistic language models. Incorporating these factors could lead to a more nuanced understanding of their computational capabilities.

Conclusion

This paper makes an important contribution to understanding the computational expressivity of RNN-based language models. By establishing upper and lower bounds on their capabilities, it provides a mathematical foundation for reasoning about the potential and limitations of these models, particularly in relation to simulating simple word2vec-style vector representations.

While the results are theoretical in nature, they have implications for the design and application of language models, suggesting that these models may be capable of a wider range of computations than traditionally assumed. Further research is needed to fully characterize their practical computational power and to understand how these theoretical results relate to the behavior of real-world language models.