Recurrent Neural Networks as Weighted Language Recognizers

Proceedings of NAACL-HLT 2018, pages 2261–2271 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics Recurrent Neural Networks as Weighted Language Recognizers Yining Chen Dartmouth College yining.chen.18@dartmouth.edu Sorcha Gilroy ILCC University of Edinburgh s.gilroy@sms.ed.ac.uk Andreas Maletti Institute of Computer Science Universit¨at Leipzig andreas.maletti@uni-leipzig.de Jonathan May Information Sciences Institute University of Southern California jonmay@isi.edu Kevin Knight Information Sciences Institute University of Southern California knight@isi.edu Abstract We investigate the computational complexity of various problems for simple recurrent neu- ral networks (RNNs) as formal models for recognizing weighted languages. We focus on the single-layer, ReLU-activation, rational- weight RNNs with softmax, which are com- monly used in natural language processing ap- plications. We show that most problems for such RNNs are undecidable, including con- sistency, equivalence, minimization, and the determination of the highest-weighted string. However, for consistent RNNs the last prob- lem 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. 1 Introduction Recurrent neural networks (RNNs) are an attrac- tive apparatus for probabilistic language model- ing (Mikolov and Zweig, 2012). Recent exper- iments show that RNNs significantly outperform other methods in assigning high probability to held-out English text (Jozefowicz et al., 2016). Roughly speaking, an RNN works as follows. At each time step, it consumes one input token, updates its hidden state vector, and predicts the next token by generating a probability distribution over all permissible tokens. The probability of an input string is simply obtained as the product of the predictions of the tokens constituting the string followed by a terminating token. In this man- ner, each RNN defines a weighted language; i.e. a total function from strings to weights. Siegel- mann and Sontag (1995) showed that single-layer rational-weight RNNs with saturated linear acti- vation can compute any computable function. To this end, a specific architecture with 886 hidden units can simulate any Turing machine in real-time (i.e., each Turing machine step is simulated in a single time step). However, their RNN encodes the whole input in its internal state, performs the actual computation of the Turing machine when reading the terminating token, and then encodes the output (provided an output is produced) in a particular hidden unit. In this way, their RNN al- lows “thinking” time (equivalent to the computa- tion time of the Turing machine) after the input has been encoded. We consider a different variant of RNNs that is commonly used in natural language processing ap- plications. It uses ReLU activations, consumes an input token at each time step, and produces soft- max predictions for the next token. It thus imme- diately halts after reading the last input token and the weight assigned to the input is simply the prod- uct of the input token predictions in each step. Other formal models that are currently used to implement probabilistic language models such as …

Content truncated to 500 words