Elamur Research⌕
☰
home / papers / 2018 / On the Practical Computational Power of Finite Precision RNNs for Language Recognition

On the Practical Computational Power of Finite Precision RNNs for Language Recognition

Summary

Classic proofs that RNNs are Turing complete depend on unlimited state precision and unbounded computation time, which do not match how RNNs are used in NLP. This paper asks what different recurrent architectures can compute when states have finite precision and the network performs one update per input symbol (input-bound, finite-precision RNNs, or IBFP-RNNs). The authors compare four architectures: the Elman SRNN with squashing activation, the ReLU-based IRNN, the GRU and the LSTM. They relate each to a simplified k-counter machine (SKCM).

Their analysis finds that the LSTM and IRNN can maintain unbounded counters in dedicated dimensions. The SRNN and GRU cannot, because their state values are confined to a bounded range, so they recognize only regular languages. Experiments on aⁿbⁿ and aⁿbⁿcⁿ support this. Trained LSTMs develop interpretable counting dimensions and generalize well past the training lengths, while GRUs do neither.

The work shows that the LSTM and GRU, often treated as interchangeable, differ in practical expressive power. This may explain why LSTMs are preferred for tasks requiring bracket counting, such as processing linearized parse trees.

Key points

  • Theoretical claim: under finite precision and real-time computation, the LSTM and IRNN can do everything SKCMs can, and their expressive power strictly exceeds that of both the SRNN and the GRU. The GRU's interpolation between the previous state and a tanh-bounded proposal prevents unbounded counting.
  • Setup: 10-dimensional, single-layer LSTM and GRU networks were implemented in DyNet and trained with SGD. Training lengths went up to n = 100 for aⁿbⁿ and n = 50 for aⁿbⁿcⁿ.
  • Generalization: the LSTM handled aⁿbⁿ correctly up to n = 256 and aⁿbⁿcⁿ up to n = 100. The GRU erred even inside its training range, for example by accepting aⁿbⁿ⁺¹ for n > 38.
  • Test accuracy (1000-sample random test sets): the LSTM scored 100% on aⁿbⁿ and 98.6% on aⁿbⁿcⁿ, against 87.0% and 86.9% for the GRU.
  • Counter imprecision: the LSTM's counters were slightly inexact, for instance stepping up by about 0.99 but down by about 0.98, because its gates did not fully saturate. This drift explains its eventual failures at very large n.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

93 papers of our library cite it (of the 140884 whose bibliographies we read); 4 of them have a page here, 89 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p18-2117 · arXiv 1805.04908

@inproceedings{weiss2018practical,
  title = {{On the Practical Computational Power of Finite Precision RNNs for Language Recognition}},
  author = {Weiss, Gail and Goldberg, Yoav and Yahav, Eran},
  booktitle = {Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2018},
  doi = {10.18653/v1/p18-2117},
  eprint = {1805.04908},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p18-2117}
}

References

19 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. 2016. Binarized neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 4107–4115. Curran Associates, Inc. find
  2. Roee Aharoni and Yoav Goldberg. 2017. Towards string-to-tree neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 132–140, Vancouver, Canada. Association for Computational Linguistics. find our card
  3. Quoc V. Le, Navdeep Jaitly, and Geoffrey E. Hinton. 2015. A Simple Way to Initialize Recurrent Networks of Rectified Linear Units. arXiv:1504.00941 [cs]. — [arXiv:1504.00941](https://arxiv.org/abs/1504.00941) find
  4. Yining Chen, Sorcha Gilroy, Kevin Knight, and Jonathan May. 2017. Recurrent neural networks as weighted language recognizers. CoRR, abs/1711.05408. find
  5. Hava Siegelmann. 1999. Neural Networks and Analog Computation: Beyond the Turing Limit, 1 edition. Birkhäuser Basel. find
  6. Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Langua… find
  7. Hava T. Siegelmann. 1996. Recurrent neural networks and finite automata. Computational Intelligence, 12:567–574. find
  8. Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. In Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, Pittsburgh, PA, USA, July 27-29, 1992., pages 440–449. find
  9. Do Kook Choe and Eugene Charniak. 2016. Parsing as language modeling. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2331–2336, Austin, Texas. Association for Computational Linguistics. find
  10. Hava T. Siegelmann and Eduardo D. Sontag. 1994. Analog computation via neural networks. Theor. Comput. Sci., 131(2):331–360. find
  11. Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2, NIPS’15, pages 2773–2781, Cambridge, MA, USA. MIT Press. find
  12. Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. 2014. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling. arXiv:1412.3555 [cs]. find
  13. Jeffrey L. Elman. 1990. Finding Structure in Time. Cognitive Science, 14(2):179–211. find
  14. Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265– 283. find
  15. F. A. Gers and E. Schmidhuber. 2001. Lstm recurrent networks learn simple context-free and context-sensitive languages. Transactions on Neural Networks, 12(6):1333–1340. find
  16. F. A. Gers and J. Schmidhuber. 2000. Recurrent nets that time and count. In Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks. find
  17. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millennium, volume 3, pages 189–194 vol.3. find
  18. K. Greff, R. K. Srivastava, J. Koutnk, B. R. Steunebrink, and J. Schmidhuber. 2017. Lstm: A search space odyssey. IEEE Transactions on Neural Networks and Learning Systems, 28(10):2222–2232. find
  19. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/weiss-2018-practical-computational-power-finite-precision/