CoChat
Sign Up
Cited by 49Natural Language Processing Techniquessemigroups and automata theoryTopic Modeling

Recurrent Neural Networks as Weighted Language Recognizers

Open access
Chen, Yining, Gilroy, Sorcha, Maletti, Andreas, May, Jonathan, Knight, Kevin·2018·Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
DOI 10.18653/v1/n18-1205
Open this paper in CoChat — free accountOpen PDF

Abstract

Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.18653/v1/n18-1205

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Finding the optimum argmax sequence from recurrent neural language models or Transformers is not tractable.

    “Since finding 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).”

    From The Curious Case of Neural Text Degeneration (2019) · cites this paper as Chen et al., 2018

    Section 4 (page unavailable) states that the best-string problem for RNNs is undecidable; Section 7 adds that the polynomial-length version for consistent RNNs is NP-complete. This supports the claim for the RNNs studied, but the paper does not establish the same result for Transformers. (LLM, conf=0.89)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 20

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ull- man. 1974. The design and analysis of computer algorithms. Addison-Wesley.
  2. Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wo- jciech Skut, and Mehryar Mohri. 2007. OpenFst: A General and Efficient Weighted Finite-State Trans- ducer Library, Springer Berlin Heidelberg, Berlin, Heidelberg, pages 11-23.
  3. D. Bahdanau, K. Cho, and Y. Bengio. 2014. Neural machine translation by jointly learning to align and translate. In Proc. ICLR.
  4. T. L. Booth and R. A. Thompson. 1973. Ap- plying probability measures to abstract languages. IEEE Transactions on Computers C-22(5):442-450. https://doi.org/10.1109/t-c.1973.223746. · DOI
  5. Francisco Casacuberta and Colin de la Higuera. 2000. Computational complexity of problems on proba- bilistic grammars and transducers. Grammatical In- ference: Algorithms and Applications Lecture Notes in Computer Science pages 15-24. https://doi.org/ 10.1007/978-3-540-45257-7 2. · DOI
  6. Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. 2007. L p distance and equivalence of probabilistic automata. International Journal of Foundations of Computer Science 18(04):761-779. https://doi.org/ 10.1142/s0129054107004966. · DOI
  7. Manfred Droste, Werner Kuich, and Heiko Vogler. 2013. Handbook of Weighted Automata. Springer Berlin.
  8. Vojtch Forejt, Petr Janar, Stefan Kiefer, and James Worrell. 2014. Language equivalence of probabilis- tic pushdown automata. Information and Computa- tion 237:1-11. https://doi.org/10.1016/j.ic.2014.04. 003. · DOI
  9. T. V. Griffiths. 1968. The unsolvability of the equiva- lence problem for ∧-free nondeterministic general- ized machines. Journal of the ACM 15(3):409-413. https://doi.org/10.1145/321466.321473. · DOI
  10. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Comput. 9(8):1735- 1780. https://doi.org/10.1162/neco.1997.9.8.1735. · DOI · Paper page
  11. Tao Jiang and B. Ravikumar. 1993. Minimal NFA problems are hard. SIAM Journal on Computing 22(6):1117-1141. https://doi.org/10.1137/0222067. · DOI
  12. Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. 2016. Exploring the lim- its of language modeling. https://arxiv.org/pdf/1602. 02410.pdf.
  13. Donald E. Knuth. 1977. A generalization of Dijkstra's algorithm. Information Processing Letters 6(1):1-5. https://doi.org/10.1016/0020-0190(77)90002-3. · DOI
  14. T. Mikolov and G. Zweig. 2012. Context depen- dent recurrent neural network language model. In 2012 IEEE Spoken Language Technology Workshop (SLT). pages 234-239. https://doi.org/10.1109/SLT. 2012.6424228. · DOI
  15. Mark-Jan Nederhof and Giorgio Satta. 2006. Estima- tion of consistent probabilistic context-free gram- mars. In Proceedings of the Human Language Technology Conference of the NAACL, Main Con- ference. Association for Computational Linguistics, New York City, USA, pages 343-350. http://www. aclweb.org/anthology/N/N06/N06-1044.
  16. Tibor Radó. 1962. On non-computable functions. Bell System Technical Journal 41:877-884.
  17. Géraud Sénizergues. 1997. The equivalence problem for deterministic pushdown automata is decidable. In Proc. Automata, Languages and Programming: 24th International Colloquium, Springer Berlin Hei- delberg, pages 671-681.
  18. Hava T. Siegelmann and Eduardo D. Sontag. 1995. On the computational power of neural nets. Journal of Computer and System Sciences 50(1):132-150. https://doi.org/10.1006/jcss.1995.1013. · DOI
  19. Khalil Simaan. 1996. Computational complexity of probabilistic disambiguation by means of tree- grammars. In Proc. COLING. pages 1175-1180. https://doi.org/10.3115/993268.993392. · DOI
  20. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural net- works. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Ad- vances in Neural Information Processing Systems 27. Curran Associates, Inc., pages 3104-3112.

Cited by

Sorted by citations

Authors
Chen, Y., Gilroy, S., Maletti, A., May, J., & Knight, K.
Affiliations
Dartmouth College (US)
ORCID
Venue
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
Published
2018
Pages
2261-2271
DOI
10.18653/v1/n18-1205
OpenAlex
W2963706817
Cited by
49
References
1
Citations by year
2025: 1 · 2024: 2 · 2023: 10 · 2022: 3 · 2021: 5 · 2020: 13 · 2019: 8 · 2018: 7
FWCI
3.35
Type
conference paper
Language
en
Open access
Licence
cc-by
Locations
  • Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) (publishedVersion, cc-by)
  • Edinburgh Research Explorer (University of Edinburgh) (submittedVersion, cc-by)
Funders
  • Deutsche Forschungsgemeinschaft (Graduiertenkolleg 1763)
  • Defense Advanced Research Projects Agency (HR0011-15-C-0115)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
Keywords
recurrent neural networks, language identification, weighted automata

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review