Elamur Research⌕
☰
home / papers / 2018 / Closing Brackets with Recurrent Neural Networks

Closing Brackets with Recurrent Neural Networks

Paper · 2018 · Natalia Skachkova, Thomas Trost and Dietrich Klakow

Summary

Language models must handle matching symbols, such as brackets, that create long-range dependencies. This paper tests whether recurrent networks can learn these rules. It uses synthetic Dyck languages D_n, which are balanced strings over n bracket types. Words are generated step by step: a new bracket opens with probability p (with p < 1/2), and bracket types are chosen uniformly. Because the generator is fully specified, the authors derive closed-form statistics, including the expected word length and a theoretical lower bound on per-symbol perplexity. This gives an absolute reference point rather than only comparisons between architectures. They train Elman-RNNs (SRNN, using the RNNLM toolkit) and GRUs and LSTMs (using TF-NNLM-TK), then evaluate them on two tasks: test perplexity and predicting the final closing bracket of a word. In most settings, all three models come close to the perplexity bound. Last-bracket prediction is very accurate overall, but accuracy on long sequences separates the architectures, and the LSTM is the most robust. The work offers a controlled diagnostic for how neural networks handle hierarchical structure.

Key points

  • Authors: The PDF lists four authors from Saarland University, with Natalia Skachkova first, Thomas A. Trost second, Adam Kusmirek third, and Dietrich Klakow last. The first two contributed equally. Adam Kusmirek is missing from the citation given for this entry.
  • Theory: The expected Dyck word length is 2/(1−2p), which diverges at p = 1/2. The perplexity baseline PP_n has a closed form and grows sublinearly in n, because the type of a closing bracket is fully predictable.
  • Perplexity results:
    • For D_1, with hidden sizes from 1 to 512 units, SRNN test perplexity reaches the theoretical baseline.
    • At p = 3/16, model scores sit very near the bound (e.g., baseline 1.444 vs. 1.445–1.451).
    • The gap widens at p = 6/16 for the largest tested configuration, where the SRNN scores 3.885 against a 3.682 baseline.
  • Last-bracket prediction:
    • The SRNN mostly reaches 0.96–1 accuracy, and the GRU and LSTM score almost perfectly.
    • On long words (p = 6/16, n = 4), SRNN accuracy is perfect only up to about 8 symbols and the GRU's up to about 20.
    • The SRNN gets no correct guesses for task lengths beyond 90, while the LSTM stays near-perfect across all lengths.
  • Error analysis: The confusion matrices show that the SRNN almost never predicts an opening bracket where a closing one is required. However, it does not treat the different bracket types as equally likely.

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

 Institutions

🎓Saarland UniversitySaarbrücken · Germany148 works · 18,287 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

Cite

Cite as Natalia Skachkova, Thomas Trost and Dietrich Klakow. 2018. Closing Brackets with Recurrent Neural Networks. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/w18-5425

@inproceedings{skachkova2018closing,
  title = {{Closing Brackets with Recurrent Neural Networks}},
  author = {Natalia Skachkova, Thomas Trost and Dietrich Klakow},
  booktitle = {Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP},
  year = {2018},
  doi = {10.18653/v1/w18-5425},
  url = {https://doi.org/10.18653/v1/w18-5425}
}

References

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

  1. Jean-Philippe Bernardy. 2018. Can Recurrent Neural Networks Learn Nested Recursion? Linguistic Issues in Language Technology, 16(1). find
  2. Tomáš Mikolov, Stefan Kombrink, Anoop Deoras, Lukáš Burget, and Jan Honza Černockỳ. 2011b. RNNLM – Recurrent Neural Network Language Modeling Toolkit. In ASRU 2011 Demo Session, Waikoloa, HI, USA. find
  3. N. Chomsky. 1956. Three models for the description of language. IEEE Transactions on Information Theory, 2(3):113–124. find
  4. Kai Lai Chung and William Feller. 1949. On Fluctuations in Coin-tossing. Proceedings of the National Academy of Sciences, 35(10):605–608. find
  5. Peter O. Müller, Ingeborg Ohnheiser, Susan Olsen, and Franz Rainer. 2015. Word-Formation: An International Handbook of the Languages of Europe, volume 40.1 of Handbooks of Linguistics and Communication Science. De Gruyter Mouton. find
  6. Sreerupa Das, C. Lee Giles, and Guo-Zheng Sun. 1992. find
  7. Learning Context-free Grammars: Capabilities and Youssef Oualil, Mittul Singh, Clayton Greenberg, and Dietrich Klakow. 2016. Long-short range context neural networks for language modeling. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1473–1481, Aus… find
  8. David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. 1985. Learning Internal Representations by Error Propagation. Technical report, University of California San Diego, La Jolla Institute for Cognitive Science. find
  9. Xiaoyu Shen, Youssef Oualil, Clayton Greenberg, Mittul Singh, and Dietrich Klakow. 2017. Estimation of gap between current language models and human performance. In Proceedings of the 18th Annual Conference of the International Speech Communication Association, pages 553–557, Stockholm, Sweden. find
  10. H. S. Sichel. 1974. On a Distribution Representing Sentence-Length in Written Prose. Journal of the Royal Statistical Society. Series A (General), 137(1):25. find
  11. Bengt Sigurd, Mats Eeg-Olofsson, and Joost van Weijer. 2004. Word length, sentence length and frequency – Zipf revisited. Studia Linguistica, 58(1):37–52. find
  12. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2017. Extracting automata from recurrent neural networks using queries and counterexamples. Computing Research Repository, arXiv:1711.09576. — [arXiv:1711.09576](https://arxiv.org/abs/1711.09576) find
  13. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the practical computational power of finite precision rnns for language recognition. Computing Research Repository, arXiv:1805.04908.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/skachkova-2018-closing-brackets-recurrent-neural-networks/