Recurrent Neural Networks as Weighted Language Recognizers

Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
PublisherAssociation for Computational Linguistics
Pages2261-2271
Number of pages11
DOIs
Publication statusPublished - 6 Jun 2018
Event16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Hyatt Regency New Orleans Hotel, New Orleans, United States
Duration: 1 Jun 20186 Jun 2018
http://naacl2018.org/

Conference

Conference16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Abbreviated titleNAACL HLT 2018
CountryUnited States
CityNew Orleans
Period1/06/186/06/18
Internet address

Fingerprint

Dive into the research topics of 'Recurrent Neural Networks as Weighted Language Recognizers'. Together they form a unique fingerprint.

Cite this