Recurrent Neural Networks as Weighted Language Recognizers

By Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight. 2017

79 citations recorded by the source corpus.

We investigate the computational complexity of various problems for simple recurrent neural networks (RNNs) as formal models for recognizing weighted languages. We focus on the single-layer, ReLU-activation, rational-weight RNNs with softmax, which are commonly used in natural language processing applications. We show that most problems for such RNNs are undecidable, including consistency, equivalence, minimization, and the determination of the highest-weighted string. However, for consistent RNNs the last problem becomes decidable, although the solution length can surpass all computable bounds. If additionally the string is limited to polynomial length, the problem becomes NP-complete. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

The Curious Case of Neural Text Degeneration (2019, background): “Since ﬁnding the optimum argmax sequence from recurrent neural language models or Transformers is not tractable (Chen et al., 2018), common practice is to use beam search (Li et al., 2016b; Shen et al., 2017; Wiseman et al., 2017).”
Analysis Methods in Neural Language Processing: A Survey (2018, background): “A few targeted attacks include Liang et al. (2018), which speciﬁed a desired class to fool a text classiﬁer, and Chen et al. (2018a), which speciﬁed words or captions to generate in an image captioning model.”
On the Turing Completeness of Modern Neural Network Architectures (2019, background): “Many of the results in Chen et al. (2018) are, in fact, a consequence of the Turing completeness of RNNs as established by Siegelmann & Sontag (1995).”
Interpreting and improving natural-language processing (in machines) with natural language-processing (in the brain) (2019, background): “Other approaches have attempted to offer a more theoretical assessment of how recurrent networks propagate information, or what word embeddings can represent (Peng et al. , 2018; Chen et al. , 2017; Weiss et al. , 2018).”
Bridging CNNs, RNNs, and Weighted Finite-State Machines (2018, background): “Other works have studied the expressive power of RNNs, in particular in the context of WFSAs or HMMs (Cleeremans et al., 1989; Giles et al., 1992; Visser et al., 2001; Chen et al., 2018).”
If Beam Search Is the Answer, What Was the Question? (2020, background): “(3) with a recurrent neural network is NP-hard (Chen et al., 2018).”
Simple Recurrent Units for Highly Parallelizable Recurrence (2017, background): “The design of recurrent networks, such as SRU and related architectures, raises questions about representational power and interpretability (Chen et al., 2018; Peng et al., 2018).”
Consistency of a Recurrent Language Model with Respect to Incomplete Decoding (2020, methodology): “This notion of consistency was raised and analyzed earlier, for instance by Booth & Thompson (1973) and Chen et al. (2017), in terms of whether the distribution induced by p θ is concentrated on ﬁnite sequences.”
On the Practical Computational Power of Finite Precision RNNs for Language Recognition (2018, methodology): “IRNN The IRNN model, explored by (Le et al., 2015), replaces the tanh activation with a non-squashing ReLU: The computational power of such RNNs (given in-ﬁnite precision) is explored in (Chen et al., 2017).”
On NMT Search Errors and Model Errors: Cat Got Your Tongue? (2019, background): “Chen et al. (2018) showed that the consistent best string problem for RNNs is decidable.”
NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics (2021, background): “As selecting the next token to generate based on the optimal future cost is NP-complete (Chen et al., 2018), we develop lookahead heuristics, which approximate cost at each decoding step based on continuations of the sequence-so-far.”