Recurrent Neural Networks as Weighted Language Recognizers
This work addresses theoretical limitations for researchers and practitioners using RNNs in natural language processing, highlighting the need for approximations and heuristics due to undecidability and hardness results.
The paper tackled the computational complexity of problems for simple recurrent neural networks (RNNs) as weighted language recognizers, showing that most problems like consistency and equivalence are undecidable, but for consistent RNNs with polynomial-length strings, the highest-weighted string problem becomes NP-complete and APX-hard.
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 and APX-hard. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.