Recurrent Neural Networks as Weighted Language Recognizers

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

doi:10.18653/v1/N18-1205

Recurrent Neural Networks as Weighted Language Recognizers

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

EPSRC CDT in Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
Publisher	Association for Computational Linguistics
Pages	2261-2271
Number of pages	11
DOIs	https://doi.org/10.18653/v1/N18-1205
Publication status	Published - 6 Jun 2018
Event	16th 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 2018 → 6 Jun 2018 http://naacl2018.org/

Conference

Conference	16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Abbreviated title	NAACL HLT 2018
Country/Territory	United States
City	New Orleans
Period	1/06/18 → 6/06/18
Internet address	http://naacl2018.org/

Access to Document

10.18653/v1/N18-1205Licence: Creative Commons: Attribution (CC-BY)

Recurrent Neural Networks as Weighted Language RecognizersFinal published version, 296 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

Chen, Y., Gilroy, S., Maletti, A., May, J., & Knight, K. (2018). Recurrent Neural Networks as Weighted Language Recognizers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) (pp. 2261-2271). Association for Computational Linguistics. https://doi.org/10.18653/v1/N18-1205

@inproceedings{d96fac4d59be4334a5dde95c3845c856,

title = "Recurrent Neural Networks as Weighted Language Recognizers",

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.",

author = "Yining Chen and Sorcha Gilroy and Andreas Maletti and Jonathan May and Kevin Knight",

year = "2018",

month = jun,

day = "6",

doi = "10.18653/v1/N18-1205",

language = "English",

pages = "2261--2271",

booktitle = "Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)",

publisher = "Association for Computational Linguistics",

note = "16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL HLT 2018 ; Conference date: 01-06-2018 Through 06-06-2018",

url = "http://naacl2018.org/",

}

Chen, Y, Gilroy, S, Maletti, A, May, J & Knight, K 2018, Recurrent Neural Networks as Weighted Language Recognizers. in Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). Association for Computational Linguistics, pp. 2261-2271, 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, New Orleans, Louisiana, United States, 1/06/18. https://doi.org/10.18653/v1/N18-1205

Recurrent Neural Networks as Weighted Language Recognizers. / Chen, Yining; Gilroy, Sorcha; Maletti, Andreas et al.
Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). Association for Computational Linguistics, 2018. p. 2261-2271.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Recurrent Neural Networks as Weighted Language Recognizers

AU - Chen, Yining

AU - Gilroy, Sorcha

AU - Maletti, Andreas

AU - May, Jonathan

AU - Knight, Kevin

PY - 2018/6/6

Y1 - 2018/6/6

N2 - 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.

AB - 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.

U2 - 10.18653/v1/N18-1205

DO - 10.18653/v1/N18-1205

M3 - Conference contribution

SP - 2261

EP - 2271

BT - Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)

PB - Association for Computational Linguistics

T2 - 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies

Y2 - 1 June 2018 through 6 June 2018

ER -

Recurrent Neural Networks as Weighted Language Recognizers

Abstract

Conference

Access to Document

Fingerprint

Cite this